Introduction to Proofs

17 min read

Quick Reference

Before You Start: Prerequisite Check

Try This First

Before any definition, try to convince a skeptical classmate of this one claim, using only complete sentences and ordinary algebra:

If $n$ is an odd integer, then $n^2$ is an odd integer.

Pick a single odd number first (say $n = 7$) and check that $n^2 = 49$ is odd. Then ask yourself the harder question: how would you argue it for every odd number at once, without checking them one at a time?

The Idea Behind a Proof

A proof is the mechanism that turns a claim into certain knowledge. An example can suggest a pattern, and a thousand examples can make a pattern feel inevitable, yet none of them rules out the possibility that the very next case fails. A proof closes that gap. It is a finite sequence of statements where each statement is either an assumption you are allowed to make or a consequence forced by earlier statements through a valid rule of inference, ending in the claim you set out to establish.

Think of a proof as a process that takes definitions, agreed-upon assumptions, and previously proven results as inputs and returns a guarantee as output. The input side is where definitions do the heavy lifting: an argument about even numbers depends on the definition “$n = 2k$,” and the argument cannot move until that definition is unpacked into algebra.

This chain takes three standard shapes. A direct proof assumes the hypothesis and walks forward to the conclusion. A proof by contraposition proves the equivalent contrapositive instead, which is sometimes far easier. A proof by contradiction assumes the claim is false and derives an impossibility, forcing the claim to be true. Each shape comes with a rule of inference that makes it valid.

Prerequisite Hub

graph LR
    subgraph Builds_On["Builds On"]
        A["Rules of<br/>Inference"]
        B["Algebra of<br/>Inequalities"]
    end

    subgraph ThisSkill["This Skill"]
        C["Introduction<br/>to Proofs"]
    end

    subgraph Unlocks
        D["Proof Methods<br/>and Strategy"]
        E["Mathematical<br/>Induction"]
    end

    A --> C
    B --> C
    C --> D
    C --> E

    style C fill:#d1fae5,stroke:#a565f0,stroke-width:3px

    click C "introduction-to-proofs.html"
    click D "../ch1-sec8/proof-methods-and-strategy.html"

Builds on:

Unlocks:

Cross-course prerequisites: none.

Official Definitions

Each definition below is quoted from Rosen, 8th edition, Section 1.7, with the page citation. These are the canonical statements to put on the board and on a study sheet.

Theorem, Proof, Axiom

A theorem is a statement that can be shown to be true. We demonstrate that a theorem is true with a proof. A proof is a valid argument that establishes the truth of a theorem. The statements used in a proof can include axioms (or postulates), which are statements we assume to be true, the premises of the theorem, and previously proven theorems.

Rosen 8e, Section 1.7, p. 84-85 (subsection 1.7.1 Introduction).

A less important theorem that helps prove other results is called a lemma; a theorem that follows quickly from a theorem already proven is a corollary.

Conjecture

A conjecture is a statement that is being proposed to be a true statement, usually on the basis of some partial evidence, a heuristic argument, or the intuition of an expert. When a proof of a conjecture is found, the conjecture becomes a theorem.

Rosen 8e, Section 1.7, p. 85.

The difference between a conjecture and a theorem is exactly a proof. The opener’s “test $n = 7$” step produced partial evidence, which is the raw material of a conjecture, not yet a theorem.

Even Integer and Odd Integer, Parity (Definition 1)

The integer $n$ is even if there exists an integer $k$ such that $n = 2k$, and $n$ is odd if there exists an integer $k$ such that $n = 2k + 1$. Every integer is either even or odd, and no integer is both even and odd. Two integers have the same parity when both are even or both are odd; they have opposite parity when one is even and the other is odd.

Rosen 8e, Section 1.7, Definition 1, p. 86.

This is the single most-used definition in the first weeks of proof writing. The phrase “there exists an integer $k$” is the part to unpack into algebra: an even number is not the word “even,” it is the expression $2k$ that you can multiply and add with.

Direct Proof

A direct proof of a conditional statement $p \rightarrow q$ is constructed when the first step is the assumption that $p$ is true; subsequent steps are constructed using rules of inference, with the final step showing that $q$ must also be true.

Rosen 8e, Section 1.7, subsection 1.7.5 Direct Proofs, p. 87.

Proof by Contraposition

