Are the Inductive Axiom and the Well ordering Principle really equivalent?

Question

I am new to formal math, so apologies if this is naive.

In class, we stated 4 of Peano's axioms. For the fifth, my professor claimed that we may either write the Well Ordering Principle or the Principle of Induction. I understand that we can arrive at the Well Ordering Principle if we assume the first 4 axioms and induction. However, all the proofs that I've seen going in reverse seem to assume something outside the 4 axioms and well-ordering. An image of this proof is attached. In saying that $m-1\in N$, we assume that every natural number has a predecessor. However, I do not find anything in the 4 axioms and well-ordering that asserts this. I find then Induction to be "better" than the well-ordering principle. But we were adamant in class that they are equivalent.

What am I missing?

Answer 1

There is a set which does not satisfies the usual PA but does satisfy the first 4 axioms and well ordering . See this http://umu.diva-portal.org/smash/get/diva2:1367075/FULLTEXT02.pdf

Answer 2

It is false as explained in Math's answer. However, the Induction Axiom is equivalent to the Well-Ordering Principle plus the axiom

Each $m \ne 0$ has a predecessor.

The argument in your question now applies to prove the Induction Axiom. It remains to be shown that the Induction Axiom implies the above additional axiom.

Let $S_1$ denote the set of all $m \in \mathbb N$ having a predecessor and $S = \{0\} \cup S_1$. We have $0 \in S$. Since by definiton each successor $m+1$ has $m$ as a predecessor, the Induction Axiom implies that $S = \mathbb N$. Hence each $m \ne 0$ has a predecessor.

Answer 3

The answers by Math and Paul Frost are not really correct. Your class seems to be talking about Peano's axioms in the form he devised, namely where induction concerns subsets of $ℕ$. But that induction axiom cannot be used if you do not also have set-existence axioms. Peano had come before FOL (first-order logic) was clearly elucidated, so he did not even realize this problem with his axiomatization of $ℕ$. Similarly, the well-ordering principle that your class is talking about is also about sets, so again it is useless without set-existence axioms.

But it is unclear what set-existence axioms should be added, and there are many choices. This is why any proper axiomatization of $ℕ$ in modern logic does not involve set-induction or set-well-ordering. Rather, they would choose one of the following axiom schemas:

Induction:
$Q(0) ∧ ∀k{∈}ℕ\ ( \ Q(k)⇒Q(k+1) \ ) ⇒ ∀k{∈}ℕ\ ( \ Q(k) \ )$, for every property $Q$ on $ℕ$.

Well-ordering:
$∃k{∈}ℕ\ ( \ Q(k) \ ) ⇒ ∃m{∈}ℕ\ ( \ Q(m) ∧ ∀k{∈}ℕ\ ( \ Q(k)⇒m≤k \ ) \ )$, for every property $Q$ on $ℕ$.

Each of these schemas has infinitely many axioms, one for each property $Q$ on $ℕ$.

You are right to point out that the purported proof uses more than the axioms you were given. In fact, I do not even see why your class gave only four. Anyway, the equivalence requires much more than the axiom Paul Frost provided. In particular, one must have axioms governing the interaction between ordering and addition, for "minimum" to even make sense, which I'm sure your class did not give.

Probably the cleanest way to understand the equivalence is by using the base system PA⁻ (given in the section "Equivalent Axiomatizations"). PA⁻ includes a discreteness axiom:

$0 < 1 ∧ ∀x{∈}ℕ\ ( \ x > 0 ⇒ x = 1 ∨ x > 1 \ )$.

and a 'difference' axiom:

$∀x,y{∈}ℕ\ ( \ x < y ⇒ ∃z{∈}ℕ\ ( \ x+z = y \ ) \ )$.

And these are the key axioms from which we can prove:

$∀x{∈}ℕ\ ( \ x = 0 ∨ ∃w{∈}ℕ\ ( \ x = w+1 \ ) \ )$.

Which is the axiom Paul Frost wants.

But more than that, these axioms of PA⁻ make it actually possible to completely rigorously prove the equivalence between induction and well-ordering. That is, PA⁻ plus Induction can prove every instance of Well-ordering, and PA⁻ plus Well-ordering can prove every instance of Induction. (You might like to try this as an exercise.)

Answer 4

When I read user21820's answer I was somewhat confused because it seemed to contradict what I believed to be "well-known" about the Peano axioms. But he is right, and my answer tries to explain the problem from my (perhaps naive) point of view.

I do not want to go down to the foundations of set theory, but one should be aware that set theory is based on certain axioms. A frequently used approach is ZF (= Zermelo–Fraenkel set theory). In my opinion a nice introduction to set theory is

Halmos, Paul R. Naive set theory. Courier Dover Publications, 2017.

The first four Peano axioms say that we consider a "successor system" $(N,0,S)$ where $N$ is a set, $0\in N$ and $S : N \to N$ is an injective function such that $0 \notin S(N)$. In such a system $N$ cannot be finite. The existence of an infinite set is assured by ZF, and using the machine of set theory we can construct quite a number of distinct models of successor systems. In particular we can construct the natural numbers $\mathbb N$ as we "naively" know them; see e.g. Halmos ($0$ and $S$ are inherent in this construction). Let us call it the standard model.

Let us now consider successor systems satisfying the Induction Axiom. The standard model satisfies the Induction Axiom, and this shows that the existence of a system satisfying all Peano axioms. It is easy to see that all such systems $(N,0,S), (N',0',S')$ are essentially identical which means that that there exists a unique bijection $b : N \to N'$ such that $b(0) = 0'$ and $S' \circ b = b \circ S$.

Using induction we can extend the successor function $S$ to an addition $A : N \times N \to N$ making $N$ a commutative semigroup with $0$ as neutral element. Based on addition we can introduce an ordering on $N$ by defining $n \le m$ if $n + k = m$ for some $k \in N$. It turns out that $(N,\le)$ is a well-ordered set (proof via induction).

But what happens if we consider an arbitrary successor system $(N,0,S)$ without assuming the induction axiom? In that case we can neither define an addition not an ordering. That is, it does not make sense to say that $N$ is well-ordered. This can only be done if we introduce an ordering $\le$ on $N$ as an additional ingredient. In other words, we have to consider systems $(N,0,S,\le)$ - and then certainly need axioms to describe the relation between $S$ and $\le$. We could for example require that $n < m$ implies $S(n) < S(m)$. In that case let us call $(N,0,S,\le)$ an "ordered successor system".

We can now show that if an ordered successor system $(N,0,S,\le)$ satisfies the Induction axiom, then $(N,\le)$ is well-ordered. However, the converse is not true (see Math's answer). It can be repaired by adding Paul Frost's axiom. But be aware that we are no longer working with successor systems $(N,0,S)$, we need an ordering $\le$ as part of the structure.

Moreover, if we consider an arbitrary ordered successor system $(N,0,S,\le)$, we still cannot define an addition on $N$. We can bypass this by appending an addition $+$ to $(N,0,S,\le)$, i.e. by considering systems $(N,0,S,\le,+)$. Of course we need suitable axioms to decribe the relations between $S, \le$ and $+$. This is the purpose of PA$^-$ in user21820's answer.