Basic proof terminology and concepts

This collection of pages gives a basic introduction to mathematical proof. First there are some definitions followed by some basic examples.

Definition: mathematical statement

A statement in proof is a collection of words or symbols that is either TRUE or FALSE. A statement cannot be BOTH True and False and it must be one of them.

So the statement (P1) 'I am currently wearing a pair of blue shoes' is either True or False. If I am wearing one red shoe and one blue shoe then P1 is False.

The expression 'x = 3' is not a statement, it is an expression. 'x = 3' becomes a statement once we know what the value of x is.

Another statement is 'I was born in Adelaide', is not about mathematical objects but is a statement because it is either True or False.

Statements can be about many different subjects, not just mathematics. For our purposes we are interested in mathematical statements, these are (true or false) statements about mathematical objects such as algebra, geometric shapes, matrices, vectors, numbers etc.

Ready to explore mathematical proofs?

Preliminary properties

Any proof builds on some very basic properties of the objects we are considering. These are so simple we almost think they are 'obvious' and not question them. There are two main 'basics' we need to be aware of before we start a mathematical proof.

  • The most basic items or "atoms" we are considering in our proof. For example: integers or real numbers. This is a bit like when we are building a house we decide what material we are going to use: say bricks, mortar, wood, nails, screws. We have to decide the simplest items we are going to use. We are not going to question how bricks or screws are made, we just use them.
  • We also need to identify or define the rules we are going to use to put together or "atoms". In a mathematical proof the rules are the laws of logic, or the rules of arithmetic. We don't question these rules, we just apply them.

In a proof we need to be clear what rules and laws we are accepting as true.

If you study proof and logic more deeply, you will need to consider whether your "atoms" and your rules are "complete" and "consistent". In building a house (or most houses) you won't get far without certain materials such as wood, electrical cables or water pipes. Similarly in building a proof you need a full set of rules (completeness) that will allow you to solve any problem (*) you might devise in that subject area. Also the rules must not lead to two different answers (consistency) from the starting point.

(*) Unfortunately, Gödel's Incompleteness Theorem(s) create a problem here, but I won't cover that as it is very technical and beyond the scope of what I am covering.

Most of the proofs in this app are about the properties of numbers. There can be proofs about other mathematical objects, and the basic principles of constructing a valid proof in this app still apply to those more abstract and complicated objects. However, to understand the basic idea and process of constructing a valid proof, the numbers we are familiar with provide more than enough examples to study.

The following definitions are not truly mathematically rigorous but they are detailed enough and familiar enough to be useful for our needs in studying proof.

Definitions

Positive Integers (or natural numbers*1) are basic counting numbers such as 1, 2, 3, ... , 37, ... , 256, ...

Integers are positive and negative counting numbers including zero: ..., -3, -2, -1, 0, +1, +2, +3, ...

Rational numbers (or fractions) are created when you divide one integer by another (excluding division by zero) for example: 1/2, -8/13*2

Real numbers we can think of as any point on the number line. I will introduce irrational and complex numbers later.

*1 Some mathematicians include 0 in the natural numbers, others do not.

*2 Note that every integer is also a rational number (e.g., 5 = 5/1).

Properties of the algebra of numbers and arithmetic

Proofs are based on taking simple properties and rules, applying logic and demonstrating more complicated properties. For any proofs we ultimately need to know what basic properties we can accept as true without proving them

We work hard at a young age to try to learn how to calculate with numbers: whole numbers, negative numbers, fractions, decimals. We do this for so long that eventually we don't question these rules or properties — we try not to think about them when we use them.

For proofs about numbers we need to state what rules or properties are so basic that we don't question them but accept them as correct and use them to build other properties of numbers. The basic properties of real numbers can be revealed by clicking on the link below. There are quite a few and I recommend you substitute some simple numbers to make sure you understand them.

Ultimately in a proof about real numbers you can only use the rules or properties listed below or any properties built from them.

Reveal →

Here are the basic algebraic properties most commonly used in mathematical proofs:

1. Closure Properties
For a given number system (like integers or real numbers):
  • Closed under addition: \((a + b)\) is in the set
  • Closed under multiplication: \((ab)\) is in the set
This ensures operations stay within the system.
2. Commutative Properties
  • Addition: \(a + b = b + a\)
  • Multiplication: \(ab = ba\)
These allow you to rearrange terms without changing the result.
3. Associative Properties
  • Addition: \((a + b) + c = a + (b + c)\)
  • Multiplication: \((ab)c = a(bc)\)
These justify regrouping of terms.
4. Distributive Property
\[a(b + c) = ab + ac\] (and similarly \((a + b)c = ac + bc\)). This is essential for expanding and factoring expressions.
5. Identity Properties
  • Additive identity: \(a + 0 = a\)
  • Multiplicative identity: \(a \cdot 1 = a\)
These show that 0 and 1 leave numbers unchanged.
6. Inverse Properties
  • Additive inverse: \(a + (-a) = 0\)
  • Multiplicative inverse (for \(a \neq 0\)): \(a \cdot \dfrac{1}{a} = 1\)
These are used to cancel terms and solve equations.
7. Cancellation Laws
  • If \(a + c = b + c\), then \(a = b\)
  • If \(ac = bc\) and \(c \neq 0\), then \(a = b\)
These are frequently used to simplify equations in proofs.
8. Zero Property of Multiplication
\[ab = 0 \implies a = 0 \text{ or } b = 0\] This is fundamental in algebra and number theory.
9. Substitution Property of Equality
If \(a = b\), then \(a\) can be replaced with \(b\) in any expression.

This underlies almost every algebraic proof step.
10. Transitive Property of Equality
If \(a = b\) and \(b = c\), then \(a = c\).

This allows chaining equalities in logical arguments.
11. Inequalities and Order
For all real numbers \(a, b, c\):

Trichotomy. Exactly one of the following is true: \[a < b, \quad a = b, \quad a > b.\] Transitivity. If \(a < b\) and \(b < c\), then \[a < c.\] Addition preserves order. If \(a < b\), then \[a + c < b + c.\] Multiplication by a positive number preserves order. If \(a < b\) and \(c > 0\), then \[ac < bc.\] These are often taken as the fundamental inequality axioms.

Fundamental properties of integers

Some proofs are about integers, or positive integers. Some of the rules/properties listed above no longer apply or need to be modified as the starting point for proofs about integers.

These distinct difference for integers from real numbers are important to understand so you know what you can and can't write in a proof about integers compared to a proof about real numbers.

Most of the algebraic properties of real numbers and integers are the same.

The key differences between the properties of integers and real numbers are highlighted in red below.

Reveal properties →

Here are the core fundamental properties of integers (\(\mathbb{Z}\)) that are typically used in mathematics:

1. Closure
If \(a\) and \(b\) are integers, then:
  • \(a + b\) is an integer
  • \(a - b\) is an integer
  • \(a \times b\) is an integer

Note: division is not closed in integers, since \(1 \div 2 = 0.5\), which is not an integer.

2. Commutative Properties
  • Addition: \(a + b = b + a\)
  • Multiplication: \(a \times b = b \times a\)
This means order does not matter for addition and multiplication.
3. Associative Properties
  • Addition: \((a + b) + c = a + (b + c)\)
  • Multiplication: \((a \times b) \times c = a \times (b \times c)\)
This allows regrouping without changing the result.
4. Distributive Property
Multiplication distributes over addition: \[a(b + c) = ab + ac\] This is a key structural property of integers.
5. Identity Elements
  • Additive identity: \(a + 0 = a\)
  • Multiplicative identity: \(a \times 1 = a\)
6. Inverse Properties
Additive inverse: for every integer \(a\), there exists \(-a\) such that: \[a + (-a) = 0\]

Multiplicative inverses generally do not exist in integers, except for \(1\) and \(-1\).

7. Ordering Properties
Integers are totally ordered: for any integers \(a\) and \(b\), exactly one is true: \[a < b, \quad a = b, \quad \text{or} \quad a > b\] The order is compatible with addition and multiplication (by positives).
8. No Zero Divisors
If \(ab = 0\), then \(a = 0\) or \(b = 0\).

9. Well-Ordering Principle (for non-negative integers)
Every non-empty set of non-negative integers has a smallest element.

This property underpins mathematical induction.
10. Infinite and Discrete Structure
  • Integers extend infinitely in both positive and negative directions.

  • Integers are discrete — there are no integers between consecutive numbers such as 2 and 3 - whereas for real numbers a and b, and b > a, there is always a real number (say (b - a)/2), between a and b.

Setting the context

It is important to know which mathematical objects the proof is about. For example, is the proof about: integers, positive integers, real numbers, rational numbers, or something else? This is important to recognise before attempting the proof since this tells us what operations are valid and can be used in the proof.

Look at the section and notice rules like "\(a + b\) is an integer if \(a\) and \(b\) are integers." The part after the word if — "\(a\) and \(b\) are integers" — is different from what comes before it. The part after if is usually what we assume to be true, and it is the starting point for a direct proof.

More formally, this context — the collection of objects and the operations permitted on them — is called the structure used in the proof.

Direct proofs

The If … then … statement

A good place to start to understand mathematical proof is with the If … then … statement. Devlin clarifies that this is the conditional rather than implication — for reasons explained in more detail in a sub-section to this page.

