David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Tarek Sayed Ahmed (2009). A Note on Substitutions in Representable Cylindric Algebras. Mathematical Logic Quarterly 55 (3):280-287.
Similar books and articles
Jean A. Larson (1985). The Number of One-Generated Cylindric Set Algebras of Dimension Greater Than Two. Journal of Symbolic Logic 50 (1):59-71.
Maarten Marx & Szabolcs Mikulás (1999). Decidability of Cylindric Set Algebras of Dimension Two and First-Order Logic with Two Variables. Journal of Symbolic Logic 64 (4):1563-1572.
I. Németi & A. Simon (2009). Weakly Higher Order Cylindric Algebras and Finite Axiomatization of the Representables. Studia Logica 91 (1):53 - 62.
Robin Hirsch (2007). Relation Algebra Reducts of Cylindric Algebras and Complete Representations. Journal of Symbolic Logic 72 (2):673 - 703.
Robin Hirsch, Ian Hodkinson & Roger D. Maddux (2002). Provability with Finitely Many Variables. Bulletin of Symbolic Logic 8 (3):348-379.
Leon Henkin (1971). Cylindric Algebras. Amsterdam,North-Holland Pub. Co..
Tarek Sayed Ahmed (2005). Algebraic Logic, Where Does It Stand Today? Bulletin of Symbolic Logic 11 (4):465-516.
Tarek Sayed Ahmed & Istvan Németi (2001). On Neat Reducts of Algebras of Logic. Studia Logica 68 (2):229-262.
Robin Hirsch & Ian Hodkinson (1997). Step by Step-Building Representations in Algebraic Logic. Journal of Symbolic Logic 62 (1):225-279.
Roger D. Maddux (1989). Nonfinite Axiomatizability Results for Cylindric and Relation Algebras. Journal of Symbolic Logic 54 (3):951-974.
Added to index2009-01-28
Total downloads5 ( #229,963 of 1,102,929 )
Recent downloads (6 months)1 ( #297,435 of 1,102,929 )
How can I increase my downloads?