On 30 Dec 2013, at 08:25, LizR wrote:
I admit I have difficulty understanding how Bruno's UD "runs" inside
arithmetic
Don't push me too much as I really want to explain this to you :)
It is not completely obvious, especially if we want be 100% rigorous.
There are not so much textbook which do that entirely correctly. But
here are three best one:
Boolos and Jeffrey (and Burgess for late edition).
http://www.amazon.com/Computability-Logic-George-S-Boolos/dp/0521701465
Epstein and Carnielli (out of stock!)
http://www.amazon.com/Computability-Computable-Functions-Foundations-Mathematics/dp/0534103561/ref=sr_1_2?s=books&ie=UTF8&qid=1388400218&sr=1-2&keywords=epstein+and+carnielli
Matiyasevitch
http://www.amazon.com/Hilberts-10th-Problem-Foundations-Computing/dp/0262132958/ref=sr_1_1?s=books&ie=UTF8&qid=1388400285&sr=1-1&keywords=matiyasevich
Matiyasevitch shows explicitly how to emulate any Turing machine with
diophantine polynomials.
Oh, well, there is also the old good Stephen Kleene 1952 book, and
many by Smullyan (although like Gödel they do that in PA or
equivalent, and not in RA, which ask for more verification.
Matiyasevitc shows that for diophantine equation, which means that it
makes the RA universal quantifier not needed, and so gives the
stronger result.
The main deep idea is already in Gödel 1931.
May be the shortest path is to explain the phi_i and use Kleene
predicate to explain that equalities involving the phi_i are made
arithmetical by the use of Kleene's predicate, but this needs the
Gödel coding, which is long to describe, and even longer to prove that
it does correctly the job.
I am thinking how to explain this without going in the technical
details.
Bruno
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
