Open In Colab

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.

  1. 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.

  2. 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.