Lemma, Proposition, and Theorems

From a logical point of view, there is no difference between a lemma, proposition,

theorem, or corollary—they are all claims waiting to be proved. However, we use
these terms to suggest different levels of importance and difficulty. A lemma is an
easily proved claim which is helpful for proving other propositions and theorems,
but is usually not particularly interesting in its own right. A proposition is
a statement which is interesting in its own right, while a theorem is a more
important statement than a proposition which says something definitive on the
subject, and often takes more effort to prove than a proposition or lemma. A
corollary is a quick consequence of a proposition or theorem that was proven
recently.
Peano Axioms
1. 0 is a natural number
2. if n is a natural number, then n++ is too.
3. 0 is not the successor of any of any natural number. ie: for any number n,
n++ ̸= 0.
4. Each natural number has a unique successor, ie: if n++ = m++, then
n = m.
5. If for some property P , proprety P (0) is true, then assuming P (n) as true,
we can assert even P (n++) is true, then P is true for each number n.
(Mathematical Induction)
We assume that there exists a set of natural number N for which axioms 1 to 5
hold true.
Proposition: Sequences recursively
Suppose for each natural number n, we have some function f : N → N from
the natural numbers to the natural numbers. Let c be a natural number. Then
we can assign a unique natural number an to each natural number n, such that
a0 = c and an++ = fn (an ) for each natural number n.

Proof (Informal) We use induction, we see that value gives one value to a0 ,
which is never overwritten by axiom 3;
Assuming an is always assigned a unique value, we can deduce that an++ is
always unique aswell, by axiom 4. This closes the induction.
Addition
Let m be a natural number. To add zero to m, we define 0 + m := m. Now
suppose inductively that we have defined how to add n to m. Then we can add
n++ to m by defining (n++) + m := (n + m)++

Lemma: For any natural number n, n + 0 = 0 We use induction: 0 + 0 = 0

is obvious by definition of addition, now assume we have have proved n + 0 = n,
n++ + 0 can be written as (n + 0)++ by definition of addition.

1
As n + 0 = n, (n + 0) + + becomes (n)++ which is n++. This closes the
induction.

Lemma: For any natural numbers n and m, n + (m++) = (n + m)++

We induct on n (keeping m fixed). For base case n = 0, we have:

