Examinable Proofs Reference

This document consolidates all proofs you should be able to reproduce under exam conditions, organised by topic.

---

Part I: Proofs

1. Irrationality of $\sqrt{2}$

Theorem: $\sqrt{2}$ is irrational.

Proof:

Suppose for contradiction $\sqrt{2} = \frac{p}{q}$ where $\gcd(p, q) = 1$.

Squaring: $2 = \frac{p^2}{q^2}$, so $p^2 = 2q^2$.

Thus $p^2$ is even, so $p$ is even. Write $p = 2k$.

Substituting: $4k^2 = 2q^2$, so $q^2 = 2k^2$.

Thus $q^2$ is even, so $q$ is even.

But $p$ and $q$ both even contradicts $\gcd(p, q) = 1$. $\square$

---

2. Infinitude of Primes (Euclid)

Theorem: There are infinitely many primes.

Proof:

Suppose finitely many primes: $p_1, \ldots, p_n$.

Let $N = p_1 \cdots p_n + 1$.

Since $N > 1$, $N$ has a prime divisor $p$.

If $p = p_i$ for some $i$, then $p \mid p_1 \cdots p_n$ and $p \mid N$, so $p \mid (N - p_1 \cdots p_n) = 1$.

No prime divides 1. Contradiction.

Thus $p$ is not in our list. $\square$

---

3. Fermat’s Little Theorem

Theorem: If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod{p}$.

Proof:

Consider $a, 2a, \ldots, (p-1)a \pmod{p}$.

Non-zeroness: Each $ia \not\equiv 0 \pmod{p}$ since $p \nmid a$ and $p \nmid i$.

Distinctness: If $ia \equiv ja \pmod{p}$, then $p \mid (i-j)a$. By Euclid’s lemma, $p \mid (i-j)$. But $|i-j| < p$, so $i = j$.

Thus $\{a, 2a, \ldots, (p-1)a\}$ = $\{1, 2, \ldots, p-1\} \pmod{p}$.

Taking products: $a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}$.

Since $\gcd((p-1)!, p) = 1$, cancel: $a^{p-1} \equiv 1 \pmod{p}$. $\square$

---

Part II: Sets, Relations, Functions

4. Relational Composition is Associative

Theorem: $(T \circ S) \circ R = T \circ (S \circ R)$.

Proof:

$a((T \circ S) \circ R)d \iff \exists c. aRc \land c(T \circ S)d$ $\iff \exists c, b. aRc \land cSb \land bTd$

$a(T \circ (S \circ R))d \iff \exists b. a(S \circ R)b \land bTd$ $\iff \exists b, c. aRc \land cSb \land bTd$

Both equivalent to $\exists b, c. aRc \land cSb \land bTd$. $\square$

---

5. Identity Laws for Composition

Theorem: $\text{id}_B \circ R = R = R \circ \text{id}_A$.

Proof:

$a(\text{id}_B \circ R)b \iff \exists c. aRc \land c\,\text{id}_B\,b \iff \exists c. aRc \land c = b \iff aRb$.

$a(R \circ \text{id}_A)b \iff \exists c. a\,\text{id}_A\,c \land cRb \iff \exists c. a = c \land cRb \iff aRb$. $\square$

---

6. Reflexive-Transitive Closure is Smallest Preorder

Theorem: $R^{\circ *}$ is the smallest preorder containing $R$.

Proof:

$R^{\circ *}$ is a preorder: reflexive (contains $\text{id}$), transitive (path concatenation).

$R \subseteq R^{\circ *}$: Clear since $R^{\circ 1} = R$.

Smallest: Let $P$ be a preorder with $R \subseteq P$. By induction on $n$: $R^{\circ n} \subseteq P$.

• Base: $\text{id} \subseteq P$ by reflexivity.
• Step: $R^{\circ(n+1)} = R \circ R^{\circ n} \subseteq P \circ P \subseteq P$ by transitivity.

Thus $R^{\circ *} = \bigcup_n R^{\circ n} \subseteq P$. $\square$

---

7. Equivalence Relations $\leftrightarrow$ Partitions Bijection

Theorem: $\Phi : \text{EqRel}(A) \to \text{Part}(A)$ by $\Phi(E) = \{[a]_E : a \in A\}$ is a bijection.

Proof:

Well-defined: Equivalence classes partition $A$ (non-empty by reflexivity, disjoint by transitivity/symmetry, cover by definition).

Inverse: Given partition $P$, define $E = \{(a, b) : \exists B \in P. a, b \in B\}$.

This is an equivalence relation (reflexive: $a$ in unique block; symmetric: trivial; transitive: blocks disjoint).

Inverses: Check $\Phi^{-1}(\Phi(E)) = E$ (elements in same class iff equivalent) and $\Phi(\Phi^{-1}(P)) = P$ (blocks are the equivalence classes). $\square$

---

8. Isomorphisms are Bijective

Theorem: $f : A \to B$ is an isomorphism iff $f$ is bijective.