Before we dive into that detail, a challenge with a lot of claims (statements, propositions, conjectures) that we are asked to prove is that the claim is not written in the If … then … format. (Very) often a useful first step in constructing a proof is to convert the claim into If … then … format.

Key habit: Before attempting a proof, rewrite the claim in the form “If [hypothesis], then [conclusion].” This makes it clear what you are assuming and what you are trying to deduce.

Recognising the If … then … structure in disguise

Mathematical claims appear in many different linguistic forms. The table below shows common wordings together with their logically equivalent If … then … translation. Practise spotting these patterns — rewriting a claim in conditional form is often the very first step of a direct proof.

Original wording Equivalent If … then … form
Whenever \(n\) is an odd integer, \(n^2\) is odd. If \(n\) is an odd integer, then \(n^2\) is odd.
Show that \(x^2 - 5x + 6 = 0\) if \(x = 2\) or \(x = 3\). If \(x = 2\) or \(x = 3\), then \(x^2 - 5x + 6 = 0\).
Prove that \(a^2 + b^2 \geq 2ab\) for all real numbers \(a\) and \(b\). If \(a\) and \(b\) are real numbers, then \(a^2 + b^2 \geq 2ab\).
A sufficient condition for \(n\) to be divisible by 4 is that \(n\) is divisible by 8. If \(n\) is divisible by 8, then \(n\) is divisible by 4.
\(n\) being even is a necessary condition for \(n^2\) to be even. If \(n^2\) is even, then \(n\) is even.
Show that \(p\) is prime given that \(p > 1\) and \(p\) has no divisors other than 1 and itself. If \(p > 1\) and the only divisors of \(p\) are 1 and \(p\), then \(p\) is prime.
Every square number is non-negative. If \(n\) is a real number, then \(n^2 \geq 0\).
The product of two negative integers is positive. If \(a < 0\) and \(b < 0\) are integers, then \(ab > 0\).
For \(n\) to be divisible by 6, it is sufficient that \(n\) is divisible by both 2 and 3. If \(n\) is divisible by both 2 and 3, then \(n\) is divisible by 6.
Provided that \(x > 0\), we have \(\sqrt{x} > 0\). If \(x > 0\), then \(\sqrt{x} > 0\).
Let \(a\) and \(b\) be integers. Show that \(a - b\) is even, assuming \(a\) and \(b\) are both odd. If \(a\) and \(b\) are both odd integers, then \(a - b\) is even.
Only if \(n\) is odd can \(n^2\) be odd. If \(n^2\) is odd, then \(n\) is odd.

Notice that some phrasings — such as “necessary condition”, “only if”, and “show that … if …” — reverse the order of hypothesis and conclusion compared to the If … then … form. Take particular care with these: identifying which part is the assumption and which is the goal is the essential first step.

This collection presents rigorous proofs of fundamental algebraic expressions and identities. Each proof is presented with clear steps and mathematical justification.

Choose a category to explore:

A good place to start proof is considering basic algebraic identities. Those studying proof will have a good background in basic algebra techniques so they will be able to follow the working while learning how to present a proof.

Basic algebra proofs

Square of a sum

\[(a + b)^2 \equiv a^2 + 2ab + b^2\]

Proof of the expansion of a binomial square using distributive property.

Proof: Square of a Sum
Step 1
Begin with the left-hand side: \[(a + b)^2 \equiv (a + b)(a + b)\]
By definition of squaring
Step 2
Apply the distributive property (FOIL method): \[(a + b)(a + b) \equiv a \cdot a + a \cdot b + b \cdot a + b \cdot b\] \[\equiv a^2 + ab + ba + b^2\]
Each term in the first factor multiplies each term in the second
Step 3
Use the commutative property: \[ab \equiv ba\] Therefore: \[a^2 + ab + ba + b^2 \equiv a^2 + ab + ab + b^2 \equiv a^2 + 2ab + b^2\]
Combining like terms
Conclusion: Therefore, \((a + b)^2 \equiv a^2 + 2ab + b^2\) ∎

Difference of squares

\[a^2 - b^2 \equiv (a + b)(a - b)\]

Factorization of the difference between two perfect squares.

View Proof →
Proof: Difference of Squares
Step 1
Start with the right-hand side and expand: \[(a + b)(a - b)\]
We will show this is identically equal to \(a^2 - b^2\)
Step 2
Apply the distributive property: \[(a + b)(a - b) \equiv a \cdot a + a \cdot (-b) + b \cdot a + b \cdot (-b)\] \[\equiv a^2 - ab + ba - b^2\]
FOIL method
Step 3
Observe that the middle terms cancel: \[a^2 - ab + ab - b^2 \equiv a^2 + 0 - b^2 \equiv a^2 - b^2\]
Since \(ba \equiv ab\) and \(-ab + ab \equiv 0\)
Conclusion: Therefore, \(a^2 - b^2 \equiv (a + b)(a - b)\) ∎

Sum of cubes

\[a^3 + b^3 \equiv (a + b)(a^2 - ab + b^2)\]

Factorization of the sum of two perfect cubes.

Proof: Sum of two cubes
Start
Since we are trying to show what the sum of two cubes is start with the right-hand side and expand: \[(a + b)(a^2 - ab + b^2)\]
We will show this is identically equal to \(a^3 + b^3\)

Square of a difference

\[(a - b)^2 \equiv a^2 - 2ab + b^2\]

Expansion of the square of a binomial difference.

Proof: Square of a Difference
Start
Since we are trying to show what the square of difference is start with the left-hand side and expand: \[(a - b)^2\]
We will show this is identically equal to \(a^2 - 2ab + b^2\)

Difference of cubes

\[a^3 - b^3 \equiv (a - b)(a^2 + ab + b^2)\]

Factorization of the difference between two perfect cubes.

Proof: Difference of Two Cubes
Start
Since we want to show what the difference of two cubes is, start with the right-hand side and expand: \[(a - b)(a^2 + ab + b^2)\]
We will show this is identically equal to \(a^3 - b^3\)
Step 1
Distribute \(a\) across the trinomial: \[a \cdot (a^2 + ab + b^2) \equiv a^3 + a^2b + ab^2\]
Distributive law
Step 2
Distribute \(-b\) across the trinomial: \[-b \cdot (a^2 + ab + b^2) \equiv -a^2b - ab^2 - b^3\]
Distributive law
Step 3
Add the results from Steps 1 and 2 and collect like terms: \[(a^3 + a^2b + ab^2) + (-a^2b - ab^2 - b^3)\] \[\equiv a^3 + (a^2b - a^2b) + (ab^2 - ab^2) - b^3\] \[\equiv a^3 + 0 + 0 - b^3\] \[\equiv a^3 - b^3\]
The \(a^2b\) and \(ab^2\) terms cancel in pairs
Conclusion: Therefore \(a^3 - b^3 \equiv (a - b)(a^2 + ab + b^2)\) ∎

Proofs of fundamental inequalities and their applications in mathematics.

Preliminary properties of inequalities

  • For each \(x \in \mathbb{R}\) exactly one of the following holds: \(x > 0\), \(x = 0\), \(x < 0\)
  • When \(x \in \mathbb{R}\) then \(x > 0 \Leftrightarrow -x < 0\)
  • Let \(x, y \in \mathbb{R}\). If \(x, y > 0\) then \(x + y > 0\)
  • Let \(x, y \in \mathbb{R}\). If \(x, y > 0\) then \(xy > 0\)

Very useful technique in inequality proof

Often if you are given or have arrived at \(\{\text{something}\} < \{\text{something else}\}\), then often it is useful, or even necessary, to rearrange this to \(\{\text{something else}\} - \{\text{something}\} > 0\) so one of the properties of inequalities (see above) can be applied.

Inequality proofs

Sum and reciprocal inequality

\(a + \frac{1}{a} \geq 2\) for \(a > 0\)

Given that \(a\) is a positive real number, prove that \(a + \frac{1}{a} \geq 2\).

Proof: Sum and Reciprocal Inequality

Method 1: Algebraic Manipulation.

Step 1
Start with the inequality we want to prove: \[a + \frac{1}{a} \geq 2\] Multiply both sides by \(a\) (which is positive): \[a^2 + 1 \geq 2a\]
Since \(a > 0\), multiplying preserves the inequality
Step 2
Rearrange the terms: \[a^2 - 2a + 1 \geq 0\] Factor the left side: \[(a - 1)^2 \geq 0\]
Completing the square
Step 3
Since the square of any real number is non-negative: \[(a - 1)^2 \geq 0\]

This is always true.

Equality holds when \((a - 1)^2 = 0\), which occurs when \(a = 1\).
Fundamental property of real numbers

Method 2: AM-GM Inequality

Apply the AM-GM inequality to \(a\) and \(\frac{1}{a}\): \[\frac{a + \frac{1}{a}}{2} \geq \sqrt{a \cdot \frac{1}{a}} = \sqrt{1} = 1\] Therefore: \[a + \frac{1}{a} \geq 2\]
The arithmetic mean is at least the geometric mean
Conclusion: Therefore, for all positive real numbers \(a\), we have \(a + \frac{1}{a} \geq 2\), with equality when \(a = 1\). ∎

Adding to an inequality

\[x > y \Rightarrow a + x > a + y\]

Let \(a, x, y \in \mathbb{R}\). Prove if \(x > y\) then \(a + x > a + y\).