=⇒ 0+(m++) = (0 + m)++(∵ n = 0) =⇒ m++ = (0 + m)++(∵ ∀n ∈ N, 0+n = 0) =⇒ m++ = m++(∵

This proves the base case, now assume for all natural numbers n, n + m++ =
(n + m)++.
Moving to n++,

=⇒ (n++)+(m++) = ((n++) + m)++ =⇒ (n + (m++)) = ((n + m)++)++(∵ ((n++)+m) = ((n + m)

This closes our induction.

Prove that for each natural number n and m, n + m = m + n We induct

on n (keeping m fixed), and work on the basecase n = 0

=⇒ n+m = m+n =⇒ 0+m = m+0 =⇒ m = m(∵ 0+n = n, n+0 = n(∀n ∈ N))

• By using Addition’s definition and Lemma #1, we can prove the base
case.
Assuming n + m = m + n, we proceed with n++

=⇒ (n++) + m = m + +(n++) =⇒ (n + m)++ = (n + m)++

• By using Addition’s definition and Lemma #2, we can prove the final case.
This closes the induction, and proves the commutative property of addition for
natural numbers.

For any natural numbers a, b and c we have (a + b) + c = a + (b + c) We

induct on c, keeping a and b fixed.
With our base case c = 0

=⇒ (a+b)+c = a+(b+c) =⇒ (a+b)+0 = a+(b+0) =⇒ a+b = a+b(∵ 0+n = n, n+0 = n(∀n ∈ N))(∵)

• By Addition’s definition and Lemma #1, we can prove the base case.

2
Moving on, assuming (a + b) + c = a + (b + c) is true for any natural number c,
we take c++

=⇒ (a+b)+c = a+(b+c) =⇒ (a+b)+(c++) = a+(b+(c++)) =⇒ ((a + b) + c)++ = (a + ((b + c)++)) =

• We use Addition’s definition, Lemma 2, Axiom 4 and Commutative Law.

By inductive step, (a + b) + c = a + (b + c) is true, thus, the induction is closed.
this proves the association of induction for natural numbers.

Let a, b, c be natural numbers such that a + b = a + c. Then we have

b = c. We induct on a (keeping b and c fixed), with base case a = 0

=⇒ a + b = a + c =⇒ 0 + b = 0 + c =⇒ b = c
• By Addition’s definition and Lemma #1, we can prove the base case.
Now assuming a + b = a + c for any natural number a, we take a++

=⇒ (a++) + b = (a++) + c =⇒ (a + b)++ = (a + c)++ =⇒ a + b = a + c

• By Addition’s definition and Axiom #4, we can simply the steps.

Since by inductive step, a + b = a + c is true, this proves the property and closes
the induction. Thus, cancellation law for natural numbers is proved.

Postive Natural numbers

A natural number n is said to be positive iff it is not equal to 0.
(“iff” is shorthand for “if and only if”; see Sect. A.1.)

Proposition: If a is a positive natural number, and b is a natural

number, then a + b is positive (and hence b + a is also, by Commutative
Law of Addition) We induct on b (keeping a fixed). Suppose b = 0, then
a + 0 = a. Since a is already postive, this proves the base case.
Now assuming a + b is postive for any natural number n, we take on b++.
Since a + (b++) can be simplified into (a + b)++ by Lemma #2, which cannot
by 0 by Axiom #3, this closes the induction.

Collary: If a and b are natural numbers such that a + b = 0, then a = 0

and b = 0. We use proof by contradiction. Suppose that a ̸= 0, then a is
postive, and by Proposition #2, a + b is too. However, as a + b = 0, this causes
a contradiction with the definition of positive numbers. Thus, a = 0.

3
Simliary, if b ̸= 0, then b is postive, and thus a + b is too by Proposition #2.
However, as a + b = 0, this causes a contradiction with the definition of positive
numbers. Thus, b = 0.

Let a be a positive number. Then there exists exactly one natural

number b such that b++ = a. We induct on a, with base a = 1.
Since 0++ = 1, the base case clearly has a predecessor. To prove uniqueness, we
rely upon contradiction. Assume that there exists a k where k ̸= 0 and k++ = 1,
now by Axiom 4, if m++ = n++ then m = n. However since k ̸= 0, this leads
to a logical contradiction. Thus, our base case is proved.
Now assuming this property is proved for a, we take on a++. By definition,
a++’s predecessor is a. Now to prove uniqueness, assume that there exists a
k where k ̸= a, and k++ = a + + By Axiom 4, if m++ = n++ then m = n.
However since k is required to not be a, this leads to a logical contradiction.
This closes the induction, and proves that every postive naturl number has a
unique predecessor.

No Number is equal to its sucessor: ie for any number n, n++ ̸= n.

We induct on a = 0, 0 = 0++, this is false as it contradicts Axiom 4 as it states
that 0 is not the successor to any number. Assuming n ̸= n++ as our inductive
hypothesis, we move on.
We use n++, to prove n++ ̸= (n++)++, we use proof by contradiction. suppose
that the opposite is true, that n++ = (n++)++, then by Axiom 4, n = n++.
However as this contradicts our inductive hypothesis (that n ≠ n++), the
opposite must be true, thus n++ ̸= (n++)++. This closes our induction.

For any natural number a, a+d ̸= a for any postive number d. We induct
on d with base case d = 1, then a + 1 =⇒ a + 0++ =⇒ (a + 0) + + =⇒ a++.
Per Lemma 4, ∀a ∈ N, a ̸= a++, this closes our base case. Under inductive
hypothesis that a + d ̸= a for any natural postive number d, we move on.
Taking on d++, we prove a + d++ ̸= a via contradiction. assume that the
opposite is true, a + d++ = a, then by Lemma 1, we can write a + d++ = a + 0,
which then by Cancellation Law, means d + + = 0. However since by Axiom 3,
no number suceeds to 0, this leads to a contrdiction, thus the opposite must be
true, which is a + d++ ̸= a, closing our induction.

Addition property of equality: if a = b, then a + c = b + c. We

induct on c. We observe that a + 0 = b + 0 =⇒ a = b by Lemma #1, proving
our base case. Now assuming this property is true for c = k where k is any
natural number as our inductive hypothesis, we take c++.
a + c++ = b + c++ =⇒ (a + c) + + = (b + c) + + by Lemma 2, which implies
a + c = b + c by Axiom 4. Since a + c = b + c is true when c = k for any natural
number k by inductive hypothesis, this concludes our induction.

4
Ordering
Let n and m be natural numbers. We say that n is greater than or equal to m,
and write n ≥ m or m ≤ n, iff we have n = m + a for some natural number a.
We say that n is strictly greater than m, and write n > m or m < n, iff n ≥ m
and n ̸= m.

Proposition: Let a, b, c be natural numbers. Then

1. (Order is reflexive) a ≥ a
As a = 0 + a, which can be turned into a = a + 0 by commutativity of addition,
there is indeed a n (with n = 0) for which you can write a = a + n. Now by
Ordering’s definition, we can indeed write a ≥ a, this concludes our proof.
2. (Order is transistive) if a ≥ b and b ≥ c, then a ≥ c.
If a ≥ b then a = b + n for some natural number n. Simliary, if b ≥ c then
b = c + m for some natural number m.
Via substituion, we can write a = c + m + n. As now have a natural number
that when combined with c add up to a that being (m + n), we can write a ≥ c
via Ordering’s definition
3. (Order is antisymmetric) If a ≥ b and b ≥ a then a = b
If a ≥ b thenn a = b + n. Simliary, if b ≥ a then b = a + m.
That means a = (a + m) + n, via Association Law, we can wrrite a = a + (m + n)
Since a = a + 0, via Cancellation Law, m + n = 0. By Collary #1, m = 0 and
n = 0.
Thus, a = b + n =⇒ a = b + 0 =⇒ a = b, this concludes our proof.
4. (Addition perserves order) a ≥ b if and only if a + c ≥ b + c.
if a + c ≥ b + c then a + c = (b + c) + n for some natural number n.
Via Commutative Law, this can be written as c + a = (c + b) + n.
Via Associative Law, c + a = c + (b + n). We cancel c via Cancellation Law, thus
writing a = b + n, which can be written as a ≥ b by definition.
Thus a + c ≥ b + c implies a ≥ b.
Simliary, if a ≥ b, then a = b + n for some natural number n. Via Addition
Property of Equality, we can add c to both sides, thus a + c = (b + n) + c.
Via Commutative Law and Associative Law, we can write a + c = (b + c) + n,
which is a + c ≥ b + c by definition.
5. a < b if and only if a++ ≤ b

5
a++ ≤ b means b = (a++) + n means b = (a + n)++.
Via commutative law, we can write b = (n + a) + +. which again implies
b = a + n++. Thus, we have a ≤ b.
Simliarily, a < b implies b = a + n for some postive number n. Since every
postive number has a predecessor, we can write b = a + m++. Which can again
be written as b = (m + a)++, then again as b = (a + m)++.
Which can be written as b = a + m++, which is a ≤ b by definition.
6. a < b if and only if b = a + d for some positive number d.
We use proof by contradiction, if a < b then a ≤ b where a ̸= b by Ordering’s
definition. If a ≤ b then b = a + n for some natural number n.
Suppose that n isnt a postive number, then n = 0 by definition. That implies
b = a + 0, which is b = a by Lemma 1, which is a contradiction, thus n must be
a postive number.
Simliary, if b = a + d then b ≥ a. For b > a to be true, b ̸= a.
We use contradiction, suppose that b = a, then a = a+d by substitution. However
by Lemma 5, ∀d ∈ N+ , a ∈ N, a ̸= a + d, thus this leads to a contradiction, and
the opposite must be true, which is b ̸= a.
Then by Ordering’s definition, b > a.

Trichotomy of order for natural numbers

1. Show that 0 ≤ b for all b, why? we can write b = 0 + b by Addition’s
definition, which is 0 ≤ b by Ordering’s definition
2. If a > b then a++ > b: a > b implies a = b + n, using Addition property
of equality, we add 1 to each side, a++ = (b + n) + 1, via associativity,
we write a++ = b + (n + 1) = b + n++. Since n is postive by definition
(otherwise it would violate Axiom 3 as no number suceeds to 0), we hve
a++ > b.
3. if a = b, then a++ > b: We can write a++ = a + 1, and substituion b in,
which implies a++ = b + 1, that is a++ > b by earlier proposition.

Multiplication
Let m be a natural number. To multiply zero to m, we define 0 × m := 0. Now
suppose inductively that we have defined how to multiply n to m. Then we can
multiply n++ to m by defining (n++) × m := (nÖm) + m.

For any natural number n, n × 0 = 0. We use induction on n, starting with

base case 0. We observe that 0 × 0 = 0 by definition. Now inductively assuming
that n × 0 = n, we try to prove n++ × 0 = 0.

6
Using multiplication’s definition, we can simply this as (n × 0) + 0. Since by our
inductive hypothesis, n × 0 = 0, we can write 0 + 0, which is 0. This closes the
induction.

For any natural number n, n × 1 = n. We use induction on n, with n = 0,

0 × 1 = 0 by definition. Inductively assuming n × 1 = n is true, we take n++.
n++ ∗ 1 =⇒ (n ∗ 1) + 1
By our inductive hypothesis, n × 1 is n, thus n++ × 1 = n + 1
Since n + 1 = n++, this proves the statement, closing the induction.

For any natural numbers n and m, n × m++ = (n × m) + n We use

induction on m, starting with m = 0.
n ∗ m++ implies n × 1 which is n by Lemma 7.
Simliarily, (n × m) + n = (n × 0) + n = n. This closes our base case.
Inductively assuming n × k++ = (n × k) + n for some m = k, we move to k++.
n × (k++)++ = (n × k++) + n.
• Via inductive hypothesis, we can simply n×(k++)++ into (n * k++) + n.
Which can further be simplified into ((n × k) + n) + n
• Via inductive hypothesis, we can simply the right side (n × k++) + n into
((n × k) + n) + n
Since, L.H.S = R.H.S, this closes our induction.

Multiplication is commutative, ie: for any natural numbers n and m,

n × m = m × n. We use induction on n, with base case n = 0.
0 × m = m × 0 = 0 by multiplication’s definition and Lemma 6. This finishes
our base case.
Inductively assuming n × m = m × n we move to n++.
n++ × m = m × n++
• L.H.S can be simplified into (n × m) + m via definition.
• R.H.S can be simplified into (m × n) + m via Lemma 8. Via our inductive
hypothesis, we can write (n × m) + m.
Since, L.H.S = R.H.S, this closes the induction and concludes our proof.

If m and n are postive, then mn is also postive. We use induction on n

(keeping m fixed), starting with n = 1.
m × 1 = m by Lemma 7, since m is postive, this closes our base case.

7
Now inductively assuming mn is postive, we move to n++.
Since m × n++ is (m × n) + n by Lemma 8. Since via inductive hypothesis,
(m × n) is postive, we can say m × n++ is postive since sum of a postive number
with any other natural number is always postive by Proposition 2.
This closes our inductive, and concludes our proof.

If mn = 0, then either m = 0 or n = 0. We use proof by contradiction.

Suppose that both m and n are not 0, then by Lemma 9, mn is postive. However
by definition, mn = 0, a contradiction. Hence, atleast one of m and n must be 0.

For any natural numbers a, b and c: a(b+c) = ac+bc. Since multiplication

is commutative, we only need to show the first identity a(b + c) = ab + ac. We
fix a and b, and use induction on c.
Base case: c = 0. That is, we need to show a(b + 0) = ab + a0.
The left-hand side is a(b + 0) = ab, while the right-hand side is ab + a0 = ab.
Therefore, the base case holds.
Inductive step: Assume that a(b + c) = ab + ac holds for some c. We now
prove that a(b + (c + 1)) = ab + a(c + 1).
The left-hand side is:

a(b + (c + 1)) = a((b + c) + 1) = a(b + c) + a.

The right-hand side is:

ab + a(c + 1) = ab + ac + a.

By the inductive hypothesis, a(b + c) = ab + ac, so we can conclude:

a(b + (c + 1)) = ab + ac + a = ab + a(c + 1).

Thus, the inductive step holds, and by induction, we have shown that a(b + c) =
ab + ac for all c.

For any natural numbers a, b, and c: (a × b) × c = a × (b × c) We induct

on b
• LHS: (a × 0) × c = 0 × c = 0
• RHS: a × (0 × c) = a × 0 = 0
Base case holds, as both sides are equal. Now inductively assuming (a × b) × c =
a × (b × c) where b = k for some natural number k, we move to b++
We now prove: (a × b++) × c = a × (b++ × c)
• LHS: simplified into ((a × b) + a) × c via Lemma 8, and further into
(ab + a) × c, which becomes abc + ac via Distrubutive Law.

8
 • RHS: simplified into a × ((b × c) + c), which becomes a × (bc + c) and
further abc + ac via Distrubutive Law and Commutative Law
Since LHS = RHS, this concludes our induction.

(Multiplication preserves order) If a, b are natural numbers such that

a < b, and c is positive, then ac < bc. Since a < b, we have b = a + d
for some positive d. Multiplying by c and using the distributive law we obtain
bc = ac + dc. Since d is positive, and c is positive, dc is positive, and hence
ac < bc as desired.

Let a, b, c be natural numbers such that ac = bc and c is non-zero. Then

a = b. By the trichotomy of order, we have three cases: a < b, a = b, a > b.
Suppose first that a < b, then by Proposition 5 we have ac < bc, a contradiction.
We can obtain a similar contradiction when a > b. Thus the only possibility is
that a = b, as desired.

Definition of exponentiation
Let m be a natural number. To raise m to the power 0, we define m0 := 1; in
particular, we define 00 := 1. Now suppose recursively that mn has been defined
for some natural number n, then we define mn++ := mn Öm

Prove identity: (a + b)2 = a2 + 2ab + b2 Using definition of exponentiation,

we can expand (a + b)2 as (a + b) × (a + b) × 1. which can be simplified into
(a + b) × (a + b).
Using distrubution law, we can expand this into (a + b)(a) + (a + b)b. Using
distrubtion law again, we can expand this into aa + ab + ba + bb.
Since aa is same as a2 (a2 = a1++ = a1 ×a = a0++ ×a = a0 ×a×a = 1×a×a =
aa), we can write a2 + ab + ba + bb.
A simliar argument can be made for bb, thus we write a2 + ab + ba + b2 .
Now using distrubitive law and commutative law, we can write ab+ba as ab(1+1).
Since 1 + 1 = 2, we can also write ab2, which is 2ab by commutative law.
Therefore, we can write a2 + ab + ba + b2 as a2 + 2ab + b2 , which proves the
identity.