Ein Typenfreies System der Logik mit Ausreichender Mathematischer Anwendungsfähigkeit I

EIN TYPENFREIES SYSTEM DER LOGIK

MIT AUSREICttENDER MATHEMATISCHER

ANWENDUNGSF~HIGKEIT I.*

Von WILm~L~ Ae~MAN~ in Liidenscheid

w 1. E i n l e i t u n g

Es ist eines der wesentlichen Ergebnisse der neueren Grundlagenfor- schung, da6 es ein in jeder Beziehung vollst~.ndiges System der Logik nicht gibt. In dieser Hinsicht sind neben den bekannten G&/e/schen Ergebnissen [17], die auf einer Arithmetisierung der Paradoxie des Liigners beruhen, ebenso bedeutsam die Untersuchungen yon Ktee~e und Rosser [19], die eine arithmetische Einkleidung des Richardsehen Paradoxons enthalten. Die letzten Untersuchungen sind yon Curry [14], [15], [16] erg~nzt worden. Ihr Ergebnis kann man nach ihm in der folgenden Form ausspreehen: Eine Logik kann nicht zugleich kom. binatorisch und deduktiv vollst~ndig sein, wenn die Widerspruchs- freiheit gewahrt sein soll. Der Begriff der kombinatorischen Vollsfiin- digkeit ist an und fiir sich der kombinatorischen Logik entnommen. Er bedeutet dort, dab jeder Ausdruck, der mit Hilfe der Terme des Systems und einer Hilfsvariablen x gebildet werden kann, innerhalb des Systems als Funktion yon x dargestellt werden kann. Auf die iiblichen Systeme der Logik, wozu in dieser Hinsicht auch das vorliegende rechnet, iiber- tragen, wiirde die kombinatorische Vollst~ndigkeit etwa besagen, dab man in dem System jedes iiberhaupt denkbare Prikiikat (jede iiberhaupt denkbare Menge) bflden und mit ihm (mit ihr) entsprechend ihrer De- iinition operieren kann. Unter der deduktiven Vollst~ndigkeit versteht man die Existenz eines Deduktionstheorems, d.h. es existiert in dem System eine Implikation ,,-~", so daB, wenn eine Formel ~ unter der Annahme 9~ (bei Festhaltung etwaiger freien Variablen in 9~) sich beweisen l ~ t , dana auch ~ -~ ~ beweisbar ist. In der Tat zeigt ein Blick auf die vorhandenen Systeme, die sich be- w~hrt haben, d.h. fiir die kein Widerspruch anzunehmen ist, da die Widerspruchsfreiheit entweder nachgewiesen ist oder alle Versuche zur Konstruktion einer Paradoxie fehlschlugen, dal~ sie zu einem yon zwei Typen gehSren. Die Systeme des Typs I besitzen die deduktive Voll- stitndigkeit, aber nicht die kombinatorisehe. Dazu gehSrt z.B. das

* Eingegangen am i2.7. 1957.

4 Wilhelm Ackermann

Russellsche System der Typentheorie (der einfachen oder der ver- zweigten), da hier die Pr~dikatbildung an die Typenbedingung gebunden ist. Ferner gehSren dazu aUe bekannten axiomatisehen Systeme der Mengenlehre, da sich hier gewisse Mengen nicht bilden lassen. Dazu reehnet in dieser Hinsieht z.B. aueh das yon Quine [20] aufgestellte System sowie das yon mir in [5] angegebene. Die Systeme des Typs II besitzen die kombinatorisehe Vollstindigkeit, aber nieht die deduktive. Sie sind weniger bekannt. Als Beispiel fiir ein derartiges System, das der kombinatorischen Logik niher steht, nenne ieh ein System yon Church [12], [13], in dem sich die deduktive Unvollst~ndigkeit dadurch zeigt, dab sich eine den Anforderungen des Deduktionstheorems ge- niigende Implikation nicht definieren liBt. Im iibrigen soll hier auf die Systeme der kombinatorischen Logik nicht welter eingegangen werden. Ferner gehSren dazu verschiedene von mir aufgestellte Systeme [2], [3], [4]. In [2] und [3] ist kein voller Ersatz fiir ein Deduktionstheorem vorhanden (vgl. die Ausfiihrungen in [2], S. 45); [4] enth~lt iiberhaupt keine Implikation. Auch die Systeme yon Schi~tte [21], [22] fallen unter diesen Typ. [21] enth~lt ebenfalls keine Implikationen, bei [22] haben wir nur einen Ersatz fiir ein Deduktionstheorem ; falls ~ unter der Annahme

beweisbar ist, liBt sich nieht ~--> ~ beweisen, sondern nur B~--> B (Bg~ ist zu lesen: 9/ist beweisbar). Angesichts dieser Sachlage seheint es nur fibrigzubleiben, sich fiir den Typ I oder II zu entscheiden und zu versuchen, ein mSglichst weitgehendes System des betreffenden Typs aufzustellen, aber so, dab die Besehr~nkung, die die vorhandene Unvollstindigkeit in der einen oder der anderen Richtung mit sieh bringt, yon einem inhaltlichen Stand- punkt aus ,,plausibel", als natfirlieher AbschluB erscheint, wobei sich natiirlich der letzte Begriff nicht niher defmieren liBt. In der vor- liegenden Arbeit wird die Aufgabe in Angriff genommen, ein System des Typs II zu konstruieren, das fiir die mathematisehen Anwendungen ausreicht. Ein derartiges System existiert meines Wissens bisher nieht. Die erw~hnten Systeme von Schiitte und mir waren (lurch die zusitz- fiche Forderung der nachweisbaren Widerspruchsfreiheit belastet, was natiirlich dem aktuellen Zweck dieser Systeme entsprach, ohne wesent- liche mathematisehe Voraussetzungen widerspruchsfreie Modelle ffir die Zahlentheorie trod die verzweigte Analysis innerhalb der Systeme zu konstruieren. Diese Forderung diente aber auch dazu, das an und fiir sieh vorhandene MiBtrauen gegen Systeme des Typs II iiberhaupt zu zerstreuen. Die mathematisehe Anwendbarkeit muBte natiirlich beschr~nkter sein. Die Forderung der naehweisbaren Widerspruehs- freiheit miissen wir jetzt fallen lassen. Systeme des Typs II haben alle die Voraussetzung gemeinsam, dab der Definitionsbereich der Pr~dikate im allgemeinen besehr~nkt ist, d.h. daB der Bereieh der Dinge, fiir die es sinnvoll ist zu sagen, dab dan Pr~dikat auf sie zutrifft oder nieht zutrifft, im allgemeinen nieht ,,alle" Dinge umfafit. Dieser Gedanke erseheint sehr plausibel. So wird man

Ein typen]reies System der Logik usw.

etwa in der Mathematik den Satz ,,die Funktion y ~ sinx ist eine Prim- zahl" weder als richtig noeh als falseh ansehen, sondern als sinnlos. AuBermathematische Beispiele lassen sich noeh in viel reieherem YIaBe finden. H. B e h n m ~ hat seit l~ngerer Zeit die These vertreten, dab dieser Gedanke, zusammen mit dem Gedanken der Eliminierbarkeit der Kurzzeichen, d.h. der durch Komprehension eingeffihrten Pr~iikate, genfigen wfirde, um alle Paradoxien zu vermeiden. Jcdoch haben seine l~berlegungen bisher nicht zu einem bestimmten System mit festgelegten Regeln des Operierens gefiihrt; ffir seine Grundgedanken sei auf [6], [7], [8], [9] verwiesen. Ein bestimmtes System auf dieser Grundiage wurde zuerst yon A. Church [10], [11] aufgeste]]t. Aus seinen l~berlegungen geht hervor, dab eharakteristisch fiir ein derartiges System ist die Vermeidung des A1]zeichens in dem fiblichen Sinne, bei dem die matrix des A1]zeichens fiir aUe in die Allzeichenvariable eingesetzten Dinge richtig ist. Statt dessen ist eine Beziehung 9~(x) ~ ~ (x) vorhanden, die nur besagt, dab

alle Dinge, die die Eigensehaft ~ haben, aueh die Eigenschaft ~ haben, w~rend fiir die Dinge, die nicht die Eigenschaft ~ haben, nichts aus- gesagt sein so]]. 9~ (x) ~ ~ (x) unterscheidet sich yon (x)(~(x) v ~ (x)) in

der iiblichen Bedeutung dadurch, dab die letzte Formel aueh etwas sagen wfirde fiber die x, ffir die 9~(x) sinnlos ist. Sie wfirde ,,~(x) ist sinnlos" mit ,,~(x) ist falsch" gleichsetzen. Neben ~ braucht man ferner

noch die Operationen des Aussagenkalkfils und ein Existenzzeichen. Auf dem gleichen Grundgedanken beruhte meine Arbeit [1]. Kfirzlieh hat V. Val1~ola [23], mehr yon empirisehen Gesiehtspunkten ausgehend, darauf hingewiesen, welche Schwierigkeiten der Deutung der genere]]en Implikationss~tze yon der Form (x)(~ (x) ~ ~ (x)) bei der fibliehen Auf- fassung entgegenstehen. Er verwendet daher ebenfa]]s einen Operator

und vermeidet gleicher Weise die freien Variablen. Die Besonderheit

seines Systems besteht noeh darin, dab er auch die Negation vermeidet und nut die Konjunktion als Aussagenverknfipfung hat. Bei derartigen Systemen lassen sich nun leicht infolge des besehr~nkten Definitionsbereiehs der Pr~clikate die bekannteren Paradoxien vermeiden, worunter ich etwa die Russellsche Paradoxie, die Paradoxie der grSBten Kardina]zahl oder der Menge a]]er Mengen und ~hnliche ver- stehe. Hierauf hat wohl zuerst Behman~ in [6] hingewiesen. Dagegen genfig~ dieser Gedanke allein nicht, um der Paradoxie yon K/eene und Rosser zu begegnen, wie die beiden Veffasser an ttand des Churchschen Systems [10], [11] gezeigt haben. Auch das von mir in [1] angegebene Axiomensystem dfirfCe, entgegen meiner damals vertretenen Ansicht, davon betroffen sein, da sich hier die wesentlichen Gedankeng~nge yon Kleene und Rosser, wenn auch in viel umst~ndlieherer Weise, wieder- geben lassen. Da ferner die Paradoxie sich schon ffir den Tefl des Church-

6 Wilhelm Ackermann