Proof: Adding to an inequality
Step 1: Start from the hypothesis
We are given that \(x > y\), which means: \[x - y > 0\]
By the preliminary property: \(x > y \Leftrightarrow x - y > 0\)
Step 2: Rewrite the target expression
Consider the difference of the two expressions we wish to compare: \[(a + x) - (a + y) = a + x - a - y = x - y\]
Expanding and cancelling \(a\)
Step 3: Conclude
From Step 1 we know \(x - y > 0\), and from Step 2 we have: \[(a + x) - (a + y) = x - y > 0\] Therefore \(a + x > a + y\).
By the preliminary property: \((a+x) - (a+y) > 0 \Leftrightarrow a + x > a + y\)
Conclusion: For all \(a, x, y \in \mathbb{R}\), if \(x > y\) then \(a + x > a + y\). ∎

AM-GM inequality

\[\frac{a + b}{2} \geq \sqrt{ab}\]

For non-negative real numbers \(a\) and \(b\), prove that their arithmetic mean is greater than or equal to their geometric mean.

Proof: AM-GM Inequality
Step 1: Start from a known truth
For any real number \(x\), we know that the square of \(x\) is non-negative: \[(\sqrt{a} - \sqrt{b})^2 \geq 0\] This holds for all \(a, b \geq 0\), since square roots of non-negative numbers are real.
The square of any real number is non-negative
Step 2: Expand the square
Expanding the left side: \[(\sqrt{a} - \sqrt{b})^2 = a - 2\sqrt{ab} + b \geq 0\]
Expanding \((p - q)^2 = p^2 - 2pq + q^2\) with \(p = \sqrt{a}\), \(q = \sqrt{b}\)
Step 3: Rearrange
Adding \(2\sqrt{ab}\) to both sides: \[a + b \geq 2\sqrt{ab}\] Dividing both sides by 2: \[\frac{a + b}{2} \geq \sqrt{ab}\]
Dividing by 2 preserves the inequality since \(2 > 0\)
Step 4: Equality condition
Equality holds when \((\sqrt{a} - \sqrt{b})^2 = 0\), i.e. when \(\sqrt{a} = \sqrt{b}\), i.e. when \(a = b\).
A square equals zero only when the expression inside is zero
Conclusion: For all non-negative real numbers \(a, b\), we have \(\dfrac{a+b}{2} \geq \sqrt{ab}\), with equality if and only if \(a = b\). ∎

Bernoulli's inequality

\[(1 + x)^n \geq 1 + nx\]

For x ≥ -1 and n a positive integer.

More inequality proofs will be added to this collection over time.

This section develops the dot product and cross product from first principles, establishing key properties including the geometric interpretation of the dot product and the perpendicularity of the cross product to the plane it spans.

Prerequisite vector knowledge: Basic vectors app

Algebraic rules used

1. Distributivity
\[\mathbf{u}\cdot(\mathbf{v}+\mathbf{w}) = \mathbf{u}\cdot\mathbf{v}+\mathbf{u}\cdot\mathbf{w}.\]
2. Scalar multiplication
\[\mathbf{u}\cdot(\lambda\mathbf{v}) = \lambda(\mathbf{u}\cdot\mathbf{v}).\]
3. Commutativity of scalar multiplication
\[ab=ba.\]
4. Cancellation
\[x - x = 0.\]

Vector definitions and proofs

Definition: Dot product in \(\mathbb{R}^2\)

\[\mathbf{a}\cdot\mathbf{b} = a_xb_x+a_yb_y\]

Let \(\mathbf{a}=(a_x,a_y)\) and \(\mathbf{b}=(b_x,b_y)\). The dot product is defined by \[\mathbf{a}\cdot\mathbf{b} = a_xb_x+a_yb_y.\] The magnitudes are \(|\mathbf{a}|=\sqrt{a_x^2+a_y^2}\) and \(|\mathbf{b}|=\sqrt{b_x^2+b_y^2}\).

Prove: \(\mathbf{a}\cdot\mathbf{b} = |\mathbf{a}|\,|\mathbf{b}|\cos\theta\)

\[\mathbf{a}\cdot\mathbf{b} = |\mathbf{a}|\,|\mathbf{b}|\cos\theta\]

If \(\theta\) is the angle between the vectors, then the component definition above is equivalent to \[\mathbf{a}\cdot\mathbf{b} = |\mathbf{a}|\,|\mathbf{b}|\cos\theta.\]

Proof: Dot Product Formula
Step 1: Cosine Rule
Apply the cosine rule to the triangle formed by \(\mathbf{a}\), \(\mathbf{b}\), and \(\mathbf{a}-\mathbf{b}\): \[|\mathbf{a}-\mathbf{b}|^2 = |\mathbf{a}|^2+|\mathbf{b}|^2 - 2|\mathbf{a}||\mathbf{b}|\cos\theta.\]
Cosine rule applied to the triangle formed by the two vectors
Step 2: Expand in coordinates
\(|\mathbf{a}-\mathbf{b}|^2\)
\(=\) \((a_x-b_x)^2+(a_y-b_y)^2\)
\(=\) \(a_x^2+a_y^2+b_x^2+b_y^2 - 2(a_xb_x+a_yb_y).\)
Expanding using the component definition of magnitude
Step 3: Substitute magnitudes
Since \(a_x^2+a_y^2=|\mathbf{a}|^2\) and \(b_x^2+b_y^2=|\mathbf{b}|^2\), we obtain \[|\mathbf{a}-\mathbf{b}|^2 = |\mathbf{a}|^2+|\mathbf{b}|^2 - 2(\mathbf{a}\cdot\mathbf{b}).\]
Recognising the component sums as squared magnitudes
Conclusion: Comparing the two expressions gives \[\mathbf{a}\cdot\mathbf{b} = |\mathbf{a}||\mathbf{b}|\cos\theta. \quad\square\]

Definition: Cross product in \(\mathbb{R}^3\)

\[\mathbf{r} = \mathbf{c}\times\mathbf{d}\]

Let \(\mathbf{c}=(c_x,c_y,c_z)^T\) and \(\mathbf{d}=(d_x,d_y,d_z)^T\) be two non-parallel vectors in \(\mathbb{R}^3\).

Let \(\mathbf{e}_x,\mathbf{e}_y,\mathbf{e}_z\) be the standard basis vectors. Define \(\mathbf{r}=\mathbf{c}\times\mathbf{d}\) using the determinant \[\mathbf{r} = \begin{vmatrix}\mathbf{e}_x & \mathbf{e}_y & \mathbf{e}_z\\ c_x & c_y & c_z\\ d_x & d_y & d_z\end{vmatrix}.\] Expanding along the first row, \[\mathbf{r} = \begin{pmatrix}c_yd_z-c_zd_y\\ c_zd_x-c_xd_z\\ c_xd_y-c_yd_x\end{pmatrix}.\]

Prove: Perpendicular vectors have zero dot product

\[\mathbf{a}\perp\mathbf{b} \implies \mathbf{a}\cdot\mathbf{b}=0\]

Suppose \(\mathbf{a}\perp\mathbf{b}\), so \(\theta=\tfrac{\pi}{2}\). Using the dot product formula, \[\mathbf{a}\cdot\mathbf{b} = |\mathbf{a}||\mathbf{b}|\cos\tfrac{\pi}{2} = 0.\]

Proof with Example in \(\mathbb{R}^2\)
Proof
Since \(\mathbf{a}\perp\mathbf{b}\), we have \(\theta=\frac{\pi}{2}\). Using the result of the dot product formula, \[\mathbf{a}\cdot\mathbf{b} = |\mathbf{a}||\mathbf{b}|\cos\frac{\pi}{2} = 0.\]
Direct application of the dot product formula with \(\cos(\pi/2)=0\)
Example in \(\mathbb{R}^2\)
Let \(\mathbf{u}=(e_x,e_y)\) and \(\mathbf{v}=(-e_y,e_x)\). Then \[\mathbf{u}\cdot\mathbf{v} = e_x(-e_y)+e_y(e_x) = -e_xe_y+e_xe_y = 0.\] Hence \((e_x,e_y)\perp(-e_y,e_x)\).
Concrete verification using components
Conclusion: \(\mathbf{a}\perp\mathbf{b} \implies \mathbf{a}\cdot\mathbf{b}=0. \quad\square\)

Definition: The cross product to the spanned plane

\[\mathbf{p} = \lambda\mathbf{c}+\mu\mathbf{d}, \qquad \lambda,\mu\in\mathbb{R}\]

Every vector in the plane generated by \(\mathbf{c}\) and \(\mathbf{d}\) has the form \[\mathbf{p} = \lambda\mathbf{c}+\mu\mathbf{d}, \qquad \lambda,\mu\in\mathbb{R}.\]

Prove: The cross product \(\mathbf{r}=\mathbf{c}\times\mathbf{d}\) is perpendicular to this plane

\[\mathbf{r} = \mathbf{c}\times\mathbf{d} \perp \{\lambda\mathbf{c}+\mu\mathbf{d} : \lambda,\mu\in\mathbb{R}\}\]

\(\mathbf{r}=\mathbf{c}\times\mathbf{d}\) is a normal vector to the plane spanned by \(\mathbf{c}\) and \(\mathbf{d}\).

