On 17 Aug 2012, at 21:14, meekerdb wrote:

## Advertising

On 8/17/2012 2:43 AM, Bruno Marchal wrote:On 16 Aug 2012, at 22:11, meekerdb wrote:

Are there any explicitly known arithmetic propositions which mustbe true or false under Peanao's axioms, but which are known to beunprovable? If we construct a Godel sentence, which correspondsto "This sentence is unprovable.", in Godel encoding it must be anarithmetic proposition. I'm just curious as to what such anarithmetic proposition looks like.I forgot to mentioned also the famous Goodstein sequences: http://en.wikipedia.org/wiki/Goodstein_theoremGoodstein sequences are sequences of numbers which always convergeto zero, but PA cannot prove this, although it can be proved insecond order arithmetic.I'd say they are not part of arithmetic, since they are generated bysubstituting one number for another - not an arithmetic operation.

`Come on. Arithmetic is Turing universal. You can program substitution`

`with only "E", "s", "0", "+" and "*".`

`It is long and tedious, and not simple prove, but has been done by`

`Matiyasevich (or just Gödel if you add the symbol "A", eliminated by`

`Davis, Robinson and Matiyasevich.`

So I find it hard to see "Goodstein sequences terminate in zero." asa proposition of arithmetic or number theory.

It is.

It seems that they depend on positional notation.

`You can program positional notations with the arithmetical little`

`language sketched above. If you want I can give more detail, but it is`

`obviously rather technical, and very long. You really need the`

`fundamental theorem of arithmetic, the chinese rest lemma, the Gödel`

`beta function, etc. I can give a shorter sketchy description, as I`

`intent to do on the FOAR list soon or later. I can sent the relevant`

`post here on that occasion.`

Bruno

You can google also on "hercule hydra undecidable" to find a game,which has a winning strategy, but again this is not provable in PA.But "machine theologians" are not so much interested in thoseextensional undecidable sentences (in PA), as they embrace theintensional interpretation of the undecidable sentence, likeCON(t), (<>t).BrunoBrentIf Goldbach is un-provable we will never know it's un-provable,we know that such statements exist, a infinite number of them,but we don't know what they are. A billion years from now,whatever hyper intelligent entities we will have evolved intowill still be deep in thought looking, unsuccessfully, for aproof that Goldbach is correct and still be grinding away atnumbers looking, unsuccessfully, for a counterexample to prove itwrong.John K Clark --You received this message because you are subscribed to theGoogle Groups "Everything List" group.To post to this group, send email to everything-list@googlegroups.com.To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com.For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.--You received this message because you are subscribed to the GoogleGroups "Everything List" group.To post to this group, send email to everything-list@googlegroups.com.To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com.For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.http://iridia.ulb.ac.be/~marchal/ --You received this message because you are subscribed to the GoogleGroups "Everything List" group.To post to this group, send email to everything-l...@googlegroups.com.To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com.For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.--You received this message because you are subscribed to the GoogleGroups "Everything List" group.To post to this group, send email to everything-list@googlegroups.com.To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com.For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.

http://iridia.ulb.ac.be/~marchal/ -- You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.