Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

We discuss Robinson's model theoretic proof of Tarski's theorem on undefinability of truth. We present two other “diagonal-free” proofs of Tarski's theorem, and we compare undefinability of truth to other forms of undefinability in nonstandard models of arithmetic.

Conservativeness has been proposed as an important requirement for deflationary truth theories. This in turn gave rise to the so-called ‘conservativeness argument’ against deflationism: a theory of truth which is conservative over its base theory S cannot be adequate, because it cannot prove that all theorems of S are true. In this paper we show that the problems confronting the deflationist are in fact more basic: even the observation that logic is true is beyond his reach. This seems to conflict (...) with the deflationary characterization of the role of the truth predicate in proving generalizations. However, in the final section we propose a way out for the deflationist — a solution that permits him to accept a strong theory, having important truth-theoretical generalizations as its theorems. (shrink)

In recent decades deflationary theories of truth have been challenged with a technical argument based on the notion of conservativeness. In this paper, I shall stress that conservative extensions of theories and expandability of their models are not equivalent notions. Then, I shall argue that the deflationary thesis of the unsubstantiality of truth is better understood as leveraging on the stronger notion of expandability of models. Once expandability is involved in the argument, some notable consequences follow: the strategy proposed by (...) Hartry Field in response to the conservativeness objection is strongly undermined and even simpler proposals (such as theories based on standard t-sentences) are shown to be quite problematical. (shrink)

The paper presents an outline of the general theory of countable arithmetically saturated models of PA and some of its applications. We consider questions concerning the automorphism group of a countable recursively saturated model of PA. We prove new results concerning fixed point sets, open subgroups, and the cofinality of the automorphism group. We also prove that the standard system of a countable arithmetically saturated model of PA is determined by the lattice of its elementary substructures.

We present a construction of a truth class (an interpretation of a compositional truth predicate) in an arbitrary countable recursively saturated model of first-order arithmetic. The construction is fully classical in that it employs nothing more than the classical techniques of formal proof theory.

The paper presents four open problems concerning recursively saturated models of Peano Arithmetic. One problems concerns a possible converse to Tarski's undefinability of truth theorem. The other concern elementary cuts in countable recursively saturated models, extending automorphisms of countable recursively saturated models, and Jonsson models of PA. Some partial answers are given.

The uniform reflection principle for the theory of uniform T-sentences is added to PA. The resulting system is justified on the basis of a disquotationalist theory of truth where the provability predicate is conceived as a special kind of analyticity. The system is equivalent to the system ACA of arithmetical comprehension. If the truth predicate is also allowed to occur in the sentences that are inserted in the T-sentences, yet not in the scope of negation, the system with the reflection (...) schema for these T-sentences assumes the strength of the Kripke-Feferman theory KF, and thus of ramified analysis up to go. (shrink)

We observe that the classification problem for countable models of arithmetic is Borel complete. On the other hand, the classification problems for finitely generated models of arithmetic and for recursively saturated models of arithmetic are Borel; we investigate the precise complexity of each of these. Finally, we show that the classification problem for pairs of recursively saturated models and for automorphisms of a fixed recursively saturated model are Borel complete.