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)|
|Through your library||Configure|
Similar books and articles
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.
James S. Johnson (1973). Axiom Systems for First Order Logic with Finitely Many Variables. Journal of Symbolic Logic 38 (4):576-578.
Natasha Alechina & Michiel van Lambalgen (1996). Generalized Quantification as Substructural Logic. Journal of Symbolic Logic 61 (3):1006-1044.
Dick Jongh & Franco Montagna (1991). Rosser Orderings and Free Variables. Studia Logica 50 (1):71 - 80.
Kosta Došen & Zoran Petrić (2003). Generality of Proofs and its Brauerian Representation. Journal of Symbolic Logic 68 (3):740-750.
Natasha Alechina (2000). Functional Dependencies Between Variables. Studia Logica 66 (2):273-283.
Roger D. Maddux (1992). Relation Algebras of Every Dimension. Journal of Symbolic Logic 57 (4):1213-1229.
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 downloads2 ( #254,287 of 1,004,692 )
Recent downloads (6 months)1 ( #64,743 of 1,004,692 )
How can I increase my downloads?