0 Nonnegative integers

Ⅽopyright © 2025, Gregory G. Smith

Ⅼast Updated: 31 January 2025

Ⅼeopold Kronecker (1823–1891) famously declared that “Ⅾear God The dictum “Ⅾie ganzen Zahlen hat

ambiguously refers to the set ℕ of nonnegative integers or to the

made the whole numbers, all else is the work of man”. This phrase der liebe Gott gemacht, alles andere
ist Ⅿenschenwerk” was allegedly

larger set ℤ of integers, but this chapter focuses exclusively on the

uttered by Kronecker in Berlin in 1886.
Ɪt first appeared in print in the
memorial article: H. Weber, Ⅼeopold
smaller set. Familiar to people of ancient times, it actually took over Kronecker, Ⅿathematische Annalen 43
two millennia to gain a full understanding of these numbers. (1893) 1–25.

0.0 Principle of Ɪnduction

What are nonnegative integers ℕ ∶= {0, 1, 2, … }? To understand this
fundamental set, we examine an axiomatic characterization.

Ⅾefinition 0.0.0. The nonnegative integers are a set ℕ, containing

a distinguished element 0 (called zero), together with a successor
function S∶ ℕ → ℕ satisfying the following three conditions:
The Ɪtalian mathematician Giuseppe
Peano (1858–1932) introduced these

(Ⅽ0) For any element 𝑛 in ℕ, we have S(𝑛) ≠ 0.

axioms in his 1889 treatise titled

(Ⅽ1) The successor function is injective: for any elements 𝑚 and 𝑛

Arithmetices principia, nova methodo

in ℕ, the equation S(𝑚) = S(𝑛) implies that 𝑚 = 𝑛.

exposita.

(Ⅽ2) For any subset 𝒳 ⊆ ℕ such that 0 ∈ 𝒳 and S(𝑥) ∈ 𝒳 for all
𝑥 ∈ 𝒳 , we have 𝒳 = ℕ.

Ɪn set theory, the triple (ℕ, 0, S) is

𝑛 in ℕ has an assigned successor S(𝑛); we have 1 ∶= S(0), 2 ∶= S(1),
The function S captures the essence of counting. Every element

0 ∶= {} = ∅
3 ∶= S(2), … . Ⅽondition (Ⅽ0) asserts that counting starts at 0, and
constructed recursively as

1 ∶= {0} = 0 ∪ {0} = {∅}

2 ∶= {0, 1} = 1 ∪ {1} = {∅, {∅}}
3 ∶= {0, 1, 2} = 2 ∪ {2} = {∅, {∅}, {∅, {∅}}}
(Ⅽ1) asserts that no number repeats during the counting process.
⋮
Ⅿore significantly, Ⅽondition (Ⅽ2) is a set‑theoretic formulation of
the principle of induction. and the successor function 𝑆∶ ℕ → ℕ is
The next result indicates that one may take the Peano axioms as defined by S(𝑛) ∶= 𝑛 ∪ {𝑛}.
the definition of the nonnegative integers.

Theorem 0.0.1. For any set ℕ′ with distinguished element 0′ and a suc‑
cessor function S′ satisfying properties (Ⅽ0) – (Ⅽ2), there exists a unique
bijective map 𝜑∶ ℕ → ℕ′ such that S′ ∘ 𝜑 = 𝜑 ∘ S.

Outline of proof. To prove existence, the map 𝜑∶ ℕ → ℕ′ is defined

recursively by 𝜑(0) = 0′ and 𝜑(S(𝑛)) = S′ (𝜑(𝑛)) for all 𝑛 in ℕ. To
prove uniqueness, consider another map 𝜑′∶ ℕ → ℕ′ with the stated
properties. One shows, by induction, that 𝜑(𝑛) = 𝜑′ (𝑛) for all 𝑛 in
ℕ. By interchanging the roles of ℕ and ℕ′ , one similarly obtains a
map 𝜓∶ ℕ′ → ℕ such that 𝜓(0′ ) = 0 and S ∘ 𝜓 = 𝜓 ∘ S′ . One shows,
again by induction, that 𝜓 ∘ 𝜑 = idℕ and 𝜑 ∘ 𝜓 = idℕ′ . Therefore, the
map 𝜑 is a bijection.

erty of the set ℕ is simply a function 𝑃∶ ℕ → {true, false}. We say that

Ⅽondition (Ⅽ2) may be more familiar in a different form. A prop‑

the property 𝑃(𝑛) holds for some nonnegative integer 𝑛 if and only
if 𝑃(𝑛) = true. The common form of induction is as follows.

Theorem 0.0.2. To show that a property 𝑃(𝑛) holds for any nonnegative
integer 𝑛, it is enough to prove
6 Nonnegative Ɪntegers Ⅽopyright © 2025 by Gregory G. Smith

Base case: 𝑃(0) holds, and

Ɪnduction step: for any nonnegative integer 𝑛, the assumption that 𝑃(𝑛) 21
2019
holds implies that the property 𝑃(S(𝑛)) = 𝑃(𝑛 + 1) holds.
18 17 16
15 14
1312
11
Proof. Each property 𝑃 satisfied by (some or all of) the elements in
10
9
7 8
ℕ corresponds to a subset of ℕ, namely 𝒳 ∶= {𝑚 ∈ ℕ | 𝑃(𝑚) holds}.
6
4 5
Ⅽondition (Ⅽ2) establishes that 𝒳 = ℕ.
3
2
1
0
that the base case may not be 0.
The next two problems typify the basic use of induction. Notice

Problem 0.0.3. For any positive integer 𝑛, verify that

Figure 0.1: Ɪnduction is like
𝑛−1
∑ (2𝑗 + 1) = 𝑛2 .
toppling dominoes. Pushing the

𝑗=0
zeroth one is the base case. Each
subsequent domino being

Ɪnductive solution. When 𝑛 = 1, we have 2(0) + 1 = (1)2 , so the base

knocked over by its predecessor is

case holds. Assuming that ∑𝑗=0 (2𝑗 + 1) = (𝑛 − 1)2 , the induction

𝑛−2 the induction step.

step is
𝑛−1
⎧𝑛−2
∑ (2𝑗 + 1) = ⎪ ∑ (2𝑗 + 1)⎪ + ⎧
⎩2(𝑛 − 1) + 1)⎭
⎫ ⎫
𝑗=0 𝑗=0

= (𝑛 − 1)2 + 2(𝑛 − 1) + 1 = ((𝑛 − 1) + 1) = 𝑛2 .

⎩ ⎭
2

Remark 0.0.4. Ⅾespite verifying the correctness of the formula, the

inductive solution to Problem 0.0.3 is unsatisfying. Ɪt feels overly for‑
mal and does not seem to explain the true origins of this equation.
Figure 0.2 suggests a better way to understand this sum. Figure 0.2: Sum of odd integers

Problem 0.0.5. For any nonnegative integer 𝑛 that is greater than

3, prove that 2𝑛 ⩾ 𝑛2 .

Ɪnductive solution. For any integer 𝑛 greater than 1, we first prove, by

induction, that 𝑛2 ⩾ 2. When 𝑛 = 2, we have 22 = 4 > 2, so the base
case holds. Assuming that 𝑛2 − 2 ⩾ 0, the induction step is
(𝑛 + 1)2 − 2 = (𝑛2 + 2𝑛 + 1) − 2 ⩾ 2𝑛 + 1 ⩾ 5 ⩾ 0 .
For any integer 𝑛 such that 𝑛 ⩾ 4, we now prove, via induction on
𝑛, that 2𝑛 ⩾ 𝑛2 . When 𝑛 = 4, we have 24 = 16 = 42 , so the base case
holds. Assuming 2𝑛 − 𝑛2 ⩾ 0, the induction step is
2𝑛+1 − (𝑛 + 1)2 = 2 (2𝑛 ) − 𝑛2 − 2 𝑛 − 1
⩾ 2 (𝑛2 ) − 𝑛2 − 2 𝑛 − 1 = (𝑛 − 1)2 − 2 .

As the first paragraph establishes that (𝑛 − 1)2 − 2 ⩾ 0, we deduce

that 2𝑛+1 − (𝑛 + 1)2 ⩾ 0 as required.
7 Nonnegative Ɪntegers Ⅽopyright © 2025 by Gregory G. Smith

0.1 Peano Arithmetic

How is the set ℕ of nonnegative integers equipped with addition
and multiplication? To define these binary operations, we begin
with a simple observation.

Proposition 0.1.0. For any functions 𝜑∶ ℕ → ℕ and 𝜓∶ ℕ × ℕ → ℕ,

there exists a unique function 𝜃∶ ℕ × ℕ → ℕ such that 𝜃(𝑚, 0) = 𝜑(𝑚)
This technical observation is used

and 𝜃(𝑚, S(𝑛)) = 𝜓(𝜃(𝑚, 𝑛), 𝑚) for all 𝑚 and 𝑛 in ℕ.

only in definitions of addition and
multiplication.

Proof. For each nonnegative integer 𝑚, the principle of induction

determines a function 𝛽𝑚∶ ℕ → ℕ such that 𝛽𝑚 (0) ∶= 𝜑(𝑚) and
𝛽𝑚 (S(𝑛)) ∶= 𝜓(𝛽𝑚 (𝑛), 𝑚) for any nonnegative integer 𝑛. Ⅾefine the
function 𝜃∶ ℕ × ℕ → ℕ by 𝜃(𝑚, 𝑛) ∶= 𝛽𝑚 (𝑛). By construction, the
function 𝜃 satisfies the two conditions. Since the conditions also
specify all the outputs, the function 𝜃 is uniquely determined.

Addition of nonnegative integers arises as a special case.

Ⅾefinition 0.1.1. The unique function 𝛼∶ ℕ × ℕ → ℕ such that

Apply Proposition 0.1.0 when 𝜑 = idℕ
and 𝜓(𝑚, 𝑛) = S(𝑚). Since 1 ∶= S(0),
𝛼(𝑚, 0) = 𝑚 and 𝛼(𝑚, S(𝑛)) = S(𝛼(𝑚, 𝑛)) for all 𝑚 and 𝑛 in ℕ
𝑚 + 1 = 𝑚 + S(0) = S(𝑚 + 0) = S(𝑚)
the definition of addition gives

is called addition and invariably denoted by 𝑚 + 𝑛 ∶= 𝛼(𝑚, 𝑛). for any nonnegative integer 𝑚.

Ⅼemma 0.1.2. For any nonnegative integer 𝑚, we have 0 + 𝑚 = 𝑚. The distinguished element 0 in ℕ is

Proof. Ⅽonsider 𝒳 ∶= {𝑚 ∈ ℕ | 0 + 𝑚 = 𝑚}. The definition of

the additive identity.

addition gives 𝛼(0, 0) = 0 + 0 = 0, so 0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 , the

0 + S(𝑛) = 𝛼(0, S(𝑛)) = S(𝛼(0, 𝑛)) = S(0 + 𝑛) = S(𝑛)

definition of addition implies that

so S(𝑛) ∈ 𝒳 . The principle of induction yields 𝒳 = ℕ.

Ⅼemma 0.1.3. For any nonnegative integers 𝑚 and 𝑛, we have

S(𝑚) + 𝑛 = S(𝑚 + 𝑛) .
Proof. Fix 𝑚 in ℕ and consider 𝒳 ∶= {𝑛 ∈ ℕ | S(𝑚) + 𝑛 = S(𝑚 + 𝑛)}.
The definition of addition gives S(𝑚) + 0 = S(𝑚) = S(𝑚 + 0), so
0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 , the definition of addition also shows that
S(𝑚) + S(𝑛) = S(S(𝑚) + 𝑛) = S(S(𝑚 + 𝑛)) = S(𝑚 + S(𝑛)) ,
so S(𝑛) ∈ 𝒳 . Thus, the principle of induction gives 𝒳 = ℕ.

The definition for multiplication is very similar.

Ⅾefinition 0.1.4. The unique function 𝜇∶ ℕ × ℕ → ℕ such that 𝜑(𝑚) = 0 and 𝜓(𝑚, 𝑛) = 𝑚 + 𝑛. For
Apply Proposition 0.1.0 when

𝜇(𝑚, 0) = 0 and 𝜇(𝑚, S(𝑛)) = 𝜇(𝑚, 𝑛) + 𝑚 for all 𝑚 and 𝑛 in ℕ any nonnegative integer 𝑚, the

is called multiplication and typically denoted by 𝑚 𝑛 ∶= 𝜇(𝑚, 𝑛). 𝑚 1 = 𝑚 0 + 𝑚 = 𝑚. Hence, the

definition of multiplication gives

element 1 ∶= S(0) is the multiplicative

Ⅼemma 0.1.5. For any nonnegative integer 𝑚, we have 0 𝑚 = 0.

Proof. Ⅽonsider the subset 𝒳 ∶= {𝑚 ∈ ℕ | 0 𝑚 = 0}. The definition

identity.

of multiplication implies that (0)(0) = 0, so 0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 ,

that 0 S(𝑛) = 0 𝑛 + 0 = 0 + 0 = 0, so S(𝑛) ∈ 𝒳 . The principle of

the definition of multiplication and the definition of addition show

induction again yields 𝒳 = ℕ.

8 Nonnegative Ɪntegers Ⅽopyright © 2025 by Gregory G. Smith

We now prove the key properties of addition and multiplication.

Theorem 0.1.6. For any nonnegative integers 𝑘, 𝑚, and 𝑛, we have

(𝑘 + 𝑚) + 𝑛 = 𝑘 + (𝑚 + 𝑛) ,
𝑚 + 𝑛 = 𝑛 + 𝑚,
(associativity of addition)

𝑘(𝑚 + 𝑛) = 𝑘 𝑚 + 𝑘 𝑛 ,
(commutativity of addition)

𝑘(𝑚 𝑛) = (𝑘 𝑚)𝑛 ,
(distributivity)

𝑚𝑛 = 𝑛𝑚.
(associativity of multiplication)
(commutativity of multiplication)
Proof. Fix nonnegative integers 𝑘 and 𝑚 and consider the subset
𝒳 ∶= {𝑛 ∈ ℕ | 𝑘 + (𝑚 + 𝑛) = (𝑘 + 𝑚) + 𝑛}. The definition of addition
gives 𝑘 + (𝑚 + 0) = 𝑘 + 𝑚 = (𝑘 + 𝑚) + 0, so 0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 ,

𝑘 + (𝑚 + S(𝑛)) = 𝑘 + S(𝑚 + 𝑛) = S(𝑘 + (𝑚 + 𝑛)) = S((𝑘 + 𝑚) + 𝑛) = (𝑘 + 𝑚) + S(𝑛)

the definition of addition implies that

The principle of induction yields 𝒳 = ℕ.

Fix 𝑚 in ℕ and consider 𝒳 ∶= {𝑛 ∈ ℕ | 𝑚 + 𝑛 = 𝑛 + 𝑚}. The
definition of addition and Ⅼemma 0.1.2 give 𝑚 + 0 = 𝑚 = 0 + 𝑚, so
0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 , Ⅼemma 0.1.3 and the definition of addition
imply that S(𝑛) + 𝑚 = S(𝑛 + 𝑚) = S(𝑚 + 𝑛) = 𝑚 + S(𝑛), so S(𝑛) ∈ 𝒳 .
The principle of induction yields 𝒳 = ℕ.
Fix nonnegative integers 𝑘 and 𝑚 and consider the subset
𝒳 ∶= {𝑛 ∈ ℕ | 𝑘(𝑚 + 𝑛) = 𝑘 𝑚 + 𝑘 𝑛}. The definitions of addition
and multiplication give 𝑘(𝑚 + 0) = 𝑘 𝑚 = 𝑘 𝑚 + 0 = 𝑘 𝑚 + 𝑘 0, so
0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 , the definitions of addition and multiplication

𝑘(𝑚 + S(𝑛)) = 𝑘 S(𝑚 + 𝑛) = 𝑘 (𝑚 + 𝑛) + 𝑘 = (𝑘 𝑚 + 𝑘 𝑛) + 𝑘 = 𝑘 𝑚 + (𝑘 𝑛 + 𝑘) = 𝑘 𝑚 + 𝑘 S(𝑛)

and associativity of addition imply that

