MATHEMATICS
JEFFREY STRACHAN
1. Foundations
(1) Extensionality: ∀X∀Y [∀z(z ∈ X ⇐⇒ z ∈ Y ) =⇒ X = Y )]
(2) Pairing ∀X∀Y ∃Z∀W (W ∈ Z ⇐⇒ W = X ∨ W = Y )
(3) Union ∀A∃U ∀x[x ∈ U ⇐⇒ ∃B(x ∈ B ∧ B ∈ A)]
(4) The Power Set ∀A∃P ∀x(x ∈ P ⇐⇒ x ⊆ A)
(5) Infinity ∃A(∅ ∈ A ∧ (∀x)(x ∈ A ⇒ x ∪ {x} ∈ A))
(6) Separation(Specification) Schema ∀A∃B∀x[x ∈ B ⇐⇒ (x ∈ A ∧ (φx))]
(7) Replacement(Image) Schema ∀A[(∀x ∈ A∃!yφ(x, y)) =⇒ ∃B∀y(y ∈
B ⇐⇒ ∃x ∈ Aφ(x, y))]
(8) Regularity(Foundation) ∀A[A ̸= ∅ =⇒ ∃x ∈ A(x ∩ A = ∅)]
(9) Choice ∀A[∀B ∈ A, B ̸= ∅ =⇒ ∃f : A → ∪A, ∀B]
1.1. Construction of The Natural Numbers. There exists at least one set I
such that ∅ ∈ I and for every x ∈ I, the successor S(X) = x ∪ {x}. a set with these
properties is called inductive. We define the natural numbers N as the smallest
inductive set.
Now we derive the Peano Axioms.
(1) Peano Axiom 1: 0 is a natural number.
Proof. Every inductive set contains ∅. N is the intersection of all inductive
sets, so ∅ ∈ N. □
(2) Peano Axiom 2: Every number n has a successor in N
Proof. If n ∈ N then S(n) = n∪{n} ∈ N, since N is inductive and inductive
sets contains successors. □
(3) Peano Axiom 3: 0 is not the successor of any number.
Proof. S(n) = n ∪ {n} is non empty because it contains n, but 0 = ∅ has
no elements, so they cannot be equal. □
(4) Peano Axiom 4: Successor function is injective
S(n) = S(m) =⇒ n = m
Proof. If n ∪ {n} = m ∪ {m} then n ̸= m, WLOG assume n ∈ / m. Then
n∪{n} contains n but m∪{m} does not contain n which is a contradiction.
So n = m □
(5) Peano Axiom 5: If 0 has a property and the property passes to successors
then all naturals have the property.
Proof. Let p ⊆ N satisfy
(a) 0 ∈ P
1
2 JEFFREY STRACHAN
(b) n ∈ P =⇒ S(n) ∈ P
Then P is inductive but N is the smallest inductive set so N ⊆ P . □
1.2. Arithmetic. We define addition as the unique function + : N × N → N
satisfying
(1) Base Step
a+0=a
(2) Recursive step
a + S(b) = S(a + b)
Theorem 1.1. a + 1 = S(a)
Proof. 1 is defined as S(0).
a + 1 = a + S(0) = S(a + 0) = S(a).
□
Theorem 1.2. If a + b = a + c then b = c
Proof. Suppose a = 0, then by definition of addition 0 + b = b and 0 + c = c, so
b = c. Now assume the claim holds for arbitrary a. We want to prove the claim
holds for S(a).
S(a) + b = S(a) + c
by the recursive definition of addition
S(a) + b = S(a + b) and S(a) + c = S(a + c)
Using Peano Axiom 4, we conclude a + b = a + c but by hypothesis b = c.
□
(1) Associativity of Addition:
(a + b) + c = a + (b + c)
Proof. Base case: c = 0. (a+b)+0 = a+b and a+(b+0) = a+b by definition
of addition. So associativity holds for base case. Now suppose it holds for
some c. We want to show (a+b)+S(c) = a+(b+S(c)). Apply the definition
of addition we get (a + b) + S(c) = S((a + b) + c). By induction hypothesis
(a + b) + c = a + (b + c), and by applying recursive definition of addition
twice we get (a+b)+S(c) = S(a+(b+c)) = a+S(b+c) = a+(b+S(c)). □
(2) Commutativity of addition
a+b=b+a
Proof. First we need to show 0+b = b for arbitrary b. Base case: b = 0, then
0 + 0 = 0 by definition. Suppose 0 + b = b, then 0 + S(b) = S(0 + b) = S(b).
Now to prove commutativity, we have Base case: b = 0
a + 0 = 0 by definition
0+a=a
So theorem holds for 0. Now suppose a + b = b + a. We have a + S(b) =
S(a + b) = S(b + a) □
MATHEMATICS 3
Multiplication
(1) Base case
x·0=0
(2) Recursive step
x · S(y) = x · y + x
The integers
An integer is a difference a−b of two naturals. We encode this by pairs (a, b) ∈ N×N
and declare two pairs equivalent when they represent the same difference.
Define a relation on N × N by
(a, b) ∼ (c, d) ⇐⇒ a + d = b + c
Because ∼ is an equivalence relation, it partitions the set N×N into disjoint classes.
Each class contains all the pairs that represent the same integer.
Addition on Z
Define [a, b] + [c, d] = [a + c, b + d].
Multiplication on Z
define [(a, b)] × [(c, d)] := [(ac + bd, ad + bc)]