2
$\begingroup$

In Terence Tao's book Analysis I, the definition of $1$ is given right after stating the first two axioms, namely the following axioms,

Axiom 1. $0$ is a natural number.

Then Tao elaborates the notion of successors (the successor of $n$ is taken there as $n{++}$) and then states the following axiom,

Axiom 2. If $n$ is a natural number, then $n{++}$ is also a natural number.

After stating these two axioms he then gives the following definition,

Definition We define $0{++}=1$.

My objection is regarding the place of occurrence of this definition in the book. In my opinion the definition shouldn't occur in the text until we have proved that $0{++}=1$.

I think that the statement $0{++}=1$ of course can be taken as a definition of $1$ but only when we have proved the following property of our intuitive natural number system, loosely speaking, $$\color{blue}{\text{There doesn't exist any natural number between $0$ and $1$.}}$$ The necessity for proving this statement is that without it we cannot say that the construction of our natural number from Peano Axioms is complete (note that Axiom of Induction only excludes the existence of any other "non-natural" elements but so far as I know, it doesn't trivially exclude the possibility of having natural number between $0$ and $0{++}$). For if there really exists any natural number between $0$ and $0{++}$, the resulting system doesn't (apparently) contradicts any one of the Peano Axioms but still clearly it isn't the natural number system that we have known since our childhood and which is our objective to treat formally. And since one of the most important objective of this axiomatic treatment of natural number is to formalize our notion of natural numbers, we mustn't include in our formalized system any property that contradicts out intuitive notion of natural numbers. Otherwise the whole point of construction becomes meaningless.

Up untill now I can't find any rigorous proof of the fact that I have stated above and which, using logical operators becomes (all the variables indicating natural numbers), $$\color{red}{\boxed{\not\exists b:0<b<0{++}}}$$

Is there any proof of this result? Can anyone elaborate where am I wrong?

I have discussed this problem with some of my friends but none of them could give me a satisfactory answer. I thought that maybe we should take this as an axiom.

In case the remaining Peano Axioms are needed,

Axiom 3. $0$ is not the successor of natural number; i.e. we have $n{+}{+}\neq 0$ for every natural number $n$.

Axiom 4. Different natural numbers must have different successors; i.e., if $n, m$ are natural numbers and $n\neq m$, then $n{+}{+}\neq m{+}{+}$.

Axiom 5.(Principle of Mathematical Induction) Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n{+}{+})$ is also true. Then $P(n)$ is true for every natural number $n$.

The definition of $+$ is given as,

Definition of $+$

$0+m:=m$ and supposing that we know to define $n+m$ we define, $$(n{++})+m:=(n+m){++}$$

Also for the notion of Ordering of natural numbers,

Definition of $\ge$ and $>$

Let $n$ and $m$ be natural numbers. We say that $n$ is greater than or equal to $m$, and write $n \ge m$ or $m \le n$, iff we have $n = m + a$ for some natural number $a$. We say that $n$ is strictly greater than $m$, and write $n > m$ or $m < n$, iff $n \ge m$ and $n \ne m$.


After I have asked it here in the comment what Emil Jeřábek pointed out I can't understand. Specifically, I don't understand,

"The only thing that you need to prove before introducing a definition of a constant is that there exists a unique element satisfying the definition. ..."

Also,

"In any case, the property you want is stated right after the definition of < in Proposition 2.2.12, and you are asked to prove it yourself in Exercise 2.2.3,.."

It is because the Proposition 2.2.12, is, (text quoted),

Proposition 2.1.12 (Basic properties of order for natural numbers)

(a) (Order is reflexive) $a \ge a$.

(b) (Order is transitive) If $a \ge b$ and $b \ge c$, then $a \ge c$.

(c) (Order is anti-symmetric) If $a \ge b$ and $b \ge a$, then $a = b$.

(d) (Addition preserves order) $a \ge b$ if and only if $a+ c \ge b +c$.

(e) $a< b$ if and only if $a{++}\le b$.

(f) $a < b$ if and only if $b = a + d$ for some positive number $d$. (A positive number is a natural number which is not equal to $0$)

