Four Variables Suffice

  • Alasdair Urquhart Department of Philosophy, University of Toronto


What I wish to propose in the present paper is a new form of “career induction” for ambitious young logicians. The basic problem is this: if we look at the n-variable fragments of relevant propositional logics, at what point does undecidability begin? Focus, to be definite, on the logic R. John Slaney showed that the 0-variable fragment of R (where we allow the sentential con- stants t and f) contains exactly 3088 non-equivalent propositions, and so is clearly decidable. In the opposite direction, I claimed in my paper of 1984 that the five variable fragment of R is undecidable. The proof given there was sketchy (to put the matter charitably), and a close examination reveals that although the result claimed is true, the proof given is incorrect. In the present paper, I give a detailed and (I hope) correct proof that the four variable fragments of the principal relevant logics are undecidable. This leaves open the question of the decidability of the n-variable fragments for n = 1, 2, 3. At what point does undecidability set in?


Download data is not yet available.

Author Biography

Alasdair Urquhart, Department of Philosophy, University of Toronto
How to Cite
URQUHART, Alasdair. Four Variables Suffice. The Australasian Journal of Logic, [S.l.], v. 5, nov. 2007. ISSN 1448-5052. Available at: <>. Date accessed: 02 july 2020. doi: