-1
$\begingroup$

The Peano axioms of $\Bbb N$ are:

  1. $1 \in \Bbb N$, i.e. $\Bbb N$ is not empty and contains an element denoted by $1$.

  2. Every natural number has a successor, i.e. $\forall n\in\Bbb N, \exists!s(n)\in\Bbb N$.

  3. if $s(n)=s(m)$ then $n=m$.

  4. $1\in\Bbb N$ is the only element that is not the successor of a natural number.

  5. The axiom of mathematical induction is valid:

    Let $S\subseteq\Bbb N$ such that

    1. $1\in S$

    2. $\forall n\in\Bbb N,n\in S\Rightarrow(s(n)\in S)$.

    Then $S=\Bbb N$.

I am trying to find an example of a collection "$\Bbb N$'' with 1,2 that satisfies 5 but not 3 and also not 4. (It is easy to find examples satisfying 3 but not 4,5, and 4 but not 3,5. My question is about 5 but not 3,4.) In other words, is there a set "$\Bbb N$'' that has a $1$, successors exist, and induction holds, but $1$ is the successor of an element and also the successor function is not one-to-one? I can't seem to think of an example. I suspect that if 1,2,5 are satisfied, then either 3 or 4 must hold. Is there an elementary proof of this?

Improve this question
$\endgroup$
9
  • 7
    $\begingroup$ Well, the induction axiom is equivalent to $\mathbb N=\{1,s(1),s(s(1)),\dots\}$ (that is, $\{s^{(k)}(1):k\in\omega\}$). Thus, the graph of $s$ consists of a single directed walk starting from $1$. Either this is an infinite path (in which case both 3 and 4 hold), or it eventually enters a cycle; if it is just a cycle, then 3 holds and 4 fails, whereas if there is a nonempty path leading to the cycle, then 3 fails and 4 holds. So, yes, 3 or 4 must hold. $\endgroup$
    – Emil Jeřábek
    Commented Sep 4, 2020 at 9:30
  • $\begingroup$ @EmilJeřábek Thanks, I see now. However, since this statement is about basic set theory, is there a proof that uses just the bare-minimum of elementary logic/reasoning rather than more advanced notions of paths/cycles? It seems like there should be such a proof. $\endgroup$
    – Curiosity
    Commented Sep 4, 2020 at 9:40
  • 5
    $\begingroup$ If you consider cycles and paths advanced, then I really have no idea what you mean by elementary. $\endgroup$
    – Emil Jeřábek
    Commented Sep 4, 2020 at 9:46
  • 1
    $\begingroup$ @PaceNielsen These are, in fact, more or less the axioms originally postulated by Peano (see archive.org/details/arithmeticespri00peangoog/page/n22/mode/2up). This is different from what later became to be known as the “Peano arithmetic”. $\endgroup$
    – Emil Jeřábek
    Commented Sep 4, 2020 at 16:42
  • 1
    $\begingroup$ I think this question would be more appropriate at math.stackexchange. $\endgroup$
    – Noah Schweber
    Commented Nov 3, 2020 at 17:42

2 Answers 2

Reset to default
0
$\begingroup$

If you imagine N with a successor function of: s(n) = the next power of 2 larger than n, then we satisfy (1) and (2) but not (3) or (4). Unfortunately, (5) also doesn't seem to hold in this setting. (As pointed-out in the comments)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are you sure that induction holds? $A=\{2^n\mid n\in\Bbb N\cup\{0\}\}$ seems to satisfy $1\in A$, since $2^0=1$, and if $n\in A$, then $n=2^k$, so $s(n)=2^{k+1}\in A$. But very obviously, $A$ does not contain any odd numbers except $1$. $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 4, 2020 at 10:36
  • $\begingroup$ Hmmm... you are right ... induction would be saying that a property holds for everything on the 1,2,4,8,16 .... path. I guess one actually has to find a different set for this, rather than a successfor function. Answer now edited to reflect this. $\endgroup$
    – JimN
    Commented Sep 4, 2020 at 10:40
0
$\begingroup$

If 4 fails because there is something $w\ne 1$ that is not a successor, then the complement of $\{w\}$ shows that 5 also fails. So in order to get 5 but not 4, we need that 4 fails because $1$ is a successor.

So suppose 1,2,5 hold and $1$ is a successor. I claim 3 also holds. "Proof is left to the reader".

Improve this answer
$\endgroup$
1
  • $\begingroup$ But, it is trivial that all we have to do is prove that 3 holds if 1,2,5 hold and 4 is false (for if 4 is true, we're done) so I'm asking "is there an elementary proof that 3 holds if 1,2,5 hold and 1 is a successor". I don't understand why you posted this as an "answer" when it's essentially a repeat of the question. I say this because making trivial modifications of a question and posting it as it it is an answer (or trivializing a question just so you can post an answer) is exactly the reason my colleague/advisor/mentor does not want anything to do with mathoverflow. $\endgroup$
    – Curiosity
    Commented Oct 5, 2020 at 19:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .