Talk:Equivalence of Well-Ordering Principle and Induction

From ProofWiki
Jump to navigation Jump to search

It's a little silly to talk about equivalence between tautologies - it would seem more meaningful (and useful) if this statement were generalized to induction on well-founded or well-ordered sets. --asalmon

Why? --GFauxPas 09:58, 29 November 2011 (CST)
If any two statements are tautologies, then they are automatically equivalent. -Andrew Salmon 15:02, 29 November 2011 (CST)
That strong and weak induction are logically equivalent holds even if they're not tautologies, they can all be false as well, or all be axiomatic (and actually I learned them as being axiomatic, not as being theorems). No? --GFauxPas 15:08, 29 November 2011 (CST)

Missing justification in the PCI implies WOP part.

In the line:

Now if $k + 1 \in S$ it follows that $k + 1$ would then be the minimal element of $S$.

How do we know that there is no number between k and k + 1 ? --TonyH 08:05, 9 May 2012 (EDT)

From the structure of $\N$ as derived either by the Peano axioms or the Naturally Ordered Semigroup technique. --prime mover 08:31, 9 May 2012 (EDT)
Well, the same could be said about every fact we know about math. Isn't the purpose of this site to give explicit proofs?--TonyH 09:02, 9 May 2012 (EDT)
Once we assume that natural numbers exist, we assume the peano axioms exist and that the natural numbers satisfy them. One of the peano axioms is: "$\forall m, n \in \N: s \left({m}\right) = s \left({n}\right) \implies m = n$, where $s$ is a Definition:Successor Mapping. Would it help to look at the expression $n + 1$ not as "the sum of $n$ and $1$", but as the "successor of $n$", i.e., the "immediate next number after $n$"? The definition of $s$ then guarantees that $s\left({n}\right)$ is unique for every $n$, and you don't need to prove definitions. --GFauxPas 09:37, 9 May 2012 (EDT)
As GFP says, the $+1$ function has already been established as a pre-existing definition, upon which this proof rests. Yes okay, a link is needed to it. This will be accomplished in due course. --prime mover 09:50, 9 May 2012 (EDT)
... happy now? --prime mover 13:01, 9 May 2012 (EDT)

One could argue that it would be better were the three abbreviations used in the proof links to the appropriate pages. However, I would like someone backing me here, before I put myself through this exercise. --Lord_Farin 13:26, 9 May 2012 (EDT)

No reason why not. Don't know why I didn't do it like that in the first place. --prime mover 14:15, 9 May 2012 (EDT)
...And 't is done. --Lord_Farin 17:54, 9 May 2012 (EDT)

WOP does not imply PMI

The proof that WOP implies PMI assumes that the minimal element of S' has a predecessor because it is nonzero. However, in Peano Arithmetic, the statement "every nonzero number has a predecessor" is a theorem that requires PMI to prove.

Furthermore, consider a model {0, 1/2, 1, 3/2, 2, 5/2, ...}. It is consistent with all the axioms of PA except induction, yet it is well-ordered. Therefore, PA - PMI + WOP + NOT(PMI) is consistent.

TheDerkus (talk) 17:08, 29 June 2016 (UTC)

We infer only that the definition of $\N$ in this theorem statement is not "a model of $\sf PA - PMI$". A valid critique of this page is therefore that it is unclear what the definition of $\N$ is. I checked only Deskins, who uses Axiom:Axiomatization of 1-Based Natural Numbers and discusses these theorems as suggesting potential replacements for Axiom F on said page.
A similar investigation should be done for the other sources -- currently it's unclear which definition of $\N$ is used, and if we want to discuss "$\N$ without $\sf PMI$", we'd better make sure that we specify clearly what the $\N$ in this phrase is... So, thank you for your valid critique. — Lord_Farin (talk) 18:00, 29 June 2016 (UTC)
The proof is given on $\N$ only. The definition of WOP as given in the sources available to the original author of this page is that it specifically refers to subsets of $\N$. Hence, while it may indeed be true that the model you cite has the properties you state, as the set in question is not a subset of $\N$, this proof does not apply to it.
The proof is copied (after interpretation and amplification) from the UWO website. The truth of the mutual equivalence of all these statements is established (stated, at least, if not actually explicitly proved) in most axiomatic treatments. While I accept that this is no more than an argumentum ad verecundiam, either the proof as given here is a serious misrepresentation of the source cited, or the proof cited there is invalid, or there exists this glaring fallacy at the very heart of the axiomatic development of number theory from e.g. ZFC.
Please feel free to either a) fix up this proof so it accurately reflects the required proof, or b) produce a solid and watertight proof, or c) publish your refutation in the context of this treatment and make it clear explicitly where this fundamental philosophical gap lies in the structure of $\N$. --prime mover (talk) 22:14, 29 June 2016 (UTC)