Number Systems

The Natural Numbers

A subset A R is an inductive set if it satisfies the following two properties :
i. 1 ∈ A
ii. If n ∈ A, then n + 1 ∈ A.

• R is an inductive set.
The set of natural numbers, N = {1, 2, 3, . . .}, is defined to be the intersection of all inductive
subsets of R.

• N is itself and inductive set and is contained in every other inductive subset of R. Why?
[The modern convention is to include 0 in the definition of an inductive set and therefore to define
the natural numbers as {0, 1, 2, . . .} . For our purposes, it is be more convenient to let N represent
only the positive natural numbers. However, when applying the principle and mathematical induction
or rescursive definitions (see below), it will be sometimes be convenient to start with 0 and so
implicitely include 0 in the inductive set.]

• If n ∈ N\{1} , then n − 1 ∈ N.
٠ Suppose n ∈ N but n ≠ 1. Therefore, by the definition of an inductive set, n = m + 1 for
some m ∈ N. Therefore, n −1 = m ∈ N.

Principle of Mathematical Induction

One immediate implication of this definition of the natural numbers is the principle of mathematical
induction. Suppose we are given a list of statements and we wish to prove that all of them
are true. The principle of mathematical induction states that it is sufficient to prove the following
two statements: (i) , and (ii) "For any natural number n, implies ." (Statement is
called the basis statement, is called the induction hypothesis, and the statement is
called the induction step .) Once statements (i) and (ii) are established, we can prove any statement
by starting with statement and successively applying the induction step. A formal statement
and proof follows.

• Suppose we assign a logical statement to each n ∈ N, and suppose
(i) is true, and (ii) implies .
Then is true for all n ∈ N.
٠ Let A = {n ∈ N : S(n) is true}. By assumption 1 ∈ A. Also if n ∈ A, then n + 1 ∈ A.
Therefore, A is an inductive set. But since N is contained in any inductive set, we have
N A N, which implies A = N.

Properties of Natural Numbers

We may use mathematical induction to establish that all natural numbers are positive and that
the set of natural numbers are discrete in the sense that if n ∈ N, then there is no m ∈ N such that
n < m < n + 1.

• (L1) n ∈ N implies n ≥ 1.
٠ The proof is by induction on n. First observe that 1 ≥ 1 provides the basis statement for
n = 1. Now consider the induction hypothesis n ≥ 1. Then, since the order axioms imply
n +1 > n, we have n + 1 > n ≥ 1, which establises the induction step.

• (L2)If m, n ∈ N and m > n, then m ≥ n + 1.
٠ If m > 1, then m −1 ∈ N and therefore the previous proposition implies m −1 ≥ 1. Therefore
m ≥ 1+1, which establishes the basis statement. Now suppose that m > n implies m ≥ n+1.
Then m > n+1 implies m−1 > n, which implies m−1 ≥ n+1 and therefore, m ≥ (n + 1)+1.

Using induction, we may also show that the natural numbers are closed under addition and multiplication .

• Suppose m, n ∈ N. Then (i) m + n ∈ N, and (ii) m ٠ n ∈ N. (iii) If m < n, then n − m ∈ N.
٠ (i) The proof is by induction. Consider any m ∈ N. Then, since N is inductive, we have
m+1 ∈ N. Now suppose m+n ∈ N. Then, since N is inductive, (m + n)+1 = m+(n + 1) ∈ N.
٠ (ii) The proof is by induction. Consider any m ∈ N. From the field axioms, we have m ٠1 =
m ∈ N. Now suppose m ٠ n ∈ N. Then m ٠ (n + 1) = m ٠ n + m ٠ 1 ∈ N by part (i).
٠ (iii) The proof is by induction on n. If m − 1 > 0, then since m ≠ 1, it follows that m = p+1
for some p ∈ N. But then m −1 = p ∈ N. Suppose m − n > 0 implies that m − n ∈ N. Then
if m − (n +1) > 0, then (m − 1) − n > 0 and m − 1 ∈ N implies m − (n +1) ∈ N.

