117b – Undecidability and Incompleteness – Lecture 1

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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: