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!
$\begingroup$
$\endgroup$
0
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
HINT: Take a set strictly larger than $\Bbb N$.
o o o o o ... o o o o o ...
answered May 26, 2012 at 5:33
$\begingroup$
$\endgroup$
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:
- $\forall x. {\bf 0}\ne {\bf s}x$
- $\forall x.\forall y.{\bf s}x={\bf s}y\rightarrow x=y$
- (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!
$\begingroup$
$\endgroup$
2
How about the non-negative rational numbers? Or just $(1/2)\mathbb N$.
-
1$\begingroup$ 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. $\endgroup$– Asaf Karagila ♦Commented May 26, 2012 at 22:13
-
$\begingroup$ @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. $\endgroup$– lhfCommented May 27, 2012 at 11:47
$\begingroup$
$\endgroup$
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?
$\begingroup$
$\endgroup$
1
{Z,SZ,SSZ,SSSZ,...} union {X,SX,SSX} with SSSX=X
-
$\begingroup$ The point here is that you need induction to prove there's no cycles in the natural numbers. $\endgroup$– user58512Commented Jan 26, 2013 at 20:42