In
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
and
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, two-variable logic is the
fragment of
first-order logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
where
formulae
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
can be written using only two different
variables. This fragment is usually studied without
function symbol
In formal logic and related branches of mathematics, a functional predicate, or function symbol, is a logical symbol that may be applied to an object term to produce another object term.
Functional predicates are also sometimes called mappings, bu ...
s.
Decidability
Some important problems about two-variable logic, such as
satisfiability
In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...
and
finite satisfiability, are
decidable. This result generalizes results about the decidability of fragments of two-variable logic, such as certain
description logic
Description logics (DL) are a family of formal knowledge representation languages. Many DLs are more expressive than propositional logic but less expressive than first-order logic. In contrast to the latter, the core reasoning problems for DLs are ...
s; however, some fragments of two-variable logic enjoy a much lower
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
for their satisfiability problems.
By contrast, for the three-variable fragment of first-order logic without function symbols, satisfiability is undecidable.
Counting quantifiers
The two-variable fragment of first-order logic with no function symbols is known to be decidable even with the addition of
counting quantifiers, and thus of
uniqueness quantification
In mathematics and logic, the term "uniqueness" refers to the property of being the one and only object satisfying a certain condition. This sort of quantification is known as uniqueness quantification or unique existential quantification, and i ...
. This is a more powerful result, as counting quantifiers for high numerical values are not expressible in that logic.
Counting quantifiers actually improve the expressiveness of finite-variable logics as they allow to say that there is a node with
neighbors, namely
. Without counting quantifiers
variables are needed for the same formula.
Connection to the Weisfeiler-Leman algorithm
There is a strong connection between two-variable logic and the Weisfeiler-Leman (or
color refinement) algorithm. Given two graphs, then any two nodes have the same stable color in color refinement if and only if they have the same
type, that is, they satisfy the same formulas in two-variable logic with counting.
[Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.]
References
Model theory
Systems of formal logic