Natural number

Mathematics

Natural Numbers

Subject classification: this is a mathematics resource.

Educational level: this is a secondary education resource.

Educational level: this is a tertiary (university) resource.

The natural numbers (or counting numbers) are the fundamental mathematical set on which all other arithmetic is based. They do not include negative numbers. (The set of integers provides negative numbers.) Whether the natural numbers include zero is a matter of taste—zero can be adjoined to the set in much the same way that the definition of the integers adjoins negative values. Sometimes the "natural numbers" are posited to include zero while the "counting numbers" are not. One can use whatever definition suits one's purpose at a given time.

Mathematicians denote the set of natural numbers with an ornate capital letter: $\mathbb {N}$ . They are the 1^st item in this hierarchy of types of numbers:

The "natural numbers"-5, -4, -3, -2, -1, — $\mathbb {N}$ , 1, 2, 3, ...
The "integers"— $\mathbb {Z}$ , positive, negative, NOT zero
The "rational numbers"— $\mathbb {Q}$ , or fractions, like 355/113
The "real numbers"— $\mathbb {R}$ , including irrational numbers
The "complex numbers"— $\mathbb {C}$ , which give solutions to polynomial equations

Sometimes the symbol $\mathbb {N} ^{+}$ is used to denote the set not including zero, while not $\mathbb {N}$ includes zero.

Arithmetic at an intuitive level. 4+3=7.

People generally understand the arithmetic operations on natural numbers, at an intuitive level, long before they appreciate the significance of careful mathematical definitions and proofs. Indeed, students often prove theorems about algebra and calculus, involving a good understanding of the rational, real, or complex numbers, before they think carefully about the axiomatic basis for the natural numbers. The seemingly intuitively fundamental existence of the natural numbers is perhaps best summed up by this saying from Leopold Kronecker:

“

God made the integers; all else is the work of man.

”

(In modern terminology, we would say that he was talking about the natural numbers.)

Can we put the natural numbers on a sound "axiomatic" basis?

Without a rigorous foundation for the natural numbers, the rest of mathematics could be considered flawed. In the 19^th century much work was done on the foundations of set theory and arithmetic. Guiseppe Peano, along with Richard Dedekind, are generally credited with the solution to the problem of the natural numbers. In 1889, Peano provided 5 axioms, from which the natural numbers could be developed rigorously. The axioms are generally called the Peano axioms, and sometimes called the Dedekind-Peano axioms.

The Peano axioms

(Also called the Peano postulates.)

Before we give the axioms and define the natural numbers, there are a few preliminary things to say:

We will define the numbers starting with 1. Zero can be added later, when the integers are defined.
We assume elementary notions of set theory and logic. For example, we assume a notion of "things" being equal. And that $x=x$ always, if $x=y$ then $y=x$ , and if $x=y$ and $y=z$ , then $x=z$ .

We will follow the presentation in the classic Foundations of Analysis by Edmund Landau^[1].

Here are the axioms:

There is a (natural) number, called "1".
There is a successor function. We denote it with a prime. So, for example, 1' is a number. It's usually called "2". 1' ' is also a number, called "3". And so on.
If x' = y', then x = y. That is, we don't have two different numbers with the same successor. (We already know that if x = y, then x' = y'; that follows from what we know about how functions work.)
1 is not the successor of any number.
If a set S contains 1, and for every x in S, x' is also in S, then S is the entire set of (natural) numbers.

This last axiom is called the axiom of induction, and is the axiom underlying all proofs by induction.

Intuitively, the axioms can be thought of as making the following statements about the natural numbers:

Axiom 1 says that the set is not empty.
Axiom 2 says that the numbers go on forever. There is no "last" number. Also, because functions are single-valued, the sequence does not "split" going upward. It is one sequence.
Axiom 3 says that the sequence does not "split" going downward either. There are no branches that converge.
Axiom 4 says that they don't go on forever in the downward direction. There is a "first" number, and it is 1. Of course, zero and the negative integers are formulated later, outside of the Peano axioms.
Axiom 5 says that there are no isolated "islands" of numbers. The number sequence starting from 1 is everything that there is.

Axiom 5 is generally used in a less formal way—rather than talking about a set S, we prove something for 1, and prove it for x' (that is, x+1) assuming it is true for x, and conclude that it is true for all x.

Addition

We can now define the fundamental notions about arithmetic, and prove as theorems the fundamental laws that people take for granted, such as associativity, commutativity, and distributivity.

Definition: There is an operation of addition, denoted x+y, as follows:

For all x, x+1 = x' (clause 1)
For all x and y, x+y' = (x+y)' (clause 2)

This is well-defined for all x and y, by induction on y: Clause 1 defines it for y=1 and all x, and clause 2 defines it for y' and all x, assuming it is defined for y and all x.

Theorem 1: 1+x = x' (or, by clause 1, 1+x = x+1)

Proof by induction on x: If x=1, this is 1+1 = 1', which is true by clause 1. Otherwise, assume it is true for x. Then:

1+x' = (1+x)' (clause 2)

= (x+1)' (induction)

= x' ' (clause 1)

Theorem 2 (associative law of addition): (x+y)+z = x+(y+z)

Proof by induction on z, for all x and y:

If z=1, (x+y)+1 = (x+y)' (clause 1)

= x+y' (clause 2)

= x+(y+1) (clause 1)

= x+(y+z)

Now assume it is true for some z, and for all x and y:

(x+y)+z' = ((x+y)+z)' (clause 2)

= (x+(y+z))' (induction)

= x+(y+z)' (clause 2)

