What is the definition of the "order" of well order property in Peano Axioms?

Question

For Peano Axiom, mathematical induction is equivalent to well order property.

But in well order property, what is the definition of "order"?

In detail, if we define the "order" $b\le c$ as:

$b = c$ or exist a finite (may be zero) number of natural numbers $a_1,... ,a_n$ such that: $(s(b)=a_1)\ \wedge\ (s(a_1)=a_2)\ \wedge \ ...\ \wedge\ (s(a_n)=c)$

($s(i)=j$ means that, natural number $j$ is the successor of $i$.)

And the corollary:

$\forall i\in \mathbb N \setminus \{0\},\ \exists j\in \mathbb N$ such that $s(j)=i$

will be trivial, since $\mathbb N$ has minimum element $0$ and $\forall i\in \mathbb N$, $i\geq 0$ means that $i=0$ or $s(0)=a_1 ... s(a_n)=i$, so we can prove that exist $a_n$ such that $s(a_n)=i$.

It seems so wired. Because if we don't use well order property, we need to prove the corollary using induction(proof by induction that every non-zero natural number has a predecessor), and the proof steps for me is not trivial.

Troposphere · Answer 1 · 2021-07-29T11:23:10.777

0

Your definition of $\le$ does not work well because it seems to be an infinitary conjunction. The Peano axioms are supposed to be interpreted in a logic that is second (or higher) order but still finitary -- every formula is finite string of symbols.

The usual definition of $\le$ in this setting is $$ x \le y \iff \exists z(x+z=y) $$ after we have defined addition recursively, of course.

We can then phrase the well-ordering property as $$ \tag1 \exists y(y\in A) \to \exists y(y\in A \land \forall z(z< y\to z\notin A)) $$ which is logically equivalent to a second-order formulation of long induction: $$ \tag2 \forall y(\forall z(z<y \to z\in B) \to y\in B) \to \forall y(y\in B) $$ (Namely, let $A$ be the complement of $B$ (or vice versa) and contrapose the outermost $\to$).

It then takes a bit of footwork to prove (2) from the usual second-order mathematical induction axiom $$ \tag3 0\in C \land \forall y(y\in C\to S(y)\in C) \to \forall y(y\in C) $$ and the recursive definition of addition. Basically, to get (2) you would apply (3) with $C=\{y\mid \forall z(z<y\to z\in B)\}$.

edited Jul 29 '21 at 11:23

answered Jul 29 '21 at 11:01

Troposphere

7,158

Why I came up with this question is that I want to use well-ordering property to prove inductions.
But in your proof, if I want to prove inductions, I will have 2 problems:
– HIGH QUALITY Male Human Being Jul 29 '21 at 13:49
The order "$\le$" is recursively defined. But I want to prove inductions, which is the bedrock of the correctness of recursive method. So I can't define anything recursively if I want to get a linear order.

HIGH QUALITY Male Human Being

Jul 29 '21 at 13:49

In the partial order set $(\mathbb N,\le)$, there can be no any partial order relation between two element. $a\not <b$ is equal to $((a,b)\not\in\le) \vee (a\ge b)$, so well-ordering property is not equivalent to your format above:

– HIGH QUALITY Male Human Being Jul 29 '21 at 13:49

score 0 · Accepted Answer · 2021-08-06T15:20:56.800

0

In second order logic you can express the relation $m\le n$ by the formula $$\forall U(Um\land(\forall t (Ut\rightarrow U(St)))\rightarrow Un)$$ where $S$ stands for successor, U is a variable quantifying over all subsets of the domain of discourse, and lowercase variables quantify over objects in the domain.

In first order logic, AFAIK there is no formula $\Psi(x,y)$ with free variables $x,y$ such that $\Psi(x,y)\iff x\le y$. However, if you introduce a binary relation symbol $\le$ into the language you can axiomatize it as follows

$\forall x (x\le x)$
$\forall x\forall y (x\le y \land y\le x\rightarrow x=y)$
$\forall x\forall y\forall z (x\le y \land y \le z \rightarrow x\le z)$
$\forall x\forall y(x\le y \lor y \le x)$
$\forall x (0\le x)$
$\forall x\forall y(x\le y\land x\ne y\leftrightarrow Sx\le y)$

edited Aug 06 '21 at 15:20

answered Jul 29 '21 at 13:53

Get it, and I want to ask another question:
Can I use your first (Second order logic) definition of "order" : $$ ∀U(Um∧(∀t(Ut→U(St)))→Un)\tag{1} $$ to prove the equivalence among first induction, well-ordering property, and Strong induction?

(Because the true question I want to ask is "use well-ordering property to prove induction", so I need a definition of "order" without recursively being defined. And sorry for not mention this question at first.)
– HIGH QUALITY Male Human Being Jul 29 '21 at 16:47
Since in the first answer to my question, for proving the equivalence between well-ordering property and Strong induction we need the "order" to satisfy: $$ \forall x\forall y(x\le y\ \vee\ y\le x)\tag{2} $$ for proving: $$ a\not < b\rightarrow a\ge b $$ (So we can " phrase the well-ordering property as $\exists y(y\in A)→∃y(y∈A∧∀z(z<y→z∉A))$") – HIGH QUALITY Male Human Being Jul 29 '21 at 16:47
And for proving the equivalence between first induction and Strong induction, "order" needs to satisfy: $$ \forall x\ (0\leq x)\tag{3} $$ for proving: $$ 0\in {y∣∀z(z<y→z∈B)} $$ (So we can use $0∈C∧∀y(y∈C→S(y)∈C)→∀y(y∈C)$ to prove $∀y(y∈C→S(y)∈C)→∀y(y∈C)$) – HIGH QUALITY Male Human Being Jul 29 '21 at 16:47
and we need: $$ \forall x\forall y(x\le y\ \wedge\ y\ne x\rightarrow S(x)\le y)\tag{4} $$ for proving: $$ \forall y(\forall z(z<y\rightarrow z\in B)\ \wedge\ y\in B\rightarrow \forall z(z<S(y)\rightarrow z\in B)) $$ And is the order $(1)$ satisfy $(2),\ (3)$ and $(4)$ in any condition?
(And for your second definition of "order", I think we only need to add $\forall y\ (y< S(y))$, and the equivalence of three can be proved.)
– HIGH QUALITY Male Human Being Jul 29 '21 at 16:48
Thx, and I finally know I can use definition $(1)$ to prove $(2)$ $(3)$ $(4)$, when I combine $(1)$ with well-ordering property and other Peano Axioms. $(2)$ is because $\forall x\forall y({x,y}\subseteq\mathbb N)$ and well-ordering property, $(3)$ is because 0 is not a successor, and $(4)$ is because $\forall x\forall y(x\neq y\rightarrow S(x)\neq S(y))$ and the definition of $(1)$. – HIGH QUALITY Male Human Being Jul 30 '21 at 03:12

What is the definition of the "order" of well order property in Peano Axioms?

2 Answers2