Hostname: page-component-7b7567c8c-kwt9d Total loading time: 0 Render date: 2026-11-14T18:54:12.576Z Has data issue: false hasContentIssue false

Decidability and essential undecidability

Published online by Cambridge University Press:  12 March 2014

Hilary Putnam*
Affiliation:
Princeton University

Extract

There are a number of open problems involving the concepts of decidability and essential undecidability. This paper will present solutions to some of these problems. Specifically:

(1) Can a decidable theory have an essentially undecidable, axiomatizable extension (with the same constants)?

(2) Are all the complete extensions of an undecidable theory ever decidable?

We shall show that the answer to both questions is in the affirmative. In answering question (1), the decidable theory for which an essentially undecidable axiomatizable extension will be constructed is the theory of the successor function and a single one-place predicate. It will also be shown that the decidability of this theory is a “best possible” result in the following direction: the theory of either of the common diadic arithmetic functions and a one-place predicate; i.e., of addition and a one-place predicate, or of multiplication and a one-place predicate, is undecidable.

Before establishing the main result, it is convenient to give a simple proof that a decidable theory can have an axiomatizable (simply) undecidable extension. This is, of course, an immediate consequence of the main result; but the proof is simple and illustrates the methods that we are going to use in this paper.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1957

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable