A Comprehensive Study Guide to Mathematical Logic and Proof

Foundations of Mathematical Reasoning

• Nature of Mathematics: High school mathematics primarily focuses on solving equations and numerical computations. College-level mathematics expands to sets, functions, and diverse abstract objects.

• Deductive Reasoning: This is the foundation of all mathematical proof. It involves justifying conclusions based on assumed premises. An argument is considered valid if it is impossible for the premises to be true without the conclusion being true as well.

• Prime Numbers: An integer greater than 1 is prime if it cannot be written as the product of two smaller positive integers.

• Conjectures and Counterexamples: A conjecture is a mathematical guess based on patterns. A single counterexample—an instance where the hypothesis holds but the conclusion fails—disproves a conjecture. For example, the conjecture that $2^n - 1$ is prime for all prime $n$ fails at $n = 11$, as $2^{11} - 1 = 2047 = 23 \times 89$.

Number Theory Principles and Classic Proofs

• Mersenne Primes: Prime numbers of the form $2^n - 1$. As of April 2005, the largest known prime was the Mersenne prime $2^{25,964,951} - 1$.

• Perfect Numbers: A positive integer $n$ where the sum of all positive divisors smaller than $n$ equals $n$ (e.g., 6 and 28).

• Euclid’s Theorem on Primes: There are infinitely many prime numbers. The proof assumes a finite list $p_1, p_2, ..., p_n$, constructs $m = (p_1 \times p_2 \times ... \times p_n) + 1$, and shows $m$ must have a prime factor not in the original list.

• Consecutive Non-Primes: For any positive integer $n$, there exists a sequence of $n$ consecutive integers containing no primes. One such sequence begins with $x = (n + 1)! + 2$, as every term $x + i$ (for $0 \le i \le n - 1$) is divisible by $i + 2$.

Sentential Logic and Statement Connectivity

• Statement Symbols: Letters ($P, Q, R$) represent unambiguous statements that are either true or false.

• Connectives:

  • Negation ($\neg$): "Not P." $\neg P$ is true if $P$ is false.

  • Conjunction ($\land$): "P and Q." True only if both are true.

  • Disjunction ($\lor$): "P or Q." Mathematically, this is the inclusive or (one, the other, or both).

  • Conditional ($\rightarrow$): "If P, then Q." $P$ is the antecedent, and $Q$ is the consequent.

  • Biconditional ($\leftrightarrow$): "P if and only if Q," or "P iff Q."

• Logical Form: Deductive validity depends on the structure (form) of the argument rather than the specific subject matter.

Truth Tables and Logical Equivalences

• Truth Values: Labels of True ($T$) or False ($F$) assigned to statements.

• Truth Table for Conditional ($P \rightarrow Q$):

  • $T \rightarrow T = T$

  • $T \rightarrow F = F$

  • $F \rightarrow T = T$

  • $F \rightarrow F = T$

• Tautology: A formula that is true under every possible truth assignment (e.g., $P \lor \neg P$).

• Contradiction: A formula that is false under every assignment (e.g., $P \land \neg P$).

• Equivalent Formulas: Formulas with identical truth tables. Key laws include:

  • DeMorgan’s Laws: $\neg(P \land Q) \iff \neg P \lor \neg Q$ and $\neg(P \lor Q) \iff \neg P \land \neg Q$.

  • Commutative Laws: $P \land Q \iff Q \land P$.

  • Associative Laws: $P \lor (Q \lor R) \iff (P \lor Q) \lor R$.

  • Distributive Laws: $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$.

  • Contrapositive Law: $P \rightarrow Q \iff \neg Q \rightarrow \neg P$.

Variables, Sets, and Elementhood Tests

• Variables: Letters used to represent objects. $P(x)$ denotes a statement about variable $x$.

• Sets: A collection of objects (elements).

  • Elementhood ($\in$): $x \in A$ means $x$ is an element of set $A$.

  • Set-Builder Notation: $\{x \mid P(x)\}$ defines a set by an elementhood test. Any $x$ making $P(x)$ true is an element.