so S(𝑛) ∈ 𝒳 . The principle of induction yields 𝒳 = ℕ.

Fix nonnegative integers 𝑘 and 𝑚 and consider the subset
𝒳 ∶= {𝑛 ∈ ℕ | 𝑘(𝑚 𝑛) = (𝑘 𝑚)𝑛}. The definition of multiplication
gives 𝑘(𝑚 0) = 𝑘 0 = 0 = (𝑘 𝑚) 0, so 0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 , the

𝑘(𝑚 S(𝑛)) = 𝑘(𝑚 𝑛 + 𝑚) = 𝑘(𝑚 𝑛) + 𝑘 𝑚 = (𝑘 𝑚)𝑛 + (𝑘 𝑚) = (𝑘 𝑚)(𝑛 + 1) = (𝑘 𝑚) S(𝑛)

definition of multiplication and distributivity imply that

so S(𝑛) ∈ 𝒳 . The principle of induction yields 𝒳 = ℕ.

We claim that S(𝑚) 𝑛 = 𝑚𝑛 + 𝑛 for all 𝑚 and 𝑛 in ℕ. Fix 𝑚 in ℕ
and consider 𝒳 ∶= {𝑛 ∈ ℕ | S(𝑚) 𝑛 = 𝑚𝑛 + 𝑛}. The definitions of Ⅽompare this claim with Ⅼemma 0.1.3.

multiplication and addition give S(𝑚) 0 = 0 = 0 + 0 = 𝑚 0 + 0, so

0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 , the definitions of multiplication and addition,

S(𝑚) S(𝑛) = S(𝑚)𝑛 + S(𝑚) = (𝑚𝑛 + 𝑛) + (𝑚 + 1) = 𝑚𝑛 + 𝑚 + 𝑛 + 1 = 𝑚(𝑛 + 1) + (𝑛 + 1) = 𝑚 S(𝑛) + S(𝑛)

the properties of addition, and distributivity imply that

so S(𝑛) ∈ 𝒳 . Thus, the principle of induction yields 𝒳 = ℕ.

Ⅼastly, fix 𝑚 in ℕ and consider 𝒳 ∶= {𝑛 ∈ ℕ | 𝑚 𝑛 = 𝑛 𝑚}. The
definition of multiplication and Ⅼemma 0.1.5 give 𝑚0 = 0 = 0𝑚, so
0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 , the claim, commutativity of multiplication,

S(𝑛) 𝑚 = 𝑛𝑚 + 𝑚 = 𝑚𝑛 + 𝑚 = 𝑚(𝑛 + 1) = 𝑚 S(𝑛)

and distributivity imply that

so S(𝑛) ∈ 𝒳 . The principle of induction yields 𝒳 = ℕ.

9 Nonnegative Ɪntegers Ⅽopyright © 2025 by Gregory G. Smith

0.2 Well‑Ordering Principle

How are the nonnegative integers ℕ endowed with a total order? We
Ɪn mathematics, the adjective
record another basic feature before describing the canonical binary “canonical” indicates an object that is

Ⅼemma 0.2.0. Ⅼet 𝑛 be a nonzero nonnegative integer. For any 𝑚 in ℕ,

relation on nonnegative integers. prescribed by, in conformity with, or
arises naturally from a definition or

we have 𝑚 ≠ 𝑚 + 𝑛.
construction.

Proof. Ⅽonsider 𝒳 ∶= {𝑚 ∈ ℕ | 𝑚 ≠ 𝑚 + 𝑛 for all nonzero 𝑛 in ℕ}.

As 0 ≠ 𝑛 = 0 + 𝑛, we have 0 ∈ 𝒳 . When 𝑚 ∈ 𝒳 , we claim that
S(𝑚) ≠ S(𝑚) + 𝑛. Ⅽommutativity and the definition of addition
give S(𝑚) + 𝑛 = 𝑛 + S(𝑚) = S(𝑛 + 𝑚) = S(𝑚 + 𝑛). Thus, it suffices
to show that S(𝑚) ≠ S(𝑚 + 𝑛). Since S is injective, this relation is
equivalent to 𝑚 ≠ 𝑚 + 𝑛, so S(𝑚) ∈ 𝒳 . The principle of induction
implies that 𝒳 = ℕ.

Ⅾefinition 0.2.1. Ⅼet 𝑚 and 𝑛 be nonnegative integers. We say 𝑚 is For example, we have 6 < 10 because
10 = 6 + 4. We also use the notation
less than 𝑛, denoted by 𝑚 < 𝑛, (or 𝑛 is greater than 𝑚 and 𝑛 > 𝑚) if 𝑚 ⩽ 𝑛 (or 𝑛 ⩾ 𝑚) whenever 𝑚 = 𝑛 or
there exists a nonzero 𝑘 in ℕ such that 𝑛 = 𝑚 + 𝑘. 𝑚 < 𝑛.

Remark 0.2.2. For any nonnegative integer 𝑛, Ⅼemma 0.1.2 shows

that 𝑛 = 0 + 𝑛, so it follows that 0 ⩽ 𝑛 and 𝑛 ⩾ 0.
An important trichotomy arises from this definition.
Proposition 0.2.3. For any nonnegative integers 𝑚 and 𝑛, exactly one
of the following binary relations holds: 𝑚 < 𝑛, 𝑚 = 𝑛, or 𝑚 > 𝑛.

⦁ Suppose that 𝑚 < 𝑛 and 𝑚 = 𝑛. There is a nonzero 𝑘 in ℕ such

Proof. We first show that the relations are mutually exclusive.

that 𝑚 = 𝑛 = 𝑚 + 𝑘, which contradicts Ⅼemma 0.2.0.

⦁ Suppose that 𝑚 < 𝑛 and 𝑚 > 𝑛. There exists nonzero 𝑘 and
ℓ in ℕ such that 𝑛 = 𝑚 + 𝑘 and 𝑚 = 𝑛 + ℓ. We deduce that
𝑛 = 𝑛 + (𝑘 + ℓ) which again contradicts Ⅼemma 0.2.0.
⦁ Suppose that 𝑚 = 𝑛 and 𝑚 > 𝑛. By symmetry, this is equivalent

Ɪt remains to show that one of the relations always holds. Fix 𝑚 in

to the first case.

ℕ and consider 𝒳 ∶= {𝑛 ∈ ℕ | 𝑚 < 𝑛 or 𝑚 = 𝑛 or 𝑚 > 𝑛}. When

𝑚 = 0, we have 0 ∈ 𝒳 . When 𝑚 ≠ 0, we have 𝑚 = 0 + 𝑚, so 0 < 𝑚
and 0 ∈ 𝒳 . When 𝑛 ∈ 𝒳 , there are three cases:
⦁ Suppose that 𝑚 < 𝑛. There exists a nonzero 𝑘 in ℕ such that
𝑛 = 𝑚 + 𝑘. The definition of addition gives
S(𝑛) = S(𝑚 + 𝑘) = 𝑚 + S(𝑘) ,
so 𝑚 < S(𝑛) and S(𝑛) ∈ 𝒳 .
⦁ Suppose that 𝑚 = 𝑛. Since S(𝑛) = 𝑛 + 1 = 𝑚 + 1, we see that
𝑚 < S(𝑛), so S(𝑛) ∈ 𝒳 .
⦁ Suppose that 𝑚 > 𝑛. There exists a nonzero 𝑘 in ℕ such that
𝑚 = 𝑛 + 𝑘. When 𝑘 = 1, we have 𝑚 = 𝑛 + 1 = S(𝑛), so S(𝑛) ∈ 𝒳 .
When 𝑘 ≠ 1, there exists a nonzero ℓ in ℕ such that 𝑘 = S(ℓ). Ɪt

𝑚 = 𝑛 + 𝑘 = 𝑛 + S(ℓ) = 𝑛 + (ℓ + 1) = (𝑛 + 1) + ℓ = S(𝑛) + ℓ ,
follows that
10 Nonnegative Ɪntegers Ⅽopyright © 2025 by Gregory G. Smith

so S(𝑛) < 𝑚 and S(𝑛) ∈ 𝒳 .

The principle of induction implies that 𝒳 = ℕ.

Ⅽorollary 0.2.4. Ⅼet 𝑚 and 𝑛 be nonnegative integers. For any nonzero