Proof: \(\mathbf{r}\) is Perpendicular to the Plane
Step 1: Reduce to two conditions
Consider \(\mathbf{r}\cdot(\lambda\mathbf{c}+\mu\mathbf{d})\). By distributivity, \[\mathbf{r}\cdot(\lambda\mathbf{c}+\mu\mathbf{d}) = \lambda(\mathbf{r}\cdot\mathbf{c})+\mu(\mathbf{r}\cdot\mathbf{d}).\] It suffices to prove \(\mathbf{r}\cdot\mathbf{c}=0\) and \(\mathbf{r}\cdot\mathbf{d}=0\).
Algebraic rule 1 (distributivity) and 2 (scalar multiplication)
Step 2: Prove \((\mathbf{c}\times\mathbf{d})\cdot\mathbf{c}=0\)
Expanding using the component formula:
\((\mathbf{c}\times\mathbf{d})\cdot\mathbf{c}\) \(=\) \((c_yd_z-c_zd_y)c_x\)
\({}+(c_zd_x-c_xd_z)c_y\)
\({}+(c_xd_y-c_yd_x)c_z.\)
Expanding the brackets:
\(c_xc_yd_z - c_xc_zd_y\)
\({}+c_yc_zd_x - c_xc_yd_z\)
\({}+c_xc_zd_y - c_yc_zd_x.\)
By commutativity of scalar multiplication (\(ab=ba\)), each term cancels with an equal and opposite term, giving \(0\).
Algebraic rules 3 and 4 (commutativity and cancellation)
Step 3: Conclude
By an identical argument, \((\mathbf{c}\times\mathbf{d})\cdot\mathbf{d}=0\). Therefore \[\mathbf{r}\cdot(\lambda\mathbf{c}+\mu\mathbf{d}) = \lambda(0)+\mu(0) = 0.\] Hence \(\mathbf{r}\) is perpendicular to every vector in the plane \(\{\lambda\mathbf{c}+\mu\mathbf{d}:\lambda,\mu\in\mathbb{R}\}\).
The two zero dot products established above suffice for all linear combinations
Conclusion: \(\mathbf{r}=\mathbf{c}\times\mathbf{d}\) is a normal vector to the plane spanned by \(\mathbf{c}\) and \(\mathbf{d}\). \(\square\)

Proofs of basic moduli properties of real numbers.

Preliminary properties of inequalities required in moduli proofs

  • For each \(x \in \mathbb{R}\) exactly one of the following holds: \(x > 0\), \(x = 0\), \(x < 0\)
  • When \(x \in \mathbb{R}\) then \(x > 0 \Leftrightarrow -x < 0\)
  • Let \(x, y \in \mathbb{R}\). If \(x, y > 0\) then \(x + y > 0\)
  • Let \(x, y \in \mathbb{R}\). If \(x, y > 0\) then \(xy > 0\)

Very useful inequality technique in modulus proof

Often if you are given or have arrived at \(\{\text{something}\} < \{\text{something else}\}\), then often it is useful, or even necessary, to rearrange this to \(\{\text{something else}\} - \{\text{something}\} > 0\) so one of the properties of inequalities (see above) can be applied.

Moduli proofs

Triangle inequality

\[|a + b| \leq |a| + |b|\]

For all real numbers \(a\) and \(b\), prove that the absolute value of their sum is at most the sum of their absolute values.

Strategy: Moduli are positive so sum of moduli is positive, so square of sum of moduli is positive. Then take the difference of the two terms in the original expression, making the inequality \(\geq 0\). Rearrange and take square roots to recover the modulus inequality.

Proof: Triangle Inequality
Step 1: Establish a key bound
For any real number \(x\), it is always the case that: \[x \leq |x| \quad \text{and} \quad -x \leq |x|\] Applying this to \(a\) and \(b\): \[a \leq |a|, \qquad b \leq |b|\] \[-a \leq |a|, \qquad -b \leq |b|\]
By definition of absolute value: \(|x| = x\) if \(x \geq 0\), and \(|x| = -x\) if \(x < 0\)
Step 2: Square both sides
Since both sides of \(|a+b| \leq |a|+|b|\) are non-negative, the inequality holds if and only if its square holds: \[|a + b|^2 = (a + b)^2 = a^2 + 2ab + b^2\] \[(|a| + |b|)^2 = |a|^2 + 2|a||b| + |b|^2 = a^2 + 2|ab| + b^2\]
\(|x|^2 = x^2\) for all real \(x\); also \(|a||b| = |ab|\)
Step 3: Compare the squares
Subtracting: \[(|a|+|b|)^2 - |a+b|^2 = 2|ab| - 2ab = 2(|ab| - ab)\] Since \(ab \leq |ab|\) for all real \(a, b\), we have \(|ab| - ab \geq 0\), and therefore: \[(|a|+|b|)^2 - |a+b|^2 \geq 0 \implies |a+b|^2 \leq (|a|+|b|)^2\]
Using \(x \leq |x|\) applied to \(x = ab\)
Step 4: Take square roots
Since both \(|a+b|\) and \(|a|+|b|\) are non-negative, taking square roots preserves the inequality: \[|a + b| \leq |a| + |b|\] Equality holds when \(|ab| = ab\), i.e. when \(ab \geq 0\) — meaning \(a\) and \(b\) have the same sign, or at least one is zero.
The square root function is increasing on \([0, \infty)\)
Conclusion: For all \(a, b \in \mathbb{R}\), \(|a + b| \leq |a| + |b|\), with equality if and only if \(ab \geq 0\). ∎

Product of moduli

\[|x||y| = |xy|\]
Proof: Product of moduli
Algebraic Manipulation

For all real numbers \( x \) and \( y \),

\[|xy| = |x||y|\]

Consider the cases where numbers are:

  • positive
  • zero
  • negative
We use: \[ |x| = \begin{cases} x & \text{if } x > 0 \\ 0 & \text{if } x = 0 \\ -x & \text{if } x < 0 \end{cases} \]
Case 1

\( x = 0 \) or \( y = 0 \)

Then: \[ xy = 0 \quad \Rightarrow \quad |xy| = 0 \] Also: \[ |x||y| = 0 \] So: \[ |xy| = |x||y| \]
Since ......
Case 2

\( x > 0 \), \( y > 0 \)

Then: \[ |x| = x,\quad |y| = y \] So: \[ |x||y| = xy \] And since \( xy > 0 \), \[ |xy| = xy \] Hence: \[ |xy| = |x||y| \]
.....
Case 3

\( x < 0 \), \( y < 0 \)

Then: \[ |x| = -x,\quad |y| = -y \] So: \[ |x||y| = (-x)(-y) = xy \] Also, \( xy > 0 \), so: \[ |xy| = xy \] Thus: \[ |xy| = |x||y| \]
.....
Case 4

One positive, one negative

Without loss of generality, let: \[ x > 0,\quad y < 0 \] Then: \[ |x| = x,\quad |y| = -y \] So: \[ |x||y| = x(-y) = -xy \] Now \( xy < 0 \), so: \[ |xy| = -(xy) \] Hence: \[|xy| = -xy = |x||y|\] (The case \( x < 0, y > 0 \) is identical.)
.....

Number theory

Typically 'Number Theory' refers to the properties of integers such as properties of divisibility and prime numbers. The definitions of the main types of numbers is given below. However, the proofs for real numbers are separated into a separate section as the approaches to proofs for integers against reals are fairly different.

Proof by cases

Often a proof about properties of integers can be splitting the working into two cases: considering what happens when we start 'n is a general even number (\(n = 2k\), \(k\) an integer)' and follow with the case 'n is a general odd number (\(n = 2k+1\), \(k\) an integer)'.

Types of number

For definitions of the main types of numbers used in these proofs, see:

Building complex definitions

We can use simpler definitions to build more complex definitions. We have to assume we understand what we mean by basic arithmetic operations such as add, subtract, multiply and divide.

Definition: An even number is 2 multiplied by an integer.

In mathematical notation: A number \(n\) is even if \(n = 2k\) for some integer \(k\).

In the example above, an even number is defined in terms of more basic objects and operations such as integer and multiplication—implicitly in "2k".

Available proofs

Even expression

\[n^2 - n \text{ is even for all integers } n\]

Prove that \(n^2 - n\) is an even number for all integers.

Proof: n² - n is Even
Method 1: Factorization
Factor the expression: \[n^2 - n = n(n - 1)\]
Factor out common factor \(n\)
Step 2
Observe that \(n\) and \((n-1)\) are consecutive integers. For any integer \(n\), exactly one of the following is true:
  • \(n\) is even and \((n-1)\) is odd
  • \(n\) is odd and \((n-1)\) is even
Consecutive integers have opposite parity
Step 3
Since one of the two factors is even, the product \(n(n-1)\) must be even. If either factor is even (say \(= 2m\) for some integer \(m\)), then: \[n(n-1) = 2m \cdot \text{(other factor)} = 2k\] where \(k\) is an integer.
A product is even if at least one factor is even
Conclusion: Therefore, \(n^2 - n = n(n-1)\) is even for all integers \(n\). ∎

Cube numbers are one of : 9k, 9k −1, 9k +1

\[n^3 \equiv 0, 1, \text{ or } 8 \pmod{9}\]

Prove that all cube numbers are either a multiple of 9 or one more or one less than a multiple of 9.

