Relation algebra reducts of cylindric algebras and an application to proof theory

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


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



    Upload a copy of this work     Papers currently archived: 74,429

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

219 (#55,490)

6 months
1 (#417,143)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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, II.Robin Hirsch & Ian Hodkinson - 2001 - Annals of Pure and Applied Logic 112 (2-3):267-297.
Relation Algebras From Cylindric Algebras, I.Robin Hirsch & Ian Hodkinson - 2001 - Annals of Pure and Applied Logic 112 (2-3):225-266.
Neat Embeddings, Omitting Types, and Interpolation: An Overview.Tarek Sayed Ahmed - 2003 - Notre Dame Journal of Formal Logic 44 (3):157-173.

View all 12 citations / Add more citations

References found in this work

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.
A Simplified Formalization of Predicate Logic with Identity.Alfred Tarski - 1964 - Archive for Mathematical Logic 7 (1-2):61-79.
Relation Algebras From Cylindric and Polyadic Algebras.I. Nemeti & A. Simon - 1997 - Logic Journal of the IGPL 5 (4):575-588.

View all 6 references / Add more references