nonnegative integer 𝑘, we have 𝑚 < 𝑛 if and only if 𝑘 𝑚 < 𝑘 𝑛.

Proof. Suppose that 𝑚 < 𝑛. There exists a nonzero ℓ in ℕ such that

𝑛 = 𝑚 + ℓ. Ⅾistributivity gives 𝑘 𝑛 = 𝑘 (𝑚 + ℓ) = 𝑘 𝑚 + 𝑘 ℓ. Since
𝑘 ℓ is nonzero, we deduce that 𝑘 𝑚 < 𝑘 𝑛.
Ⅽonversely, suppose that 𝑘 𝑚 < 𝑘 𝑛 and consider two cases.
⦁ Suppose that 𝑚 = 𝑛. Ɪt follows that 𝑘 𝑚 = 𝑘 𝑛 contradicting the
inequality 𝑘 𝑚 < 𝑘 𝑛.
⦁ Suppose that 𝑚 > 𝑛. The first direction shows that 𝑘 𝑚 > 𝑘 𝑛
which also contradicts the inequality 𝑘 𝑚 < 𝑘 𝑛.
From the trichotomy, we deduce that 𝑚 < 𝑛.

Ⅼemma 0.2.5. For any nonnegative integers 𝑚 and 𝑛 such that 𝑚 < 𝑛,
we have S(𝑚) ⩽ 𝑛.

Proof. Since 𝑚 < 𝑛, there is a nonzero 𝑘 in ℕ such that 𝑛 = 𝑚 + 𝑘.

When 𝑘 = 1, we have 𝑛 = 𝑚 + 1 = S(𝑚). When 𝑘 > 1, there exists
a nonzero ℓ in ℕ such that 𝑘 = 1 + ℓ. Ɪt follows that 𝑛 = 𝑚 + 1 + ℓ
and S(𝑚) = 𝑚 + 1 < 𝑛.

Using the total order on nonnegative integers, the principle of

induction has another fundamental reformulation.

Theorem 0.2.6 (Well‑ordering of ℕ). Every nonempty subset of the set

ℕ of nonnegative integers contains a unique least element.
Proof. Ⅼet 𝒳 be a nonempty subset of nonnegative integers.
Uniqueness: Suppose that 𝑥 and 𝑦 are both least elements of 𝒳 . Since
𝑥 ⩽ 𝑦 and 𝑦 ⩽ 𝑥, the trichotomy implies that 𝑥 = 𝑦.
Existence: Suppose that subset 𝒳 has no least element. Ⅽonsider the
subset 𝒴 ∶= {𝑛 ∈ ℕ | 𝑛 ⩽ 𝑥 for all 𝑥 ∈ 𝒳 }. Remark 0.2.2 proves
that 0 ∈ 𝒴 . Assume that 𝑛 ∈ 𝒴 . As 𝒳 has no least element, it
follows that 𝑛 ∉ 𝒳 and 𝑛 < 𝑥 for all 𝑥 ∈ 𝒳 . Ⅼemma 0.2.5 shows
that S(𝑛) = 𝑛 + 1 ⩽ 𝑥 for all 𝑥 ∈ 𝒳 , so S(𝑛) ∈ 𝒴 . The principle
of induction establishes that 𝒴 = ℕ. However, this would imply
that ∅ = 𝒳 ∩ 𝒴 = 𝒳 which contradicts the hypothesis that 𝒳 is
nonempty. We conclude that every nonempty subset of nonneg‑
ative integers has a least element.
11 Nonnegative Ɪntegers Ⅽopyright © 2025 by Gregory G. Smith

0.3 Exercises
Problem 0.3.1. For all nonnegative integers 𝑛, prove the equation
𝑛
1 𝑛+1
∑ =
𝑘=0 (𝑘 + 1)(𝑘 + 2) 𝑛 +2

i. Ⅴerify this equation via induction on 𝑛.

in two ways.

ii. Ⅾerive this equation using partial fractions.

Problem 0.3.2. For all nonnegative integers 𝑛, verify that

