×

Über die Erfüllbarkeit gewisser Zählausdrücke. (German) JFM 54.0057.01

Nach einem Satze von L. Löwenheim ist jeder Zahlausdruck, d. h. logischer Aussagenausdruck, worin “alle” und “es gibt” nur auf Individuen angewandt sind, entweder widerspruchsvoll oder schon in einem abzählbaren Bereiche erfüllbar. Für gewisse einfach gebaute Zählausdrücke kann man zeigen, daß sie, wenn überhaupt, schon in einem endlichen Bereiche erfüllbar sind. Die vorliegende Arbeit von Ackermann enthält einen Beweis dafür, daß dies für alle Zählausdrücke gilt, worin nur eine Anwendung von “alle” vorkommt.
Er beweist seinen Satz dadurch, daß er von einem abzählbar unendlichen Bereich ausgeht, worin die Zählaussage erfüllt ist, und daraus durch gewisse Identifizierungen der Individuen mit zugehörigen neuen Bestimmungen der Werte der Aussagenfunktionen einen endlichen Bereich ableitet, worin der Zählausdruck gilt.
Ein einfacheres Beweisverfahren, das auch zu kleineren endlichen Bereichen führt, ist jedoch möglich. Es sei \(L\) die Zahl der im Schema auf S. 645 vorkommenden Wertsysteme der Relationen \(\Phi\) für die verschiedenen Systeme \(y_1,\dots,y_l\), und es bestehe jede der Symbolreihen \(a_1,\dots,a_{lL},b_1,\dots, b_{lL}, c_1,\dots,c_{lL}\) aus \(L\) Systemen mit je \(l\) Symbolen. Für diese Symbole werden die Werte von \(\Phi\) so bestimmt, daß die \(L\) Wertsysteme auf die \(L\) \(l\)-Systeme jeder Reihe verteilt werden. Für \(a_ia_i\) haben dann die \(\Phi\) dieselben Werte wie für gewisse \(xx\) im Schema. Gehören \(y_1,\dots y_l\) zu einem solchen \(x\), so haben die \(\Phi\) für diese dieselben Werte wie für ein \(l\)-System der \(b\)-Reihe, etwa \(b_{ij}\) \((i=1,2,\dots,l)\). Dem \(a_i\) ordnen wir die \(b_{ij}\) zu, und die Relationen \(\varPhi\) werden für die Paare \(a_i b_{ij}\) in Übereinstimmung mit ihren Werten für die \(xy_j\) bestimmt. Da die Paare \(a_ib_{ij}\) von allen Paaren \(a_{i'}b_{i'j}\) verschieden sind, wenn \(i \neq i'\) ist, so ist dies ohne Widerspruch für alle \(i\) \((i=1,2,\dots,lL)\) gleichzeitig möglich. Ebenso ordnen wir den \(b\) je \(n\) Symbole \(c\) und den \(c\) je \(n\) Symbole \(a\) zu. Dann ist der Zählausdruck offenbar im Bereiche der 3 \(lL\) Symbole erfüllt, wie die \(\Phi\) auch sonst bestimmt werden.
Übrigens hat Referent, ohne Ackermanns Arbeit zu kennen, in der nachstehend referierten Arbeit u. a. dasselbe Problem wie Ackermann in § 3 behandelt und mit Hilfe eines Exhaustionsverfahrens das Entscheidungsproblem gelöst.

PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] P. Bernays und M. Sch?nfinkel, Zum Entscheidungsproblem der math. Logik, Math. Annalen99 (1928).
[2] Die Symbolik ist die gleiche wie in: D. Hilbert u. W. Ackermann, Grundz?ge der theoretischen Logik (Springer 1928) [zitiert im folgenden als H.-A.]. · JFM 54.0055.01
[3] Vgl. H.-A., S. 79.
[4] Vgl. Bernays und Sch?nfinkel, P. Bernays und M. Sch?nfinkel, Zum Entscheidungsproblem der math. Logik, Math. Annalen99 (1928) S. 3.
[5] Vgl. H.-A., Seite 80.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.