Four Variables Suffice

  • Alasdair Urquhart Department of Philosophy, University of Toronto

Abstract

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?

Author Biography

Alasdair Urquhart, Department of Philosophy, University of Toronto
Published
2007-11-10
How to Cite
URQUHART, Alasdair. Four Variables Suffice. The Australasian Journal of Logic, [S.l.], v. 5, nov. 2007. ISSN 1448-5052. Available at: <https://ojs.victoria.ac.nz/ajl/article/view/1786>. Date accessed: 18 july 2019. doi: https://doi.org/10.26686/ajl.v5i0.1786.