Journal of Symbolic Logic 67 (1):197-213 (2002)

We confirm a conjecture, about neat embeddings of cylindric algebras, made in 1969 by J. D. Monk, and a later conjecture by Maddux about relation algebras obtained from cylindric algebras. These results in algebraic logic have the following consequence for predicate logic: for every finite cardinal α ≥ 3 there is a logically valid sentence X, in a first-order language L with equality and exactly one nonlogical binary relation symbol E, such that X contains only 3 variables (each of which may occur arbitrarily many times), X has a proof containing exactly α + 1 variables, but X has no proof containing only α variables. This solves a problem posed by Tarski and Givant in 1987
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1190150037
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,497
Through your library

References found in this work BETA

Cylindric Algebras. Part I.Leon Henkin, J. Donald Monk, Alfred Tarski, L. Henkin, J. D. Monk & A. Tarski - 1985 - Journal of Symbolic Logic 50 (1):234-237.
Cylindric Algebras. Part II.Leon Henkin, J. Donald Monk & Alfred Tarski - 1988 - Journal of Symbolic Logic 53 (2):651-653.
Relation Algebras From Cylindric and Polyadic Algebras.I. Nemeti & A. Simon - 1997 - Logic Journal of the IGPL 5 (4):575-588.

Add more references

Citations of this work BETA

Algebraic Logic, Where Does It Stand Today?Tarek Sayed Ahmed - 2005 - Bulletin of Symbolic Logic 11 (3):465-516.
Provability with Finitely Many Variables.Robin Hirsch, Ian Hodkinson & Roger D. Maddux - 2002 - Bulletin of Symbolic Logic 8 (3):348-379.
Relation Algebras From Cylindric Algebras, I.Robin Hirsch & Ian Hodkinson - 2001 - Annals of Pure and Applied Logic 112 (2-3):225-266.
A Note on Substitutions in Representable Cylindric Algebras.Tarek Sayed Ahmed - 2009 - Mathematical Logic Quarterly 55 (3):280-287.

View all 8 citations / Add more citations

Similar books and articles


Added to PP index

Total views
218 ( #38,519 of 2,348,160 )

Recent downloads (6 months)
2 ( #329,024 of 2,348,160 )

How can I increase my downloads?


My notes