schen Systems konstruieren liil3t, in dem die Negation nicht vorkommt, ist zu vermuten, dal3 des gleiche flit das negationslose System yon Fa~po/a gilt: Vollst~ndige Gewi~eit kann man allerdings erst dann dariiber erhalten, wenn man die sehr miihevoUe und zeitraubende Arbeit auf sich nimmt, die Gedankengiinge yon K/eene und Rosser in der Abi~nderung, wie sie dutch das jeweilige System bedingt ist, wirklich durehzufiihren. Ieh babe die kritische Situation, der gegenfiber wit uns bei einer Kon- struktion eines weitgehendes Systems des Typs H befinden, so aus- fiihrlieh dargestellt, um Versti~ndnis zu weeken fiir die Behutsamkeit, mit der ich bei der Aufstellnng eines Axiomensystems im folgenden vorgehe. Die Grundlage des folgenden Aufbaus bilden einmal meine Ausfiihrungen in [1] (mit Aussehlull des Teiles, der sieh mit dem dortigen Axiomemsystem befallt), die wesentlich erweitert werden, ztun anderen meine Arbeiten [2], [3]L

w Die S y m b o l i k

Wit wollen also eine Logik konstruieren, die aul}er den Aussageverkniip- fungen das Existenzzeiehen und ~ , ~ . . . . (Zeichen, die ich anstelle yon ~ , ~ verwende) benutzt. BeidenAussageverkniipfungenbeschr/inken

z ~ y

wit uns auf ,,--" (nicht), ,,&" (und) ,,v" (oder). ~x~(z) hat den fiblichen Sinn~ desgleichen t~ (x ) . In ez~(x) soil s das Hi/bertsche e bedeuten. Die Grundsymbole unseres Aufbaus sind die folgenden:

a) Ze/rs f/~r Variable: x, y, z . . . . . auBerdem ~, ~, ~, ~ , . . . und andere grieehische Buchstaben, mit Ausnahme yon e, ~, t, die spezielle Be- deutung haben. - - Ein Unterschied im Gebraueh der kleinen ]ateinischen und kleinen griechischen Buchstaben wird nieht gemacht. Wir werden zwar die ~, ~ , . . . vorzugsweise dort gebrauchen, wo sie dem Sinn der Formel nach ein Pr/klikat bedeuten, ohne dab abet irgendwelche formale Konsequenzen im Gebraueh der beiden Arten yon Variablen be- dinfft sein sollen.

b) Zeiehen fflr Aussageverkniipfungen: --, &, v;

e) die Existenzialzeichen (/gx), (/~y), ( / ~ ) , . . . ;

d) die Zeiehen ~z, ~xy, ~ . . . . ; e) das Zeichen: = ; f) Die Subsumtionszeichen: ~-, ~ , ~>, . . . ; g) die Zeiehen e, t; h) Klammern (runde, eckige und geschweifte).

1 Beziiglich [2] hat iibrigens R. Harro~ [18] auf eine gewisse Unvollst~ndigkeit in der Definition der Negation hingewiesen, die in [3] beseitig~ ist.

Ein typen]rei~ System der Logi]~ u~w.

Wir geben nun die simultane rekursive Definition yon ,,Formel", ,,Gegen- standszeichen", ,,freier Variable" und ,,gebundener Variable".

(1) Variable sind Gegenstandszeichen. Wir sagen, die Variable kommt in dem Gegenstandszeichen in freier Form vor.

(2) Sind a und b Gegenstandszeichen, so ist ,,a = b" Formel. Freie bzw. gebundene Variable der Formel sind die freien bzw. gebundenen Variablen yon a und b. DaB a -~ beine Formel ist, unterliegt noch der Beschr~in- kung, dab nicht die gleiehe Variable in einem der beidon Gegenstands' zeichen in freier und in dem anderen in gebundener Form vorkommt.

(3) Es seien a, b l , . . . , b~ (~ ~ 1) Gegenstandszeichen solcher Art, dab nicht die gleiehe Variable in einem der Gegenstandszeiehen in freier und in einem anderen in gebundener Form vorkommt. ])ann ist (a} (b l , . , . , bn) eine Formel. Eine in dieser Formel vorkommende Variable heiflt innerhalb der Formel frei odor gebunden, falls sie in einem der Gegen- standszeichen in gleieher Eigenschaft vorkommt.

( 4 ) Ist 9~ eine Formel, so aueh ~. Die in ~ vorkom menden Variablen heiBen darin frei odor gebunden, falls sie in gleicher Eigenschaft in ~I auftreten.

(5) Sind ~ und ~ derartige Formeln, dab nicht die gleiehe Variable in der einen Formel in f~eier und in der anderen in gebundener Form auftritt, so sind (~I) & (~) und (~) v (~) Formeln. Eine in (~)& (~) bzw. (~I) v (~) vorkommende Variable heiBt darin frei oder gebunden, wenn sie in gleicher Eigenschaft in einer der beiden Formein ~I, ~ auftritt. (6) Ist ~ eine Formel, die eine gewisse Variable tt in freier Form ent- hiilt (tt ist ein Mitteilungszeichen flit eine Variable beliebiger Art), so ist (Ett) (9~) eine Formel. Die Variable tt heiBt in (Ett) (9~) gebunden. Andere in (Ett)~ vorkommende Variable heiflen darin frei oder ge- bnnden, wenn sie in gleicher Eigensehaft in ~I vorkommen. (7) ~ sei eine Formel, die die Variablen Ul, �9 �9 tt~ (~ ~ 1) in freier Form enth~l~; ~ sei eine Formel der Art, dab keine ffeie Variable yon ~ in in gebundener Form auitritt nnd umgekehrt. Dann ist ( ~ ) ~ (~) eine Formel. In dieser Formel sind die Variablen t h . . . . , tt~ gebunden, andere frei oder gebunden, wenn sie in einer der beiden Formein in gleieher Eigensehaft auftreten. (8) Ist ~ eine Formel, die die Variablen tt 1 . . . . , ttn in f reier Form enth~lt, so ist ~tt 1 . . . tt~(~) ein Gegenstandszeiehen. In dem Gegenstands, zeichen sind die Variablen th,. . . . . tt~ gebunden; die anderen Variablen kommen darin in gleicher Eigenschaft wie in ~ vor. (9) a sei ein Oegenstandszeichen. Dann sind auch t [a] und ~ [a] Gegen- sgandszeichen. Die Freiheit oder Gebundenheit der Variablen bleibt durch das Vorsetzen yon 8 bzw. ~ nnver~ndert.

Bei diesem Aufbau der Formeln und Gegemstandszeiehen k6nnen Klammem vielfach weggelassen werden, niimlich dann, wenn dadureh der Aufbau der Formel odor des Gegenstandszeichens nicht zweifel-

8 Wilhelm Ackermann

haft wird. Z.B. werden wir die folgenden klammersparenden Regeln benutzen: Eine Klammer um eine Formel {a} (b 1 . . . . , b,), (Eu) (9/) oder a = b wird fortgetassen. Statt {a} (bl, �9 �9 b,) sehreiben wir abl �9 �9 �9 5~, wenn die Gegenstandszeichen a, 51 . . . . 5~ alle Variable sind. Diese Fort- lassung yon Klammern benutzen wir auch bei den Mitteflungszeichen. Wir schreiben also start {a} (51 . . . . . 5~) einfach a51 . . . 5~, da das Mit- teflungszeichen fiir jedes Gegenstandszeichen aus einem Buchstaben (evtl. mit Index) besteht. Das ist natiirlieh unabh~ngig davon, dab bei dem, was {a} (51 . . . . , 5~) im gegebenen Fall bedeutet, die Klammern mSglicherweise nicht fortgelassen werden kSnnen. Ebenso schreiben wir bei Mitteflungen start (9/)& (~) gewShnlich 9/& ~, usw. Weitere Fort- lassung yon Klammern erhalten wir dadurch, dab wir festsetzen, dab ,,v" enger bindet als ,,&" und ,,v" und ,,&" beide enger als , , - - - -~" . Am

1~1. , . U n

engsten soll (Eu) binden sodaf l (Eu) 9/& ~ fiir (Eu) (9/)& ~ steht. Zur Interpretation der Formeln bemerken wir, dab {a} (51 . . . . . b~) bedeutet, dab das Pr~likat a auf das geordnete n-tupel (bl . . . . . 5,,) zutrifft. 9 / ~ ~ war schon in w 1 erl~utert worden. Entsprechend bedeutet 9 / ~ !~, dab fiir jedes x, y, fiir das 9/richtig ist, auch ~ riehtig ist. ~ x (~) bedeutet ein einstelliges Pr~dikat, das auf x dann und nur dann zutrifft, wenn 9/riehtig ist. ~ x y (9/) bedeutet ein zweistelliges Pr~dikat, daM auf das geordnete Paar (x, y) dann und nur dann zutriffr wenn 9/riehtig ist, usw. ~ [~] bedeutet, falls ~ ein einstelliges Pr~likat ist, das auf genau ein Ding zutrifft, eben dieses Ding. Falls ~0 ein einstelliges Pr~i~kat ist, das auf mindestens ein Ding zutriffr bedeutet e [~] ein lest gew~hltes, aber im iibrigen unbestimmt gelassenes Ding, auf daM ~0 zutrifft, tx (9/) und e~(9/) mSgen als Abkiirzungen fiir ~[2x9/] und s[~xg/] dienen. Zu dem Aufbau der Formeln bemerken wir, dab darunter solche vorkommen, die interpretativ ohne weiteres als sinnlos zu erkennen sind, )vie etwa die Formel {~x~x}(y, z) oder die Formel ~x& ~xy. Es lohnt sich aber nieht die Miihe, den Aufbau so zu gestalten, daft derartige Formein von vorne herein ausgeschlossen werden. Denn es kommen noch viele andere Formein vor, deren Sinnlosigkeit nieht auf den ersten Blick zu erkennen ist. Wir kSnnen iiberhaupt kein allgemeines Kriterium aufstellen, das uns erlaubt, bei einer gegebenen Formel zu entscheiden, ob sie sinnvoll ist oder nieht. In der Tatsache, daft der Begriff der sinnvollen Formel nieht von vorne herein gegeben ist, liegt die Eigenart unMeres logisehen Systems und zu- g]eieh auch die besondere Schwierigkeit, die die Aufstellung eines Axi0mensystems maeht.

w A u s d r i i e k e u n d T e r m e

,,Ausdrticke" und ,,Terme" soUen, wie wir zun~chst provisorisch sagen, die sinnvollen Formeln und sinnvollen Gegenstandszeichen sein. Es war in w 2 gesagt worden, dab es nioht m6glich ist, die Ausdriicke und Terme

Ein typen]reies System der Logilc usw.

in ihrer Gesam~heit anzugeben. Wir kSnnen aber gewisse Leits~tze angeben, nach denen sich Ausdriicke und Terme gewinnen lassen. Diese Leits~tze hatte ich zum grSBten Tefl sehon in [1] niedergelegt. Sie sind nich~ als strenge formale Prinzipien anzusehen, dienen aber dazu, den in den folgenden Paragraphen gegebenen formalen Aufbau zu motivieren. Wir nennen eine Formel 9~ ohne freie Variable einen Ausdruek, wenn

v ~ richtig ist. Eine Formel ~ mit den alleinigen freien Variablen ul, - . . , un heiBt ein Ausdruek, wenn ( E u l ) . . . (Enn)(~ v ~) richtig ist. Was ,,richtig" is~, sind entweder gewisse logisehe Axiome, die in unserer Axiomatik auftreten bzw. gewisse andere als Axiome auftretenden Formeln, die yon uns aus auBerlogischen Griinden als riehtig angesehen werden, oder es sind die Ergebnisse der Beweisfiihrungen aus derartigen Formeln. Der Begriff ,,Ausdruck" ist also mit dem der ,,beweisbaren Formel" gekoppelt. Die beim Beweise benu~zten Sehlfisse sind so zu modifizieren, dab sie yon Ausdriieken wieder zu Ausdriieken fiihren. Unter einem ,,Term" kSnnen wir ein Gegenstandszeiehen a verstehen, fiir das (E~)~ a riehtig ist, falls f keine freien Variablen enth~lt, und ffir das (Eu l ) . . . (Eltn)(EqD)q)a riehtig ist, falls a allein die freien Variablen ul, �9 �9 �9 u , enth~lt. Um welter zu bestimmten Leitsgtzen ffir die Bildung yon Ausdriicken zu gelangen, bemerken wir, dab es offenbar in Ordnung ist, wenn wir verlangen, dab die Teflformeln und Teilgegenstandszeiehen yon Aus- drficken und Termen selbst wieder Ausdrfieke und Terme sind. Im einzelnen bedeutet das folgendes:

la) Wenn 2& !~ bzw. ~Iv ~ Ausdruck ist, so sind ~ und ~ Ausdriicke. I b) Wenn ~ Ausdruek ist, so ist ~I Ausdruck. 1 e) Wenn (EU)2 Ausdruek ist, so ist ~l Ausdruek. ld) Wenn ~ ~ ~ Ausdruck ist, so sind 9~ u n d ~ Ausdriicke.

111 . . �9 l l n

le) Ist f51 �9 . . bn Ausdruck, so Mind f, b l , . �9 bn Terme. l f ) Ist ~1~1.. �9 l~n2 Term, so ist ~[ Ausdruek. lg) Ist f = b Ausdruek, so sind f und b Terme. lh) I s t s If] Term, so is$ f u Ausdruek, vorausgesetzt dab es fiberhaupt eine Formel ist. l i) Ist t[f] Term, so ist flu Ausdruck, vorausgesetzt dab es fiberhaupt eine Formel ist.

Wir fragen nun umgekehrt, wann beim Zusammenbau yon Ausdriieken, yon Termen oder yon Ausdrfieken und Termen wieder Ausdriieke und Terme entstehen. Diese Frage kann natfirlieh nieht abschlieBend be- antwortet werden, da sie veto Ergebnis yon Beweisfiihrungen abh~ngt. Die S~tze 1 a ) - - l i ) lassen sieh nicht alle einfach umkehren. Immerhin sind die Iolgenden Bemerkungen yon Vortefl. Es seien z. B. 2 und !~ zwei Ausdriieke mit der alleinigen freien Variablen x. Dann braueht 2& !~ kein Ausdruek zu sein, d. h. (Ex) ((2& ~) v (2 & ~))

10 Wilhelm Aekermann

braucht nieht richtig zu sein, Es w~re n~mlich denkbsr, dal~ for die Werte yon x, fiir die ~I sinnvoll ist, jedesmal ~ nieht sinnvoll ist, und umgekehrt. Damit nun ~ & ~ Ausdruck ist, miil3ten ~ und ~ beide schon in irgendeiner Kombination sls Bestandtefle des gleiehen Ausdrueks vorkommen. Z.B. wiirde es genfigen, wenn ~ v ~ oder ~ v ~& ~ v Ausdruck w~re. Um hier zu einem bestimmten Satz zu gelangen, definieren wir die PrimbestandSel/e einer Formel dutch Rekursion dureh die folgenden Regeln: cr Formeln der Form a -~ ~, abi'. b~, ( E u ) ~ oder ~[-----* ~ haben

�9 . ~ 111 , , , I1 ~

sis einzigen Primbestandtefl sieh selbst; ~) Die Primbestandteile yon sind die yon ~ ; y) Die Primbestandteile yon ~ & ~ oder yon ~ v ~ sind die Primbestsndteile yon ~I und die yon ~ . ~ Bei der Aufz~blung der Primbestandtefle sollen solehe gleicher Gestalt nur einmal gez~hlt werden. Z .B. hat ~ x & ~ x als einzigen Primbestandteil ~ x. Wit k6nnen ]etzt eine gewisse Umkehrung der Regeln la) und 1 b) in der folgenden Form aussprechen: 2a) Ist ~I ein Ausdruck und sind die Primbestandteile der Formel ~ such alle Primbestsndteile yon ~, so ist such ~ ein Ausdruek. 2b) I s t~ iAusd ruckunds indu l , . . . , l ~ in~vorkommende f r e i eVar i ab l e , so ist 2u 1 . . . u~9I Term. (Umkehrung yon lf). 2c) Ist ~u Ausdruck, so ist e[a] Term (Umkehrung yon 1 h).

1 i) l ~ t sieh nicht in einfacher Weise umkehren. Wit haben aber den folgenden Satz, der aueh 1 i) selbst erweitert: 2d) e[a] ist daun und nur dsun ein Term, wenn es genau ein u gibt, so dal~ ~ u riehtig ist.

Im iibrigen haben wir zum sllgemeinen Aufbsu der Ausdriieke nur die Regel, dad ~ mit Hilfe der Sehluflregein sls riehtig oder fslsch erkannt werden mul~, so dal~ wit auf das naehfolgende Axiomensystem verweisen miissen.

w 4. V o r b e m e r k u n g e n zu r A u f s t e l l u n g e ines A x i o m e n s y s t e m s

Es handelt sich nun datum, ein unseren Intentionen entsprechendes Axiomensystem aufzusteUen. Was zun~ehst den Aussagenkalkiil anbe- trifft, so haben wir nicht allgemein den Satz yore ausgesehlossenen Dritten; wir k6nnen.nicht ~ v ~ fiir beliebige Formeln ~ als Grund- formel nehmen, da sonst jede beliebige Formel als sinnvoU hingestellt w~re. Dies hat allerdings niehts mit intuitionistischen Gedankeng~ngen zu tun. Im Gegenteil gelten die Sehliisse der gewSbnliehen (zweiwertigen) Aussagenlogik, da auch wir die Aussageverkniipfungen als Wahrheits- funktionen auffassen. Es mu~ aber dafiir gesorgt werden, dal3 man yon Ausdruek wieder zu Ausdruek iibergeht. Z. B. gilt der SehluB yon ~ auf ~ ; denn mit ~ ist nach unseren Ausdrucksregeln aueh ~ ein Ausdruck. Ds- gegen gilt nicht der SchluB yon ~ auf ~ v ~ mit beliebigem ~. Denn die

Ein typen/reies System der Logik u~w. 11

Richtigkeit yon ~ v !~ wiirde einschlieBen, dab die beliebige Formel ein Ausdruck ist. Der SchluB yon ~ auf ~ v ~ ist dagegen in Ordnung. Damit h~ngt auch zusammen, daB, wenn man yon ~ auf ~ schlieBen daft, der umgekehrte SchluB yon ~ auf ~ nicht immer mSglich ist. Z. B. diiften wir yon ~ v ~ auf ~ schlieBen, weil eben mit ~ v ~ auch

ein Ausdruck ist. Der umgekehr~ SchluB wiirde aber bedeuten, dab man yon ~ au[ ~ v ~, oder was dasselbe ist, yon ~ auf ~ v ~ schlieBen daft, und dieser SchluB ist, wie wir sahen, nicht zul~ssig. Auch ist es nicht immer miiglich, yon ~ v ~ auf ~ v !~ zu schlieBen, wenn man yon ~[ auf fi~ schlieBen daft. Das ist dann nicht der Fail, wenn mit der Richtig- keit yon ~ nichts fiber den Ausdruckscharakter yon !8 gesagt ist. Denn

v ~ kSnnte ja bedeuten, dab ~ richtig und ~ falsch ist. Unsere Auf- fassung bedeutet auch, dab wir yon den Schliissen durch reductio ad absurdum nur einen beschrfidlkten Gebrauch machen kSnnen. Um ~ zu beweisen, geniigt es nicht, zu zeigen, dab die Annahme ~ zu einem Wider- spruch ffihrt; es sei denn, wir w ~ t e n schon, dab ~ ein Ausdruck ist, dab also ~ v ~ beweisbar ist. ]~ber (Ex)~(x) ist zu sagen, dab die Handhabung des Existenzzeichens im wesentlichen die gleiche ist wie in der gewShnlichen Pr~ikatenlogik. Das gilt aber nur ffir den positiven Gebrauch des Existenzzeichens. Differenzen sind aber auch hier vorhanden Z.B. kann man aus (E z) ~(x) V (Ex)~(x) nicht immer auf (Ex)(~(x) v ~(v)) schlieflen. Es w~re ja mSglich, dab die Bereiche der x, fiir die 2(x) mad fiir die !8 (x) simavoll is%, sich gegenseitig ausschlieBen. Formein mit freien Variablen kSnnen nicht bewiesen werden. Denn derartige Formeln, falls nicht die Art der Einsetzung mit unhandlichen Komplikationen verbunden sein sollte, kSnnten nut den Sinn haben, dab beliebige Oegenstandszeichen ffir die Variablen eingesetzt werden dfiften, was yon unserem Standpunkt aus unsinnlg ist. Aus dem gleichen Grunde haben wir auch keinen entsprechenden universalen Quantor. Ailgemeinheitsbehauptungen, die wir in unserem System aufstellen k6nnen, sind zun~chst yon der Form ~(x) ~ ~ (x). Auf den ersten Blick erscheint die Beschr~nkung auf diese Art yon universalen Behauptungen sehr eng. Das ist abet nicht der Fall. Wenn wir gewShnlich irgendein Axiomensystem aufstellen, z. B. fiir die Zahlentheorie, so sind die zu- geh6rigen Allgemeinheitsbehauptungen auf einen bestimmten Indivi- duenbereich bezogen, bier den der natiirlichen Zahlen, und nicht etwa auf die Gesamtheit der Gegenstandszeichen. W~re also ~ (x) ein Pr~likat, das dem ,,Zahlsein" entsprechen wiirde, so wiirde die Behauptung, dab alle Zahlen die Eigenschaft ~(x) haben, durch ~(x)~-~(x) wieder- gegeben. Da bei unserem System yon einem in irgendeiner Hinsicht abgeschlessenem Bereich keine Rede sein kann, so ist es niitig, dab wir jedesmal den Bereich, auf den sich die Ailgemeinheit bezieht, explizit angeben. Wir kiinnen abet sogar ausdriicken, dab eine Allgemeinheit sich

12 Wilhelm Ackermann

auf alle Terme, d. h. auf alle verniinftigen Gegenstandszeichen, bezieht, z. B. in der Form (Eq~)q~x -~ 2(x). Die zweite Art yon Allgemeinheits- behauptungen w~ren die yon der Form (E x ) 2 (x). Hier w~re der SchluB yon (Ex)2(x) auf 2(a) mit beliebigem a nicht mSglich, sondem nur dann, wenn wit wissen, dab 2(a) Ausdruek ist. Wir haben aber wenig MSglichkeiten, (E x) 2 (x) zu beweisen, da die MSgliehkeit einer reductio ad absurdum groBen Besehr~nkungen unterworfen ist. Ein derartiger ScMul~ lieBe sieh allerdings vielfaeh durchffihren, wenn wit annehmen dfirften, dab mit 2(x) auch immer (Ex)2(x) ein Ausdruek ist. Abet ffir diese Annahme im allgemeinen besteht nach unseren Prinzipien keine Veranlassung. Dagegen werden wit etwas Entspreehendes annehmen, wenn sieh die dureh (Ex)2(x) ausgedrfiekte Allgemeinheit auf einen ,,vernfinftigen" Bereich yon Dingen beziehk Unter einem vernfinftigen Bereich yon Dingen wollen wir einen solehen verstehen, bei dem die Identit~t zwischen zwei Dingen des Bereiches immer ein Ausdruek ist, d. h. wenn 2(x) den Bereieh defmiert, soll 2(x) & 2(y) ~ x -~ y v X ~ y gelten. Ist nun ~(x) eine Formel, die ffir Dinge x aus dem Bereich 2(x) einen Ausdruck darstellt, so sol1 auch (Ex)(2(x)& ~ (x)) ein Ausdruek sein. So welt wir das aufzubauende System bisher schilderten, ist es seinen grundlegenden Ideen naeh, yon der zuletzt beschriebenen Erwciterung abgesehen, nicht wesentlich versehieden yon dem System yon A. Church. [10], [11]. Ein Unterschied zeigt sich aber in der Auffassung yon 2(x) -~ !~(x). Wie sol] diese Beziehung genauer gedeutet werden? Wir wollen darunter verstehen, dal3 aus 2(a) immer ~ (a) nach bestimmten Regeln ableitbar ist. Wir mfissen uns aber klar maehen, dab damit 2 (x) ~ !8 (x) zu einer synt~ktisehen Stufe hiiherer Art gehSrt als 2 (x) und !~(x). Auch im gewShnliehen Spraehgebrauch wfirden wir meist nieht sagen: ,,Wenn 2 und wenn ~} aus 2 ableitbar ist, so ~ " , sondern wir wiirden sagen: ,,Wenn 2 ableitbar ist und wenn ~ aus 2 ableitbar ist, so ist auch

ableit.bar". Um also Schlfisse zu ziehen, ist in der Regel eine gewisse Gleiehheit in den Stufen der Pr~missen erforderlieh. Im obigen Falle wfirden wir hSchstens noeh sagen: ,,Wenn 2 richtig 1st, und wenn ~ aus 2 ableitbar ist, so ist auch ~ richtig". Abet der Satz , ,2 ist riehtig" ge- hSrt streng genommen auch sehon einer anderen Stufe an als , ,2". Wenn ich sage: ,,die Zahl 6 ist gerade", so sage ieh etwas fiber die Zahl 6 aus; wenn ich abet sage: ,,es ist richtig, dal~ die Zahl 6 gerade ist", so sage ich etwas fiber das Urteil ,,die Zahl 6 ist gerade" aus. Unter Be- rficksichtigung dieser Bedeutung yon ~ , w~re die F ormeI (yu & (y x ~ z x))

zu als riehtige Formel abzulehnen. Wie sollen wir aber , ,2 ist ab- y z ~

leitbar" ausdrficken~. Es ist gleiehbedeutend zu sagen , ,2 ist aus rich- tigen Formeln ableitbar". Wir haben im folgenden , ,2 ist ableitbar" durch PI3 -~ 2 ausgedrfickt, wo ~ eine Variable ist, die nicht in 2 vorkommt. VonF~ brauchen wir in diesem Zusammenhange nur zu wissen,

Ein typen]reies System der Logik usw. 13

daf es eine Formel mit der einzigen freien Variablen D ist, fiir die (ED) I'D riehtig ist. Start der obigen Formel (xu & (yx -~ zx)} ---* zu h~tten wir yZU

dann ((I'D -~ yu) & (yx --~ zx)) ~-z~ (I'D ~ zu). Diese Gleichheit der Stufen haben wit nun bei allen Sehliissen zu beriicksiehtigen. W~re z .B. (E x) (9~ (x) & ~ (x)) der Fall, so k~nn natiirlich 9~ (x) • ~ (x) nieht zutreffen. Um die Gleichheit der Stufen zu beriieksichtigen , schliefen wir abet nieht von (Ex)(~(x)& ~ (x)) auf ~ ( x ) 7 ~ (x), sondem yon/~i~ -~ (Ex) (9~ (x) & ~ (x)). Diese Beriieksiehtigung der Gleiehheit der Stufen hatte ich sehon in [2] bei der Einfiihrung der dortigen Beziehung ,,9~-->~", die ieh interpretierte als ,,Aus der Beweisbarkeit yon ~I ergibt sich die Beweisbarkeit yon ~", beobaehtet. Es erscheint mir dieses Prinzip der Beriicksichtigung der Gleiehheit yon Stufen bei implikativen Zu- sammenh~ngen durchau s plausibel und natiirlich. Eine gewisse be- wufte Inkonsequenz in dieser Hinsicht haben wir allerdings im folgenden begangen, indem wir den Schluf yon I'D ~ ~ auf ~, aber nieht den um- gekehrten Schluf auch noch durch -~ ausdrficken, w Nun wollen wir gewif nieht behaupten, da f jede implikative Aussage, die die angegebene Gleiehheit der Stufen nicht beriieksichtigt, als falseh anzusehen ist, da f also etwa der Satz: ,,Wenn es sehneit, so ist es richtig, da f es schneit" unzul~ssig ist. Was wir meinen, ist nur, daft bei derartigen Zusammen- hangen yon einer Implikation in einem weiteren Sinne die Rede ist als der, die bei einer Gleichheit der Stufen auftritt, l~ur fiir diese engeren implikativen Zusammenh~nge benutzen wir das Zeichen ~.~ Die implikativen Zusammenh~nge im weiteren Sinne treten bei uns hSchstens in Form yon Ableitungsregeln auf , so da f wir z .B. von 9~, falls es bewiesen ist, auf/~D -~ 9~ sehliefen diiffen, ohne da f wir aber z. B. eine Formel wie ~x ~ (I'z -~ ~x) als richtig ansehen. Daf aus 9~(a) immer ~ (a) ableitbar ist, geniigt iibrigens noch nicht, um die Richtig- keit yon ~I(x)~ ~(x) sicherzustellen. Es ist auch erforderlich, da f 9~(x) und ~ (x) Ausdriicke sind, sonst h~tten wir ja unter Umst~nden sinnvolle Formeln mit sinnlosen Bestandteilen. Wenn ferner die Ab- leitung yon ~ (x) aus 9~(x) mit einem unbestimmten x sinnvoll sein soll, miissen wir voraussetzen, daf (E x) 9~ (x) riehtig ist, oder dal~ (E x) 9~ (x) wenigstens ein Ausdruck ist. Auf den geschilderten beiden Gedanken, der Beriicksichtigung des Aus- druckseharakters der Formeln und der Beri~eksichtigung der Gleich- heit oder Verschiedenheit der Stufen beim Sehliefen beruht das folgende Axiomensystem.

w Das A x i o m e n s y s t e m

Wir setzen jetzt den in w 2 begonnenen rein formalen Aufbau fort, naehdem die Art des Weitergehens dureh w 3 und w 4 geniigend motiviert ist.


Wir definieren zun~chst den Begriff der ,,Tautologie". Wir rufen uns dabei den in w 3 definierten Begriff ,,Primbestandteil einer Formel" ins Ged~chtnis zur~ck. Ersetzt man in einer Formel in willkiirlicher Weise die Primbestandteile durch W oder F, aber immer so, da6 formal gleiche Primbestandteile auch in gleicher Weise ersetzt werden, so kann man in bekannter Weise die so ver~nderte Formel auf W oder F reduzieren, indem man immer wieder W durch F ; F durch W; W & F, F & W, F & F durch F ; W& W durch W; F v W , WvF, WvW durch W und FVF durch F ersezt. Reduziert sich bei jeder Anfangsverteilung yon W und F die Formel auf W, so hciBt sie ~ologisch. Im folgenden dienen wie bisher 9/, ~ , ~ , . . . als Mitteilungszeiehen ffir beliebige Formeln, a, b, c . . . . als Mitteilungszeichen fiir Gegenstands- zeiehen ul . . . . , un, ~, ro . . . . als Mitteilungszeichen ffir beliebige Variable. Unter 9/(u), ~(u) , 9 / (U l , . . . , u , ) , . . , verstehen wir Forme]n, die die freie Variable u, bzw. die freien Variablen l h , . . . , t~ enthalten. Das gleichzeitige Auftreten yon 9/(u) und 9/(a) bedeutet, dab 9/(a) aus 9/(u) dadurch entsteht, da6 die freie Variable u an allen Stellen dutch 6 ersetzt wird; entsprechend ist der Zusammenhang zwischen 9/(th . . . . . u~) und 9/(al,. �9 a~). Stat t (EUl) . . . (Eun) sehreiben wir gewShnlich ( E u l . . . u,). /'t~ soil eine Abkiirzung sein fiir (Eu)ul~. Das folgende Axiomensystem ist nun in dem Sim~e aufgebaut, da6 die Beziehung yon -~ zu dem Ableitbarkeitsbegriff durchsichtig ist. An Grund/ormeln haben wir zun~chst die Formeln (EI~)/'I~. Als weitere Grundformeln haben wir nur die, die man mit Hilfe der folgenden Regel gewinnt: Ist 9/eine Grundformel, so ist a u e h / ~ ~- 9/eine Grundformel. (DaB die Variable t~ nicht in 9/vorkommt, ergibt sich aus unserem For- melbegriff.) Wir haben ferner eine Reihe yon Ableitungsregelu oder Ableitungsschemata. Wir bemerken dazu, da6 sich diese Schemata auch auf Formeln mit freien Variablen beziehen, obwohl, wie wir sehen werden, nut Formeln ohne freie Variable herleitbar sind. Die Schemata mit freien Variablen treten aber als Hilfsschemata auf. Die Ableitungs- schemata sind, mit Ausnahme des folgendes Schemas (1), alle solche mit einer Priimisse. Wir haben zun~chst die folgenden Ableitungssehemata (1)--(31), die wir als Grundschemata bezeichnen. (1) Aus 9/mad ~ ergibt sieh 9/& ~. (2) Die gebundenen Variablen in einer Formel kSnnen in der iiblichen Weise umbenannt werden. (3) In einer Formel, in der ein Zeichen ~ vorkommt, kann bei diesem

1 , t l �9 �9 �9 11~

Zeichen die Reihenfolge der Variablen ul . . . . . un beliebig permutiert werden. (4) Der SchluB yon einer Formel 9 /auf eine Formel 9/' soll untcr den folgenden Bedingungen a) und b), die beide erfiillt sein mfissen, mfglich sein: a) ~ v 9/' ist tautologisch; b) alle Primbestandtefle yon 9/' kommen

Ein typen/reies System der Logilr usw. 15

auch unter den Primbestandteilen yon !~I vor. - - In der Bedingung b) ist eingeschlossen, daft ~ ' nur so]che freie Variable enth~lt, die auch in

vorkommen. Beispiele fiir den SchluB (4) sind der Schlull yon ~ auf ~ und yon 9~ v i~ auf ~.

Im folgenden werden wit die weiteren Ableitungsregeln dadurch bezeichnen, dab wir die Priimissen, bei mehreren durch Kommata ge- trennt, vor, und die Konklusion hinter ein Semiko]on setzen.

(5) ~(a); (gu) ~(u) (6) In einer Formel kann ich ~ (al, �9 �9 am) dutch {$ul . . . tt, ~ (up �9 �9 u,)} (al, �9 �9 a~) ersetzen, falls die Variablen us, �9 �9 ~n nieht in ~ (as, . . . , a~) vorkommen. (Die selbstverst/~ndliche, fiir alle Regeln geltende Be- dingung, dab durch die Ver/~nderung wieder eine F o m e l entsteht, brauchen wir nicht besonders zu erw/~hnen.) (7) In einer Formal kann ich {2ul ... u,~[(Ul, . . . , u~)} (a 1 . . . . , a,) durch ~[ (as . . . . , an) ersetzen.

Die folgenden Schemata betreffen die Identitgt. Man k6nnte an und fiir sich denken, dab eine besondere Einfiihrung der Identit/~t entbehrlieh w/~re, da sich a = b dutch ~a -~ ~b definieren lieBe. Diese Ein/iihrung w/~re aber insofern unbefriedigend, well damit die Identitt~t als Be. ziehung h6herer Stufe erscheinen wiirde, w/~hrend wir sic als grund. legende Beziehung ansehen wollen.

(8) ~(a); a = a (9) a - - ~ ( a ) ; ~(b) (lO) ~ ( a ) & ~(~) ; a = b a = a kann als formaler Ausdruek dafiir angesehen werden, dab a ein Term ist. In w 3 hat ten wir (Er als einen derartigen Ausdruek an- gegeben. Man kann aber yon a = a zu (EqJ)efa mit Hilfe unserer Regein iibergehen und umgekehrt.

(11) 2us .-- lt~2 -- 2ul ... tt~2; (Eth ... tin) (9~ v ~)

(12) (Eu) au & (Eulu2) (aul & auz & u - ~ u2); {a} (~ [a])

(13) (t[a] = t[a]; {a}(~[a]) (14) {a}(~[a]); (EUxa~)(aul& ate& u~ --~-~-~) (15) Man kann innerhalb einer beliebigen Formel (Eu)au durch {a} (~[a]) ersetzen, oder aueh umgekehrt. Die Ersetzung ist nur zuli~ssig, falls a nicht die Variable u enth~ilt.

(16) e[a] = ~[a]; (Eu)au v (~u )au

(17) (aU~- btt)& (]bu ~" au)& (PV --~ (Err)all); PV ~ ~[a] = e[b].

Bei dem letzten Schema sollen a und b nicht die Variable u enthalten. Das Auftreten yon/~V ~ in (17) und den weiteren Schemata ist immer so zu verstehen, dab der dahinter stehende Teil der Formel nicht die Variable ~ enth~lt, e [a] ist ein nicht weiter bestimmtes Ding aus dem


Definitionsbereieh yon a, aber ein solches, auf das a zutrifft, falls (Eu)a u der Fall ist. Fiir Pr~dikate mat gleichem abet nicht leerem Umfang soU das ~ das gleiche sein.

(18) F , ~ !g; 2 (19) F1)-~2v!8;(F1)--2.2)v(F1),-I!8)

(20) P1) -2 ( E u l . �9 �9 u~)2 ; 2 ....~,---~ 2

(22) ( 2 ~ %)& ( % ' - - - ~ ' ) ; 2 - - - - + �9 - �9 ~)m u i ... ltn

Unter den I)1, . . . , t),,~ kommen alle Variablen der Reihe ul . . . . . tln vor. !~' und ~' unterseheiden sieh eventuell yon ~ und ~ da~lureh, dab etwaige Variablen der Reihe 01,- . . , t)m, die niehr unier den ul . . . . . u~ vorkommen, so umbenannt sind, dab das Ganze wieder eine Formel darstellt.

(23) (2 ~ %) & (2 u .... u----~ ~) & ( F , ~> ( E u l . . . tt~) ~); 2 ~...u---~ i~ &

(24) ( 2 ~ ) & ( ~ , , _ - - - 5 ~ ) & ( P v ~ ( E u ~ . . . u n ) ( 2 v ! ~ ) ) ; 2vfB~. u I , �9 �9 u i ' ~ ,ul �9 �9 �9 | ]~ ,~ . . . .

Hierbei sind 1), . . . . t),,. bzw. 1)1, .-. , 1)~ diejenigen Variablen aus der Reihe ul, ... un, die in !~ bzw. !~ vorkommen.

(25) 2(u, 1). . . . , ,~)~,~ .... ,----~ ~ ; (Eu)2(u, 1)~ . . . . , ,~) ~

darf hier nicht die Variable u enthalten.

(26) (~(ul , *.., u,~)~ ~ ( U l , - - - , Un) ) & ( F 1 ) ~> (E1)1 . , . 1)/v)~[ (r . . . . (In)); 2 ( 6 [ 1 , f in) - - - - - ~ %(611, . . . a n )

(27) (~ (ul, . . . . 1~) u~...~-~ ~ (U~, . . . 1~)) & (/'1) ~ (E 1)~, . . , 1),)2 (aD ..-, an)

v (~1)~ . . . , ~ ) 2 (a~ . . . . . a ,)) & (F1) ~ (E,1 . . . 1),) ( ~ ( ~ , . . . . o~)

v ~(~1, . - - . ~ ) ) ; 2 ( a l . . . . , ~ ) ~ ~(al . . . . . ~,).

Bei (26) un~ (27) braueht ~ (u l . . . . . 1~) nicht alle Vari~b]en ul, . . . . un zu enthalten; evtL kommen fiberhaupt keine vor. a l , - - . , an sind gewisse Gegenstandszeichen, die auBer 1)1 . . . . , ~ nur solehe freie Variable enthalten, die in 2 ~ ~ vorkommen. Die Variablen ~1, -.. U~ kommen in 2 (u , . . . . 1~) ~"~u~U~ . . . . . lt~) nieht auBerhalb Ul, .- . , ~ vor. Bei

dem Formelteil (Et~ 1 .. . 1)~)(!~(~ x . . . . . a~) vf~(al , . . . , a,)) sind gege- bench Fil ls die Existenzzeiehen fortzulassen, bei denen die entspre- chende Variable nieht in ~ (a l , . . . , c~) vorkommt.

(2s) ~ - - - ~ ~ ; ( / b V (~u~ ... u . )~ v (~ul ... ~ ) 2 ) Ill.. .lI,n

& (r1) 7. ( ~ 1 ... 1)~)(~ v ~) ) . . . . b~ siad diejenigen Variablen aus der Reihe u~, . . . , ~ , die in

vorkommen.

Ein typen]reies System der Zogilc usw. 17

(29) FIJ-~ (Eli I ... Un)(9~& ~)" ~ ------~ l i l . . . nn

(30) 2 ~ ~ ; F ~ - 2 (Eu~ ... u~)(~& ~) Wir bemerken dazu, dal3 wir kein Extensionalit~tsaxiom eingefiihrt haben, da uns andere MSglichkeiten zur Verfiigung stchen, die Ab- straktion, die im ~bergang yon den Pr~dikaten zu den Mengen liegt, oder fiberhaupt andere Abstraktionen aus Gleichheitskreisen wiederzugeben.

(31) Es sei 2(x) eine Formel, unter !~(~) sei hier 2(xl)& . . .& 2(x~), unter ~(t)) sei 2(yl)& ... & 2(y . ) verstanden. ~ stehe fiir x l . . . x~ und t) fiir y~... Yn. Die Pr~misse des folgenden Schlusses ist nun die Kon- junktion der folgenden Pr~missen: / '~ ~ (Ex)2(x) , 2(x)& 2(y) ~-~ X

--~ y v x = y und i~(~)& ~(t~) ~ ~(~, t)) v ~)(~,t)). Die Konklusion ist

F , & ~(t)) ~ (E~)(fi~(~) & ~)(~, t))) v (E~) (!3(~) & ~)(~, ~)). Die Vari- ablen t~ k6nnen auch fehlen. Es sind dann die Bestandteile ~(t~) in obigen Formeln fortzulassen. Die Grundschemata (1)--(31) sind nicht die einzigen Schemata. Aus jedem Schema mit einer Pr~misse erh~lt man ein neues Schema. Die Regel heiBt:

(32) Is~ 2 ; ~ ein Schema, so ist auch