• Bound vs. Free Variables: In \{x \mid x^2 < 9\}, $x$ is a bound variable (dummy variable); it does not stand for a specific object. Variables standing for specific objects are free.

• Truth Set: For any statement $P(x)$, its truth set is the set of all values for which the statement is true: $\{x \mid P(x)\}$.

• Common Universes:

  • $\mathbb{R}$: Real numbers.

  • $\mathbb{Q}$: Rational numbers.

  • $\mathbb{Z}$: Integers.

  • $\mathbb{N}$: Natural numbers ($0, 1, 2, ...$).

  • $\emptyset$: The empty set (no elements).

Set Theory Operations

• Intersection ($\cap$): $A \cap B = \{x \mid x \in A \land x \in B\}$.

• Union ($\cup$): $A \cup B = \{x \mid x \in A \lor x \in B\}$.

• Difference ($\setminus$): $A \setminus B = \{x \mid x \in A \land x \notin B\}$.

• Symmetric Difference ($\triangle$): $A \triangle B = (A \setminus B) \cup (B \setminus A)$. Elements in exactly one of the sets.

• Subsets ($\subseteq$): $A \subseteq B \iff \forall x(x \in A \rightarrow x \in B)$.

• Disjoint Sets: Sets with an empty intersection ($A \cap B = \emptyset$).

• Venn Diagrams: Visual tools representing set relations within a universe $U$.

Quantificational Logic

• Universal Quantifier ($\forall$): "For all." $\forall x P(x)$ means $P(x)$ stays true for every value in the universe.

• Existential Quantifier ($\exists$): "There exists." $\exists x P(x)$ means there is at least one value for which $P(x)$ is true.

• Quantifier Negation Laws:

  • $\neg \forall x P(x) \iff \exists x \neg P(x)$.

  • $\neg \exists x P(x) \iff \forall x \neg P(x)$.

• Unique Existence ($\exists!$): "There exists exactly one." $\exists! x P(x) \iff \exists x (P(x) \land \forall y (P(y) \rightarrow y = x))$.

• Bounded Quantifiers: Quantifiers restricted to a set, e.g., $\forall x \in A P(x)$, which means $\forall x (x \in A \rightarrow P(x))$.

Higher-Order Set Operations

• Indexed Families: A collection of sets $\{A_i \mid i \in I\}$ where each index $i$ corresponds to a set $A_i$.

• Power Set ($\mathcal{P}(A)$): The set of all subsets of $A$. If $A$ has $n$ elements, $\mathcal{P}(A)$ has $2^n$ elements.

• Union of a Family ($\cup F$): $\cup F = \{x \mid \exists A \in F (x \in A)\}$.

• Intersection of a Family ($\cap F$): $\cap F = \{x \mid \forall A \in F (x \in A)\}$.

Proof Strategies and Structured Proving

• Givens and Goals: The basic workflow of a proof. Givens are assumed true; the goal is what must be demonstrated.

• Strategy for $P \rightarrow Q$: Assume $P$, prove $Q$. Alternatively, use the contrapositive: Assume $\neg Q$, prove $\neg P$.

• Strategy for $\neg P$: Use Proof by Contradiction: Assume $P$, derive an impossible statement (a contradiction), thus proving $P$ is false.

• Strategy for $\forall x P(x)$: Let $x$ be an arbitrary object and prove $P(x)$.

• Strategy for $\exists x P(x)$: Find a specific value for $x$ and verify that $P(x)$ holds.

• Existence and Uniqueness: Prove existence of $x$ such that $P(x)$, then assume two such objects $y$ and $z$ exist and prove $y = z$.

• Proof by Cases: If given $P \lor Q$, prove the goal twice—once assuming $P$ and once assuming $Q$.

Relations and Orderings

• Ordered Pairs: $(a, b)$ where order matters. $(a, b) = (c, d) \iff a = c \land b = d$.

