Skip to content
The Lumenary

Practice · First-year graduate

Gödel's incompleteness theorems

Gödel's incompleteness theorems

Warm-upHuman

To which of these theories does the first incompleteness theorem (Rosser's form) apply, assuming each is consistent? Choose all that apply.

Choose all that apply

Gödel's incompleteness theorems

Warm-upHuman

Code a string s1s2⋯sks_1 s_2 \cdots s_k by 2c(s1)3c(s2)5c(s3)⋯2^{c(s_1)} 3^{c(s_2)} 5^{c(s_3)} \cdots, with symbol codes c(0)=1c(0) = 1, c(=)=5c(=) = 5 and c(S)=3c(S) = 3. What is the Gödel number of the string S0=0S0 = 0?

Gödel's incompleteness theorems

CoreHuman

In Gödel's form of the first theorem, part (a) shows T⊬GTT \nvdash G_T and part (b) shows T⊬¬GTT \nvdash \neg G_T. Which hypothesis does part (b) need beyond those of part (a)?

Choose one

Gödel's incompleteness theorems

CoreHuman

Assume PA\mathsf{PA} is consistent, and let T′=PA+GT' = \mathsf{PA} + G where GG is the Gödel sentence of PA\mathsf{PA}. Which statements are true? Choose all that apply.

Choose all that apply

Gödel's incompleteness theorems

StretchHuman

Löb's theorem: if T⊢ProvT(⌜φ⌝)→φT \vdash \mathrm{Prov}_T(\ulcorner\varphi\urcorner) \to \varphi, then T⊢φT \vdash \varphi (for T⊇PAT \supseteq \mathsf{PA} recursively axiomatised). Apply it with φ\varphi the sentence 0=S00 = S0. What do you obtain?

Choose one

Gödel's incompleteness theorems

CoreFormal

In the Lean file, which statement correctly formalises the abstract form of Tarski's theorem for a diagonalisable system S (with hcompl and hdiag as hypotheses)?

Choose one

Gödel's incompleteness theorems

CoreFormal

The Lean theorem halting_incompleteness has hypotheses hre : REPred Provable, hc : Computable nonHalt and sound. Which hypothesis expresses that the theory is recursively axiomatised?

Choose one

Gödel's incompleteness theorems

StretchComputational

Write encode(codes), which sends a list of positive symbol codes [c1,…,ck][c_1, \dots, c_k] to 2c13c2⋯pkck2^{c_1} 3^{c_2} \cdots p_k^{c_k}, and decode(n), which recovers the list (and [] from 1). Why is decode(encode(xs)) == xs guaranteed?

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.