Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.

For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k (free or bound) variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and extensions by so-called counting quantifiers.

Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time (PTIME) or polynomial space (PSPACE) can be characterized as collections of all classes of (ordered) finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth.

§1. Introduction. The problem raised by the liar paradox has long been an intriguing challenge for all those interested in the concept of truth. Many “solutions” have been proposed to solve or avoid the paradox, either prescribing some linguistical restriction, or giving up the classical true-false bivalence or assuming some kind of contextual dependence of truth, among other possibilities. We shall not discuss these different approaches to the subject in this paper, but we shall concentrate on a kind of formal construction which was originated by Kripke's paper “Outline of a theory of truth” [11] and which, in different forms, reappears in later papers by various authors.

The main idea can be presented as follows: assume a first order language ℒ containing, among other unspecified symbols, a predicate symbol T intended to represent the truth predicate for ℒ. Assume, also, a fixed model M = 〈D, I〉 (the base model)where D contains all sentences of ℒ and I interprets all non-logical symbols of ℒ except T in the usual way. In general, D might contain many objects other than sentences of ℒ but as that would raise the problem of the meaning of sentences in which T is applied to one of these objects, we shall assume that this is not the case.

A way is found to add axioms to sequent calculi that maintains the eliminability of cut, through the representation of axioms as rules of inference of a suitable form. By this method, the structural analysis of proofs is extended from pure logic to free-variable theories, covering all classical theories, and a wide class of constructive theories. All results are proved for systems in which also the rules of weakening and contraction can be eliminated. Applications include a system of predicate logic with equality in which also cuts on the equality axioms are eliminated.