• Cartesian Product: $A \times B = \{(a, b) \mid a \in A \land b \in B\}$.

• Relation: Any set of ordered pairs $R \subseteq A \times B$. If $A = B$, it is a "relation on A."

• Domain and Range:

  • Dom(R): $\{a \in A \mid \exists b \in B ((a, b) \in R)\}$.

  • Ran(R): $\{b \in B \mid \exists a \in A ((a, b) \in R)\}$.

• Properties of Relations (on set A):

  • Reflexive: $\forall x \in A(xRx)$.

  • Symmetric: $\forall x, y \in A(xRy \rightarrow yRx)$.

  • Transitive: $\forall x, y, z \in A((xRy \land yRz) \rightarrow xRz)$.

  • Antisymmetric: $\forall x, y \in A((xRy \land yRx) \rightarrow x = y)$.

• Equivalence Relation: A relation that is reflexive, symmetric, and transitive. It divides a set into equivalence classes ($[x]_R = \{y \in A \mid yRx\}$), which form a partition of the set (pairwise disjoint nonempty subsets whose union is the set).

• Partial Order: A relation that is reflexive, antisymmetric, and transitive.

• Total Order: A partial order where every pair of elements is comparable ($xRy \lor yRx$).

Function Theory

• Function Definition: A relation $f \subseteq A \times B$ is a function ($f: A \rightarrow B$) if $\forall a \in A \exists! b \in B ((a, b) \in f)$.

• One-to-One (Injective): $\forall a_1, a_2 \in A(f(a_1) = f(a_2) \rightarrow a_1 = a_2)$. Distinct inputs yield distinct outputs.

• Onto (Surjective): $\forall b \in B \exists a \in A(f(a) = b)$. The range equals the codomain.

• Bijection: A function both one-to-one and onto. Also called a one-to-one correspondence.

• Inverse Function: If $f$ is a bijection, $f^{-1}$ is a function from $B$ to $A$ where $f^{-1}(b) = a \iff f(a) = b$.

• Composition: $(g \circ f)(x) = g(f(x))$.

Mathematical Induction

• Principle of Induction: To prove $\forall n \in \mathbb{N} P(n)$:

  1. Base Case: Prove $P(0)$.

  2. Induction Step: Prove $\forall n \in \mathbb{N} (P(n) \rightarrow P(n+1))$.

• Strong Induction: To prove $\forall n \in \mathbb{N} P(n)$, prove that if $P(k)$ holds for all k < n, then $P(n)$ holds.

• Well-Ordering Principle: Every nonempty set of natural numbers contains a smallest element.

• Recursive Definitions: Defining a function by its value at base cases and providing a rule to determine higher values from smaller ones (e.g., Factorials: $0! = 1$, $(n+1)! = (n+1) \times n!$; Fibonacci Sequence: $F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$).

Infinity and Set Cardinality

• Equinumerosity ($A \sim B$): Two sets have the same size if there exists a bijection between them.

• Countable Sets: Sets equinumerous to a subset of $\mathbb{Z}^+$. Includes all finite sets and denumerable sets (like $\mathbb{Z}$ and $\mathbb{Q}$).

• Uncountable Sets: Sets that are not countable (e.g., $\mathbb{R}$ and $\mathcal{P}(\mathbb{Z}^+)$).

• Cantor’s Diagonal Argument: Used to prove $\mathcal{P}(\mathbb{Z}^+)$ is uncountable by showing that any list of subsets must miss at least one set $D = \{n \in \mathbb{Z}^+ \mid n \notin f(n)\}$.

• Cantor–Schröder–Bernstein Theorem: If $A \preceq B$ (one-to-one function from $A$ to $B$) and $B \preceq A$ (one-to-one function from $B$ to $A$), then $A \sim B$.

• Continuum Hypothesis: The conjecture (neither provable nor disprovable in standard set theory) that there is no cardinality strictly between denumerable infinity and the cardinality of the real numbers.