Some Problems in Logic: Applications of Kripke's Notion of Fulfilment

Abstract

This is a study of S. Kripke's notion of fulfilment. Motivated by Paris-Harrington statement, Kripke was looking for a proof of Gödel's Incompleteness Theorem which was model-theoretic, natural (without self-reference), and easy. Fulfilment gives a versatile tool for both Proof and Model Theory. We begin with short proofs to a number of classical results. With two new results: there is an easily definable subring $R$ of the primitive recursive functions such that for any non-principal ultrafilter $D$ on $\omega$, $R/D$ is a recursively saturated model of Peano arithmetic; and for any r.e. theory $\text{T}$ and for any given r.e. set, we can feasibly find a ${\Sigma }_1^0$ formula which semi-represents it in $\text{T}$. We then give a version of Herbrand's Theorem, and of the Hilbert-Ackermann method of proving consistency, answering a problem of D. Guaspari:\[\{\ulcornerϕ\urcorner\inΠ^0_k:ϕ\text{ is }Σ^0_k\text{-conservative over $\text{PA}$}\}\]is a complete ${\Pi }_2^0$ set. We extend H. Friedman's method for results of such as ${\Sigma }_2^1\text{-AC}$ is ${\Pi }_3^1$-conservative over $({\Pi }_1^1\text{-CA}{)}_{<{\epsilon }_0}\upharpoonright$, along with uniform versions\[\forallα<\varepsilon_0\;(Π^1_1\textsf{-CA})_α\upharpoonright\,\vdash\textsf{RFN}_{Π^1_3}({Σ^1_2}\textsf{-AC})\] Then there are some model-theoretic applications, starting with non-$\omega$-models. We extend the theorem of D. Scott involving Weak König's Lemma, and describe the order types of elementary initial segments of recursively saturated models. For $\omega$-models, we extend Friedman's theorem on minimal models of analysis, and develop indicators for countable fragments of ${\mathcal{L}}_{\infty \omega }$, with some representability results in $\omega$-logic. We close with an exposition of the Paris-Harrington statement.

arXiv commentvi+84 pages

Cited by in corpus (1)

• Independence in Arithmetic: The Method of $(\mathcal{L},n)$-Models