The natural numbers are the set ℕ = { 0, 1, 2, 3, .... }. These correspond to all possible sizes of finite sets; in a sense, the natural numbers are precisely those numbers that occur in nature: one can have a field with 0, 1, 2, 3, etc. sheep in it, but it's hard to have a field with -12 or 22/7 sheep in it.

Warning: While this is definition of ℕ is almost universally used in computer science, and is used in RosenBook, some mathematicians—including the author of BiggsBook—leave zero out of the natural numbers. There are several possible reasons why you might do this:

• You were born well before the invention of zero approximately two millenia back by the ancient Indians, Babylonians, and/or Mayans.
• You were taught by extremely conservative schoolmasters who still hadn't got a handle on this newfangled zero thing.
• You live in a country that is so rich in sheep that the thought of a field with no sheep in it seems unnatural.
• You are a number theorist, and you don't want to have follow "Let n be a natural number..." with "(except zero)" in every theorem you write.

My suspicion is that Biggs falls into the last category (and might fall into some of the earlier ones). For the purposes of CS202 we will adopt the usual convention in ComputerScience and start the naturals at zero. However, you should keep an eye out for assumptions that the natural numbers don't include zero. The terms positive integers (for {1, 2, 3, ...}) and non-negative integers (for {0, 1, 2, 3, ...}) can also be helpful for avoiding confusion.

1. Axioms

There are several different ways to define the naturals. That these definitions all yield the same object is one of the reasons why they are so natural.

1.1. Peano axioms

The PeanoAxioms define the natural numbers directly from logic. It is not hard to show that the usual natural numbers satisfy these axioms (whether or not you throw out zero). Unfortunately, the Peano axioms by themselves don't give us many of the usual operations (like addition and multiplication) that we expect to be able to do to numbers.

1.2. Set-theoretic definition

In SetTheory, a natural number is defined as a finite¹ set x such that (a) every element y of x is also a subset of x, and (b) every element y of x is also a natural number. The existence of the set of natural numbers is asserted by the Axiom of Infinity. The smallest natural number is the empty set, which we take as representing 0. Next is 1 = { 0 }, 2 = { 0, 1 }, 3 = { 0, 1, 2 }, etc. It can easily be verified that each natural number defined in this way is indeed a subset of the next. It's not hard to show that these set-theoretic natural numbers satisfy the Peano axioms, and it's possible to define addition and multiplication operations on them that satisfy the arithmetic and order axioms below (we'll see more of this in HowToCount). Ordering is by inclusion: for the set-theoretic definition, n < m just in case n is an element of m.

1.3. Arithmetic and order axioms

Axioms for arithmetic in ℕ-{0} are given in Section 4.1 of BiggsBook. RosenBook doesn't spend much time on axiomatizing the naturals, relying instead on the deep intuition about natural numbers that most of us had trained into us from early childhood.

You've probably already seen all of the usual axioms early in your mathematical education, with the possible exception of mz = nz implies m = n. Note that unlike the other axioms, this one does not extend to ℕ, since m⋅0 = n⋅0 = 0 for any m and n. An extended list of axioms for ℕ including zero might look like

1. a+b is in ℕ. [Closure under addition]
2. a⋅b is in ℕ. [Closure under multiplication]
3. a+b = b+a. [Commutativity of addition]
4. (a+b)+c = a+(b+c). [Associativity of addition]
5. ab = ba. [Commutativity of multiplication]
6. (ab)c = a(bc). [Associativity of multiplication]
7. There is an element 1 of ℕ such that n1 = n for all n. [Multiplicative identity]
8. mz = nz implies m = n when z ≠ 0 (see below for 0). [Multiplicative cancellation]
9. a(b+c) = ab+ac. [Distributivity of multiplication over addition]

10. For any m and n, exactly one of n < m, n = m, or n > m is true. [Trichotomy]

11. There is an element 0 of ℕ such that n+0 = n for all n. [Additive identity]
12. 0a = 0. [Multiplicative annihilator]

The numbering follows BiggsBook, except for the last two axioms, which don't appear in BiggsBook outside of Exercise 4.1.3.

Note that < is defined in terms of +. In our terms, n < m means that there exists some x such that x is not equal to 0 and n+x = m.

One problem with these axioms (as compared to the Peano axioms) is that they are not very restrictive: they work equally well for e.g. the non-negative reals or the non-negative rationals, and extend to all of the reals or the rationals if we adjust the definition of <. So the arithmetic axioms can't be used as a definition of the naturals, even though they are much more convenient for doing actual arithmetic than the more basic definitions.

Much of the work in logic in the early 20th century involved showing that addition, multiplication, etc. could be defined in terms of much more primitive operations like successor, and that the operations so defined behaved the way we'd expect. This program was not always popular with non-logicians: as Henri_Poincaré put it (quoted in Bell and Machover's A Course in Mathematical Logic, North-Holland, 1977): "On the contrary, I find nothing in logistic for the discoverer but shackles. It does not help us at all in the direction of conciseness, far from it: and if it requires 27 equations to establish that 1 is a number, how many will it requires to demonstrate a real theorem?" Thankfully, we get to build on these efforts, and can treat the arithmetic axioms as our own convenient library of lemmas rather than having to reach down into the raw logical swamps.

1.3.1. Formal definition of arithmetic operations in terms of successor

Here's a formal definition of + in terms of successor:

1. ∀x 0+x = x.
2. ∀x ∀y Sx+y = x+Sy.

This defines the sum of two natural numbers uniquely because we can use the second rule to move all the S's off of the first addend onto the second one, until we get down to zero (recall that under the PeanoAxioms a natural number like 37 is really just a convenient shorthand for SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS0).

Here's multiplication:

1. ∀x 0x = 0.
2. ∀x ∀y (Sx)y = xy + y.

With the above rules for addition, this lets us multiply any two numbers very slowly: SS0⋅SS0 = (S0⋅SS0) + SS0 = ((0⋅SS0) + SS0) + SS0 = (0 + SS0) + SS0 = SS0 + SS0 = S0 + SSS0 = 0 + SSSS0 = SSSS0. Normal people write this as 2⋅2 = 4 and skip all the S's.

Here's <:

1. x < y ⇔ ∃z (z ≠ 0 ∧ x+z = y).

Note that this fails badly if z ranges over a larger set, like the integers.

With enough time on your hands, it is in principle possible to prove all of the arithmetic axioms given earlier hold for these definitions of +, ⋅, and <.

2. Order properties

The < relation is a total order (see Relations). This means that in addition to trichotomy, transitivity holds: a < b and b < c implies a < c. Transitivity can be proved from the definition of < and axioms 1-12; see Exercise 4.2.1 in BiggsBook.

However, < is even stronger than this: it is also a well order. This means that any subset of the natural numbers has a least element, which is the key to carrying out InductionProofs.

---

CategoryMathNotes