Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T07:44:43.758Z Has data issue: false hasContentIssue false

Provability with Finitely Many Variables

Published online by Cambridge University Press:  15 January 2014

Robin Hirsch
Affiliation:
Department of Computer Science, University College, Gower Street, London WC1E 6BT, UK, E-mail: R.Hirsch@cs.ucl.ac.uk
Ian Hodkinson
Affiliation:
Department of Computing, Imperial College, 180 Queen's Gate, London SW7 2BZ, UK, E-mail: imh@doc.ic.ac.uk
Roger D. Maddux
Affiliation:
Department of Mathematics, 400 Carver Hall, Iowa State University, Ames, Iowa 50011-2066, USA, E-mail: maddux@iastate.edu

Abstract

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable