Über die Erfüllbarkeit gewisser Zählausdrücke. (Q5907240)

Nach einem Satze von \textit{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 \textit{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 \S\,3 behandelt und mit Hilfe eines Exhaustionsverfahrens das Entscheidungsproblem gelöst.