How do I prove there does not exist a natural number $n$ such that $2n=1$ by using Peano's axioms.

Question

I know that the members of the natural numbers are either $0$ or $S(n)$,for some $n\in\mathbb{N}$. So if I proceed from here and define "addition" as $+:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ such that:-

$m+0=0$ and $m+S(n)=S(m+n)$ then I can conclude that $2n=S(m)+S(m)$ . Now what I want to say is that the sum of two equal natural numbers cannot be $1$ using Peano's axiom. This is what I cannot prove as I am having a lot of confusion as to where and how to start. These formalisms are new to me and my english is not very strong as to understand all of the subtelties . Can anyone help me out with this?. If someone proceeds without using the $+$ then also it is fine by me. I just want to know how a proof would look like. That would help me in developing a framework as to how I should prove such things if I encounter them in the future.

Answer 1

The first question is: How can you express that a number is even using the peano axioms? By definition, we say that $0$ is even. We recursively say that a number $y$ is even if $y$ is of the form $y=S(S(x))$ where $x$ was already established to be an even number.

With the above in mind, how can we show that $1$ is not even? Clearly, $1\neq 0$ as $S(0)=1$ and of the axioms precisely states that $S(n)\neq n$. Great, so $1$ is not the even number $0$. The 'next' even number (after zero) is $2=S(S(0))$ and we know that $2\neq 1$ as $2=S(1)\neq 1$ by the same axiom. That's great but even if we keep doing this, it's not immediately clear that every even number can be attained by repeatedly applying $S(S(-))$ to zero and so on.

So here's the proof: Assume that $1=S(S(x))$ for some even number $x$. Hence $S(0)=S(S(x))$ and thus $0=S(x)$ as $S$ is injective (this is a Peano axiom). But $0\neq S(x)$ for any $x$ (again this is an axiom). Hence we reached a contradiction. This means that our assumption that $1$ is even must be false.

Note that this does not yet imply that $1$ is odd (we haven't even defined odd yet).

Answer 2

Here is a formal proof created in Fitch. It uses the axioms of Peano arithmetic, including the axiom of induction.

Answer 3

If you didn't already have this part, it's simple to show $2n = n+n$ using the theorem that multiplication is commutative:

$$ 2 \cdot n = n \cdot 2 = n \cdot S(S(0)) = n + n \cdot S(0) = n + (n + n \cdot 0) = n + (n + 0) = n + n $$

---

Now for the main piece, to show that $2n \neq 1$ for every natural number $n$, we'll suppose the opposite, and see if it leads to a contradiction. That is, suppose that there exists some natural number $n$ so that $2n = 1$.

To start, there's essentially one thing we know about $n$: either $n=0$ or $n=S(m)$ for some natural $m$.

Case 1: $n=0$. But $2n = n+n = 0+0 = 0$, and $1 = S(0)$, so $2n=1$ implies $S(0)=0$. An axiom tells us $S(x)=0$ is never true, so this is a contradiction.

Case 2: $n=S(m)$ for some natural $m$. Then

$$ S(0) = 1 = 2n = n+n = S(m)+S(m) = S(S(m)+m) $$

implying that $S(m)+m = 0$. Since addition is defined by $a+0=a$ and $b+S(c)=S(b+c)$, the equation must match one of the two defining options part by part.

Case 2a: There is some natural number $a$ so that $a=S(m)$, $0=m$, and $a=0$. But then $S(m) = a = 0$, and we know $S(m) \neq 0$. Contradiction.

Case 2b: There are some natural numbers $b$ and $c$ so that $b=S(m)$, $S(c)=m$, and $S(b+c)=0$. But $S(b+c) \neq 0$; contradiction.

Since all cases lead to contradiction, it can't be true that $2n=1$.