We review the statements of the first, second and tenth problems of the list presented by Hilbert during the International Congress in 1900. The tenth problem (*undecidability of Diophantine equations*) will be our immediate focus. The goal is to show that any r.e. set is Diophantine. The undecidability of the halting problem will give the result. Then we will use this characterization as part of the proof of the incompleteness theorems.

Diophantine sets are closed under conjunction and disjunction. `Easy’ number theoretic relations and functions (e.g., being divisible by, the least common multiple) are Diophantine.

### Like this:

Like Loading...

*Related*

This entry was posted on January 23, 2007 at 2:47 pm and is filed under 117b, Undecidability and incompleteness. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply