Basic Logic and Proof Techniques

Why This Matters

Every theorem on this site is built from a small set of proof moves. If those moves feel mysterious, learning theory, optimization, probability, algorithms, and statistics all become harder than they need to be.

The goal is not to memorize proof names. The goal is to look at a statement and ask:

• What are the assumptions?
• What must be shown?
• Which quantifier or implication is the bottleneck?
• Would a direct proof, contrapositive, contradiction, induction, construction, or counterexample make the structure simpler?

Propositions And Implications

Definition

Proposition

A proposition is a statement that is either true or false. "The model overfits" is not precise enough by itself. "The training error is lower than the validation error by at least $0.2$" is closer to a mathematical proposition.

Definition

Implication$P\Rightarrow Q$

The implication $P\Rightarrow Q$ means: whenever $P$ is true, $Q$ must be true. It is false only in the case where $P$ is true and $Q$ is false.

The last two rows are called vacuous truth. If the premise is false, the implication has not been violated.

Definition

Contrapositive

The contrapositive of $P\Rightarrow Q$ is $\neg Q\Rightarrow \neg P$. The original implication and its contrapositive are logically equivalent.

Definition

Converse and Inverse

The converse of $P\Rightarrow Q$ is $Q\Rightarrow P$. The inverse is $\neg P\Rightarrow \neg Q$. Neither is equivalent to the original implication in general.

Quantifiers

Definition

Universal Quantifier

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

Definition

Existential Quantifier

$\exists x\in S,\ P(x)$ means at least one element of $S$ satisfies $P(x)$.

Negating quantifiers is one of the highest-yield proof skills:

$$\neg(\forall x\in S,\ P(x)) \equiv \exists x\in S\ \text{such that}\ \neg P(x),$$ $$\neg(\exists x\in S,\ P(x)) \equiv \forall x\in S,\ \neg P(x).$$

For nested quantifiers, negate from the outside inward. For example, the negation of

$$\forall \epsilon>0,\ \exists \delta>0,\ \forall x,\ |x-a|<\delta\Rightarrow |f(x)-f(a)|<\epsilon$$

is

$$\exists \epsilon>0,\ \forall \delta>0,\ \exists x \quad\text{such that}\quad |x-a|<\delta\ \text{and}\ |f(x)-f(a)|\geq \epsilon.$$

That is the logical shape of discontinuity.

Choosing A Proof Technique

Direct Proof

Assume the hypotheses and derive the conclusion.

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)$, so $a+b$ is even.

Direct proof is usually best when definitions immediately unpack into useful algebra.

Contrapositive

To prove $P\Rightarrow Q$, prove $\neg Q\Rightarrow \neg P$.

Example

If n squared is even, then n is even

Prove the contrapositive: if $n$ is odd, then $n^2$ is odd. Write $n=2k+1$. Then

$$n^2=4k^2+4k+1=2(2k^2+2k)+1,$$

which is odd.

Contrapositive is especially useful when the conclusion has a simple negation, such as "not injective," "not continuous," or "not linearly independent."

Contradiction

To prove a statement $P$, assume $\neg P$ and derive an impossibility.

Example

The square root of 2 is irrational

Assume $\sqrt{2}=a/b$ where $a,b$ are integers with no common factor. Then $2b^2=a^2$, so $a$ is even. Write $a=2k$. Then $2b^2=4k^2$, so $b^2=2k^2$, hence $b$ is even. This contradicts the assumption that $a$ and $b$ had no common factor.

Contradiction is powerful, but it can hide structure. If a contrapositive proof works cleanly, it is often more informative.

Induction

Definition

Weak Induction

To prove $P(n)$ for all $n\geq n_0$, prove the base case $P(n_0)$ and prove $P(k)\Rightarrow P(k+1)$ for every $k\geq n_0$.

Definition

Strong Induction

To prove $P(n)$ for all $n\geq n_0$, prove enough base cases and prove that $P(n_0),P(n_0+1),\ldots,P(k)$ together imply $P(k+1)$.

Theorem

Principle Of Mathematical Induction

Statement

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 every $n\geq n_0$.

Intuition

The base case starts the chain. The inductive step says every true case forces the next case. Together they cover all later natural numbers.