Proofs by contraposition make use of the fact that the conditional statement $p \rightarrow q$ is equivalent to its contrapositive, $\neg q \rightarrow \neg p$. In a proof by contraposition of $p \rightarrow q$, we take $\neg q$ as a premise, and using axioms, definitions, and previously proven theorems together with rules of inference, we show that $\neg p$ must follow.

Rosen 8e, Section 1.7, subsection 1.7.6 Proof by Contraposition, p. 87-88.

Proof by Contradiction

Suppose we want to prove that a statement $p$ is true, and suppose we can find a contradiction $q$ such that $\neg p \rightarrow q$ is true. Because $q$ is false but $\neg p \rightarrow q$ is true, we conclude that $\neg p$ is false, which means $p$ is true. We can prove that $p$ is true if we can show that $\neg p \rightarrow (r \wedge \neg r)$ is true for some proposition $r$; proofs of this type are called proofs by contradiction.

Rosen 8e, Section 1.7, subsection 1.7.7 Proofs by Contradiction, p. 92.

The Three Direct and Indirect Methods

Each method has two representations: the worded plan (what you assume and what you aim for) and the symbolic shape. Read across each row and translate one into the other.

A direct proof and a proof by contraposition both establish the same conditional $p \rightarrow q$; they differ only in which end you grab. Contraposition is the right tool when the negated conclusion $\neg q$ gives you something concrete to compute with and the original hypothesis $p$ does not. The worked examples below show one claim where contraposition is far easier than the direct attempt.

Why contraposition is valid, in one line

The contrapositive $\neg q \rightarrow \neg p$ is logically equivalent to $p \rightarrow q$: the two have identical truth tables. Proving one proves the other. This is a result from Propositional Equivalences, reused here as a proof technique.

Worked Examples

Worked Example 1: A Direct Proof

Claim. If $m$ and $n$ are both even integers, then $m + n$ is even.

Predict first. Before writing anything, predict the result and its form. Even plus even should be even, so you expect the final line to read $m + n = 2(\text{some integer})$. Hold that target; the algebra below has to land on it.

Proof (direct).

Step 1 (assume the hypothesis). Assume $m$ and $n$ are both even.

Step 2 (unpack the definition). By the definition of even, there exist integers $s$ and $t$ with $m = 2s$ and $n = 2t$. Use different letters for the two numbers; reusing one letter would force $m = n$, which is not given.

Step 3 (compute). $$m + n = 2s + 2t = 2(s + t).$$

Step 4 (match the definition). Because $s + t$ is an integer, $m + n$ has the form $2(\text{integer})$, so $m + n$ is even by the definition of even. $\blacksquare$

Check against the prediction. The last line is $2(s+t)$, exactly the $2(\text{integer})$ form predicted in the “Predict first” step. The proof reached its target.

Worked Example 2: Why Contraposition Beats a Direct Attempt

Claim. For every integer $n$, if $n^2$ is odd, then $n$ is odd.

Predict first. Try the direct route in your head: assume $n^2$ is odd, so $n^2 = 2k + 1$. To reach a statement about $n$, you would have to take a square root of $2k+1$, which does not stay inside the integers cleanly. Predict that the direct route stalls and that flipping to the contrapositive will be smoother.

Proof (contraposition). The contrapositive of “if $n^2$ is odd, then $n$ is odd” is:

if $n$ is not odd, then $n^2$ is not odd,

which, since every integer is even or odd (Definition 1), reads “if $n$ is even, then $n^2$ is even.”

Step 1 (assume the negated conclusion). Assume $n$ is even.

Step 2 (unpack). Then $n = 2k$ for some integer $k$.

Step 3 (compute). $$n^2 = (2k)^2 = 4k^2 = 2(2k^2).$$

Step 4 (match the definition). Because $2k^2$ is an integer, $n^2 = 2(\text{integer})$, so $n^2$ is even.

This proves the contrapositive, and the contrapositive is equivalent to the original. Therefore, if $n^2$ is odd, then $n$ is odd. $\blacksquare$

Check against the prediction. The direct attempt needed a square root and stalled, as predicted; the contrapositive needed only one squaring step. One way to see this claim is the contrapositive route just used. Another way is a proof by contradiction (assume $n^2$ odd and $n$ even, then derive that $n^2$ is even, a contradiction); both are valid, and which one reads better is a matter of taste. Which do you prefer, and why?

Worked Example 3: A Proof by Contradiction (the irrationality of $\sqrt{2}$)

This is the standard model proof by contradiction, Example 11 in Rosen.

Theorem. The number $\sqrt{2}$ is irrational.

