mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...

and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, two-variable logic is the fragment of

first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

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 betwee ...

can be written using only two different

variable Variable may refer to: * Variable (computer science), a symbolic name associated with a value and whose associated value may be changed * Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...

s. 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, but ...

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 logics; 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 A counting quantifier is a mathematical term for a quantifier of the form "there exists at least ''k'' elements that satisfy property ''X''". In first-order logic with equality, counting quantifiers can be defined in terms of ordinary 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 ...

. 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

n

neighbors, namely

\Phi = \exists x \exists^{\geq n} y E(x,y)

. Without counting quantifiers

n+1

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

C^2

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