(~ ~ 2) & (/'l~ ~- (EU~ ... Un)~); ~ ~ !~ ein Schema.

w 6. Zu den H e r l e i t u n g e n aus dem A x i o m e n s y s t e m

Wit bemerken zun~chst, dab nur Formeln ohne freie Variable her- geleitet werden kSnnen, in ~bereinstimmung mit dem angenommenen Standpunkt. Denn kein Schema enth~lt in der Konklusion andere freie Variable als solche, die auch in den Pr~missen vorkommen. Da nun die Grundformeln keine freie Variable enthaltcn, ist das auch fiir alle hergeleiteten Fo1~neln der Fall. Wir haben ferner den folgenden Satz: Satz I: Ist eine Formel 9/herleitbar, so ist auchFD ~ 9/herleitbar.

Das gilt zun~chst ffir die Grundformeln, da mit 9 /auch/ '~ 7> 2 Grund- formel ist. Es mSge ferner 9I& ~ aus 2 und !~ nach Schema (1) bewiesen sein. Sind nun Ft~ -~ 2 u n d / ' ~ -~ f~ beweisbar, so erh~lt man aus diesen beiden Formeln und der Grundformel/ 'm ~ (ED)FV nach (1) (/'t~ ~- 2) & (/'t~ -~ !3) & (/ 'tU~ (Et~/'l~), also infolge des Schemas (23) FtJ ~- 9/& ~ . Sei ferner !3 aus 2 nach einem anderen Schema beweisbar. Ist n u n / ' ~ ~- 9/beweisbar, so erh/~lt man nach (1) (/'lJ ~- 9/) & (/'l~-~ (Et~)F~), also nach dem Schema, das aus 2 ; ~ dutch Er- weiterung nach (32) entsteht, / 't~-~ i~. Damit ist der SaSz I dutch Induktion bewiesen. 2 Mathematlsche Logik (4/1, 2)


Satz II: Aus der Pr~misse 9/sei mit Hflfe unserer Ableitungsschemata und evtl. unter Benutzung von hergeleiteten Formeln E~l,..., ~k die Formel % ableitbar. Ferner sei (Eui ...un)9/ herleitbar. Dann ist 9 / ~ % herleitbar.

III .. ,llr~

Beweis: Jede Formel ~ der Herleitung yon % aus 9/veriindern wir in der Weise, dab wir sie durch ( 9 / ~ ~)& (FV ~ ( E l l 1 . . . Un)9/) ersetzen; bei der letzten Formel lassen wir das Konjunktionsglied/'~ -~ (Eul ... un)2 fort. Die Anfangsformel der so vcrinderten Herleitung ist dann ( 9 / ~ 9/) & (FI) ~ (Eth ... u~) 9/), die Endformel 9 / ~ %. Die Anfangsformel ist beweisbar. Denn da (EUl... u~)9/beweisbar ist, ist nach Satz I auch FV ~ (Eui . . . u~)9/beweisbar. Nach Schema (20) ist 9 / ~ 2 und nach (1) auch ( 9 / ~ 9/)&(EV-~ (Eul...lin)9/)

l~i.- .lha i.-- n

beweisbar. Ferner kann die so vedinderte Herleitung wieder zu einem Beweise erginzt werden. Seien ~)l und ~)~ zwei konsekutive Formeln der urspriinglichen Herieitung. Aus ( 9 / ~ ~)1) & (FV -~ (Eul ... un)9/) erhiilt man nach einem erweiterten Schema 9 / ~ ~)2, mi t / 'V-~

U I �9 �9 .11~ t)

(Eui ... u,)9/ zusammen nach (1) ( 9 / ~ ~)2) & (/'0 -$ (Eul ... 1~)9/). Es m6ge ferner in der urspriinglichen Herleitung ~)i & ~2 aus ~)i und ~)~ entstehen. Aus (9/u,..,,----~ ~)i) & (/'I~ -~ (EUl ... its)9/) und ( 9 / ~ ~)2) & (F0 T (Eui...lt~)9/) erhilt man nach (1) und (4) ( 9 / ~ ) 1 ) & (9/~,------~..v~ ~)~)& (I' , "2" (Eu~ ...u,)9/) also nach (23) 9/u .... u-----~ ~)~& ~)~' und weiter auch ( 9 / - - - - ~ i & ~ ) ~ ) & ( F V ~ (Eul...u~)9/). Ist eine

U 1 .., H~

Formel ~i der urspriinglichen Herleitung unabhiingig yon 9i schlechthin beweisbar, so ist nach Satz I auch FV -~ ~i, nach (21) 9/u~...u----~ ~ und nach (1) ( 9 / ~ ~ ) & (/'V -~ (Eui . . . u,)9/) beweisbar. Demnach ist also 9 / ~ % beweisbar.

Bemerkung: Der Satz II enth~lt eine Art Deduktionstheorem. Die Giiltigkeit dieses Deduktionstheorems ist aber davon abhingig, dab die Grundformeln und Ableitungsregeln in der angegebenen speziellen Form gewihlt werden. Z.B. gilt das Deduktionstheorem nicht fiir das in w 7 aufgestellte Axiomensystem, obwohl es die gleichen beweisbaren Formeln liefert.

Satz I I I : Es l~iBt sich ein Gegenstandszeichen a angeben, so dal~ Fa beweisbar ist.

Beweis: Aus der Grundformel (Ex)['x erhi~lt man nach (6) (Ex) {~yFy} (x), nach (15) {~yFy} (~[~yI'y]) und nach (7) F(~[2yT'y]). a ist also ~[~ ylT'y].

Satz IV: Sind 9/(~1 . . . . , ~n) und 9/(ui, ..., Un) ~ %(ui . . . . , u.) herleitbar, so auch % (~ . . . . . ~). % braucht nicht alle Variablen Ul . . . . . u~ zu enthalten.

Ein typen/reies System der Logik usw. 19

Beweis: Aus ~I(Ul . . . . , u , )& Fz ist nach (4) 92(ul . . . . . u~) ableitbar. Da 92(a 1 . . . . , a ~ ) & F a, also nach (5) auch (EUl . . . u~z)(92(ul . . . . , u,~)&Fz) beweisbar ist, so ist nach Satz I I 92 (ul . . . . . 1~) & F z -~ 92 (ul, . .- , u~)

~ I " �9 * t i n Z b e w e i s b a r u n d n a c h (22) 92(Ul, . . . , Un) & / 1 z l~l...l~n"- ~ ~ (111, . . . , l~n). N a c h

(26) erhalten wir 92(al, . . . , o~)& Fz-~. !8(a1 . . . . . an). Da 92(al . . . . , an) beweisbar ist, kSnnen wir aus Fz nach (1) 92(al . . . . ", an)&I'z beweisen, so dab naeh Satz I I Fz -2" 92(al . . . . . a,) &Fz beweisbar ist. Nach (22)

erhal ten w i r / ' z ~ !~ (ai, . . . , a,) und naeh (19) ~ (al . . . . . , an).

Satz V: Sind (E u l . . . u~) 92 (ul . . . . , un) und 92 (ul . . . . . un) ~ ~ (Ul . . . . . Un) U 1 . . �9 l l r ;

beweisbar, so auch (Eul ... u~) !8 (ul, . . . , u~). Die Behauptung und der Beweis ist entsprechend zu modifizieren, falls !~ die Variablen .ul, ... Un nicht alle oder f iberhaupt nicht enthi~lt.

Beweis: Aus (Eul .. . u , )92(ul , . . . , un) erh~lt man dutch wiederholte Anwendung des Schemas (15) eine Formel 92(s~, . . . , en), wobei ex . . . . , e. gewisse Gegenstandszeichen der F o r m e[a] sind. Nach Satz IV ist

(~1, . . . , ~n) beweisbar und nach (5) (Eu~ ... 1~) ~ (ui, . . . , un).

Satz VI : I s t (Eu~ ... u~)92(111, . . . , un) beweisbar, so auch (E~I ... 1~) 92 (Ul . . . . , un), wobei die ~1, ... I~, nur eine Permuta t ion der Ul . . . . , l~n darstellen.

Beweis: Aus (EUl .. . u,)92(u~, . . . , u.) erh~lt man die oben erw~hnte Formel 92(e~, . . . , en) und dann ( E ~ ... I)~) 92(u~ . . . . . un~ dutch passende Anwendung yon (5).

w E i n z w e i t e s A x i o m e n s y s t e m

Das in w 5 angegebene Axiomensystem ist besonders geeignet, erkennen zu lassen, dab es gem~B den in w 4 entwiekelten Grundgedanken aufgebaut ist. I m folgenden gehen wir ein zweites ~quivalentes Axiomen- system mehr in der iiblichen Form, da~ mit endlieh vielen Ableitungs- regeln arbeitet. Fa sei wieder eine Abktirzung fiir ( E u ) u a . S tar t x x .. . x~ schreiben wir oft ~, s tar t Yl ... ym wird t) und start z 1 .. zk wird $ ge- schrieben.

Gru~d/ormeln sind die folgenden:

(1) epx ~ (Ey)rpy

(2) ~ x ~ x = x

(3) x = y&q~x----~

(4) ~ x & ~-~- -~ y = x a CXy

(5) ~ ( ~ ) = ~ ( ~ ) 7 ( ~ ) ( ~ v ~ ) 2*


(6) (Ex)q~x& (Exy)(qgx& ~y& ~ ) - ~ {~}(t[~])

(7) ~[~] = ~[~]; {~}(,[~])

(8) {~} (t[~]) -~ (Exy)(~x& q~y& ~--=-~)

(9) e[~] = e[~] ~ (Ex)~x v (Ex)~x

(10) (~x -~ ~x) �9 (~x -2 ~ ) ~ (Fy -~ (Ex)~z) j~ e[~] = e[~]

(11) ( F y - ~ x ) ~

(12) (Fz -~ qJx v ZY) ~ (Fz -~ ~x) v (Fz 7 %Y)

(13) (py 7~ (E~)e~) ~ (e~ 7 e~) (14) (I'y ~ ~x) & (Fy -~ (E~)~o~) ~ (yJ~ -~ q~x)

(15) (e~ 7 ~ ) a ( ~ ~ ~ ) ~--i~ (e~ 7 ~$) entsteht hier aus t) durch Umbenennung der Variablen.

(16) ( ~ 7" ~ ) ~ ( ~ 7 ~ ) ~ (~z ~ (E~)~) ~ ( ~ ~ ~ v ~ )

(17) ( ~ y ~ ) a ( ~ y ~ ) ~ (Fz ~ (E~)(~ v ~)) ~%-~ (~ v ~ 7 ~) (18) (q~y~ -~ yJ~) ~ ((Ey)q~y~ -~ y~)

(10) ( ~ 7 ~P~) ~ (~z 7 (E~)~ v (E~)e~) a (rz 7 (~)(~P~ v~)) .

(20) (Fz 7 ( E ~ ) ( ~ ) ) ~ 7 ~

(21) ~ 7 ~ ~ (~z ? (Z~)(~ a ~))

(22) (Fz 7 (Ex)q~x)& (qgx&q~y-* x = y v x -~ y)

(~(~) ~ ~ (~) ~ x ~ v ~i-~) ~ (Fza ~ (~) (~) ~(~) �9 z ~ ) v (E~)(~(~) ~ Z~)) zl)

