natural number

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at . 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. 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. 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. The numbering follows BiggsBook , except for the last two axioms, which don't appear in BiggsBook outside of Exercise 4.1.3. 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. 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). Note that this fails badly if z ranges over a larger set, like the integers.