In [1] we have considered a certain system L and shown that although its axioms are considerably weaker than those of [2], it suffices for purposes of the topics covered in [2]. The purpose of the present paper is to consider the system L more carefully and to show that with suitably chosen definitions for numbers, the ordinary theory of real numbers is also obtainable in it. For this purpose, we shall indicate that we can prove in L a certain set of twenty axioms used by Tarski which are sufficient for the arithmetic of real numbers and are to the effect that real numbers form a complete ordered field. Indeed, we cannot prove in L all Tarski's twenty axioms in their full generality. One of them, stating in effect that every bounded class of real numbers possesses a least upper bound, can only be proved as a metatheorem which states that every bounded nameable class of real numbers possesses a least upper bound. However, all the other nineteen axioms can be proved in L without any modification.

This result may be of some interest because the axioms of L are considerably weaker than those commonly employed for the same purpose. In L variables need to take as values only classes each of whose members has no more than two members. In other words, only classes each with no more than two members are to be elements. On the other hand, it is usual to assume for the purpose of natural arithmetic that all finite classes are elements, and, for the purpose of real arithmetic, that all enumerable classes are elements.

Es ist bekannt, daβ man aus den Funktionen 0 und n + 1 ausgehend, die in der elementaren Zahlentheorie benutzten Funktionen durch eine endliche Kette von Substitutionen und “primitiven Rekursionen” der Form

(α(a1, …, ar) und β(n, a1, …, ar, ar+1) bereits eingeführte Funktionen) definieren kann. Aber die “mehrfache Rekursion”, wobei die Rekursion gleichzeitig nach mehreren Variablen läuft, führt aus der so entstehenden Klasse der “primitiv-rekursiven Funktionen” hinaus. Die sogenannten “mehrfachen”, und zwar “k-rekursiven” Funktionen (zu welchen als Spezialfall auch die primitiv-rekursiven Funktionen gehören) lassen sich von gewissen Ausgangsfunktionen ausgehend durch eine endliche Kette von Substitutionen und “k-fachen Rekursionen” (wobei die Rekursion gleichzeitig nach k Variablen läuft) einer gewissen Normalform aufbauen. Die k + 1-fache Rekursion führt für ein jedes k aus der Klasse der k-rekursiven Funktionen hinaus. Das kann mit Hilfe des Diagonalverfahrens bewiesen werden. Das Diagonalverfahren auf sämtliche mehrfach-rekursive Funktionen angewandt (auch wenn man sich auf Funktionen von einer gegebenen Variablenanzahl beschränkt) würde als Beispiel einer nicht mehrfachrekursiven Funktion eine Funktion ergeben, bei der es vom ersten Argument abhängt, wievielstellig die Funktion ist.

Man sagt allgemein, daβ eine Funktion durch irgendeine Rekursion definiert wird, wenn ihr Wert an gewissen Anfangsstellen angegeben, und an einer anderen Stelle aus Werten aufgebaut wird, welche die Funktion an vorherigen Stellen angenommen hat. Es kann aber verschieden vorgeschrieben werden, welche Stellen als Vorgänger einer gegebenen Stelle zu betrachten sind.

Nach Gödel ist der Prädikatenkalkül der ersten Stufe vollständig in dem Sinne, daβ alle identischen Ausdrücke dieses Kalküls ableitbar sind. Für den einstelligen Prädikatenkalkül gilt darüber hinaus, daβ zwei Ausdrücke deduktionsgleich (HB I, p. 149) sind, wenn sie für dieselben Individuenbereiche identisch bzw. nicht identisch sind. Solche Ausdrücke mögen identitätsverbunden heiβen. Daβ umgekehrt deduktionsgleiche Ausdrücke identitätsverbunden sind, gilt auch für den vollen Prädikatenkalkül. Dagegen gibt es dort Ausdrücke, die identitätsverbunden, aber nicht deduktionsgleich sind. Solche Ausdrücke sind die in HB I, p. 123, 124 angegebenen und , die beide genau im Endlichen identisch, also identitätsverbunden sind. Die Frage der gegenseitigen Ableitbarkeit bleibt dort allerdings noch unentschieden. Ich werde im Folgenden die gegenseitige Nichtableitbarkeit von und im Prädikatenkalkül der ersten Stufe beweisen. Daraus folgt dann, daβ für den vollen Prädikatenkalkül die Bernayssche Deduktionsgleichheit nicht mit der Identitätsverbundenheit zusammenfällt. Es sei erwähnt, daβ die Identitätsverbundenheit sich zwar in der “Protosyntax” (d.h. metasprachliches “Alle” und “Es gibt” beschränkt auf Zeichenreihen) definieren läβt. Trotzdem kann man nicht von einer verschärften Vollständigkeit des Prädikatenkalküls sprechen; denn es läβt sich zeigen, daβ die Identitätsverbundenheit keine Beziehung vom Typ der Beweisbarkeit ist.

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 .