Proofs — Discrete Mathematics

Overview

Proofs are at the core of any branch of mathematics.
Proofs of correctness and complexity motivate the implementation and modification of algorithms.
For this reason, proving is a necessary skill in computer science.
You will learn about the types of proof and strategies typical of discrete mathematics: direct, contraposition, contradiction, cases, existence and uniqueness.

Python / SymPy — imports (run once) from sympy import symbols, Rational, sqrt, simplify, Eq, S, isprime, primerange from sympy.logic.inference import satisfiable from sympy.abc import x, y, z from fractions import Fraction import math

2 / 13

Statements

The vocabulary of proofs.

Proposition	A mathematical statement.
Axiom (postulate)	A proposition regarded as self-evident without proof.
Conjecture (hypothesis)	An unproven proposition that is consistent with current data.
Proof	A rigorous mathematical explanation demonstrating that a proposition is true.
Theorem	A proposition that was proven true by accepted mathematical operations and arguments.
Lemma	A short theorem used in proving a larger theorem.
Corollary	A statement that follows almost immediately from a theorem.

A proof is built from axioms, previously proven theorems, and rules of inference (covered in the Logic lesson on inference).

3 / 13

Direct Proof

In the proposition $p \Rightarrow q$, assume $p$ is true, then derive $q$ step by step (this is modus ponens).

Example — the product of two rationals is rational

Let $x, y \in \mathbb{Q}$. Write $x = \dfrac{a}{b}$, $y = \dfrac{c}{d}$ with $b, d \neq 0$. Then:

$x \cdot y \;=\; \dfrac{a}{b} \cdot \dfrac{c}{d} \;=\; \dfrac{ac}{bd}$ where $bd \neq 0$, therefore rational. $\square$

Python — sanity check from fractions import Fraction x = Fraction(3, 7) y = Fraction(5, 2) print(x * y) # 15/14 print(isinstance(x * y, Fraction)) # True

SymPy from sympy import Rational, simplify x = Rational(3, 7) y = Rational(5, 2) z = simplify(x * y) print(z, z.is_rational) # 15/14 True

Another classic — sum of two even numbers is even

If $a = 2k$ and $b = 2m$ with $k, m \in \mathbb{Z}$, then $a + b = 2(k + m)$ is even. $\square$

4 / 13

Proof by Contraposition

$p \Rightarrow q$ is logically equivalent to its contrapositive $\neg q \Rightarrow \neg p$.

So we assume $q$ is false and derive that $p$ is false.

Example — if $ab < 0$ then $a < 0$ or $b < 0$

Direct statement: $\;ab < 0 \;\Rightarrow\; (a < 0) \vee (b < 0)$.
Contrapositive: $\;\neg(a < 0 \vee b < 0) \;\Rightarrow\; \neg(ab < 0)$.
Simplify: $\;(a \geq 0) \wedge (b \geq 0) \;\Rightarrow\; ab \geq 0$.

As a rule of arithmetic, the product of two non-negative numbers is non-negative. $\square$

Python — empirical check on the contrapositive import itertools for a, b in itertools.product(range(0, 10), repeat=2): # a,b ≥ 0 assert a * b >= 0 print("Contrapositive holds on the tested grid ✓")

5 / 13

Proof by Contradiction

To prove a proposition $p$, assume $\neg p$ and reach a contradiction (something obviously false). That forces $p$ to be true.

Example — Euclid: the set of primes is infinite

Assume the set of primes is finite: $L = \{p_1, p_2, \dots, p_n\}$.
Consider $q = 1 + \displaystyle\prod_{i=1}^{n} p_i$.
$q$ is larger than $p_n$ and is not divisible by any $p_i$ (it leaves remainder 1).
So $q$ is prime (or has a prime factor not in $L$). Contradiction: $q \notin L$.

$\therefore$ The set of primes is infinite. $\square$

Python — Euclid construction for small n from math import prod from sympy import isprime, primerange for n in range(1, 8): primes_n = list(primerange(2, [2, 3, 5, 7, 11, 13, 17, 19, 23][n])) q = 1 + prod(primes_n) print(f"n={n} primes={primes_n} q={q} prime? {isprime(q)}")

Famous: the classical proof that $\sqrt{2} \notin \mathbb{Q}$ is also a proof by contradiction.

6 / 13

Proof by Cases (Exhaustion)

Divide the statement into a finite list of mutually-exhaustive cases, then prove it in each one.

Example — if $n \in \mathbb{Z}$ is not divisible by 3, then $n^2 - 1$ is divisible by 3

If $n$ is not divisible by 3, then $n = 3k + 1$ or $n = 3k + 2$ for some $k \in \mathbb{Z}$.

Case 1: $n = 3k + 1$

$n^2 - 1 = (3k+1)^2 - 1 = 9k^2 + 6k + 1 - 1 = 3\,(3k^2 + 2k) = 3c$ with $c \in \mathbb{Z}$.

Case 2: $n = 3k + 2$

$n^2 - 1 = (3k+2)^2 - 1 = 9k^2 + 12k + 4 - 1 = 3\,(3k^2 + 4k + 1) = 3c$ with $c \in \mathbb{Z}$.

Thus $n^2 - 1$ is divisible by 3 in both cases. $\square$

Python — verify on a wide range for n in range(-1000, 1001): if n % 3 != 0: assert (n*n - 1) % 3 == 0 print("Verified on n in [-1000, 1000] ✓")

