2011/11/03 by Hajnal Andréka, Istvàn Németi, Andréka, H. +3
Computer Science · #03B10 #03B20 #03B45 #03E75 (Secondary) #03G15 #06E25 (Primary) 03E30 #Advanced Algebra and Logic #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1111.0995
openalex publication_date 2011/11/03 · openalex created_date 2022/09/12 · openalex updated_date 2026/07/28
We show that first-order logic can be translated into a very simple and weak\nlogic, and thus set theory can be formalized in this weak logic. This weak\nlogical system is equivalent to the equational theory of Boolean algebras with\nthree commuting complemented closure operators, i.e., that of diagonal-free\n3-dimensional cylindric algebras (Df3's). Equivalently, set theory can be\nformulated in propositional logic with 3 commuting S5 modalities (i.e., in the\nmulti-modal logic [S5,S5,S5]). There are many consequences, e.g., free finitely\ngenerated Df3's are not atomic and [S5,S5,S5] has G "odel's incompleteness\nproperty. The results reported here are strong improvements of the main result\nof the book: Tarski, A. and Givant, S. R., Formalizing Set Theory without\nvariables, AMS, 1987.\n