Rosen 8e, Section 1.7, Example 11, p. 92-93.

Predict first. “Irrational” means “cannot be written as a fraction of integers.” There is no direct way to compute the absence of a fraction. Predict that the right move is to assume the opposite (that $\sqrt{2}$ is a fraction) and hunt for an impossibility.

Proof (contradiction).

Step 1 (assume the negation). Suppose, for contradiction, that $\sqrt{2}$ is rational. Then there are integers $a$ and $b$ with $b \neq 0$ such that $$\sqrt{2} = \frac{a}{b},$$ and the fraction is in lowest terms, so $a$ and $b$ have no common factor greater than $1$.

Step 2 (square both sides). $$2 = \frac{a^2}{b^2}, \qquad \text{so} \qquad a^2 = 2b^2.$$

Step 3 ($a$ must be even). Since $a^2 = 2b^2$, the integer $a^2$ is even. By the result of Worked Example 2, if $a^2$ is even then $a$ is even, so $a = 2c$ for some integer $c$.

Step 4 (substitute and reduce). Replace $a$ with $2c$: $$ (2c)^2 = 2b^2 \quad\Longrightarrow\quad 4c^2 = 2b^2 \quad\Longrightarrow\quad b^2 = 2c^2.$$ So $b^2$ is even, and again $b$ is even.

Step 5 (the contradiction). Now $a$ and $b$ are both even, so they share the common factor $2$. This contradicts Step 1, where the fraction was assumed to be in lowest terms ($a$ and $b$ with no common factor greater than $1$). The proposition “the fraction is in lowest terms” and “the fraction is not in lowest terms” cannot both hold; this is the impossibility $r \wedge \neg r$.

Step 6 (conclude). The assumption that $\sqrt{2}$ is rational forced a contradiction, so that assumption is false. Therefore $\sqrt{2}$ is irrational. $\blacksquare$

Check against the prediction. The proof never tried to compute “no fraction exists.” It assumed a fraction did exist and squeezed out an impossibility, exactly the contradiction shape predicted.

Common Misconceptions

Mastery Checklist

Novice (Level 1-2):

• I can state, from memory, the definitions of theorem, proof, axiom, and conjecture.
• I can write a general even integer as $2k$ and a general odd integer as $2k + 1$, using a fresh letter for each number.
• I can explain why testing examples does not prove a universal claim.

Competent (Level 3-4):

• I can write a direct proof of a simple conditional about integer parity.
• I can convert a conditional to its contrapositive and prove the contrapositive.
• I can say which method (direct or contraposition) is easier for a given claim and justify the choice.

Proficient (Level 5):

• I can reproduce the proof by contradiction that $\sqrt{2}$ is irrational and identify the exact line that is the contradiction.
• I can distinguish a genuine proof by contradiction from a contraposition proof dressed up as one.
• I can spot and repair the “same letter for two different numbers” error in a draft proof.

Mental Model

The “forced chain” view. Picture a proof as a row of dominoes you are allowed to set up. The first domino is whatever you assume (the hypothesis in a direct proof, the negated conclusion in contraposition, the negated claim in contradiction). Every later domino is one that an earlier domino forces to fall through a rule of inference or a definition. A direct proof tips the first domino and watches the conclusion fall at the far end. A contradiction proof tips a domino you suspect should never fall, and when it knocks over both “$r$” and “not $r$,” the impossibility tells you the starting domino was placed wrong, so the claim must be true. The discipline is simply this: never let a domino fall that nothing forced.

Connections

Looking back:

• Rules of Inference supply modus ponens, modus tollens, and the other valid steps that each line of a proof depends on.
• Propositional Equivalences prove that $p \rightarrow q$ and its contrapositive $\neg q \rightarrow \neg p$ are equivalent, which is what makes proof by contraposition valid.

Looking ahead:

• Proof Methods and Strategy (Section 1.8): proof by cases, existence and uniqueness proofs, finding counterexamples, and how to choose a method.
• Mathematical Induction (Chapter 5): a dedicated method for statements indexed by the positive integers, built on the proof discipline started here.

Real-world connections:

• Formal verification of software and hardware certifies that a system meets its specification by proof, not by testing every input.
• Cryptographic protocols rest on theorems (for example, about factoring) whose proofs, or whose hardness arguments, guarantee security claims.
• A type checker in a compiler is a proof engine: a program that type-checks carries a machine-checked proof that certain errors cannot occur at run time.

Practice Problems

Resources

Last updated: 2026-06-16