$\endgroup$
  • $\begingroup$ "...but only when we have proved the following property of our intuitive natural number system, loosely speaking, There doesn't exist any natural number between 0 and 1." wrong. we just take it to be the definition $\endgroup$ – Mister Benjamin Dover Jan 10 '15 at 11:53
  • 1
    $\begingroup$ So another person may come up with his/her favourite formula $\phi$, and argue that you are not allowed to define $1$ as $0++$ until you have proven $\phi$ to be true. $\endgroup$ – zarathustra Jan 10 '15 at 12:28
  • 1
    $\begingroup$ @user170039 Because writing mathematics lies in abbreviations. You start with some primitive symbols which constitute what one names language and because it is a drag to use only the primitive symbols, one abbreviates formulas by other symbols. This action is not mathematical, it's a device we use to facilitate communication. But still, this is something that must be done with care. (...) $\endgroup$ – Git Gud Jan 10 '15 at 12:44
  • 1
    $\begingroup$ (...) In the context of real numbers, if you decide to say 'I want to abbreviate one of the zeroes of $x^2+1$' by $i$ you will run into problems because there isn't any real number that satisfies the equation, the existence and uniqueness fails due to the lack of existence. If you instead consider $x^2-2$ and decide to abbreviate the roots by $r$, the uniqueness fails, because $r$ can be either $-\sqrt 2$ or $\sqrt 2$ and by using $r$ will be referring to two distinct objects by the same name, which is, at best, very bad practice. $\endgroup$ – Git Gud Jan 10 '15 at 12:48
  • 1
    $\begingroup$ @user170039 Certain people do not worry about this sort of thing. You can find them in most fields of mathematics, but they abound in non-(Algebra or Logic). There has 'always' been a feud between those who care about these things and those who don't. I'm sure you'll find many others who think that this retarded at all levels of mathematics. You're welcome. $\endgroup$ – Git Gud Jan 10 '15 at 12:55
1
$\begingroup$

Starting with the first-order Peano Axiom including the recursive axioms for sum, and avoiding the use of the defined symbol $1$, we have to prove that :

$\lnot \exists k (x < k \land k < S(x))$,

where $S(n)$ is the successor function (avoiding thus the cumbersome symbol : $n++$).

We need the definition of $<$; we will use :

$n < m$ iff $\exists z(m = n + S(z))$.

i) First, we will prove that :

for all $n, \ n < S(n)$.

According to the definition of $<$, we have to prove that : $\exists z(S(x) = x + S(z))$.

But (first axiom for $+$) : $x = x + 0$; thus : $S(x)=S(x+0)$.

By second axiom for $+$ : $S(x) = x + S(0)$.

Thus, by $\exists$-introduction :

$\exists z (S(x) = x + S(z))$.

ii) Now, assume that, for some $k$ :

$x < k \land k < S(x)$.

From $x < k$, by the definition of $<$, we have that :

$k = x + S(z_1)$, for some $z_1$;

in the same way :

$S(x) = k + S(z_2)$.

So : $S(x) = x + S(z_1) + S(z_2)$; using the axiom for $+$ we have that :

$S(x) = x + S(z_1 + S(z_2)) = x + S(S(z_1 + z_2)) = S(x + S(z_1 + z_2))$.

By property of $S$, we have that :

$x = x + S(z_1 + z_2)$.

But : $x = x + 0$; thus :

$S(z_1 + z_2) = 0$

i.e. $\exists z (S(z)=0)$, contrary to axiom : $\forall x \lnot (S(x) = 0)$.

Thus, we have proved that :

$\lnot \exists z (x < z \land z < S(x))$.


About :

$∀n(n=0 \lor ∃b(n=S(b)))$

this is : $∀n(\lnot(n = 0) \rightarrow ∃b(n=S(b)))$ and is provable by Induction on $n$.

Basis : $n=0$. We have that $0=0$; thus, by tautological consequence (with the tautology : $P \rightarrow (\lnot P \rightarrow Q)$) :

$\lnot (0 = 0) \rightarrow ∃b(0=S(b))$

Induction step : we have $S(n)=S(n)$; thus, by $\exists$-introduction : $\exists b (S(n)=S(b))$ and by tautological consequence (with the tautology : $P \rightarrow (Q \rightarrow P)$) : $\lnot (S(n) = 0 ) \rightarrow \exists b(S(n)=S(b))$.

Thus, having proved it for $0$ and for $S(n)$, we conclude by Induction with :

$\forall n (\lnot (n = 0) \rightarrow \exists b (n=S(b)))$.

Alternatively :

Basis : $n=0$. We have that $0=0$; thus, by $\lor$-introduction :

$0 = 0 \lor ∃b(0=S(b))$

Induction step : we have $S(n)=S(n)$; thus, by $\exists$-introduction : $\exists b (S(n)=S(b))$ and by $\lor$-introduction : $S(n)=0 \lor \exists b(S(n)=S(b))$.

Thus, having proved it for $0$ and for $S(n)$, we conclude - again by Induction - with :

$\forall n ((n = 0) \lor \exists b (n=S(b)))$.

