Gödel's incompleteness theorems
Warm-upHumanTo which of these theories does the first incompleteness theorem (Rosser's form) apply, assuming each is consistent? Choose all that apply.
To which of these theories does the first incompleteness theorem (Rosser's form) apply, assuming each is consistent? Choose all that apply.
Code a string by , with symbol codes , and . What is the Gödel number of the string ?
In Gödel's form of the first theorem, part (a) shows and part (b) shows . Which hypothesis does part (b) need beyond those of part (a)?
Assume is consistent, and let where is the Gödel sentence of . Which statements are true? Choose all that apply.
Löb's theorem: if , then (for recursively axiomatised). Apply it with the sentence . What do you obtain?
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)?
The Lean theorem halting_incompleteness has hypotheses hre : REPred Provable, hc : Computable nonHalt and sound. Which hypothesis expresses that the theory is recursively axiomatised?
Write encode(codes), which sends a list of positive symbol codes to , and decode(n), which recovers the list (and [] from 1). Why is decode(encode(xs)) == xs guaranteed?