Proof:

$(\Rightarrow)$: If $f^{-1}$ exists: injective (if $f(a_1) = f(a_2)$, then $a_1 = f^{-1}(f(a_1)) = f^{-1}(f(a_2)) = a_2$); surjective (for $b$, $b = f(f^{-1}(b))$).

$(\Leftarrow)$: Define $f^{-1}(b) =$ the unique $a$ with $f(a) = b$. Verify $f^{-1} \circ f = \text{id}$ and $f \circ f^{-1} = \text{id}$. $\square$

---

9. Sections and Idempotents

Theorem: $(s, r)$ section-retraction pair $\leftrightarrow$ $e = s \circ r$ idempotent.

Proof:

$(\Rightarrow)$: $e \circ e = s \circ r \circ s \circ r = s \circ \text{id} \circ r = s \circ r = e$.

$(\Leftarrow)$: Given idempotent $e$, let $B = \text{Im}(e)$. Define $r(a) = e(a)$, $s(b) = b$ (inclusion). Then $r(s(b)) = e(b) = b$ since $b \in \text{Im}(e)$ means $b = e(a)$ for some $a$. $\square$

---

10. Cantor’s Theorem

Theorem: No surjection $A \twoheadrightarrow \mathcal{P}(A)$ exists.

Proof:

Suppose $e : A \twoheadrightarrow \mathcal{P}(A)$. Define $U = \{x \in A : x \notin e(x)\}$.

Since $e$ surjective, $\exists a. e(a) = U$.

Is $a \in U$?

• If yes: $a \in U \Rightarrow a \notin e(a) = U$. Contradiction.
• If no: $a \notin U \Rightarrow a \in e(a) = U$. Contradiction.

Thus no such $e$ exists. $\square$

---

11. Well-Founded Induction

Theorem: If $(\forall y \prec x. P(y)) \Rightarrow P(x)$ for all $x$, then $\forall x. P(x)$.

Proof:

Suppose $S = \{x : \neg P(x)\} \neq \emptyset$.

By well-foundedness, $S$ has minimal element $m$.

For all $y \prec m$: $y \notin S$, so $P(y)$ holds.

By assumption, $P(m)$ holds, contradicting $m \in S$.

Thus $S = \emptyset$. $\square$

---

Part III: Formal Languages and Automata

12. Rule Induction

Theorem: If $S$ is closed under all rules in $R$, then $X_R \subseteq S$.

Proof:

Induction on derivation height.

Base: Axioms have height 1. Since $S$ closed under rules with no premises, axioms are in $S$.

Step: Derivation of height $n+1$ uses rule $\frac{u_1, \ldots, u_k}{v}$ where each $u_i$ derived by height $\leq n$.

By IH, each $u_i \in S$. Since $S$ closed under the rule, $v \in S$. $\square$

---

13. Subset Construction Correctness

Theorem: $L(\mathcal{P}(M)) = L(M)$.

Proof:

Soundness ($L(\mathcal{P}(M)) \subseteq L(M)$): DFA path $s' \to S_n \cap F \neq \emptyset$. Build NFA path by tracing elements in each $S_i$ back to NFA states. Some $q_f \in S_n \cap F$ reachable from $s$.

Completeness ($L(M) \subseteq L(\mathcal{P}(M))$): NFA path $s \Rightarrow_w q_f$. Track reachable states $S_i$ at each step. $q_f \in S_n$, so $S_n \cap F \neq \emptyset$. $\square$

---

14. Kleene’s Theorem

Theorem: $L$ is regular iff $L = L(R)$ for some regex $R$.

Proof:

Regex $\Rightarrow$ NFA: Inductive construction (Thompson) for $\varepsilon$, $\emptyset$, symbols, union, concat, star. Each preserves language.

NFA $\Rightarrow$ Regex: Region decomposition. Compute $R(q, S, q')$ for paths through regions. Eliminate all states: $L(M) = \bigcup_{q_f \in F} R(s, Q, q_f)$. $\square$

---

15. Pumping Lemma

Theorem: For $L$ regular, $\exists p. \forall w \in L$ with $|w| \geq p$: $w = xyz$ with $|xy| \leq p$, $|y| \geq 1$, and $\forall i. xy^iz \in L$.

Proof:

Let DFA have $n$ states. Set $p = n$.

For $|w| \geq n$: computation visits $n+1$ states. By pigeonhole, some state repeated.

Let $x$ = prefix before loop, $y$ = loop, $z$ = suffix.

• $|xy| \leq n = p$ (loop within first $n$ states)
• $|y| \geq 1$ (loop non-trivial)
• Can repeat or omit loop; stays accepting. $\square$

---

Summary

These 15 proofs form the core of examinable material. Key strategies:

1. Contradiction: Assume negation, derive $\sqrt{2}$, primes, Cantor
2. Induction: Natural numbers, derivation height, state elimination
3. Construction: Explicit bijections, automata constructions
4. Unfolding definitions: Relational composition, closure properties