6
$\begingroup$

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? Taken From http://www.math.utah.edu/~bronson/files/4030-f18/4030-notes.pdf

$\endgroup$
4
  • 1
    $\begingroup$ @MauroALLEGRANZA I think that they are not equivalent $\endgroup$
    – Lobic
    Oct 18 at 9:30
  • 1
    $\begingroup$ Look at link.springer.com/content/pdf/10.1007/s00283-019-09898-4.pdf. $\endgroup$
    – Paul Frost
    Oct 18 at 9:38
  • $\begingroup$ It's not stated that $m-1\in\Bbb N$ for every $m\in\Bbb N$, just that this holds if $m\ne0$. With that restriction this is one of the axioms $\endgroup$ Oct 18 at 10:04
  • 1
    $\begingroup$ @DavidC.Ullrich The existence of a predecessor for $m \ne 0$ is not required by the first four Peano axioms. $\endgroup$
    – Paul Frost
    Oct 18 at 10:12
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I found that helpful! Thanks. $\endgroup$
    – Sal_99
    Oct 18 at 18:27
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, that made sense to me. Thanks!! $\endgroup$
    – Sal_99
    Oct 18 at 18:29
2
$\begingroup$

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.)

$\endgroup$
11
  • 2
    $\begingroup$ So you say the the "classic" Peano axioms are inadequate. Of course we need a set theoretic base (like ZF), and perhaps this was not properly addressed in the OP's class, but ZF + Peano do not seem that bad. One can define addition via induction and introduce the "natural" ordering via addition. Or is this approach too naive? At least it can be found in many textbooks written by renowned mathematicians (for example Paul Halmos). $\endgroup$ Oct 19 at 9:02
  • 1
    $\begingroup$ @KritikerderElche: ZF + Peano does not seem that bad? No, that's extremely bad. ZF has the Infinity axiom and already proves Peano including Induction and Well-ordering (on $ℕ$) and much much much more. Thus it would make absolutely no sense to say Induction and Well-ordering are equivalent over ZF + Peano-minus-induction, because ZF already proves both. As I already said in my answer, the way to understand the equivalence is by having PA− as the base system. $\endgroup$
    – user21820
    Oct 19 at 9:12
  • 1
    $\begingroup$ @Sal_99: No problem, you're welcome! It's very good that you are thinking hard about what you're being told in class. Feel free to clarify any point in my answer, and no hurry at all! $\endgroup$
    – user21820
    Oct 19 at 12:46
  • 1
    $\begingroup$ @user21820 Of course you can very well talk about the axioms given in the paper which use set theoretic principles . It does seem like judging from the image that op was doing something like this $\endgroup$
    – Lobic
    Oct 19 at 15:41
  • 2
    $\begingroup$ Your answer is absolutely correct and it is much better than mine. But do you think it is really helpful for a beginner ("I am new to formal math, so apologies if this is naive")? $\endgroup$
    – Paul Frost
    Oct 22 at 22:15
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Your understanding of my answer is okay, and I edited the first line accordingly. But I wish to emphasize that your talk of "successor systems" is a second-order notion, which is not really a good thing because what subsets of $ℕ$ exist now would depend on the meta-system MS. It turns out that to be able to prove the facts you desire about successor systems, your MS would need to already have induction or well-ordering. This sort of implies that you are not really getting a true equivalence over a weaker base system; you only get ( if meta-induction holds then ( induction ⇔ well-ordering ) ). $\endgroup$
    – user21820
    Oct 20 at 14:18
  • 1
    $\begingroup$ @user21820 The axioms that the op is using are set theoretically stated. This is not first order PA agreed. But you can still talk about sets (and functions and relation) satisfying those axioms that’s what Kritikar is saying. $\endgroup$
    – Lobic
    Oct 20 at 17:22
  • $\begingroup$ @Kritiker Correct me if I’m wrong $\endgroup$
    – Lobic
    Oct 20 at 17:37
  • 1
    $\begingroup$ @Math I am not an expert in formal logic and its relation to set theory, but I think you are right. My main point was that an arbitrary "successor system" does not have an inherent ordering, hence it does not make sense to say it satisfies the Well Ordering Principle. $\endgroup$ Oct 20 at 23:00

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.