Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-03T02:17:03.499Z Has data issue: false hasContentIssue false
  • English
  • Français

A remark concerning decidability of complete theories1

Published online by Cambridge University Press:  12 March 2014

Antoni Janiczak
Antoni Janiczak*
Affiliation:
University of Warsaw
Get access Rights & Permissions [Opens in a new window]

Extract

A formalized theory is called complete if for each sentence expressible in this theory either the sentence itself or its negation is provable.

A theory is called deciddble if there exists an effective procedure (called decision-procedure) which enables one to decide of each sentence, in a finite number of steps, whether or not it is provable in the theory.

It is known that there exist complete but undecidable theories. There exist, namely, the so called essentially undecidable theories, i.e. theories which are undecidable and remain so after an arbitrary consistent extension of the set of axioms. Using the well-known method of Lindenbaum we can therefore obtain from each such theory a complete and undecidable theory.

The aim of this paper is to prove a theorem which shows that complete theories satisfying certain very general conditions are always decidable. In somewhat loose formulation these conditions are: There exist four effective methods M1, M2, M3, M4, such that

(a) M1 enables us to decide in each case whether or not any given formula is a sentence of the theory;

(b) M2 gives an enumeration of all axioms of the theory;

(c) the rules of inference can be arranged in a sequence R1, R2, … such that if p1, … pk, r are arbitrary sentences of the theory, we can decide by M3 whether or not r results from p1, … pk, by the n-th rule;

(d) M4 enables us to construct effectively the negation of each effectively given sentence.

In order to express these conditions more precisely we shall make use of an arithmetization of the considered theory .

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 15 , Issue 4 , December 1950 , pp. 277 - 279
Copyright
Copyright © Association for Symbolic Logic 1950

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.)

Footnotes

1

I am very indebted to Professor Andrzej Mostowski for kind encouragement and very helpful criticisms.

References

[1]Church, Alonzo, An unsolvable problem of number theory, American journal of mathematics, vol. 58 (1936), pp. 345–363.CrossRefGoogle Scholar
[2]Mostowski, Andrzej, On definable sets of positive integers, Fundamenta mathematicae vol. 34 (1947), pp. 85–112.CrossRefGoogle Scholar
[3]Post, Emil L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[4]Rosser, J. B., Extensions of some theorems of Gödel and Church, this Journal, vol. 1 (1936), pp. 87–91.Google Scholar
[5]Tarski, Alfred, Fundamentale Begriffe der Methodologie der deduktiven Wissenschaften, Monatshefte für Mathematik und Physik, vol. 37 (1930), pp. 361–404.CrossRefGoogle Scholar
[6]Tarski, Alfred, On essential undecidability (Eleventh meeting of the Association for Symbolic Logic), this Journal, vol. 14 (1949), p. 75.Google Scholar