Original question: Prove that $1<2<3<4$,etc in a Peano System
That is the definition of Peano system by the used textbook.
Peano Systems: By a Peano System we mean a set $P$, a particular element 1 in $P$, and a singulary operation $S$ on $P$ such that the following axioms are satisfied.
$(P1)$: 1 is not the successor $S(x)$ of any object $x$ in $P$. In symbols, $(\forall x)(S(x) \neq 1)$.
$(P2)$: Different objects in $P$ have different successors. This can be formulated as follows:
$$(\forall x)(\forall y)(x \neq y \Rightarrow S(x) \neq S(y))$$.
$(P3)$: Principle of Mathematical Induction: Any subset of P containing $1$ and closed under the successor operation must be identical with $P$. This can be symbolically rendered as follows:
$$(\forall B)([B \subseteq P \land 1 \in B \land (\forall x)(x \in B \Rightarrow S(x)\in B)]\Rightarrow P=B)$$
Such a Peano system will be denoted by a ordered triple $(P,S,1)$, $P$ is called the underlying set, $S$ the successor operation, and $1$ the distinguished element.
Consider a standard Peano System $(\mathbb{N},S,1)$, where $S:\mathbb{N}\rightarrow\mathbb{N}$ is defined as $S(x) = x+1$, and we have the following theorems.
- $(\forall x)(x=1 \lor (\exists y)(x = S(y))$
- $(\forall x)(S(x) \neq x)$
- x < S(x)
- $\lnot(\exists y)(x < y < S(x))$
- $x \neq 1 \Rightarrow $ 1 < x
$x<y$ is defined as a shorthand for $(\exists z)(x+z = y)$.
We have addition defined also, with commutative, associative and cancellation law.
edit 3
As the question got considered ambiguous because the usage of "…" or "etc", I tried to do some reasearch seeking for what could be the meaning of "$1<2<3<4$,etc", and as I stated in a commentary, this exercise is present in a section about order relation. Thus I started looking for order properties and related definitions.
First I reached a paper about relations where the author a give quick explanation about order relations and show the equivalence between a Partially-ordered sets(poset) and Directed Acyclic Graphs(DAG). In section 4.1 and 4.2 it is presented a Theorem which states that a "poset has no directed cycles other than self-loops.
The previous mentioned paper show a pattern $a_1 \leq a_2 \leq a_3 \leq a_4 …$ which is similar to the pattern stated in the question but its not the same. From this point I tried to found the difference from orders which is established with $<$ instead of $\leq$. Then I found the definition about strict and non strict partial orders, where the DAG got related to strict order $<$.
But after this point I wanted to understand what is the difference between the total and partial order, thus it made me to reach the wikipedia page about total order, which in fact have a little section defining chains as: "The term chain is a synonym for a totally ordered set" and a more specific case, Ascending Chain as "totally ordered set having a (unique) minimal element", from this section I have gone to the definition of Ascending Chain Condition which states in the first line the assertion the non existence of a strictly ascending sequence $a_1<a_2<a_3…$
Taking a look on some definitions as strictly ascending order or strictly increasing sequence. I have found they all capture the same concept as strictly ascending sequence which capture the same concept stated by the author of the original question.
Thus I think the question can be stated in a non ambigous way, and Im changing the title according to those findings.
From "Prove "$1<2<3<4$",etc" to "Prove that the entire underlying set in a Peano System with strict order relation($<$) forms a unique strictly ascending sequence".
end edit 3
Here is my atempt:
From $(5)$ its clear that $(\forall x)(1<x)$, thus the order starts with,
$1 < x$, where from $(1)$, $x=1 \lor (\exists u)(x = S(u))$, if we assume $x \neq 1$ then by $(3,4)$ we have also that $u<S(u)$ and no one element in $\mathbb{N}$ is between $u$ and $S(u)$.
Now if we take $S(S(u))$ we have also by (3,4) that $S(u) < S(S(u))$ and there is no element between them. Thus for any $x \neq 1$ we have $x=S(u)$ where $u < S(u) < S(S(u))$.
If we let $x=S(1)$ or $2$ we get: $1 < S(1) < S(S(1))$, or $1 < 2 < 3$.
If we let $x=S(S(1))$ or $3$ we get $S(1) < S(S(1)) < S(S(S(1)))$, or $2<3<4$
By $(5)$ we have that $4<1)$
Thus if we let $x=4$ we get $3<4<5$,
By $(5)$ we have that $1<5$ and by transitivity of $<$ when $x=3$ we have that $[2<3 \land 3<4]\Rightarrow 2<4$, but if $[2<4 \land 4<5] \Rightarrow 2<5$
Thus we have $1<2<3<4<5…$
Edit 1 begin
I noticed using the definition of $<$, that if $x < y$ then there we have $x+p = y$ for some $p \in \mathbb{N}$ and from this we have that $S(x+p) = S(y)$, thus $(x+p)+1 = s(y)$ and from commutativity a associativity of addition $(x+1) + p = s(y)$, so $S(x) + p = S(y)$ then by definition $S(x) < S(y)$, so $x<y \Rightarrow S(x) < S(y)$.
Here is we start from $1<2$ which is true by $(5)$, and from previous conclusion $1<2 \Rightarrow 2<3$, but if $2<3$ then $3<4$…
I still not knowing how to avoid the (…)
Edit 1 end
Edit 2 begin
Here Im trying another approach which follows from the idea on edit 1.
First we have that $x<S(x)$, by (3), from this we know that $x+p = S(x)$ for some $p$ in $\mathbb{N}$, namely $p=1$, from this we have that $S(x+p) = S(S(x))$ and then $S(x)+p = S(S(x))$, so by definition of $<$ we have that $S(x)<S(S(x))$ and therefore $x<S(x) \Rightarrow S(x)<S(S(x))$.
We have that $1<S(1)$ since $1+1=S(1)$, thus if we take a initial segment $I_n$ from $\mathbb{N}$ from $1$ up to $n$. Lets say $n=4$ we have defined $I_4 = \{1,2,3,4\}$ First we have that $1<2$ is true by (5) then we have that $1<2 \Rightarrow 2<3 \Rightarrow 3<4$. It can be encoded as $(1<2) \land (2<3) \land (3<4)$ from this follows that $1<2<3<4$.
Now let $A = \{x : x \in \mathbb{N} \land x < S(x)\}$, first we have that $1 \in A$ since $1 \in A \land 1 < S(1)$, now we assume that $x \in A$, thus we have that $x \in \mathbb{N} \land x<S(x)$, but we have that $x<S(x) \Rightarrow S(x) < S(S(x))$, then $S(x) \in A$. We have show that $x \in A \Rightarrow S(x) \in A$. then by mathematical induction $A = \mathbb{N}$.
As we have $x<S(x)$ for any $x \in \mathbb{N}$, now we take the some initial segment $I_n$ of $\mathbb{N}$ from 1 up to $n \in \mathbb{N}$, and we have that $1<2<3<4,etc$ holds true in $I_n$, where $etc$ goes up to $n$, as $n$ is arbitrary $1<2<3<4,etc$ holds true in $\mathbb{N}$.
Edit 2 end
I think the same proccess can be repeated using all $x \neq 1$ in $\mathbb{N}$, but the usage of $…$(dots) turn what I need to do imprecise, so how Im supposed to do this proof?
Best Answer
Let’s prove that $<a_i>$
Where:
$a_0=1$
$a_i=S(a_{i-1})$
is a strictly ascending sequence.
We need to prove two things: