Solution

ID: past-exam-of-the-model-theory-and-godel-s-incompleteness-theorems-course-of-the-university-of-oxford/2007/a/1/b/solution

Bounded completeness of an arithmetic theory means that every bounded arithmetic first-order sentence true in the standard natural numbers is provable in . If is first-order consistent and proves a false bounded arithmetic sentence , bounded completeness of an arithmetic theory also proves its true bounded negation, a contradiction. Conversely, if every bounded theorem is true, cannot be inconsistent, because inconsistency would prove the false bounded arithmetic sentence . Thus
If is one-consistent and proves with bounded matrix, that existential sentence cannot be false: otherwise every would be a true bounded arithmetic sentence and hence provable, contrary to one-consistency. Thus has Sigma-1 soundness.
Conversely, Sigma-1 soundness excludes inconsistency. If , it supplies a standard witness with true. Bounded completeness of an arithmetic theory proves , so first-order consistency forbids a formal proof of . Hence there cannot simultaneously be refutations of all standard instances. Therefore
Finite blocks of existential logical variables are treated as finite tuples of witnesses, with the same argument.

New to topics? Read the docs here!