Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for a set containing an element 0 and a successor function s that satisfies the first two Peano postulates (s is injective and 0 is not in its image), but not the third (the one about induction). This is of course exercise 1.4.9 in MacLane's Algebra book, so it's more or less homework, so if you could do the thing where you like point me in the right direction without giving it all away that'd be great. Thanks!

share|improve this question

5 Answers 5

HINT: Take a set strictly larger than $\Bbb N$.

    o    o   o  o o ...  o    o   o  o o ...
share|improve this answer

Since your set has 0 and a successor function, it must contain $\Bbb N$. The induction axiom is what ensures that every element is reachable from 0. So throw in some extra non-$\Bbb N$ elements that are not reachable from 0 and give them successors. There are several ways to do this.

Geometrically, $\Bbb N$ is a ray with its endpoint at 0. The Peano axioms force it to be this shape. Each axiom prevents a different pathology. For example, the axiom $Sn\ne 0$ is required to prevent the ray from curling up into a circle. It's a really good exercise to draw various pathological shapes and then see which ones are ruled out by which axioms, and conversely, for each axiom, to produce a pathology which is ruled out by that axiom.

Addendum: I just happened to be reading Frege's Theorem and the Peano Postulates by G. Boolos, and on p.318 it presents a variation of this exercise that you might enjoy. Boolos states a version of the Peano axioms:

  1. $\forall x. {\bf 0}\ne {\bf s}x$
  2. $\forall x.\forall y.{\bf s}x={\bf s}y\rightarrow x=y$
  3. (Induction) $\forall F. (F{\bf 0}\wedge \forall x(Fx\rightarrow F{\bf s}x)\rightarrow \forall x. F x) $

And then says:

Henkin observed that (3) implies the disjunction of (1) and (2)… It is easy to construct models in which each of the seven conjunctions ±1±2±3 other than –1–2+3 holds; so no other dependencies among 1, 2, and 3 await discovery.

Your job: find the models!

share|improve this answer

How about the non-negative rational numbers? Or just $(1/2)\mathbb N$.

share|improve this answer
1  
For the first suggestion I'm not sure a dense set would work. What would be the successor function? In the case of $(1/2)\mathbb N$ simply replace the successor function with $S(x)=x+\frac12$ (addition as rational numbers). I do have the assumption that the first two axioms in the formulation at hand include the fact that every non-zero number is a successor. –  Asaf Karagila May 26 '12 at 22:13
    
@Asaf, the Peano postulates in MacLane-Birkhoff's Algebra do not assume that every non-zero number is a successor. This is given as a consequence of the induction principle. –  lhf May 27 '12 at 11:47

Think about the question for a moment (and think about the first two parts I'm assuming you got).

You need some set X with a unary operation and an element 0 that satisfies P.P. (i) and (ii).

When you constructed the first two sets, was your unary operation x+1? Or did you create some other mapping? (It shouldn't have been x+1 given that, for one of them at least, you needed 0 in the image).

Can you create a unary operation over N that is injective and does not include 0 in its image, but whose image is not N?

share|improve this answer

{Z,SZ,SSZ,SSSZ,...} union {X,SX,SSX} with SSSX=X

share|improve this answer
    
The point here is that you need induction to prove there's no cycles in the natural numbers. –  user58512 Jan 26 '13 at 20:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.