Interactive mathematical proof collection

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. However, if we are attempting to be rigorous in our proof it helps to know what we are accepting as true and what we can build proofs using logic rules. Knowing that these properties are 'complete' or 'consistent' can involve some really hard work and for our purposes we don't probe to that depth. We can still produce satisfying proofs by knowing and accepting the basic properties.

For each topic I will list some of the preliminary properties used in proofs about these objects.

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).

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

Properties of the algebra of numbers and arithmetic

Click on the link to reveal properties of algebra and arithmetic we apply to numbers without usually thinking about them. These are the basic properties and rules of addition and multiplication we can use in a proof about numbers without thinking about them. The rules can themselves be studied and modified according to needs for other purposes and that is a basic idea in 'abstract algebra', which is beyond our scope in this app.

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.

View Proof →

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\) ∎

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. 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 also 'other' numbers too. These 'other' numbers, the 'irrational' numbers, were famously (allegedly?) rejected by the Ancient Greek mathematicians and philosophers — just google 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 it 'exists', it must be a different kind of number — an 'irrational number'.

View Proof →

Proof by Contradiction: \(\sqrt{2} \notin \mathbb{Q}\)

Step 1: Assumption

Assume for the sake of contradiction that \(\sqrt{2}\) is rational.

Then by definition of a rational number, there exist integers \(p, q \in \mathbb{Z}\) with \(q \neq 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 expressed 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\]

Algebraic manipulation; \(q \neq 0\) so multiplication is valid

Step 3: Conclude \(p\) is even

Since \(p^2 = 2q^2\), the right-hand side is divisible by 2, so \(p^2\) is even.

By the Parity Lemma (proved above): if \(p^2\) is even then \(p\) is even.

Therefore there exists an integer \(m\) such that: \[p = 2m\]

Parity Lemma: \(k^2 \text{ even} \Rightarrow k \text{ even}\)

Step 4: Show \(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. Again by the Parity Lemma, \(q\) is even.

Parity Lemma applied a second time: \(q^2 \text{ even} \Rightarrow q \text{ even}\)

Step 5: Derive a contradiction

We have shown that both \(p\) and \(q\) are even, meaning both are divisible by 2.

But this contradicts our assumption that \(\dfrac{p}{q}\) was in lowest terms, i.e. that \(\gcd(p, q) = 1\).

If both \(p\) and \(q\) are divisible by 2 then \(\gcd(p, q) \geq 2 \neq 1\). This is a contradiction.

A fraction in lowest terms cannot have both numerator and denominator sharing a common factor

Conclusion: Our assumption that \(\sqrt{2} \in \mathbb{Q}\) must be false. Therefore \(\sqrt{2}\) is irrational, i.e. \(\sqrt{2} \notin \mathbb{Q}\). ∎

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.

View Proof →

Square of a Difference

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

Expansion of the square of a binomial difference.

View Proof →

Difference of Cubes

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

Factorization of the difference between two perfect cubes.

View Proof →

Binomial Theorem (n=3)

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

Cubic expansion using the binomial theorem.

View Proof →

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 \text{ for } a > 0\]

Given a is a positive real number, prove that a + 1/a ≥ 2.

View Proof →

Proof: Sum and Reciprocal Inequality

Method 1: Algebraic Manipulation

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\] 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, b, x, y \in \mathbb{R}\). Prove if \(x > y\) then \(a + x > a + y\).

View Proof →

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}\]

The arithmetic mean is greater than or equal to the geometric mean.

Coming Soon

Cauchy-Schwarz Inequality

\[(ac + bd)^2 \leq (a^2 + b^2)(c^2 + d^2)\]

Fundamental inequality with applications in many areas of mathematics.

Coming Soon

Triangle Inequality

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

The absolute value of a sum is at most the sum of absolute values.

Coming Soon

Bernoulli's Inequality

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

For x ≥ -1 and n a positive integer.

Coming Soon

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

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: Number systems →

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

Fundamental properties of integers

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. However, for proofs we ultimately need to state what rules or properties are so basic that we don't question them but accept them as correct and use these properties in proofs. The basic properties of integers 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 integers you can only use these rules or properties or any properties built from them. In normal life we don't worry about this detail — we just accept and apply the rules of calculation we have been taught.

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\)

So, 0 and 1 play special roles.

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\).

This makes integers an integral domain under addition and multiplication.

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.
They are discrete — there are no integers between consecutive numbers such as 2 and 3.

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.

View Proof →

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 modulo 9

\[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.

View Proof →

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

Real numbers include all 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

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

View Proof →

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

View Proof →

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 √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 √2 can be shown to not be rational. Therefore, because √2 'exists', it must be a different kind of number — an 'irrational number'.

View Proof →

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}\). ∎

More real number proofs 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.

In this section, we explore fundamental geometric theorems and their proofs, building from basic axioms and definitions to more complex results. These proofs demonstrate the deductive nature of mathematics and the power of logical reasoning in establishing mathematical truths.

Available Proofs

Pythagorean Theorem

\[a^2 + b^2 = c^2\]

In a right triangle, the square of the hypotenuse equals the sum of squares of the other two sides.

Coming Soon

Sum of Triangle Angles

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

The sum of the interior angles of any triangle equals 180 degrees.

Coming Soon

Vertical Angles Theorem

\[\angle AOC = \angle BOD\]

Vertical angles formed by two intersecting lines are congruent.

Coming Soon

Parallel Lines and Transversals

\[\text{Alternate interior angles are equal}\]

When parallel lines are cut by a transversal, alternate interior angles are congruent.

Coming Soon

Future Proof 5

\[\text{Theorem}\]

Description of the theorem.

Coming Soon

Future Proof 6

\[\text{Theorem}\]

Description of the theorem.

Coming Soon

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.

View Proof →

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.

View Proof →

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. ∎

√2 is irrational

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

Classic proof that the square root of 2 cannot be expressed as a ratio of integers.

Coming Soon

Infinitude of primes

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

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

Coming Soon

Future Proof 5

\[\text{Theorem}\]

Description of the theorem.

Coming Soon

Future Proof 6

\[\text{Theorem}\]

Description of the theorem.

Coming Soon

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

Definition: Mathematical Statement

Preliminary properties

Definitions

Properties of the algebra of numbers and arithmetic

Basic algebra proofs

Square of a Sum

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

Difference of Squares

Sum of Cubes

Square of a Difference

Difference of Cubes

Binomial Theorem (n=3)

Preliminary properties of inequalities

Very useful technique in inequality proof

Inequality proofs

Sum and reciprocal inequality

Adding to an inequality

AM-GM Inequality

Cauchy-Schwarz Inequality

Triangle Inequality

Bernoulli's Inequality

Number theory

Proof by cases

Types of number

Building Complex Definitions

Fundamental properties of integers

Available Proofs

Even Expression

Cube numbers modulo 9

Introduction to Real Number Proofs

Available Proofs

Parity lemma

The irrationality of √2

Introduction to Geometric Proofs

Available Proofs

Pythagorean Theorem

Sum of Triangle Angles

Vertical Angles Theorem

Parallel Lines and Transversals

Future Proof 5

Future Proof 6

Introduction to proof by contradiction

Available proofs

No largest positive integer

No smallest positive rational

Cube implies even

Sum odd implies component odd

√2 is irrational

Infinitude of primes

Future Proof 5

Future Proof 6

Learning Resources

Recommended Resources

Online Learning Materials

Recommended Textbooks