David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Bulletin of Symbolic Logic 8 (3):348-379 (2002)
For every finite n ≥ 4 there is a logically valid sentence φ n with the following properties: φ n contains only 3 variables (each of which occurs many times); φ n contains exactly one nonlogical binary relation symbol (no function symbols, no constants, and no equality symbol): φ n has a proof in first-order logic with equality that contains exactly n variables, but no proof containing only n - 1 variables. This result was first proved using the machinery of algebraic logic developed in several research monographs and papers. Here we replicate the result and its proof entirely within the realm of (elementary) first-order binary predicate logic with equality. We need the usual syntax, axioms, and rules of inference to show that φ n has a proof with only n variables. To show that φ n has no proof with only n - 1 variables we use alternative semantics in place of the usual, standard, set-theoretical semantics of first-order logic
|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
Miklós Ferenczi (2009). On Conservative Extensions in Logics with Infinitary Predicates. Studia Logica 92 (1):121 - 135.
Similar books and articles
Roger D. Maddux (1992). Relation Algebras of Every Dimension. Journal of Symbolic Logic 57 (4):1213-1229.
Natasha Alechina (2000). Functional Dependencies Between Variables. Studia Logica 66 (2):273-283.
Kosta Došen & Zoran Petrić (2003). Generality of Proofs and its Brauerian Representation. Journal of Symbolic Logic 68 (3):740-750.
Dick Jongh & Franco Montagna (1991). Rosser Orderings and Free Variables. Studia Logica 50 (1):71 - 80.
Natasha Alechina & Michiel van Lambalgen (1996). Generalized Quantification as Substructural Logic. Journal of Symbolic Logic 61 (3):1006-1044.
James S. Johnson (1973). Axiom Systems for First Order Logic with Finitely Many Variables. Journal of Symbolic Logic 38 (4):576-578.
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.
Robin Hirsch, Ian Hodkinson & Roger D. Maddux (2002). Relation Algebra Reducts of Cylindric Algebras and an Application to Proof Theory. Journal of Symbolic Logic 67 (1):197-213.
Added to index2009-01-28
Total downloads8 ( #168,674 of 1,099,017 )
Recent downloads (6 months)6 ( #43,697 of 1,099,017 )
How can I increase my downloads?