twjudson
Induction turns out not to be equivalent to well-ordering
Who knew?
But in Lars-Daniel Öhman's article in the Intelligencer from last year, he points out that while many (most?) texts (including mine) state this, it is false. Relative to Peano's first four axioms, the induction axiom and the well-ordering principle are not equivalent axioms. In particular, there is an easy to describe model for well-ordering where (finite) induction does not hold - the set of ordinals up to $\omega+\omega$.
Since AATA is explicitly mentioned as one of the texts the author makes clear he "would recommend to ... anyone", I figured I should open an issue once I had time 😄 here is the line:
https://github.com/twjudson/aata/blob/7b4b294371963cdacd8658f7c382e98f2f31a885/src/integers.xml#L208
I would suggest a commit, but find this is the sort of thing that an author would want to keep in his or her individual style, as opposed to fixing a typo.
I’m going to have to think long and hard about this one. I have seen many proofs that the two are equivalent, but I am really not a foundations person.
Tom
On Aug 28, 2020, at 5:28 PM, kcrisman <[email protected]mailto:[email protected]> wrote:
Who knew?
But in Lars-Daniel Öhman's article in the Intelligencerhttps://urldefense.proofpoint.com/v2/url?u=https-3A__link.springer.com_article_10.1007_s00283-2D019-2D09898-2D4&d=DwMFaQ&c=2X_btuPRWkGwRX26NHIotzR6MNUgJAbf6yNNV5-qTbU&r=BQmZUphR5rjzEsIGWo4gOhHhb8A_MVZPtDOMQxdFlh8&m=La6qz9tGggka5x7TYIws5kJ2kNkDFzfQqx9tZoJdZWY&s=Hic8JjSPAE0grHKof3c1JkEUbLvJR-mH37lc4bXnSNI&e= from last year, he points out that while many (most?) texts (including mine) state this, it is false. Relative to Peano's first four axioms, the induction axiom and the well-ordering principle are not equivalent axioms. In particular, there is an easy to describe model for well-ordering where (finite) induction does not hold - the set of ordinals up to $\omega+\omega$.
Since AATA is explicitly mentioned as one of the texts the author makes clear he "would recommend to ... anyone", I figured I should open an issue once I had time 😄 here is the line:
https://github.com/twjudson/aata/blob/7b4b294371963cdacd8658f7c382e98f2f31a885/src/integers.xml#L208https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_twjudson_aata_blob_7b4b294371963cdacd8658f7c382e98f2f31a885_src_integers.xml-23L208&d=DwMFaQ&c=2X_btuPRWkGwRX26NHIotzR6MNUgJAbf6yNNV5-qTbU&r=BQmZUphR5rjzEsIGWo4gOhHhb8A_MVZPtDOMQxdFlh8&m=La6qz9tGggka5x7TYIws5kJ2kNkDFzfQqx9tZoJdZWY&s=IruXIqq_XLbXQ02CeLxm5YZrpLrg4xHrkb-xWMSWgFs&e=
I would suggest a commit, but find this is the sort of thing that an author would want to keep in his or her individual style, as opposed to fixing a typo.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_twjudson_aata_issues_45&d=DwMFaQ&c=2X_btuPRWkGwRX26NHIotzR6MNUgJAbf6yNNV5-qTbU&r=BQmZUphR5rjzEsIGWo4gOhHhb8A_MVZPtDOMQxdFlh8&m=La6qz9tGggka5x7TYIws5kJ2kNkDFzfQqx9tZoJdZWY&s=mhOeF5nwFSBzjsZSKBDDWnsnruc4iRldp1YM7yKpGrw&e=, or unsubscribehttps://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_notifications_unsubscribe-2Dauth_ABN3O25TRONCKGZ34PG23O3SDAVPRANCNFSM4QOSNQJA&d=DwMFaQ&c=2X_btuPRWkGwRX26NHIotzR6MNUgJAbf6yNNV5-qTbU&r=BQmZUphR5rjzEsIGWo4gOhHhb8A_MVZPtDOMQxdFlh8&m=La6qz9tGggka5x7TYIws5kJ2kNkDFzfQqx9tZoJdZWY&s=Z8DD4d917uKSiDyxoIzhMW8eoFIWIVUM-bVGpq09868&e=.
I’m going to have to think long and hard about this one. I have seen many proofs that the two are equivalent, but I am really not a foundations person.
Oh, neither am I! Personally, it's probably easiest to say that both principles hold under the usual axiomatizations of the natural numbers, that they are both useful, and leave it at that.
Sadly, the counterexample makes it pretty clear. The fallacy in proofs that you can get induction from well-ordering apparently, if I read the article correctly, lies in assuming that each element of your well-ordered set has a predecessor - and the first infinite ordinal doesn't. The Intelligencer article is really quite nicely written. See MR0593906 (83f:04001) for the original place the author of the article I mention discovered this (his own introductory book also has this unintentional and unexpected error, which is why he felt he had to write it).
Actually, I'm now realizing this also impacts Exercise 14. So maybe not so simple. Sorry.