1

As I was trying to answer this question (using only the peano axioms), I came up with the following "proof". On a second look, I noticed a flaw. But I'm struggling to articulate why or what the flaw is. Could somebody take a look, and let me know if I'm on the right track? Thanks!

$\textbf{Incorrect Proof}$: Take any arbitrary $b \in \mathbf{N}$. Suppose for the sake of contradiction that there is some $a,a' \in \mathbf{N}$ such that $b++=a$ and $b++ = a'$. Then we can write $a = b++ = a'$ yielding $a=a'$ as required.

$\textbf{Self-critique}$: I am assuming that $b++$ doesn't have two different successors. What if we're working with some number system where it does? The right way to show this is induction on $b$ that uses the axiom "if $n\neq m$, then $n++ \neq m++$."

Hans Hüttel
  • 4,271
skm
  • 81
  • 1
    You ought to learn logic first... – user21820 Dec 17 '18 at 06:38
  • 2
    How is $b\text{++}$ defined in your context? If this is the successor function in Peano Axioms, then it is assumed to have a unique value for each $b\in \mathbf{N}$. – Sangchul Lee Dec 17 '18 at 06:51
  • We have the following definitions: 1) $n \in \mathbb{N} \to n++ \in \mathbb{N}$, 2) for all $n$, $n++ \neq 0$, and 3) $\forall n.(n\neq m \to n++\neq m++)$. – skm Dec 17 '18 at 07:02
  • @skm Sure. But usually, right before you get to that part, the successor function is defined as a function. And part of the definition of a function is exactly that for any input the output is unique. Is this the case for you? And if not, then what is your $++$? – Arthur Dec 17 '18 at 07:13
  • @Arthur I don't see a successor function in the definition for incrementation. What I do have is a proposition that follows from the axiom stating induction about recursive definitions: Suppose for each $n \in N$, we have some function $f_n :N\to N$. Take some $c \in N$. Then we can assign a unique natural number $a_n$ to each natural number $n$, such that $a_0 := c$ and $a_n++ := f_n(a_n)$. Is this what you're referring to? – skm Dec 17 '18 at 07:28
  • Alternatively, we have an informal definition stating $0++ = 1, 1++ = 2, etc.$ – skm Dec 17 '18 at 07:31
  • We can come up with a model, different from $\mathbf{N}$, that satisfies all the Peano axioms except the 'uniqueness of successor' part. For instance, prepare two copies of $\mathbf{N}$ and identify their initial elements. – Sangchul Lee Dec 17 '18 at 07:36
  • I'll repeat myself that you need to learn logic first, because if you knew basic logic you would not even consider your 'incorrect proof' because it makes completely no logical sense... Trying to use Peano Arithmetic without basic logic is like trying to jump off a cliff without something to hold you up. – user21820 Dec 17 '18 at 16:04
  • And mathematics does not use "$++$". It's ugly and incorrect. – user21820 Dec 17 '18 at 16:04
  • Thanks for the comment user21820. For the basic logic piece, I have learned logic. I'm using these first chapters as a way to firm up those concepts, and hence, the struggles. As for the "++", I'm using the same notation used in the book I'm going through (Analysis by Terence Tao). I think I've got a good sense from the above comments what I need to do, so I'll write it up and post here relatively soon. All the help is much appreciated! – skm Dec 18 '18 at 05:50

1 Answers1

1

You write

Suppose for the sake of contradiction that there is some $a,a' \in \mathbf{N}$ such that $b++=a$ and $b++ = a'$. Then we can write $a = b++ = a'$ yielding $a=a'$ as required.

We cannot conclude this, as we are assuming that $b\!+\!\!+$ is not unique.

Hans Hüttel
  • 4,271