$\endgroup$
  • $\begingroup$ I have just finished reading your argument. If I got your idea correctly then your basic argument is that $n<m<n{++}\implies (m=n+r)\land(n{++}=m+s)\implies 0{++}=r+s$ where $r$ and $s$ are positive numbers. Am I correct so far? It would be very good if you can write $S(x)=x{++}$. $\endgroup$ – user 170039 Jan 10 '15 at 13:22
  • $\begingroup$ @user170039 - from the "double inequality" we derive : $n++=n+(r++)+(s++)$, for $r,s$ numbers. From this : $n++=n+(((r+s)++)++)$ an thus, by "functionality" of the successor function $S$ : $n = n + ((r+s)++)$, which is de required contradiction. $\endgroup$ – Mauro ALLEGRANZA Jan 10 '15 at 13:28
  • $\begingroup$ But the definition of $>$ can be stated as $n>m\iff \exists b(\ne 0)\mid n=m+b$. How do you know that that $b$ should be of the form, say, $x{++}$? Aren't you implicitly assuming for every positive natural number $v$ there exists a natural number $u$ such that $u{++}=v$? If that's so then please read the linked questions. $\endgroup$ – user 170039 Jan 10 '15 at 13:34
  • 1
    $\begingroup$ This follows directly from the axioms, excluding 0 all the other numbers are the successor of a number $\endgroup$ – Alessandro Codenotti Jan 10 '15 at 13:39
  • $\begingroup$ @user170039 - see the expanded answer; we have proved that $\forall n((n \ne 0) \rightarrow \exists z(n=S(z)))$. $\endgroup$ – Mauro ALLEGRANZA Jan 10 '15 at 16:55
1
$\begingroup$

We define $1$ as the successor of $0$, but we need to define an order relations on the naturals numbers before being able to argue that there are no natural numbers in between $0$ and $1$.

I'm going to use $S(n)$ as the successor of $n$ instead of $n++$ because it gets confusing when writing additions otherwise.

You gave the definition of the usual order relation in your question so i won't repeat it here, but note that it relies on addition, so we need to define that first, this is usually done recursively:

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

Now we can argue that $0<1$ since $0+S(0)=S(0)=1$.
We can also show that $1<2$ since $S(0)+S(0)=S(S(0)+0)=S(S(0))$ (of course we need to define $2=S(S(0))$ before)

We can show that $S(n)=n+1$ since $n+1=n+S(0)=S(n+0)=S(n)$ (for comodity of notation later on)

Now we need to show that if $k>1$ then $k+1>1$.
We now that $k=1+n$ for some integer $n$.
we also now, by the axioms, that if $a=b$ then $a+1=b+1$ thus $k+1=1+n+1$ and since $n+1$ is the successor of $n$ then $k+1$ can be written as $1+b$ for some integer $b$.

So, we know that $0<1$, $1=1$ and all the other integers are $>1$, as we wished to prove.

I've written this a bit in a hurry, so I hope it's clear enough

$\endgroup$
  • $\begingroup$ yes, and it seems to me that this question was already answered in another question you asked, so i don't really understand what is still unclear to you. When we say $1=S(0)$ we do not know that there isn't a number between $0$ and $1$, after defining addition and the order relation we can show that this is indeed the case, as I have (hopefully, if I didn't make any mistake) done in my answer $\endgroup$ – Alessandro Codenotti Jan 10 '15 at 12:46
0
$\begingroup$

The set $\mathcal M=\{0,1,1\!+\!+,\dots\}$ satisfies axiom 1-4. Suppose $\mathbb N$ satisfies axiom 1-5. Now, $0\in \mathcal M$ and $n\in \mathcal M\implies n\!+\!+\in \mathcal M$ (by definition), which implies $\forall n\in\mathbb N:n\in \mathcal M$ (by induction) why $\mathbb N\subseteq \mathcal M$.

Then show $0<b<1\implies \neg\exists n\in \mathcal M: n\!+\!+=b$.

$\endgroup$
  • $\begingroup$ If you are going to use set theory then there I think that it can be done in a much simpler way. Suppose that such $b$'s exist. Then consider the set of all such "troublesome natural numbers". Call it $\mathfrak{N}$. Now let, $\mathcal{N}:=\{b:n<b<n{++}\}$. Then define $\mathbb{N}=\mathfrak{N}\setminus\mathcal{N}$. $\endgroup$ – user 170039 Jan 11 '15 at 5:08
0
$\begingroup$

Axiom 2 can be restated:

$\forall x\in N: \exists y\in N: y=x++$

So, the definition $1=0++$ is just an application of this axiom. You are simply naming the successor of $0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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