On 17 Aug 2012, at 21:14, meekerdb wrote:
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 must
be true or false under Peanao's axioms, but which are known to be
unprovable? If we construct a Godel sentence, which corresponds
to "This sentence is unprovable.", in Godel encoding it must be an
arithmetic proposition. I'm just curious as to what such an
arithmetic proposition looks like.
I forgot to mentioned also the famous Goodstein sequences:
http://en.wikipedia.org/wiki/Goodstein_theorem
Goodstein sequences are sequences of numbers which always converge
to zero, but PA cannot prove this, although it can be proved in
second order arithmetic.
I'd say they are not part of arithmetic, since they are generated by
substituting 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." as
a 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 those
extensional undecidable sentences (in PA), as they embrace the
intensional interpretation of the undecidable sentence, like
CON(t), (<>t).
Bruno
Brent
If 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 into
will still be deep in thought looking, unsuccessfully, for a
proof that Goldbach is correct and still be grinding away at
numbers looking, unsuccessfully, for a counterexample to prove it
wrong.
John K Clark
--
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
.
--
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
.
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-
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 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
.
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.
