Wikipedia:Reference desk/Archives/Mathematics/2016 August 9

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 9

Peano Arithmetic

Let φ(x) be a proposition in First order Peano language (1 being the first element) - with x as a free variable, and let y be a number satisfying: ¬φ(1)∧φ(y). I wonder, how one can prove in PA there exists a least number c satisfying φ(c).

Or formally: How can one prove in PA, that $\exists (c)(\phi (c)\land \forall (a,b)(a+b=c\rightarrow \neg \phi (a)))$ ?

A few days ago, I thought I could prove that by the First-order Axiom of Induction, but now I still wonder about how this First-order axiom can entail the well-ordering principle - with regard to φ mentioned above. HOTmag (talk) 09:05, 9 August 2016 (UTC)

There's a couple of errors in what you wrote. Firstly φ(c) might always be false, secondly the a+b+c would give a≤c rather than a<c. First try showing that a≤b defines a total order for the natural numbers. Then try setting up a predicate which is true if its predecessor is true or the predicate you are interested in is true. Dmcq (talk) 10:17, 9 August 2016 (UTC)

No errors at all:

"Firstly φ(c) might always be false ". Impossible, because I have already written that: "let y be a number satisfying: ¬φ(1)∧φ(y) ". It seems like you missed that.

"secondly the a+b=c would give a≤c rather than a<c ". Impossible, because I have already written that: "1 being the first element " (Hence, for every a,b,c, if a+b=c then a is different from c). It seems like you missed that.

Anyways, the right way to use the Axiom of Induction for proving what I've wanted , is by contraposition, as was proven a few days ago here, in the paragraph beginning with the words "Here's the general proof ". In other words: By contraposition, one can formulate the Axiom of Induction as following: "If both: Φ(1), and there exists x not satisfying Φ(x), then there exists c, satisfying Φ(c), but not Φ(c+1) ". Now, when one substitutes, both Φ(n)=∀(k)(k<n → ¬φ(k)), and x=y+1, one receives that there exists a least number c satisfying φ(c). QED. HOTmag (talk) 10:38, 9 August 2016 (UTC)

Yes I missed those out because you said 'Or formally' and I read that rather than the words before. Also I normally assume 0 in Peano Arithmetic like in the Wikipedia article. I was pointing out the steps needed to show your proof works, ignore if you wish. Dmcq (talk) 12:40, 9 August 2016 (UTC)

"I missed those out because you said 'Or formally' ". Yes, and when you were reading the formal proposition with the variable φ, you thought φ was totally free, even though it was not - because it was already referred to by the paragraph followed by the formal proposition.

"I was pointing out the steps needed to show your proof works". Doesn't the proof I gave here contain already all steps? Please notice this proof is totally logical, and does not need the very concept of well-ordering.

Anyways, I'm still interested in everything you say, and that's why I never neglect any response of yours, but rather refer to all of your responses. However, what happened in our case was the following: I asked a question, and was interested in everybody's answer (including your one of course). Some minutes later, I noticed that my question was already answered a few days ago - in the paragraph I mentioned in my first response to you, so I wanted to delete the whole question. When I tried to do so, I noticed that you had already responded, so I responded back (instead of deleting my original question). Anyways, I will be glad if you keep answering my questions, and I also appreciate all of your responses as well. However, this case was really exceptional (I'm guilty), as I've explained above why. HOTmag (talk) 13:26, 9 August 2016 (UTC)