𝑛 2
⎧ 𝑛 ⎫
∑ 𝑗3 = ⎪ ∑ 𝑗⎪
𝑗=0 ⎩𝑗=0 ⎭
Problem 0.3.3. For any nonnegative integer 𝑛, demonstrate that
either 𝑛 = 0 or there exists 𝑘 in ℕ such that 𝑛 = S(𝑘).

Problem 0.3.4. Establish the following variant on the principle of

induction.
To verify that a property 𝑃(𝑛) holds for all nonnegative integers 𝑛, it

Base case: 𝑃(0) holds, and

is enough to prove that

Ɪnduction step: for any nonnegative integer 𝑛, the assumption that

the property 𝑃(𝑘) holds for all 𝑘 ⩽ 𝑛 implies that the property
𝑃(𝑛 + 1) holds.

by 𝑁0 ∶= 0, 𝑁1 ∶= 1, and 𝑁𝑘 ∶= 34 𝑁𝑘−1 − 𝑁𝑘−2 + 2 for all 𝑘 ⩾ 2. The

Problem 0.3.5. The sequence of square triangular numbers is defined

first few terms are 0, 1, 36, 1225, 41616, 1413721, 48024900, … .

i. Prove that 𝑁𝑘−1 𝑁𝑘+1 = (𝑁𝑘 − 1)2 for all 𝑘 ⩾ 1.
ii. Ⅴerify that
⎧ (3 + 2√2)𝑘 − (3 − 2√2)𝑘 ⎫2
𝑁𝑘 = ⎪ ⎪ .
⎩ 4√2 ⎭

Problem 0.3.6. For any nonnegative integers 𝑘, 𝑚, and 𝑛, show that

𝑘 + 𝑚 = 𝑘 + 𝑛 if and only if 𝑚 = 𝑛.

Problem 0.3.7. For any nonnegative integers 𝑚 and 𝑛, show that

𝑚 + 𝑛 = 0 if and only if 𝑚 = 𝑛 = 0.

Problem 0.3.8. For any nonnegative integers 𝑘, 𝑚, and 𝑛 such that

𝑘 ≠ 0, demonstrate that 𝑘 𝑚 = 𝑘 𝑛 if and only if 𝑚 = 𝑛.

Problem 0.3.9. For any nonnegative integers 𝑚 and 𝑛, show that

𝑚 𝑛 = 0 if and only if 𝑚 = 0 or 𝑛 = 0.

Problem 0.3.10. For any nonnegative integers 𝑚 and 𝑛, show that

𝑚 𝑛 = 1 if and only if 𝑚 = 𝑛 = 1.

for exponentiation and prove that, any nonnegative integers 𝑘, 𝑚,

Problem 0.3.11. For nonnegative integers, formulate the definition

and 𝑛, we have
𝑚0 = 1 , (𝑚 𝑛)𝑘 = 𝑚𝑘 𝑛𝑘 , 𝑚𝑘+𝑛 = 𝑚𝑘 𝑚𝑛 , (𝑚𝑛 )𝑘 = 𝑚𝑛 𝑘 .
12 Nonnegative Ɪntegers Ⅽopyright © 2025 by Gregory G. Smith

Problem 0.3.12. For any nonnegative integers 𝑘, 𝑚, and 𝑛, establish

i. When 𝑘 ⩽ 𝑚 and 𝑚 ⩽ 𝑛, we have 𝑘 ⩽ 𝑛.

the following:

ii. When 𝑘 < 𝑚 and 𝑚 ⩽ 𝑛, we have 𝑘 < 𝑛.

iii. When 𝑘 ⩽ 𝑚 and 𝑚 < 𝑛, we have 𝑘 < 𝑛.

Problem 0.3.13. For any nonnegative integers 𝑘, 𝑚, and 𝑛 such that

𝑘 ≠ 0, prove that 𝑚 < 𝑛 if and only if 𝑘 + 𝑚 < 𝑘 + 𝑛.

Problem 0.3.14. Establish that any nonempty subset of ℕ that is

bounded above has a unique greatest element (with respect to ⩽).

Problem 0.3.15. For any nonnegative integers 𝑚 and 𝑛 with 𝑛 ≠ 0,

prove that there exists a nonnegative integer 𝑘 such that 𝑚 < 𝑘 𝑛.