= x+(y+z') (clause 2)

Theorem 3 (commutative law of addition): x+y = y+x

Proof by induction on x, for all y:

If x=1, 1+y = y+1 (theorem 1)

Now assume it is true for some x, and for all y:

x'+y = (x+1)+y (clause 1)

= (1+x)+y (theorem 1)

= 1+(x+y) (associativity)

= 1+(y+x) (induction)

= (1+y)+x (associativity)

= (y+1)+x (theorem 1)

= y+(1+x) (associativity)

= y+x' (theorem 1)

Ordering

Lemma^[2] 1: We never have x+y = x

Proof by induction on x, for all y: If x=1, this would be y+1 = y' = 1, which is impossible by axiom 4. Otherwise, suppose x'+y = x'. Then:

(x+y)' = x' (clause 2)

x+y = x (axiom 3)

which is impossible by induction.

Lemma 2: If y ≠ z, then x+y ≠ x+z

Proof by induction on x, for all y and z: If x=1, this is y' ≠ z', which follows from axiom 3. Otherwise, assume x+y ≠ x+z. Then:

(x+y)' ≠ (x+z)' (axiom 3)

so x'+y = (x+y)' ≠ (x+z)' = x'+z (clause 2)

Lemma 3: If y ≠ 1, there is some v for which y = v'

In other words, every number other than 1 has a predecessor. We will call that predecessor "y-1". We will say more about subtraction shortly.

We will show that, for all y, either y=1 or y = v' for some v.

Proof by induction on y. For y = 1, the statement is trivial. Otherwise, we need to show that y' = 1 or y' = v' for some v. Letting v = y satisfies this.

The trichotomy law, and subtraction

Theorem 4 (trichotomy law): For a given x and y, exactly one of the following is true:

(A) x = y

(B) x = y+u for some u

(C) y = x+v for some v

Proof: We first show that at most one of these is true. (A) and (B) can't both be true by lemma 1. Similarly, (A) and (C) can't both be true. If (B) and (C) are both true, then

x = (x+v)+u = x+(v+u), which is impossible by lemma 1.

Now we show that one of them is true. The proof is by induction on x, for fixed y. For x=1, either y=1, so it's case (A), or y ≠ 1, so y = v' by lemma 3, so y = 1+v = x+v, so it's case (C).

Assume the theorem is true for x; we must prove it for x'.

If case (A) was true, x = y, so x' = y+1, so case (B) holds for x'.

If case (B) was true, x = y+u, so x' = y + (u+1), so case (B) holds for x', using u+1.

If case (C) was true, y = x+v. If v=1, then y=x', so case (A) holds for x'. Otherwise,

y = x+(v-1)' (lemma 3)

= (x+(v-1))' = x'+(v-1), so case (C) holds for x', using the number "v-1" that lemma 3 provides.

Definition:

If x=y+u for some u (case (B) above), we say "x > y". The number u is called "x-y". If y=x+v for some v (case (C) above), we say "x < y". The number v is called "y-x".

The trichotomy law then says that, for any x and y, exactly one of x=y, x<y, or x>y is true.

We define the operation of finding the number u or v, above, as "subtraction". We can subtract any smaller number from a larger one.

Everything that we have done is severely constrained by the fact that we are dealing only with positive nonzero numbers. When the full integers are defined, we will be able to subtract freely.

Multiplication

Definition: There is an operation of multiplication, denoted x•y, as follows:

For all x, x•1 = x (clause 1)
For all x and y, x•y' = x•y + x (clause 2)

This is well-defined for all x and y, by induction on y: Clause 1 defines it for y=1 and all x, and clause 2 defines it for y' and all x, assuming it is defined for y and all x.

Lemma 4: 1•x = x•1 = x

Proof by induction on x: If x=1, this is obvious by clause 1. Otherwise, assume it is true for x. Then:

1•x' = 1•x + 1 (clause 2)

= x•1 + 1 (induction)

= x + 1 = x' (clause 1)

Lemma 5: x'•y = x•y + y

Proof by induction on y: If y=1, this is obvious by lemma 4. Otherwise, assume it is true for y. Then:

x'•y' = x'•y + x' (clause 2)

= x•y + y + x' (induction)

= (x•y + x) + y' (various theorems about addition)

= x•y' + y' (clause 2)

Theorem 4 (commutative law of multiplication): x•y = y•x

Proof by induction on x: If x=1, this follows from lemma 4. Otherwise, assume it is true for x. Then:

x'•y = x•y + y (lemma 5)

= y•x + y (induction)

= y•x' (clause 2)

Theorem 5 (distributive law): x•(y+z) = x•y + x•z

Proof by induction on z, for all x and y:

If z=1, x•(y+1) = x•y + x = x•y + x•1 (clauses 1 and 2)

Now assume it is true for some z, and for all x and y:

x•(y+z') = x•((y+z)') = x•(y+z) + x (clause 2)

= x•y + x•z + x (induction)

= x•y + x•(z') (clause 2)

Theorem 6 (associative law of multiplication): (x•y)•z = x•(y•z)

Proof by induction on z, for all x and y: If z=1, this follows from lemma 4. Otherwise, assume it is true for z. Then, for all x and y:

(x•y)•z' = (x•y)•z + x•y (clause 2)

= x•(y•z) + x•y (induction)

= x•((y•z) + y) (distributive law)

= x•(y•z') (clause 2)

Continuing, we can define, and prove the properties of, all the other operations of integer, rational, real, and complex arithmetic. All from intuitive set theory and the Peano axioms.

References

↑ Edmund Landau, Foundations of Analysis, Chelsea Pub Co. ISBN 0-8218-2693-X
↑ A lemma is a very small theorem that is not important in its own right, but is just used in the proof of something else.