ist Xx ... x~, t) ist y~ ... y~. 9~(~) steht fiir ~xx& . . . & ~ x ~ , ~(t)) ~fir eye& ... & q0y~. Hier kSnnen die Variablen t) und die Glieder !~ (t)) auch fortgelassen werden. Die Grundformeln (15)--(21) kSrmen auBerdem in modifizierter Gestalt auftreten, die dadurch ents~eht, dab man bei einer oder bei mehreren auftretenden Pr~dikatvariablen ~0, ~o, z~ gewisse Argumente streieht und die Indizes bei den Subsumtionszeichen und die Existenzzeichen fort- l~Bt, in deren Wirkungsbereich die Variable nicht mehr vorkommt. Die Streiehung muB bei derselben Pr~dikatvariablen gleiehm[iBig erfolgen, so dab fiberaU die Argumente mi~ der gleiehen Nummer ges~richen werden. Selbstverst/indlieh ist Bedingung, dab das Ganze wieder eine Formel darstellt. Beispielsweise wiirde die Grundformel (20) aueh in der Form (Fz -~ (E xx x~) (~ xx x~ & ~-~)) ~ ~0 x~ x~ ~ ~o x~ vorkommen.

Ein typen]reies System der Logik usw. 21

An Ableitungsregeln haben wir die folgenden:

I. Eine Umbenennungsregel fiir die gebundenen Variablen.

II. Bei einem Subsumtionszeichen ~ innerhalb einer Formel kann lI 1 �9 ~ �9 Un

die Reihenfolge der ul . . . . , un permutiert werden.

III . Aus 9~ und !~ erhglt man ~ & !~.

IV. Aus 2 erhi~l~ man_F~ -~ 9~.

V. Aus 9/(al, a~) und 9/(ul, u ~ ) - - - - > ~(u l , .. ~n) erhMt man . . . ~ , . . ~ i~i., .i~ n "~ (al . . . . , an). (Es is~ nicht nStig, dal3 alle Variablen ul, -. . , u~ in

!~ (ul . . . . , un) vorkommen).

VI. Ist (E~)9~ beweisbar, so auch ~I-~ 2 ' . Dabei stehen 9I' und 9~ in dem gleichen Verh~ltnis zueinander wie die gleieh benannten Formeln des Schemas (4) yon w 5.

VII und VII I sind die Schemata (6) und (7) yon w 5.

IX ist die Regel (15) yon w 5.

X. Wir nennen ein Gegenstandszeichen a einen Term, wenn bei konstantem a die Formel a ~ a beweisbar ist, und bei Gegenstands- zeichen a mit den alleinigen freien Variablen ~, wenn (E~)(a : a) beweisbar ist. Es seien nun al . . . . , an Terme, die nur die freien Variablen t~ und $ enthalten. Dann ist

(qJxl . . . xn~ .~ . .~ ~x~ . . . x ~ ) ~ (Fz 7 (E~)q~a~ . . . an)

- - * (~a~ . . . an 7 ~a~ . . . an)

eine beweisbare Formel. Unter den gleichen Bedingungen ist femer

(~x l . . . xn ~ ~x~ . . . x~) & (Fz T (E~)q~a~ . . . a~ v (E~)qDa~ . . . an)

~5 ( / ~ Z - ~ ( E ~ ) ) ( ~ 0 { ~ I . . . a n v ~ / ) a l . . . ~ n ) ) ~ ( ~ ~ * . - a n - ~ ~ 0 a l . - - a n )

beweisbar. Wir wollen dieses Axiomensystem fortan mit /- /bezeichnen und das yon w 5 mit 27. Zeigen wit nun die ~quivalenz yon 27 u n d / / i n dem Sinne, dab jede Formel, die in dem einen System beweisbar ist, sich auch in dem anderen beweisen l~Bt. Relativ einfach ist zu zeigen, dal~ jede in / /beweisbare Formel auch in Z beweisbar ist. Der Ausdruck ,,beweisbar" in den folgenden Ausffihrungen bezieht sich also zuntichst immer auf das System 27. Dal~ die Grundformeln y o n / / b e w e i s b a r sind, ergibt sich sofort aus dem Satz I I yon w 6, da jeder Grundformel y o n / / e i n Grundschema yon 2: entspricht. Um den Satz I I anwenden zu kSnnen, sind nur gewisse Existenzbehauptungen zu beweisen. Die leich$ zu fiihrenden Beweise geben wir nicht im einzelnen. Als Beispiel mSgen die Beweise der zu den Grundformeln (4) und (6) geh6rigen Existenzbehauptungen geniigen.

2 ~


Aus/~a (Satz I I I yon w 6) erh~lt man naeh (4) und (1 )Fa&/ ' a . , naeh (6)

{), y F y } (a) & {). yT'y} (a) , weiter nach (6) {]~zza} (~ y Fy) & {)~(z~)} (4 yI" y),

hieraus nach (5) (Ecxy)(cpx&q~y) . Bei dem zweiten Beispiel ist zu- n~chst aus x = a & y - - a unter Benutzung yon (9) x ~ - - y v x - - - - y ableitbar, so dab man nach S a t z I I x ~ a & y - ~ x = y v x = y erh~lt, und auch x = a & y = a ~ x ~ y v x = y . Unter Benut. zung yon (31) erhalten wir / ~ -~ ( E x y ) (x : a & y = a & ~ )

v (E x y) (x = a & y = a & x = y ) , also auch die gleiche Formel ohne den Zusatz F ~ ~ . Es sei nun 81 eine Abkfirzung ffir 8 [4 x (Ey) (x = a & y = a

& ~ ) ] , 8~ eine solche ffir e[2y(81-----a& y - - - - a& ~ ) ] . Nach Schema (15), (6) und (7) erhalten ~ i r (~ t - - - - a& e~ = a & 8 1 = ~ )

V 81 m O" & 8 2 = O" & 81 = 8~. Ferner ist aus x = a & y = a auch x = a & y ----- ~ & x ~ - y ableitbar, so dab x ~- a & y = a - ~ x y

x = a & y = a & ~ beweisbar is~. Endlich ist x = a v y - - ~ v x - - y -~ x = a & y ---- a & ~ beweisbar, so dab sich nach Schema (24) x y

(x - ~ a & y = a ) v x = a v y = a v x ~- y ~ x = a & y - - - - a & x = y x y

ergibt. AuBerdem ist

(x = a & y = a & ~ ) v x = a & y = a & x ~- y - ~ (x ----a& y = a ) x y

VX=avy=avx =y

wegen des Schemas (4) ableitbar. Nach Schema (22) erhalten wir ( x = a & y = a & ~ - ~ - ~ y ) v x = ~ & y = a & x - - - y ~ x = a & y = a & x = y.

Nach Satz IV ist claim e~----a & 8~ = a & 8~----8~ abteitbar, was sieh

mit Hilfe yon (15) in ( E x y ) ( x ~- a & y = a & ~ y) umformen l~Bt. Aus F a ist naeh (8) ~ = ~, nach (5) ( E x ) ( x = a) ableitbar. Nach (1)

