Basic Logic and Proof Techniques

Why This Matters

Every theorem in this entire site is proved using one or more of these techniques. If you cannot recognize whether a proof proceeds by contradiction or contrapositive, you will struggle to read learning theory papers. Choosing the right proof technique often turns an intractable argument into a short one.

Logical Foundations

Definition

Implication

A statement $P \Rightarrow Q$ ("if $P$, then $Q$") is false only when $P$ is true and $Q$ is false. If $P$ is false, the implication is vacuously true regardless of $Q$.

Definition

Contrapositive

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$. These are logically equivalent. The converse $Q \Rightarrow P$ is not equivalent to the original.

Quantifiers

Definition

Universal and Existential Quantifiers

$\forall x \in S, P(x)$ means $P(x)$ holds for every element of $S$.

$\exists x \in S, P(x)$ means there is at least one element of $S$ for which $P(x)$ holds.

Negation swaps quantifiers: $\neg(\forall x, P(x)) \equiv \exists x, \neg P(x))$ and $\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$.

The negation rule is critical for proofs by contradiction. To disprove "for all $x$, $P(x)$," you need only find one counterexample.

Proof Techniques

Direct Proof

Assume $P$ is true. Through a chain of logical deductions, conclude $Q$. This is the simplest proof structure.

Example

The sum of two even integers is even

Let $a = 2m$ and $b = 2n$ for integers $m, n$. Then $a + b = 2(m + n)$, which is even. Done.

Proof by Contradiction

To prove $P$, assume $\neg P$ and derive a logical contradiction. Since the assumption led to a contradiction, $\neg P$ must be false, so $P$ is true.

Example

The square root of 2 is irrational

Assume $\sqrt{2} = a/b$ with $a, b$ integers and $\gcd(a, b) = 1$. Then $2b^2 = a^2$, so $a^2$ is even, so $a$ is even. Write $a = 2k$. Then $2b^2 = 4k^2$, so $b^2 = 2k^2$, so $b$ is even. But then $\gcd(a, b) \geq 2$, contradicting $\gcd(a, b) = 1$.

Proof by Contrapositive

To prove $P \Rightarrow Q$, instead prove $\neg Q \Rightarrow \neg P$. These are logically equivalent. Often easier when the negation of $Q$ gives a concrete condition to work with.

Example

If n squared is even, then n is even

Contrapositive: if $n$ is odd, then $n^2$ is odd. Proof: $n = 2k + 1$ implies $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd.

Proof by Induction

Definition

Weak Induction

To prove $P(n)$ for all $n \geq n_0$: (1) Base case: prove $P(n_0)$. (2) Inductive step: prove that $P(k) \Rightarrow P(k+1)$ for all $k \geq n_0$.

Definition

Strong Induction

To prove $P(n)$ for all $n \geq n_0$: (1) Base case: prove $P(n_0)$. (2) Inductive step: prove that $P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(k) \Rightarrow P(k+1)$. The inductive hypothesis assumes all previous cases, not just one.

Weak and strong induction are logically equivalent, but strong induction is sometimes more natural (e.g., proving properties of recursive algorithms where the recursion references multiple smaller inputs).

Proof by Construction

To prove that an object with certain properties exists, explicitly build it. Constructive proofs are stronger than existence proofs by contradiction because they produce the witness.

Proof by Cases

Split the domain into exhaustive, mutually exclusive cases and prove the claim separately in each case. Useful when a single argument does not cover all possibilities.

Main Theorems

Theorem

Principle of Mathematical Induction

Statement

Let $P(n)$ be a predicate on the natural numbers. If $P(n_0)$ is true and $P(k) \Rightarrow P(k+1)$ for all $k \geq n_0$, then $P(n)$ is true for all $n \geq n_0$.

Intuition

Induction is the domino effect. The base case knocks over the first domino. The inductive step ensures each domino knocks over the next. Together, they guarantee all dominoes fall.

Proof Sketch

This follows from the well-ordering principle: every nonempty subset of $\mathbb{N}$ has a least element. Suppose $P(n)$ fails for some $n$. Let $S = \{n \geq n_0 : \neg P(n)\}$. By well-ordering, $S$ has a least element $m > n_0$ (since $P(n_0)$ holds). Then $P(m-1)$ holds but $P(m)$ does not, contradicting the inductive step.

Why It Matters

Induction is the standard technique for proving statements about sequences, sums, algorithm correctness, and recursive structures. In learning theory, induction arguments appear in proving properties of iterative algorithms (e.g., convergence of gradient descent after $T$ steps).

Failure Mode

Forgetting the base case is the classic failure. The inductive step "$P(k) \Rightarrow P(k+1)$" can be vacuously true if $P$ is never true for any starting value. Both the base case and inductive step are required.

Common Confusions

Watch Out

Contradiction vs. contrapositive

To prove $P \Rightarrow Q$ by contradiction, you assume $P \wedge \neg Q$ and derive any contradiction. To prove it by contrapositive, you assume $\neg Q$ and derive $\neg P$ directly. Contrapositive is a direct proof of an equivalent statement. Contradiction is more general (you can derive any contradiction, not just $\neg P$), but contrapositive is cleaner when it works.

Watch Out

Converse is not the same as contrapositive

The converse of $P \Rightarrow Q$ is $Q \Rightarrow P$. This is a completely different statement that may be true or false independently. The contrapositive $\neg Q \Rightarrow \neg P$ is logically equivalent to the original. Confusing these leads to invalid proofs.

Watch Out

Induction does not work on the reals

Mathematical induction works on $\mathbb{N}$ (or any well-ordered set). You cannot use it to prove a statement for all real numbers. For the reals, you need different techniques (e.g., the least upper bound property, or transfinite induction with the axiom of choice).

Exercises

ExerciseCore

Problem

Prove by induction: for all $n \geq 1$, $\sum_{i=1}^n i = n(n+1)/2$.

Hint

Reveal Solution

ExerciseCore

Problem

Write the negation of: "For every $\epsilon > 0$, there exists $\delta > 0$ such that $|x - a| < \delta$ implies $|f(x) - f(a)| < \epsilon$." (This is the definition of continuity.)

Hint

Reveal Solution

References

Canonical:

• Velleman, How to Prove It, 3rd ed., Chapters 1-6
• Hammack, Book of Proof, 3rd ed., Chapters 1-10

Current:

• Bloch, Proofs and Fundamentals (2011), Chapters 1-3

• Enderton, Elements of Set Theory (1977), Chapters 1-6

• Halmos, Naive Set Theory (1960), Chapters 1-25

• Munkres, Topology (2000), Chapter 1 (set theory review)

Next Topics

• Sets, functions, and relations: the basic objects that proofs operate on
• Counting and combinatorics: proof by bijection and double counting