math final

Term,Definition/Theorem "Statement","A mathematical sentence that is either TRUE or FALSE." "Truth Value","The value of a statement: TRUE if the statement is true, FALSE if the statement is false." "Negation (¬)","Logical connective meaning “NOT P”. Truth‑table: P=T ⇒ ¬P=F, P=F ⇒ ¬P=T." "Conjunction (∧)","Logical connective meaning “P AND Q”. True exactly when both P and Q are true." "Disjunction (∨)","Logical connective meaning “P OR Q”. Inclusive: true when at least one of P or Q is true." "Implication (→)","Logical connective read “IF P THEN Q”. Truth‑table: false only when P is true and Q is false." "Biconditional (↔)","Logical connective read “P IFF Q”. Equivalent to (P→Q) ∧ (Q→P)." "Logical Equivalence","Sentences P and Q are logically equivalent (P ≡ Q) iff they have identical truth‑values for all interpretations." "Converse","For an implication P→Q, the converse is Q→P." "Contrapositive","For P→Q, the contrapositive is ¬Q→¬P (logically equivalent to the original implication)." "Tautology","A compound sentence that is TRUE under every possible truth assignment." "Contradiction","A sentence that is FALSE under every possible truth assignment." "Universal Quantifier (∀)",""For all". (∀x∈A) P(x) means P(x) is true for every element of A." "Existential Quantifier (∃)",""There exists". (∃x∈A) P(x) means at least one element of A satisfies P." "Unique Existence (∃!)",""There exists exactly one". Equivalent to (∃x)(P(x) ∧ (∀y)(P(y)→y=x))." "De Morgan’s Laws – Logic","¬(P∧Q) ≡ ¬P ∨ ¬Q and ¬(P∨Q) ≡ ¬P ∧ ¬Q." "Distributive Laws – Logic","P∧(Q∨R) ≡ (P∧Q)∨(P∧R) and P∨(Q∧R) ≡ (P∨Q)∧(P∨R)." "Implication Equivalence","P→Q ≡ ¬P ∨ Q." "Biconditional Equivalence","P↔Q ≡ (P→Q)∧(Q→P)." "Modus Ponens (Tautology)","[(P→Q) ∧ P] → Q is always true." "Modus Tollens (Tautology)","[(P→Q) ∧ ¬Q] → ¬P is always true." "Tautology – Law of Excluded Middle","P ∨ ¬P is always true." "Set","An unordered collection of distinct elements." "Subset (A⊆B)","Every element of A is an element of B." "Proper Subset (A⊂B)","A⊆B and A≠B." "Union (A∪B)","{x | x∈A ∨ x∈B}." "Intersection (A∩B)","{x | x∈A ∧ x∈B}." "Set Difference (A\B)","{x | x∈A ∧ x∉B}." "Cartesian Product (A×B)","Set of ordered pairs (a,b) with a∈A, b∈B." "Power Set P(X)","Set of all subsets of X." "De Morgan’s Laws – Sets","S\(A∪B) = (S\A)∩(S\B) and S\(A∩B) = (S\A)∪(S\B)." "Distributive Laws – Sets","A∩(B∪C)= (A∩B)∪(A∩C) and A∪(B∩C)= (A∪B)∩(A∪C)." "Cardinality |X|","Number of elements in set X." "Finite Set","Set X with |X| = n for some n∈ℕ∪{0}." "Infinite Set","A set that is not finite." "Equinumerous Sets","Sets X and Y with a bijection between them." "Countably Infinite","Set equinumerous with ℕ." "Countable Set","Finite or countably infinite." "Uncountable Set","Not countable (e.g. ℝ)." "Function f:A→B","Rule assigning each a∈A a single value f(a)∈B." "Domain","The set A in a function f:A→B." "Codomain","The set B in a function f:A→B." "Image / Range of f","{f(a) | a∈A} ⊆ B." "Injective Function","f(a)=f(b) ⇒ a=b (one‑to‑one)." "Surjective Function","For every b∈B there exists a∈A with f(a)=b." "Bijective Function","Function that is both injective and surjective." "Inverse Function f⁻¹","Defined for bijective f, satisfies f⁻¹∘f = id_A and f∘f⁻¹ = id_B." "Constant Function","f:A→B with f(a)=b₀ for all a." "Identity Function id_A","id_A(a)=a for all a∈A." "Indicator Function 1_S","1_S(a)=1 if a∈S, 0 otherwise." "Relation R⊆A×B","Set of ordered pairs relating elements of A to elements of B." "Reflexive","∀a∈A, aRa." "Antireflexive","∀a∈A, ¬(aRa)." "Symmetric","aRb⇒bRa." "Antisymmetric","aRb ∧ bRa ⇒ a=b." "Transitive","aRb ∧ bRc ⇒ aRc." "Equivalence Relation","Reflexive, symmetric, and transitive relation." "Equivalence Class [a]","{b∈A | aRb}." "Partition","Collection of non‑empty, pairwise‑disjoint subsets whose union is the whole set." "Partial Order","Reflexive, antisymmetric, transitive relation." "Total Order","Partial order where any two elements are comparable." "Graph (on A)","Relation on A that is antireflexive and symmetric (undirected simple graph)." "Principle of Mathematical Induction","To prove P(n) ∀n∈ℕ: (i) Base Case P(1) true; (ii) Inductive Step: P(k)⇒P(k+1)." "Strong Induction","Inductive step assumes P(1)…P(k) to prove P(k+1)." "Sum of First n Integers","1+2+…+n = n(n+1)/2 (proved by induction)." "Inequality n<2ⁿ","True ∀n∈ℕ (proved by induction)." "Divisibility 4ⁿ−1","3 divides 4ⁿ − 1 for every n (proved by induction & modular insight)." "Existence of Prime Factor","Every integer n≥2 has at least one prime divisor (proved by strong induction)." "Fundamental Theorem of Arithmetic","Every integer ≥2 factors uniquely as a product of primes (up to order)." "Theorem on Division by a Prime","If prime p divides xy then p divides x or p divides y." "Euclid’s Algorithm","Recursive process gcd(a,b)=gcd(b,a−bq) to compute gcd efficiently." "Bézout’s Identity","∃x,y∈ℤ with ax+by = gcd(a,b)." "Coprime Integers","Integers a,b with gcd(a,b)=1." "Pigeonhole Principle","If |X|>|Y| then no injection X→Y exists; at least two elements of X map to same Y." "Power‑Set Cardinality Theorem","No bijection exists between a set X and its power set P(X) (|P(X)|>|X|)." "Cantor’s Diagonal Argument","(0,1) and thus ℝ is uncountable; any list of reals omits a constructed diagonal number." "Cartesian Product Cardinality","|A×B| = |A|·|B| (finite sets)." "Counting – Subsets","If |A|=n and S⊆A then |A∪{S}|=n+1; |A\{s}|=n−1 for s∈A." "Indicator of Infinite Set","Set is infinite ⇔ there exists an injection ℕ→X (or surjection X→ℕ)."

General Proof‑Solving Template

Step 0  Clarify the claim and rewrite it formally.
Step 1  Write down all relevant definitions (start the proof by invoking them).
Step 2  Choose an appropriate proof technique (direct, contrapositive, contradiction, induction, strong induction, etc.).
Step 3  Execute the logical argument, citing definitions, previously‑proved theorems, or known identities at each step.
Step 4  Conclude explicitly, restating what has been proved and marking the end (■).