Proof: Cube Numbers Modulo 9
Step 1
Any integer \(n\) can be written in one of the forms: \[n \equiv 0, 1, 2, 3, 4, 5, 6, 7, \text{ or } 8 \pmod{9}\]
Complete residue system modulo 9
Step 2
Calculate \(n^3 \pmod{9}\) for each case:
  • If \(n \equiv 0 \pmod{9}\): \(n^3 \equiv 0^3 \equiv 0 \pmod{9}\)
  • If \(n \equiv 1 \pmod{9}\): \(n^3 \equiv 1^3 \equiv 1 \pmod{9}\)
  • If \(n \equiv 2 \pmod{9}\): \(n^3 \equiv 2^3 \equiv 8 \pmod{9}\)
  • If \(n \equiv 3 \pmod{9}\): \(n^3 \equiv 3^3 \equiv 27 \equiv 0 \pmod{9}\)
  • If \(n \equiv 4 \pmod{9}\): \(n^3 \equiv 4^3 \equiv 64 \equiv 1 \pmod{9}\)
  • If \(n \equiv 5 \pmod{9}\): \(n^3 \equiv 5^3 \equiv 125 \equiv 8 \pmod{9}\)
  • If \(n \equiv 6 \pmod{9}\): \(n^3 \equiv 6^3 \equiv 216 \equiv 0 \pmod{9}\)
  • If \(n \equiv 7 \pmod{9}\): \(n^3 \equiv 7^3 \equiv 343 \equiv 1 \pmod{9}\)
  • If \(n \equiv 8 \pmod{9}\): \(n^3 \equiv 8^3 \equiv 512 \equiv 8 \pmod{9}\)
Direct computation
Step 3
From the calculations above, we see that: \[n^3 \equiv 0, 1, \text{ or } 8 \pmod{9}\] This means:
  • \(n^3 \equiv 0 \pmod{9}\): cube is a multiple of 9
  • \(n^3 \equiv 1 \pmod{9}\): cube is one more than a multiple of 9
  • \(n^3 \equiv 8 \pmod{9}\): cube is one less than a multiple of 9 (since \(8 \equiv -1 \pmod{9}\))
Interpretation of residues
Conclusion: All cube numbers are either a multiple of 9, one more than a multiple of 9, or one less than a multiple of 9. ∎

Introduction to real number proofs

The real numbers include both (and only) rational and irrational numbers. Proofs involving real numbers often require careful consideration of properties such as ordering, absolute values, and the completeness of the real number system.

Common proof techniques for real numbers include using techniques such as:

  • splitting the proof into three cases — every real number is either positive, negative, or zero
  • properties of absolute values
  • inequalities

Available proofs

More real number proofs will be added to this collection over time.

See also:

What is a counter-example?

A counter-example is a single specific instance that disproves a general statement. To prove that a proposition of the form "for all \(x\), property \(P(x)\) holds" is false, it is enough to exhibit just one value of \(x\) for which \(P(x)\) fails. No matter how convincing a pattern looks, one counter-example is sufficient to demolish it entirely.

Counter-examples are important in mathematics because they:

  • show the limits of a result — exactly where and why it breaks down
  • guard against over-generalisation from patterns observed in small cases
  • motivate the need for careful hypotheses in theorems
  • remind us that plausibility is not proof

Propositions disproved by counter-example

A false proposition about integers

\[n^2 + n + 41 \text{ is prime for every non-negative integer } n\]

The expression \(n^2 + n + 41\) produces primes for \(n = 0, 1, 2, \ldots, 39\) — forty consecutive cases. This striking pattern, discovered by Euler, makes the proposition feel compelling. Yet the general statement is false.

Counter-example: \(n^2 + n + 41\) is not always prime
✗ Disproof by Counter-example — To disprove a "for all" statement we need only one failing case.
Observe the pattern for small \(n\)
Computing the first several values: \[ \begin{array}{c|c|l} n & n^2+n+41 & \text{prime?} \\ \hline 0 & 41 & \checkmark \\ 1 & 43 & \checkmark \\ 2 & 47 & \checkmark \\ 3 & 53 & \checkmark \\ \vdots & \vdots & \vdots \\ 39 & 1601 & \checkmark \end{array} \] Every value from \(n = 0\) to \(n = 39\) is prime. The pattern appears unbreakable.
40 consecutive successes makes the proposition seem very likely to be true
The counter-example: \(n = 40\)
Substitute \(n = 40\): \[40^2 + 40 + 41 = 1600 + 40 + 41 = 1681\] Now factorise \(1681\): \[1681 = 41 \times 41 = 41^2\] Since \(1681 = 41^2\) has a factor other than 1 and itself, it is not prime.
We can see why it fails at \(n=40\): substituting \(n = 41k - 1\) for any integer \(k\) always gives a multiple of 41, since \((41k-1)^2 + (41k-1) + 41 = 41(41k^2 - k + 1)\)
Conclusion: The single case \(n = 40\) gives \(n^2 + n + 41 = 41^2\), which is composite. Therefore the proposition "\(n^2 + n + 41\) is prime for every non-negative integer \(n\)" is false. ∎

A false proposition about real numbers

\[\text{For all } x \in \mathbb{R},\quad \sqrt{x^2} = x\]

Squaring a number and then taking the square root seems like it should simply return the original number. For positive reals the formula works perfectly, and it is easy to assume it holds for all real numbers. Yet the general statement is false.

Counter-example: \(\sqrt{x^2} = x\) does not hold for all \(x \in \mathbb{R}\)
✗ Disproof by Counter-example — To disprove a "for all" statement we need only one failing case.
Why the formula seems true
For any positive real, for example \(x = 5\): \[\sqrt{5^2} = \sqrt{25} = 5 = x \quad \checkmark\] For \(x = 0\): \[\sqrt{0^2} = \sqrt{0} = 0 = x \quad \checkmark\] The formula works in every case one is likely to try first — positive numbers and zero.
Positive reals and zero satisfy the formula, which is why it looks universally true
The counter-example: \(x = -3\)
Substitute \(x = -3\): \[\sqrt{(-3)^2} = \sqrt{9} = 3\] But \(x = -3\), so \(\sqrt{x^2} = 3 \ne -3 = x\).

The formula fails because the square root function \(\sqrt{\phantom{x}}\) is defined to return the non-negative square root. The correct identity for all real \(x\) is: \[\sqrt{x^2} = |x|\] which equals \(x\) only when \(x \geq 0\).
\(\sqrt{\phantom{x}} : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}\) is defined as the principal (non-negative) square root, so \(\sqrt{9} = 3\), never \(-3\)
Conclusion: Taking \(x = -3\) gives \(\sqrt{x^2} = 3 \ne -3 = x\). Therefore the proposition "\(\sqrt{x^2} = x\) for all \(x \in \mathbb{R}\)" is false. The correct statement is \(\sqrt{x^2} = |x|\) for all \(x \in \mathbb{R}\). ∎

More counter-examples will be added to this collection over time.

Introduction to geometric proofs

Geometry is the branch of mathematics concerned with questions of shape, size, relative position of figures, and the properties of space. Geometric proofs use logical reasoning to establish the truth of geometric statements.

These proofs are for Euclidean geometry which models the properties of shapes on a flat surface or plane.

In this section, we explore fundamental geometric theorems and their proofs, building from basic axioms and definitions to more complex results. As a result is proved, it is accepted as true and can then be used to prove other results. This is the process of building mathematical results from the simplest statements.

Fundamental Euclidean geometric property

There is a basic property of angles that is needed and used in most proofs, that is so 'obvious' it seems silly to even need to state it. However, if we are trying to build proofs from the simplest components or parts, we need this property. We can describe it as 'The whole is equal to the sum of its parts' or 'Every object is made by adding together parts it is made from'. In Euclidean geometry this can be applied as: If we split any angle by drawing a line through the vertex of the angle creating two new angles then the size (*) of the original angle is equal to the sum of the size of the smaller angles.

α β α + β = whole angle

A line from the vertex splits the angle into two parts

(*) We have to ignore what is meant by 'the size of an angle'. If you are interested in this look up 'measure theory'.

Available proofs

Adjacent angles on a straight line

\[\alpha + \beta = 180°\]

Adjacent angles formed by a straight line standing on a base always sum to two right angles.

Preliminaries

There are some basic definitions or properties of objects that we accept as true to be our starting point for the proof. One task is to make these definitions or properties as simple as possible. To be used in the proof:

  • (see from above) If an angle is split by a straight line from the vertex, the sum of the two created angles is equal to the size of the original angle.
  • Special case when the adjacent angles on a straight line are equal.

Let us accept we "know" what an "angle" is.

View Proof →
Proof: Adjacent angles on a straight line sum to two right angles

1.1 Definition of right angle

Angle size = 2 right-angles

1.2 Size of straight line angle

α β

2. Adjacent angles on a straight line

Step 1
A (half) straight line constructed (drawn) on another straight line where the angles created are equal, each new angle is defined as a right angle. Since the whole (angle) is the sum of its parts, the angle of a straight line is two right angles (in size).
Step 2
If we construct (draw) a straight line on the base line, so the angles created are not equal, then since the (size of the) angle on a straight line is two right angles (from step 1), and adjacent angles add up to the whole (given property), the adjacent angles on a straight line always add up to two right angles.
Conclusion: Adjacent angles formed by any straight line standing on a base always sum to two right angles, regardless of whether or not those angles are equal. ∎