ergibt sich ( E x ) ( x = a) & ( E x y ) ( x = a & y ----- a & ~ - - ~ ) und mit Hflfe yon (6) und (5) (E~f)((Ex)q~x & (Exy) (epx &cpy& Z-"~ y)). Zeigen wit weiter, da[3 man auch dureh die Ableitungsregeln yon H aus in ~: bcweisbaren Formeln wieder ebensolche Formeln enth~lt. Zu- niichst sind die Ableitungsregeln I, I I , I I I , VII , V I I I und I X yon / / auch im System Z vorhanden. Auch die Regeln IV und V y o n / / k S n n e n wieder nur in 2: beweisbare Formeln liefern wegen der S~tze I und IV yon w 6, und auch die Regel VI wegen des Satzes I I yon w 6. Wegen des Satzes I I yon w 6 ist das auch fiir die Regel X der Fall, da man in ~ die Schemata (26) und (27) hat. Wir wollen nun umgekehrt zeigen, dab jecle in 2: beweisbare Formel auch i n / / b e w e i s b a r ist. Alle Bemerkungen fiber Beweise irn folgenden beziehen sich also auf das S y s t e m / / . Wir beweisen dazu verschiedene HiIfss~tze:

H 1. Jede Grundformel yon 2: ist i n / / b e w e i s b a r .

Ein typen]reies Sysgem der Logits u.sw. 23

Zungchst l/~Bt sich ein Gegenstandszeiehen a angeben, so d a b / ' a beweisbar ist. Aus der Grundformel ~0 x ~ x : x erhalten wir nach Regel VII q)x~{~y(y----y)}(x) tend weiter {~z(q~x~zx}}(2y(y:y)) . Ferner ist in / / m R 92(a} auch (Ey}92(y) beweisbar. Aus 92(a) erh~lt man n~mlich nach Regel VII {2u92(u}}(a). Infolge der Grundformel qZx -~ (Ey}Ty erh/ilt man nach der Regel V (Ey} {~u92(u}} (y} und nach VIII (Ey)92(y). Wir erhalten demnach aus {2z(qjx ~ zx}} (~y(y : y}) die Formel (E~){~} (2u(u -----u}) d.h. F (2u(u := u)). Aus der letzten Formel ergibt sich die Grundformel (ED)FD yon 2:. Nach der Regel IV erhalten wir alle weReren Grundformeln yon 2:. Die Grundsehemata yon 27 mit Ausnahme der Schemata (1}, (2), (3}, (6}, (7) und 15) wollen wir im folgenden Schemata vom 1. Rang nennen. Entsteht ein Schema yon Z" nach der Regel (32} yon 27 aus einem Schema yore Rang n, so soll es den Rang n d- 1 haben. Neben (I}, (2}, (3), (6), (7} und (15} bleiben dann als Schemata ohne Rang solche iibrig, die aus den vorgenannten Schemata mit Ausnahme yon (1) dureh An- wendung der Regel (32) yon 27 entstehen. Diese Schemata liefern aber gegeniiber (2}, (3}, (6}, (7} und (15} nichts Neues, so dab wir sie nicht weiter zu beriicksichtigen brauehen. Wir wollen ferner sagen, ein Schema 92; ~ entsteht aus einer Subsum- tionsformel ~(xl, x~} ~ ~) (xl, x~) dutch Einsetzung wenn es gewisse Gegenstandszeichen al . . . . , a,~ gibt, so dab ~(al, . . . , a~} mit

identisch ist oder durch Anwendung der in den Regeln I und VHI y o n / 7 angegebenen Umformungen in 92 iibergefiihrt werden kann und wenn das gleiche VerhgRnis zwischen ~D(al,..., a~) und ~8 vorliegt. Diese Definition soll auch entsprechend zutreffen, falls ~(x~ . . . . , xn} nicht alle Variablen x~ enth~R. Das Schema 92; ~ kaml in 9I und ~ auch freie Variable enthalten.

H 2. Es sei 92; ~ ein Schema yon 27 vom Rang 1. Ferner sei 9~ beweisbar oder falls 92 die freien Variablen ~ enthgl~, sei (E~}92 beweisbar. Da~n entsteht 92; ~ aus einer in H beweisbaren Subsumtionsformel durch Einsetzung. - - Wegen tier Regel V yon / - /bedeute t das, dab diese Schemata (natiirlich nut sower sie keine freie Variable enthalten} aueh i n / / g i i l t i g sind. Fiir d~s Schema 92(a); (Ey)92(y) haben wir oben sehon gezeigt, dab es ans der Grundformel ~x -~ (Ey)qJy durch Einsetzung entsteht. Xhnlich zeigt sieh das ffir die meisten anderen Schemata, da ihnen entspreehende Grundformeln yon/ /gegeni ibers tehen. Ffir die Schemata (26) und (27} lieferb die Regel X y o n / / d i e passenden Subsumtionsformeln. Fiir das Schema (1 8) und einige anderen Schemata ist beziiglich der betreffenden Subsumtionsformeln, hier (/'D ~ ~x} ~-~x , folgendes zu beaehten. Jede Formel 9~ lgBt sieh vermittels der in Regel VII angegebenen Um- formung auf die Form {c} (b) bringen und naeh Regel VIII ist der umgekehrte ~bergang m6glich. Enthi41t ngmlieh 92 eine Pr imfomel der

24 Wilhelm A ckermann

Form a----b, so schreiben wir {iuV(u = •)} (a, b) daffir innerhalb ~I. Ffir 92(iu~(u ---- D)) schreiben wir dann {t~92(~)} ( lu~(u = ~)). u, 1), ro kommen d~bei in ~ nicht vor. Falls ~I keine derartige Primformel ent- h~lt, enth/flt sie eine Primformel der Form abl ... b,. Wir ersetzen diese dann innerhalb ~ durch { i~u l . . . un (Vul. . . u~)} (a, bl . . . . , bn) und gehen im iibrigen wie oben vor. I-Iat das Schema die Form 9~; 92' so ist

-~ ~I' die Subsumtionsformel, die nach VI beweisbar ist.

H 3. Der Satz H 2 grit auch fiir Schemata vom Rang > 1.

Wir beweisen das durch Induktion nach dem Rang des Schemas. Ein Schema vom Rang n + 1 hat die Form

(~-~ 9~) & (F~ -~ (E~)~);~ ~ !~, wo 92; !~ ein Schema vom Rang hist .

Enth~lt ~ ~ 92 keine freie Variable, so ist F~ ~ (E~)~, also aueh (E~)~ beweisbar, und ferner eine Formel ~', die nach Regel IX aus (E~)~ dadurch entsteht, dab die Stellen der freien Variablen in ~ mit gewissen e-Termen besetzt werden. Nach Regel V y o n / / i s t dann ~I odor (E~)92 beweisbar. - - Enth~lt ~ 7 92 freie Variable t), so ist (Et))((~-~ 9~) & (P~-~ (E~)~)) beweisbar, und man zeigt in ahnlicher Weise unter Benutzung der Regel IX, dab (E~t))92 beweisbar ist. Nach der In- duktionsvoraussetzung exisr nun eine in / / beweisbare Formel

(ul . . . . . u.) ~ ~ ( u l , . . . , u~) und Gegenstandszeiehen al . . . . . a~, so dab 9~ bis auf die genannten Umformungen mit (~ (al, . . . , an) und !8 mit ~ (al, -.., an) identisch ist.

1) 92; !~ mSge keine freie Variable enthalten. . . . . . . �9 > (~0~ - ~ (~ (Vl , . , Vn) ) ~5 ((~) (1~1, " ' l ln ) l~.-------->..,n ~0(111' " ' Un)) epv,...vn

(q~-~ ~ (vl , . . . , Vn)) entsteht dann nach dem auch ff i r / /gf i l t igen Schema (26) von Zaus einer Grundformel (15). Da (~ (ul , . . . , un) ~...----~ ~ (up �9 �9 �9 un) beweisbar ist, erhglt man hieraus ( ~ - ~ (~(vl . . . . '%)) ~n...v~

(9~ 7 O(vl . . . . , v~)) und (9~ 7 @(vl, . . . , %)) & (/'~ ~ (E~)~) ~n...v2 (q)~ ~ ~ (vi . . . . . vn) ). Das ist abet eine Formel der verlangten Art.

2) Enth~lt 92 freie Variable, so seien davon ~ diejenigen, die auch in vorkommen, t) die anderen. Die al, . . . , an mfissen in diesem Falle die Variablen ~, t) enthalten. Die Reihen ~l und t h mSgen sich yon ~ und t) nur durch Umbenennung unterscheiden. Aus der Formel (~ (ui . . . . . un) u~...~i~ ~(u~, . . . , u,) erhalten wir nach (26) (~(v21~1~1 . . . . ,Vn~l~l)

+ ~) (~l~lth, . . . ,Vn~lt)l ). Weiter entsteht ( ~ -~ (~ (0~t), . . . , v~n ~ ~)))

-~ $ ( ~ l ~ t h , . . . , ? ~ l ~ ) ) ~ . . .~ ,~ ( ~ - ~ ~ (~l~t) . . . . , v ~ t))) aus einer Grundformel (15) nach Schema (26), woraus sich ~hnlich wie oben ( ~ 7 ff~ (v~l~t)' "'" ' v~n~ t))) & (F~ ~ (E~)~)

~... a, ~ (~ ~ 7 ~ (#~ ~ t), . . . , ~, ~ t)) ) abgeleitet. Das ist wieder eine Formel der verlangten Art.

Ein typen]reies System der Log~k usw. 25

Mit H 2 und H 3 sind infolge der Regel V yon / / a l l e Schemata mit einer Pr~misse auch in / /g i i l t ig , zun~chst mit Ausnahme der in H 2 genannten. Diese letzten kommen aber aUe auch als Regeln in / / v o r . Ebenso ist es mit dem einzigen Schema yon 2: mit mehreren Pr~missen, dem Schema (1) der Fall, das als Regel I I I in H vorkommt. Damit ist gezeigt, dal] alle in 2: beweisbaren Formeln auch i n / / b e w e i s - bar sind, und darfiber hinaus mit dem vorigen zusammen die ~quivalenz yon 2: u n d / / .

L I T E R A T U R

[1] W. Aclcermann: Ein System der typenfreien Logik I. Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften, N.F. , Heft 7, 1941.

[2] - - : Widerspruehsfreier Anbau der Logik. Typenfreies System ohne tertium non datur. Journal of Symbolic Logic 15 (1950), S. 33--57.

[3] - - : Widerspruchsfreier Aufbau einer typenfreien Logik {erweitertes System). Math. Zeitschrift 55 (1952), S. 364---384.

[ 4 ] - - : ~Tiderspruchsfreier Aufbau einer typenfreien Logik II . Math. Zeitschr, 57 (1953), S. 155--166.

[5] - - : Zur Axiomatik der Mengenlehre. Math. Annalen 131 (1956), S. 336--- 345.

[6] H. Behmann: Zu den Widersprtichen der Logik und Mengenlehre. Jahresbericht der Deutschen Methematiker-Vereinigung 40 (1931), S. 37--48.

[7] - - : Deskription und limitierte Variable (1944, erweitert 1952). [8] - - : Die Ausschaltung der logisehen Paradoxien durch die typenfreie

Logik mit den Werten ,,wahr", ,,siImlos" und ,,falsch". (1953). (Die letzten beiden Arbeiten sind durch ttandabzug vervielf~ltigt).

[9] - - : Die Besetzungskette und der widerspruchsfreie Pr~dikatenkalkfil (1956). (Vom Verfasser zugesandter Durchschlag eines Manuskripts).

[10] A. Church: A set of postulates for the foundation of logic. Annals of Mathematics 33 (1932), S. 346---366.

[ 11] - - : A set of postulates for the foundation of logic (second paper). Annals of Mathematics 34 (1933), S. 839--864.

[ 12] - - : A proof of freedom from contradiction. Proc. Nat. Acad. of Sciences 21 (1935), S. 275---281.

[13] - - : Mathematical Logic. Vorlesungen an der Princetoner Universit~tt 1935/36. Mimeographiert.

[ 14] H. B~ Curry: The paradox of Kleene and Rosser. Transactions American Mathematical Society 50 (1941), S. 454---516.

26 Wilhelm Ackernmnn, Bin typen]reie8 System der Logik usw.

[15] - - : The inconsistency of certain formal logics. Journal of Symbolic Logic 7 {1942), S. 115---117.

[16] - - : Philosophische Bemerkungen zu einigen Problemen der mathe- mathischen Logik. Archly fiir Philosophie, Heft 4]2, 1951.

[17] K. G6del: ~ber formal unentscheidbare S~tze der Principia Mathe- matica und verwandter Systeme I. Monatshefte f'fir Mathematik und Physik 38 (1931), S. 173--198.

[18] R. Harrop. An investigation of the propositional calculus used in a particular system of logic. Proceedings of the Cambridge Philosophical Society 50 (1954), S. 495--512.

[19] S. C. Kleene and J. B. Roaser. The inconsistency of certain formal logics. Transactions American Mathematical Society 36 (1935), S. 630--- 636.

[20] W. V. Qulne: Mathematical Logic. 2. Aufl. 1951. [21] K. Schi~te: Zur Widerspruchsfreihcit einer typenfreien Logik. Math.

Annalen 125 (1953), S. 395 ~00. [22] - - : Ein widerspruehsfreies System der Analysis auf typenfreier Grund-

lage. Math. Zeitschrift 61 (1954), S. 160---179. [23] V. Valpola: Ein System der negationslosen Logik mit ausschliel31ich

realisierbaren Pr~dikaten. Acta Philosophica Fennica, Fasc. IX, 1955.

Documents

Ein Typenfreies System der Logik mit Ausreichender Mathematischer Anwendungsfähigkeit I