The first proof of the four-colour theorem was a proof by exhaustion with 1834 cases — computer-assisted.

7 / 13

Existence Proofs

To show $\exists x \,P(x)$, it suffices to exhibit an example.

Example — satisfiability of a Boolean formula

Show that $(\neg x \vee y \vee z) \wedge (x \vee \neg y \vee z) \wedge (x \vee y \vee \neg z) \wedge (x \vee y \vee z)$ is satisfiable.

SymPy — find a witness from sympy.abc import x, y, z from sympy.logic.inference import satisfiable from sympy import And, Or, Not f = And(Or(Not(x), y, z), Or(x, Not(y), z), Or(x, y, Not(z)), Or(x, y, z)) print(satisfiable(f)) # {x: True, y: True, z: True} ← a witness assignment

Non-constructive existence proofs are also valid — for example, the pigeonhole principle proves that two people in any city of 1 million have the same number of hairs, without identifying them.

8 / 13

Uniqueness Proofs

Show there is only one object fulfilling the given properties. Standard recipe:

Show existence (at least one object satisfies $P$).
Suppose two such objects exist, $u_1$ and $u_2$, and prove $u_1 = u_2$.

Example — there is only one integer that is both prime and even

Let $p$ be prime. Its only positive divisors are 1 and $p$.
$p$ is also even, so $p$ is divisible by 2. Hence $p \in \{1, p\}$ must contain 2, i.e. $p = 2$.
$\therefore$ $p = 2$ is the unique even prime. $\square$

Python — sanity scan from sympy import isprime even_primes = [n for n in range(2, 1000) if n % 2 == 0 and isprime(n)] print(even_primes) # [2]

9 / 13

Canonical contradiction — $\sqrt{2} \notin \mathbb{Q}$

Assume $\sqrt{2} = \dfrac{p}{q}$ with $p, q \in \mathbb{Z}$, $\gcd(p, q) = 1$.
Then $2 q^2 = p^2$, so $p^2$ is even $\;\Rightarrow\; p$ is even. Write $p = 2k$.
Substituting: $2 q^2 = 4 k^2 \;\Rightarrow\; q^2 = 2 k^2$, so $q$ is also even.
$p$ and $q$ both even contradicts $\gcd(p, q) = 1$.

$\therefore$ $\sqrt{2}$ cannot be written as $p/q$ — it is irrational. $\square$

Python — numerical hint from fractions import Fraction approx = Fraction(1.4142135623730951).limit_denominator(10**6) print(approx) # 1414213/1000000 print(approx ** 2 == 2) # False — no exact rep.

SymPy — exact from sympy import sqrt, Rational print(sqrt(2).is_rational) # False print((sqrt(2))**2 == 2) # True

10 / 13

Strategies

Good practice guidelines for proofs:

Looking forward
- List the facts given and their definitions, to assess what knowledge you have access to.
- Construct your proof using this knowledge.
Looking backward
- Simplify or decompose the concluding statement.
- Search for correspondence between the initial statement and the concluding statement.
Finding examples
- Find examples to progressively generalize the patterns observed.
- Search for counterexamples — one counterexample disproves a universal claim.

In Python, "finding examples" is often a one-liner with itertools or a SymPy satisfiable call — extremely useful for conjecturing.

11 / 13

Summary

The types of proofs are direct, by contraposition, by contradiction and by cases.
Some propositions allow for existence or uniqueness proofs.
When proving, consider looking forward, backward, and for examples / counterexamples.
One important type of proof — mathematical induction — is so central to discrete mathematics that it has its own lesson.

Python — key tools for this lesson from fractions import Fraction import itertools, math from sympy import (symbols, Rational, sqrt, simplify, Eq, S, isprime, primerange, And, Or, Not) from sympy.logic.inference import satisfiable

12 / 13

Quick reference — proof patterns & Python helpers

Pattern	How to think about it / what helps in Python
Direct: $p \Rightarrow q$	Assume $p$ and chain implications until $q$. `Fraction` / `Rational` for arithmetic statements.
Contraposition: $\neg q \Rightarrow \neg p$	Often simpler than the original. Use when the direct conclusion is a disjunction or a negation.
Contradiction: assume $\neg p$, reach $\bot$	Classic for irrationality, infinitude (Euclid). `sympy.isprime`, `primerange`.
Cases	Split by remainder, parity, sign, etc. Python `for` loop + `assert` for sanity checks.
Existence: exhibit a witness	`satisfiable(expr)` for boolean, `solve` for equations.
Uniqueness: existence + "any two are equal"	Often reduced to "all solutions of an equation coincide" with `sympy.solve`.
Counterexample: disprove $\forall$	One offending value is enough — easy with `itertools.product`.

13 / 13

Introduction to Discrete Mathematics

Overview

Statements

Direct Proof

Example — the product of two rationals is rational

Another classic — sum of two even numbers is even

Proof by Contraposition

Example — if $ab < 0$ then $a < 0$ or $b < 0$

Proof by Contradiction

Example — Euclid: the set of primes is infinite

Proof by Cases (Exhaustion)

Example — if $n \in \mathbb{Z}$ is not divisible by 3, then $n^2 - 1$ is divisible by 3

Existence Proofs

Example — satisfiability of a Boolean formula

Uniqueness Proofs

Example — there is only one integer that is both prime and even

Canonical contradiction — $\sqrt{2} \notin \mathbb{Q}$

Strategies

Summary

Quick reference — proof patterns & Python helpers