Opposite angles theorem

\[\alpha = \gamma \quad \text{and} \quad \beta = \delta\]

When two straight lines intersect, the opposite angles formed are equal.

Preliminaries

This proof uses only one previously established result:

  • Adjacent angles on a straight line (proved above): a straight line standing on a base creates two adjacent angles that sum to two right angles (180°).
View Proof →
Proof: Opposite angles formed by two intersecting straight lines are equal
A B C D O α β γ δ

Two straight lines crossing at O

α+β=180° (line CD) β+γ=180° (line AB) A B C D O α β γ

Adjacent angle pairs at O

Step 1: Apply the adjacent angles result to line CD
CD is a straight line. Ray OA stands on line CD at O, dividing it into two adjacent angles: \[\alpha + \beta = 180° \quad \text{...[1]}\]
Step 2: Apply the adjacent angles result to line AB
AB is a straight line. Ray OD stands on line AB at O, dividing it into two adjacent angles: \[\beta + \gamma = 180° \quad \text{...[2]}\]
Step 3: Equate and cancel
Both [1] and [2] equal 180°, so: \[\alpha + \beta = \beta + \gamma\] Subtracting \(\beta\) from both sides: \[\alpha = \gamma\]
Step 4: The remaining opposite pair
By the same argument — applying the adjacent angles result to line AB (giving \(\alpha + \delta = 180°\)) and to line CD (giving \(\delta + \gamma = 180°\)) — it follows that: \[\beta = \delta\]
Conclusion: When two straight lines intersect, both pairs of opposite angles are equal: \(\alpha = \gamma\) and \(\beta = \delta\). ∎

Parallel lines and transversals

\[\alpha = \alpha\]

When a transversal crosses two parallel lines, the alternate interior angles formed are equal.

Parallel lines (definition): two lines in the same plane that never meet however far they are extended.

Preliminaries

This proof uses two previously established results and one axiom:

  • Adjacent angles on a straight line (proved): a straight line standing on a base creates two adjacent angles summing to two right angles.
  • Opposite angles theorem (proved): when two straight lines intersect, the opposite angles are equal.
  • Corresponding angles axiom (accepted, equivalent to the parallel postulate): when a transversal crosses two parallel lines, the angles in the same position at each intersection are equal.
View Proof →
Proof: Alternate interior angles on parallel lines are equal
α α p q t P Q

Alternate interior angles α = α

ϕ α ϕ p q t P Q

Corresponding and opposite angles

Step 1: Corresponding angles at P and Q
The transversal t cuts parallel lines p and q at P and Q respectively. Let ϕ be the angle at P in the upper-right position (above p, right of t). The angle in the same position at Q (above q, right of t) is a corresponding angle. Since p ∥ q, corresponding angles are equal: \[\varphi_P = \varphi_Q = \varphi \quad \text{...[1]}\]
Step 2: Opposite angles at P
At P, the angle ϕ (upper-right) and the angle α (lower-left) are opposite angles formed by the intersection of t and p. By the opposite angles theorem: \[\alpha = \varphi \quad \text{...[2]}\]
Step 3: Identify the alternate interior angles
The angle α at P is below p and to the left of t — it lies between the parallel lines on the left side of the transversal. The angle ϕ at Q is above q and to the right of t — it lies between the parallel lines on the right side of the transversal. These two angles are on opposite sides of t and between the parallel lines: they are the alternate interior angles.
Step 4: Conclude
From [1] and [2]: \[\alpha = \varphi = \varphi_Q\] That is, the alternate interior angle at P equals the alternate interior angle at Q. ∴
Conclusion: When a transversal crosses two parallel lines, the alternate interior angles are equal. The same argument applied to the supplementary angle at P shows that the other pair of alternate interior angles is also equal. ∪

Sum of triangle angles

\[\alpha + \beta + \gamma = 180°\]

The interior angles of any triangle sum to two right angles.

Parallel lines (definition): two lines in the same plane that never meet however far they are extended.

Preliminaries

This proof builds on the following results and definitions, each accepted as either proved or axiomatic:

  • Adjacent angles on a straight line (proved above): a straight line standing on a base creates two adjacent angles that sum to two right angles.
  • Parallel postulate (accepted without proof): through any point not on a given line, there is exactly one line parallel to the given line.
  • Alternate interior angles: when a straight line (transversal) crosses two parallel lines, the alternate interior angles — on opposite sides of the transversal and between the parallel lines — are equal.
View Proof →
Proof: The interior angles of a triangle sum to two right angles
A B C α β γ

Triangle ABC

A B C D E β α γ β γ

Line DE through A, parallel to BC

Step 1: Construct a line through A parallel to BC
Draw line DE through vertex A parallel to the base BC. By the parallel postulate such a line exists and is unique.
Step 2: Identify the first pair of alternate interior angles
Line AB is a transversal crossing the parallel lines DE and BC. The angle \(\angle DAB\) (at A, between AD and AB) and the angle \(\beta\) (at B, between BA and BC) are alternate interior angles. Therefore: \[\angle DAB = \beta\]
Step 3: Identify the second pair of alternate interior angles
Line AC is a transversal crossing the parallel lines DE and BC. The angle \(\angle EAC\) (at A, between AE and AC) and the angle \(\gamma\) (at C, between CA and CB) are alternate interior angles. Therefore: \[\angle EAC = \gamma\]
Step 4: Apply the straight line result
The angles \(\angle DAB\), \(\alpha\), and \(\angle EAC\) together make up the straight line DAE at point A. By the result proved for adjacent angles on a straight line: \[\angle DAB + \alpha + \angle EAC = \text{two right angles}\]
Step 5: Substitute and conclude
Substituting \(\angle DAB = \beta\) from Step 2 and \(\angle EAC = \gamma\) from Step 3: \[\beta + \alpha + \gamma = \text{two right angles}\] That is: \[\alpha + \beta + \gamma = 180°\]
Conclusion: The interior angles of any triangle sum to two right angles (180°). The parallel postulate guarantees the construction works for any triangle, so the result holds universally. ∎

More geometric proofs will be added to this collection over time.

Introduction to proof by contradiction

Proof by contradiction (p.b.c.) is often useful when the statement to be proved, often called a theorem or proposition, is one of two forms. If "P" and "Q" are both expressions then p.b.c. might be used if the proposition is:

  • '(Prove) Not P'
  • 'If P then not Q'

Examples include:

  • (Prove) there is no largest positive integer
  • (Prove) there is no smallest positive rational number
  • (Prove) The sum of a rational number and an irrational number is irrational
  • (Prove) if \(a, b > 0\), then \(\sqrt{a + b} \neq \sqrt{a} + \sqrt{b}\)

The approaches are in general: for 'not P' assume 'P' is true then try to deduce a contradiction, for 'If P then not Q', assume 'P AND Q' are true at the same time, then work from either P or Q to a contradiction (this takes a bit of getting used to but the vital first step is converting 'If P then not Q', and 'P AND Q'). So 'Prove there is no largest integer' becomes 'Assume there is a largest integer'. 'Prove if we add a rational number to an irrational number then the result is irrational' becomes 'Assume adding rational number to an irrational number the result is a rational (not irrational) number'. All of these examples are worked through in detail below.

Available proofs

No largest positive integer

\[\nexists \max \mathbb{Z}^+\]

There does not exist a largest positive integer.

View Proof →
Proof by Contradiction: There is no largest positive integer
Step 1: Assumption
Assume for the sake of contradiction that there exists a largest positive integer. Let's call this largest positive integer \(N\). So \(N\) is a positive integer and \(N \geq n\) for all positive integers \(n\).
Setting up the contradiction
Step 2: Construct a larger integer
Consider the number \(N + 1\). Since \(N\) is a positive integer, and 1 is a positive integer: \[N + 1 \text{ is also a positive integer}\] Furthermore: \[N + 1 > N\]
The integers are closed under addition, and adding 1 increases the value
Step 3: Derive Contradiction
We have found that \(N + 1\) is a positive integer and \(N + 1 > N\). But we assumed \(N\) was the largest positive integer, meaning \(N \geq n\) for all positive integers \(n\). Since \(N + 1\) is a positive integer, we must have \(N \geq N + 1\). But we also showed \(N + 1 > N\), which means \(N < N + 1\). We cannot have both \(N \geq N + 1\) and \(N < N + 1\). This is a contradiction!
A number cannot be both greater than or equal to and less than another number
Conclusion: Our assumption that there exists a largest positive integer must be false. Therefore, there is no largest positive integer. ∎

No smallest positive rational

\[\nexists \min\{r \in \mathbb{Q} : r > 0\}\]

There does not exist a smallest positive rational number.

View Proof →
Proof by Contradiction: There is no smallest positive rational number
Step 1: Assumption
Assume for the sake of contradiction that there exists a smallest positive rational number. Let's call this smallest positive rational number \(r\). So \(r > 0\) and \(r \leq s\) for all positive rational numbers \(s\).
Setting up the contradiction
Step 2: Construct a smaller positive rational
Consider the number \(\frac{r}{2}\). Since \(r\) is a positive rational number:
  • \(r > 0\), so \(\frac{r}{2} > 0\) (positive number divided by 2 is positive)
  • \(r\) is rational, so \(\frac{r}{2}\) is rational (rationals are closed under division by non-zero rationals)
  • \(\frac{r}{2} < r\) (since \(\frac{r}{2} = \frac{1}{2} \cdot r\) and \(\frac{1}{2} < 1\))
