Book contents
- Frontmatter
- Contents
- Preface to the Fifth Edition
- COMPUTABILITY THEORY
- BASIC METALOGIC
- FURTHER TOPICS
- 19 Normal Forms
- 20 The Craig Interpolation Theorem
- 21 Monadic and Dyadic Logic
- 22 Second-Order Logic
- 23 Arithmetical Definability
- 24 Decidability of Arithmetic without Multiplication
- 25 Nonstandard Models
- 26 Ramsey's Theorem
- 27 Modal Logic and Provability
- Annotated Bibliography
- Index
23 - Arithmetical Definability
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface to the Fifth Edition
- COMPUTABILITY THEORY
- BASIC METALOGIC
- FURTHER TOPICS
- 19 Normal Forms
- 20 The Craig Interpolation Theorem
- 21 Monadic and Dyadic Logic
- 22 Second-Order Logic
- 23 Arithmetical Definability
- 24 Decidability of Arithmetic without Multiplication
- 25 Nonstandard Models
- 26 Ramsey's Theorem
- 27 Modal Logic and Provability
- Annotated Bibliography
- Index
Summary
Tarski's theorem tells us that the set V of (code numbers of) first-order sentences of the language in arithmetic that are true in the standard interpretation is not arithmetically definable. In section 23.1 we show that this negative result is poised, so to speak, between two positive results. One is that for each n the set Vn of sentences of the language of arithmetic of degree of complexity n that are true in the standard interpretation is arithmetically definable (in a sense of degree of complexity to be made precise). The other is that the class {V} of sets of natural numbers whose one and only member is V is arithmetically definable (in a sense of arithmetical definability for classes to be made precise). In section 23.2 we take up the question whether the class of arithmetically definable sets of numbers is an arithmetically definable class of sets. The answer is negative, according to Addison's theorem. This result is perhaps most interesting on account of its method of proof, which is a comparatively simple application of the method of forcing originally devised to prove the independence of the continuum hypothesis in set theory (as alluded to in the historical notes to Chapter 18).
Arithmetical Definability and Truth
Throughout this chapter we use L and N for the language of arithmetic and its standard interpretation (previously called L* and N*), and V for the set of code numbers of first-order sentences of L ture in N.
- Type
- Chapter
- Information
- Computability and Logic , pp. 286 - 294Publisher: Cambridge University PressPrint publication year: 2007