Well Ordering Principle

If min B exists for each nonempty subset B X, then we say that a set X is well-ordered by '≤'.

• R is not well ordered by '≥'. Neither are the set of integers or the set of rationals defined below.

For any n ∈ N, the set ≡ {m ∈ N : m ≤ n} is called the n^th-segment of N.

• N is well-ordered.
٠ Let A = {n ∈ N : if B N and then min B exists}. We will prove by induction
that A = N. From (L1), we have that 1 ≤ n for all n ∈ N. Therefore, if , then
1 =minB. Therefore, 1 ∈ A, which is our basis statement.
٠ Now suppose n ∈ A. To show that n + 1 ∈ A, consider any B N such that B ∩ ≠ '.
Then either in which case min B exists by the induction hypothesis, or B ∩ = in which case m ∈ B implies n < m and therefore (L2) implies that n + 1 ≤ m. But then
B ∩ ≠ implies min B = n + 1. Therefore n +1 ∈ A.
٠ To complete the proof, consider any nonempty subset B N. Then n ∈ B implies B ∩ ≠ .
But since n ∈ A, it follows that min B exists.

Principle of Recursive Definition.

When proving theorems is often useful to construction a sequence of elements () inductively
in which the value of each is based on the values already defined for Stated
equivalently in the langange of functions, for some set of possible values Y, we wish to construct
a function x : N → Y in which for each n ∈ N, the value of x(n + 1) depends on the value of the
restriction that has already been defined. The following theorem provides a
formal statement of the requirements for constructing a unique sequence.

• (PRC): Suppose Y is a nonempty set and we are given a function σ : → Y. Then for
any a ∈ Y, there is a unique function f : N → Y for which (i) f(1) = a, and (ii) for each n ∈ N,
f (n + 1) = σ(f |).
٠ (sketch of proof) We use mathematical induction to construct a unique sequence of functions
→ Y and show that for m < n. Then define
Complete proofs can be found in Royden, RealAnalysis and Kelly , General Topology.

Example: An example from decision theory illustrates an application of a recursive definition.
Suppose time is discrete and each point in time is represented by a positive integer. At each
point in time, the decision maker must choose some action in a set Y (e.g. Y = {Lef t, Right}).
An n-period history is an n-tuple where each ht specifies the decision
taken in period t. We let denote the initial history in which no decisions have been made.
Then denotes the set all (partial) histories. A strategy (or decision
rule ) is a function σ : H → Y, which specifies for each history h a choice in Y. An outcome is
a sequence that specifies the decision taken in each period n. Then the principle of
recursive definition implies that each strategy implies a unique outcome , where
and for each period n ∈ N.

Monomials

In applying the principle of recursive definition, we often require a weaker version in which f (n+1)
depends only on f (n), rather than all of the information contained in. In this case we can
replace the function σ : → Y with the simpler function s : Y → Y.

• (Principle of Simple Recursive Definition): Suppose Y is a nonempty set and we are given
a function s : Y → Y. Then for any a ∈ Y, there is a unique function f : N → Y for which (i)
f(1) = a, and (ii) for each n ∈ N, f (n +1) = s(f (n)).

We may use this simplified principle to define a monomial function .

For any x ∈ R, we define . For any n ∈ N and x ∈ R, we define ≡ f (n) recursively as
follows

[The formal application of the simple PRD works as follows: Y ≡ R, a ≡ x, s(z) ≡ x ٠ z. Then
≡ f(1) = x, and ≡ f (n + 1) = s(f (n)) = x ٠ f (n) ≡ x ٠ .]

• (a)
٠ The proof of (a) is by induction on n. By definition, for any
m ∈ N. Suppose for any m ∈ N. Then

٠ The proof of (b) is by induction on n. Observe first that for all m ∈ N.
Suppose for any m ∈ N. Then
,where the first and third equalities follow from part (a).