Therefore, \(\frac{r}{2}\) is a positive rational number and \(\frac{r}{2} < r\).
Division by 2 preserves rationality and positivity while decreasing the value
Step 3: Derive Contradiction
We have found that \(\frac{r}{2}\) is a positive rational number and \(\frac{r}{2} < r\). But we assumed \(r\) was the smallest positive rational number, meaning \(r \leq s\) for all positive rational numbers \(s\). Since \(\frac{r}{2}\) is a positive rational number, we must have \(r \leq \frac{r}{2}\). But we also showed \(\frac{r}{2} < r\), which means \(r > \frac{r}{2}\). We cannot have both \(r \leq \frac{r}{2}\) and \(r > \frac{r}{2}\). This is a contradiction!
A number cannot be both less than or equal to and greater than another number
Alternative Construction
Note: We could also have used \(\frac{r}{10}\) or \(\frac{r}{n}\) for any integer \(n > 1\). This shows that between 0 and any positive rational number, we can always find infinitely many other positive rational numbers.
The rational numbers are dense in the real numbers
Conclusion: Our assumption that there exists a smallest positive rational number must be false. Therefore, there is no smallest positive rational number. ∎

Cube implies even

\[n^3 \text{ even} \Rightarrow n \text{ even}\]

If n³ is even then n is even.

Proof by Contradiction: If n³ is even then n is even
Step 1: Assumption
Assume for the sake of contradiction that \(n^3\) is even but \(n\) is odd. If \(n\) is odd, then \(n = 2k + 1\) for some integer \(k\).
Setting up the contradiction
Step 2: Calculate n³
Cube the expression for \(n\): \[n^3 = (2k + 1)^3\] \[= (2k + 1)(2k + 1)(2k + 1)\] \[= (2k + 1)(4k^2 + 4k + 1)\] \[= 8k^3 + 12k^2 + 6k + 1\] \[= 2(4k^3 + 6k^2 + 3k) + 1\]
Expanding using binomial theorem or direct multiplication
Step 3: Derive Contradiction
From Step 2, we have: \[n^3 = 2(4k^3 + 6k^2 + 3k) + 1 = 2m + 1\] where \(m = 4k^3 + 6k^2 + 3k\) is an integer. This shows that \(n^3\) is odd (of the form \(2m + 1\)). But we assumed \(n^3\) is even. This is a contradiction!
An odd number cannot be even
Conclusion: Our assumption that \(n\) is odd must be false. Therefore, if \(n^3\) is even, then \(n\) must be even. ∎

Sum odd implies component odd

\[p + q \text{ odd} \Rightarrow p \text{ odd or } q \text{ odd}\]

If p + q is odd then at least one of p or q is odd.

Proof by Contradiction: If p + q is odd then at least one of p or q is odd
Step 1: Assumption
Assume for the sake of contradiction that \(p + q\) is odd but both \(p\) and \(q\) are even. If \(p\) is even and \(q\) is even, then: \[p = 2m \text{ for some integer } m\] \[q = 2n \text{ for some integer } n\]
Setting up the contradiction by assuming the negation
Step 2: Calculate p + q
Add \(p\) and \(q\): \[p + q = 2m + 2n = 2(m + n)\] Since \(m + n\) is an integer, \(p + q = 2(m + n)\) is even.
Sum of two even numbers is even
Step 3: Derive Contradiction
We have shown that \(p + q\) is even. But we assumed that \(p + q\) is odd. This is a contradiction, as a number cannot be both even and odd.
A number has unique parity
Conclusion: Our assumption that both \(p\) and \(q\) are even must be false. Therefore, if \(p + q\) is odd, then at least one of \(p\) or \(q\) must be odd. ∎

Parity lemma

\[k^2 \text{ even} \Rightarrow k \text{ even}, \quad k \in \mathbb{Z}\]

The following property is a key part of the proof of the irrationality of \(\sqrt{2}\), but it is usually glossed over. It is covered here, with two different proof approaches, as a prelude to that famous proof. Although this is a proof about integers, it is an important proof about \(\sqrt{2}\), a real number.

Theorem. Let \(k \in \mathbb{Z}\). If \(k^2\) is even then \(k\) is even.

Proof 1 — Contraposition

