Provability with finitely many variables

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)
DOI 10.2178/bsl/1182353893
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 24,463
External links
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
Alfred Tarski (1941). On the Calculus of Relations. Journal of Symbolic Logic 6 (3):73-89.
Roger Maddux (1983). A Sequent Calculus for Relation Algebras. Annals of Pure and Applied Logic 25 (1):73-101.

View all 6 references / Add more references

Citations of this work BETA
Thomas Donaldson (2015). Reading the Book of the World. Philosophical Studies 172 (4):1051-1077.

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

20 ( #232,939 of 1,925,534 )

Recent downloads (6 months)

1 ( #418,152 of 1,925,534 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.