Proof Sketch

Suppose some $n\geq n_0$ fails. By the well-ordering principle, the set of failing $n$ has a smallest element $m$. Since the base case holds, $m>n_0$. Then $P(m-1)$ is true by minimality of $m$, so the inductive step gives $P(m)$, a contradiction.

Why It Matters

Induction proves formulas for sums, loop invariants, recursion correctness, convergence bounds after $T$ steps, and dynamic programming recurrences.

Failure Mode

The most common invalid induction proof assumes what it needs to prove. The inductive hypothesis gives $P(k)$ only for the previous case, not for every future case.

Cite as claim:basic-logic-and-proof-techniques::principle-of-mathematical-induction

report a correction →

Construction, Cases, And Counterexamples

Definition

Constructive Proof

To prove $\exists x\in S$ with property $P(x)$, explicitly define such an $x$ and verify the property.

Definition

Proof By Cases

Split the situation into exhaustive cases and prove the claim in each case. The cases must cover everything and should not silently overlap in a way that loses logic.

Definition

Counterexample

To disprove a universal claim $\forall x,\ P(x)$, find one $x$ such that $\neg P(x)$.

Counterexamples are not "negative examples." They are surgical logic tools. A single valid counterexample defeats a universal statement.

ML And Math Examples

Common Confusions

Watch Out

Contrapositive is not the converse

The contrapositive of $P\Rightarrow Q$ is $\neg Q\Rightarrow \neg P$ and is equivalent to the original. The converse $Q\Rightarrow P$ is a different claim.

Watch Out

A proof by examples is not a proof of a universal statement

Checking many examples can build intuition, but it does not prove $\forall x,\ P(x)$. A universal proof must cover every allowed object.

Watch Out

Induction needs a base case

The step $P(k)\Rightarrow P(k+1)$ can be true even if no case ever starts. The base case is what activates the chain.

Watch Out

Negating an implication changes it into an and statement

The negation of $P\Rightarrow Q$ is $P\wedge \neg Q$, not $\neg P\Rightarrow \neg Q$.

Quick Drills

Negate: "For every model, there exists a dataset on which it performs well."

Answer: There exists a model such that for every dataset, it does not perform well.

Identify the proof move: "Assume the algorithm does not terminate; then construct an infinite strictly decreasing sequence of nonnegative integers."

Answer: contradiction, usually with well-ordering or a descent measure.

Find the flaw: "The theorem holds for $n=1,2,3$, so it holds for all $n$."

Answer: examples are not induction. You still need a step proving $P(k)\Rightarrow P(k+1)$.

Contrapositive: "If a matrix has full column rank, then its columns are linearly independent."

Contrapositive: If the columns are linearly dependent, then the matrix does not have full column rank.

What To Remember

• An implication fails only when the premise is true and the conclusion is false.
• Contrapositive is equivalent to the original; converse is not.
• Negating quantifiers swaps $\forall$ and $\exists$.
• Induction needs both a base case and a valid step.
• To disprove "for all," find one counterexample.
• Good proof technique follows statement structure, not vibes.

Exercises

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$."

Hint

Reveal Solution

ExerciseCore

Problem

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

Hint

Reveal Solution

ExerciseAdvanced

Problem

Disprove: "If $ab=0$, then $a=0$ and $b=0$."

Hint

Reveal Solution

ExerciseAdvanced

Problem

Give a proof template for a PAC-style statement of the form: with probability at least $1-\delta$, every hypothesis in a finite class satisfies a deviation bound.

Hint

Reveal Solution

References

Canonical:

• Velleman, How to Prove It, 3rd ed., Chapters 1-6.
• Hammack, Book of Proof, 3rd ed., Chapters 1-10.
• Bloch, Proofs and Fundamentals (2011), Chapters 1-3.

Further:

• Rosen, Discrete Mathematics and Its Applications, logic and proof chapters.
• Sipser, Introduction to the Theory of Computation, proof examples in automata and computability.

Next Topics

• Sets, functions, and relations: the objects most proof statements talk about.
• Counting and combinatorics: proof by bijection, double counting, and induction.

Continue on ComputationPath

• SAT, SMT, and automated reasoning: what happens when logic becomes computation.