×

zbMATH — the first resource for mathematics

Die Unentscheidbarkeit der einstelligen unendlichwertigen Prädikatenlogik. (German) Zbl 0533.03007
Die unendlichwertige Prädikatenlogik ist ’komplizierter’ als die zweiwertige in dem Sinne, dass die Formelmengen dieses Systems in der arithmetischen Hierarchie höher klassiert werden als entsprechende der zweiwertigen Logik. Im vorliegenden Artikel wird das am Beispiel der Menge der erfüllbaren Sätze mit vier einstelligen Prädikatszeichen gezeigt. Dazu wird folgende Struktur betrachtet: Individuenbereich ist die Menge der Paare natürlicher Zahlen. Die vier Prädikatsfunktionen haben folgende Werte: \(P(m,n)=2^{-m}\), \(Q(m,n)=2^{-n}\), \(R(m,n)=2^{-(m+n)}\), \(S(m,n)=2^{-mn}\). Diese Struktur lässt sich nun einerseits durch eine Formel \(\xi\) genügend genau charakterisieren (bis auf elementare Äquivalenz), andererseits lassen sich in ihr arithmetische Formeln mit beschränkten Existenz-, aber unbeschränkten Allquantoren wahrheitstreu interpretieren, d.h. jeder solchen Formel \(\beta\) lässt sich eine Formel \(\beta^*\) der einstelligen Prädikatenlogik rekursiv zuordnen, so dass \(\beta^*\) in der erwähnten Struktur genau dann gilt, wenn \(\beta\) wahr ist. Somit ist \((\xi \wedge \beta^*)\) genau dann erfüllbar, wenn \(\beta\) wahr ist: Das Erfüllungsproblem der einstelligen unendlichwertigen Prädikatenlogik ist \(\Pi_ 1\)-vollständig.

MSC:
03B50 Many-valued logic
03D35 Undecidability and degrees of sets of sentences
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Belluce, L.P.: The theory of infinite valued predicate logic. Ph.D. Thesis, University of California, Los Angeles, 1963.
[2] Belluce, L.P.: Further results on infinite valued predicate logic. J. Symb. Logic29, 69–78 (1964). · Zbl 0127.00801
[3] Belluce, L.P., Chang, C.C.: A weak completeness theorem for infinite valued first-order logic. J. Symb. Logic28, 43–50 (1963). · Zbl 0121.01203
[4] Chang, C.C.: Theory of models of infinite valued logic. I. Notices Am. Math. Soc.8, 68 (1961).
[5] Fenstad, J.E.: On the consistency of the axiom of comprehension in the Łukasiewicz infinite valued logic. Math. Scand.14, 65–74 (1964). · Zbl 0134.01601
[6] Hay, L.S.: An axiomatization of the infinitely many-valued predicate calculus. J. Symb. Logic28, 77–86 (1963) · Zbl 0127.00703
[7] Lorenzen, P.: Metamathematik. Mannheim 1962. · Zbl 0105.24601
[8] Łukasiewicz, J., Tarski, A.: Untersuchungen über den Aussagenkalkül. Comptes Rendues des séances de la Société des Sciences et des Lettres de VarsovieXXIII, 1–21, Classe III (1930).
[9] McNaughton, R.: A theorem about infinite-valued sentential logic. J. Symb. Logic16, 1–13 (1951). · Zbl 0043.00901
[10] Mostowski, A.: Axiomatizability of some many valued predicate calculi. Fund. Math.L, 165–190 (1961). · Zbl 0099.00701
[11] Ragaz, M.: Arithmetische Klassifikation von Formelmengen der unendlichwertigen Logik. Diss. ETH Nr. 6822, Zürich 1981. · Zbl 0516.03011
[12] Rutledge, J.D.: On the definition of an infinitely many-valued predicate calculus. J. Symb. Logic25, 212–216 (1960). · Zbl 0105.00501
[13] Rutledge, J.D.: A preliminary investigation of the infinitely many-valued predicate calculus. Ph.D. Thesis at Cornell University, 1959.
[14] Scarpellini, B.: Die Nichtaxiomatisierbarkeit des unendlichwertigen Prädikatenkalküls von Łukasiewicz. J. Symb. Logic27, 159–170 (1962). · Zbl 0112.24503
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.