Definition and equivalent formulations#
Exercise 78
Prove that there is no partial computable function \(f: N\to N\) such that for all \(p\), if \(W_p \neq \emptyset\), then \(f(p)\) is the least element of \(W_p\).
Exercise 79
To contrast with the previous exercise, prove that there is a partial computable function \(f: N\to N\) such that for all \(p\), if \(W_p \neq \emptyset\), then \(f(p)\) is some element of \(W_p\).
Relation to K#
This is a placeholder for missing text.
\(\Sigma_1\) form#
This is a placeholder for missing text.
Exercise 80
If you know about first-order logic, you should believe that the relation \(\{ \phi : \vdash \phi\}\) is decidable.
If you also know about an axiomatic set theory such as Zermelo-Fraenkel set theory (ZFC), check that the set of theorems of ZFC is a computably enumerable set.
Is the set of theorems of ZFC decidable? Why or why not?
Closure properties of the c.e. sets#
This is a placeholder for missing text.
Simple sets#
This is a placeholder for missing text.