Proof by Contraposition: If \(k\) is odd then \(k^2\) is odd
Strategy
To prove \(k^2 \text{ even} \Rightarrow k \text{ even}\), we instead prove the contrapositive: \[k \text{ odd} \Rightarrow k^2 \text{ odd}\] These two statements are logically equivalent.
A statement \(P \Rightarrow Q\) is logically equivalent to its contrapositive \(\neg Q \Rightarrow \neg P\)
Step 1: Assume \(k\) is odd
Since \(k\) is odd, there exists an integer \(m\) such that: \[k = 2m + 1\]
Definition of an odd integer
Step 2: Compute \(k^2\)
\[k^2 = (2m+1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1\] Let \(n = 2m^2 + 2m\). Since \(m \in \mathbb{Z}\), we have \(n \in \mathbb{Z}\), so: \[k^2 = 2n + 1\]
Expanding and factoring; integers are closed under addition and multiplication
Step 3: Conclude \(k^2\) is odd
Since \(k^2 = 2n + 1\) for some integer \(n\), by definition \(k^2\) is odd.
Definition of an odd integer
Conclusion: We have shown \(k \text{ odd} \Rightarrow k^2 \text{ odd}\). By contraposition, \(k^2 \text{ even} \Rightarrow k \text{ even}\). ∎

Proof 2 — Contradiction

Proof by Contradiction: Let \(k \in \mathbb{Z}\). If \(k^2\) is even then \(k\) is even.
Step 1: Assumption
Assume for the sake of contradiction that \(k^2\) is even but \(k\) is not even, i.e. \(k\) is odd.

Since \(k\) is odd, there exists an integer \(m\) such that: \[k = 2m + 1\]
We assume the hypothesis (\(k^2\) even) and the negation of the conclusion (\(k\) odd) simultaneously
Step 2: Compute \(k^2\)
\[k^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1\] Let \(n = 2m^2 + 2m \in \mathbb{Z}\), so: \[k^2 = 2n + 1\]
Expanding; integers are closed under addition and multiplication
Step 3: Derive a contradiction
From Step 2, \(k^2 = 2n + 1\), which means \(k^2\) is odd.

But we assumed \(k^2\) is even. A number cannot be both even and odd — this is a contradiction.
Every integer is either even or odd, but not both
Conclusion: The assumption that \(k\) is odd must be false. Therefore, if \(k^2\) is even, then \(k\) is even. ∎

The irrationality of \(\sqrt{2}\)

\[\sqrt{2} \notin \mathbb{Q}\]

This is the classic proof that has a long heritage. However, in my opinion it is introduced far too early in the study of proof, before more straightforward contradiction proofs have been understood, and an important detail, the parity lemma, is often glossed over. Remember on the number theory page there are different types of 'basic' numbers. We can think of numbers as used for counting or measuring things — different activities, but all relate to numbers. An idea from Ancient mathematics (maybe Arabic, Greek, Indian or other) is that every number corresponds to a point or length on a straight line. There is a type of number, the 'real' number (tricky to define rigorously), which we can think of as a set or collection of numbers that in a sense 'contains' the rational numbers but 'other' numbers too. These 'other' numbers, the 'irrational' numbers, were famously (allegedly?) rejected by the Ancient Greek mathematicians and philosophers — just search for the stories about this. Back to the maths. The purpose of this proof is to show that the number 2 has a square root that can be shown to 'exist' (the length of the hypotenuse of a right-angled triangle with two sides equal to 1), but \(\sqrt{2}\) can be shown to not be rational. Therefore, because \(\sqrt{2}\) 'exists', it must be a different kind of number — an 'irrational number'.

Proof: \(\sqrt{2}\) is irrational, i.e. \(\sqrt{2} \notin \mathbb{Q}\)
⚡ Proof by Contradiction — We assume the opposite of what we want to prove and derive a logical impossibility. The contradiction shows the assumption must be false.
Step 1: Assume (for contradiction) that \(\sqrt{2}\) is rational
Proof by contradiction in action: We assume the negation of our goal — that \(\sqrt{2}\) is rational — and aim to reach a contradiction.
By definition of a rational number, there exist integers \(p, q \in \mathbb{Z}\) with \(q \ne 0\) such that: \[\sqrt{2} = \frac{p}{q}\] Furthermore, we may assume this fraction is in its lowest terms, meaning \(p\) and \(q\) share no common factors — i.e. \(\gcd(p, q) = 1\).
Every rational number can be written as a fraction in lowest terms
Step 2: Square both sides
Squaring both sides of \(\sqrt{2} = \dfrac{p}{q}\): \[2 = \frac{p^2}{q^2}\] Multiplying both sides by \(q^2\): \[p^2 = 2q^2\] Since the right-hand side is \(2 \times (\text{integer})\), we conclude that \(p^2\) is even.
Algebraic manipulation; \(q \ne 0\) so multiplication is valid
Step 3: Conclude that \(p\) is even
We have shown \(p^2\) is even. We now need to conclude that \(p\) itself is even.
🔑 Parity Lemma applied here: The parity lemma states that if \(k^2\) is even then \(k\) is even (for \(k \in \mathbb{Z}\)). Applying this with \(k = p\): since \(p^2\) is even, it follows that \(p\) is even.
See the Parity Lemma proof card above for the full proof of this step.
Therefore there exists an integer \(m\) such that: \[p = 2m\]
Parity Lemma: \(k^2 \text{ even} \Rightarrow k \text{ even}\)
Step 4: Show that \(q\) is also even
Substitute \(p = 2m\) into \(p^2 = 2q^2\): \[(2m)^2 = 2q^2\] \[4m^2 = 2q^2\] \[q^2 = 2m^2\] So \(q^2\) is even (it equals \(2 \times m^2\)).
🔑 Parity Lemma applied again: Applying the parity lemma with \(k = q\): since \(q^2\) is even, it follows that \(q\) is even.
Therefore \(q\) is even.
Parity Lemma applied a second time: \(q^2 \text{ even} \Rightarrow q \text{ even}\)
Step 5: Derive the contradiction
Proof by contradiction — the contradiction arrives: We now have everything needed to reach the impossibility.
We have shown that both \(p\) and \(q\) are even — meaning both are divisible by 2, so \(\gcd(p,q) \geq 2\).

But in Step 1 we assumed that \(\dfrac{p}{q}\) was in lowest terms, meaning \(\gcd(p, q) = 1\).

We have \(\gcd(p,q) \geq 2\) and \(\gcd(p,q) = 1\) simultaneously — this is a contradiction.
A fraction in lowest terms cannot have both numerator and denominator divisible by 2
Conclusion: Our assumption (from Step 1) that \(\sqrt{2} \in \mathbb{Q}\) must be false. Therefore \(\sqrt{2}\) is irrational, i.e. \(\sqrt{2} \notin \mathbb{Q}\). ∎

Uniqueness of prime factorization of integers (Fundamental theorem of arithmetic)

\[\text{Every integer } n \geq 2 \text{ has a unique prime factorization (up to order)}\]

Every integer greater than 1 can be written as a product of prime numbers, and this factorization is unique up to the order of the factors.

Proof: Uniqueness of prime factorization (Fundamental Theorem of Arithmetic)
⚡ Proof by Contradiction — We assume a smallest integer with two distinct prime factorizations exists, then derive a logical impossibility.
Note on structure: The theorem has two parts: existence (every integer \(\geq 2\) has some prime factorization) and uniqueness (there is only one). Existence follows by strong induction and is straightforward; the proof here focuses on the uniqueness part, which is the deeper result.
Preliminary: Euclid's Lemma
The uniqueness argument relies on a key lemma:
Euclid's Lemma: If a prime \(p\) divides a product \(ab\) (where \(a, b \in \mathbb{Z}\)), then \(p \mid a\) or \(p \mid b\) (or both).
By induction this extends to products of any finite length: if \(p\) is prime and \(p \mid a_1 a_2 \cdots a_k\), then \(p \mid a_i\) for at least one \(i\).

In particular, if \(p\) and \(q\) are both prime and \(p \mid q\), then since \(q\) has no divisors other than \(1\) and itself, we must have \(p = q\).
Follows from the fact that \(\gcd(p, a) = 1\) whenever prime \(p\) does not divide \(a\), together with Bézout's identity
Step 1: Assume (for contradiction) that uniqueness fails
Proof by contradiction in action: We assume there exists at least one integer with two genuinely different prime factorizations.
Let \(S\) be the set of all integers \(\geq 2\) that have more than one distinct prime factorization. Assume for contradiction that \(S\) is non-empty.

By the well-ordering principle (every non-empty set of positive integers has a least element), \(S\) has a smallest element; call it \(n\).

So \(n\) has (at least) two different prime factorizations: \[n = p_1\, p_2 \cdots p_r = q_1\, q_2 \cdots q_s\] where all \(p_i\) and \(q_j\) are prime. The two factorizations are genuinely different — they are not merely the same primes written in a different order.
Well-ordering principle: every non-empty subset of \(\mathbb{Z}^+\) has a least element
Step 2: No \(p_i\) equals any \(q_j\)
Suppose some \(p_i = q_j\). Cancel that common prime from both sides: \[\frac{n}{p_i} = p_1 \cdots \hat{p}_i \cdots p_r = q_1 \cdots \hat{q}_j \cdots q_s\] (where \(\hat{\phantom{x}}\) denotes omission). Then \(\dfrac{n}{p_i} < n\) is an integer \(\geq 2\) with two distinct factorizations — contradicting the minimality of \(n\).

Therefore no prime on the left equals any prime on the right: the sets \(\{p_1,\ldots,p_r\}\) and \(\{q_1,\ldots,q_s\}\) are entirely disjoint.
\(n\) was chosen as the smallest counter-example, so any proper factor of \(n\) must have a unique factorization
Step 3: Apply Euclid's Lemma to reach a contradiction
Consider the prime \(p_1\). Since \[p_1 \mid n = q_1\, q_2 \cdots q_s\] Euclid's Lemma tells us that \(p_1\) must divide at least one of the \(q_j\).

Say \(p_1 \mid q_j\). But \(q_j\) is prime, so its only divisors are \(1\) and \(q_j\) itself. Since \(p_1 > 1\), we must have \(p_1 = q_j\).
The contradiction arrives: We have just shown \(p_1 = q_j\) for some \(j\). But Step 2 established that no \(p_i\) equals any \(q_j\). This is a contradiction.
Euclid's Lemma: prime \(p \mid a_1 a_2 \cdots a_k \Rightarrow p \mid a_i\) for some \(i\)
Conclusion: The assumption that \(S\) is non-empty leads to a contradiction. Therefore \(S\) is empty: every integer \(n \geq 2\) has a unique prime factorization up to the order of the factors. ∎

Infinitude of primes

\[\text{There are infinitely many primes}\]

Euclid's proof that the set of prime numbers is infinite.

Proof: There are infinitely many primes
⚡ Proof by Contradiction — We assume the set of primes is finite and construct a number that cannot be divisible by any of them, giving a contradiction.
Step 1: Assume (for contradiction) there are finitely many primes
Proof by contradiction in action: We assume the negation of our goal — that the set of all primes is finite — and aim to reach a contradiction.
Suppose there are only finitely many primes. List them all as: \[p_1,\ p_2,\ p_3,\ \ldots,\ p_k\] This list is assumed to be complete — every prime appears somewhere in it.
If the set of primes is finite it can be written as an exhaustive list
Step 2: Construct a new number \(N\)
Define: \[N = p_1\, p_2\, p_3 \cdots p_k + 1\] That is, \(N\) is the product of every prime on our list, plus one. Since \(p_1 \geq 2\), we have \(N \geq 3\), so \(N\) is an integer greater than 1.
\(N\) is well-defined because the list is finite
Step 3: \(N\) is not divisible by any prime on the list
Take any prime \(p_i\) from the list. Since \(p_i\) divides the product \(p_1 p_2 \cdots p_k\), we have: \[N = p_1 p_2 \cdots p_k + 1 \equiv 0 + 1 \equiv 1 \pmod{p_i}\] So the remainder when \(N\) is divided by \(p_i\) is \(1\), not \(0\). Therefore \(p_i \nmid N\).

This holds for every \(p_i\) on the list, so no prime in our list divides \(N\).
If \(p \mid a\) and \(p \mid b\) then \(p \mid (a - b)\); here \(p_i \mid p_1 p_2 \cdots p_k\) but \(p_i \nmid 1\)
Step 4: Derive the contradiction
The contradiction arrives: We now combine two facts that cannot both be true.
By the Fundamental Theorem of Arithmetic, every integer \(\geq 2\) has at least one prime factor. Since \(N \geq 3\), \(N\) must be divisible by some prime \(q\).

But Step 3 shows \(N\) is not divisible by any prime on our list \(p_1, \ldots, p_k\). So \(q\) is a prime that does not appear on the list.

This contradicts our assumption that the list was complete — containing every prime.
Every integer \(\geq 2\) has a prime factor (from the FTA); yet \(N\)'s prime factor is not on our supposedly exhaustive list
Conclusion: The assumption that there are finitely many primes leads to a contradiction. Therefore the set of prime numbers is infinite. ∎

More proof by contradiction examples will be added to this collection over time.

Learning resources

This page provides a curated collection of resources to help you develop your mathematical proof skills. Whether you're just starting out or looking to deepen your understanding, these materials offer various approaches to learning proof techniques.

Recommended resources

Below are some excellent resources for learning mathematical proof. These materials cover fundamental concepts and provide practical guidance for developing your proof-writing skills.

Online learning materials

Long Form Math - Free Online Proofs Book

A comprehensive free resource covering proof techniques and mathematical reasoning.

https://longformmath.com/proofs-book/

Long Form Math YouTube Channel

Video tutorials and explanations of mathematical proofs and concepts.

https://www.youtube.com/@LongFormMath

Recommended textbooks

How to Read and Do Proofs by Daniel Solow

An excellent introduction to mathematical proof techniques. Consider finding a second-hand copy to save money.

Amazon UK Link

Daniel Solow - Video Presentation

Watch the author present key concepts from his book on proof techniques.

YouTube Video

More resource recommendations will be added to this page over time.