Two-variable logic: Difference between revisions

Revision as of 14:23, 15 August 2014

Latest revision as of 13:07, 13 September 2022

(24 intermediate revisions by 11 users not shown)

Line 1:

In [[mathematical logic]] and [[computer science]], '''two-variable logic''' is the [[fragment (logics)|fragment]] of [[first-order logic]] where [[formula (logics)|formulae]] can be written using only two different [[variable (logics)|variable]]s.<ref>L. ThisHenkin. fragment''Logical issystems usuallycontaining studiedonly withouta [[functionfinite symbol]]s, and onenumber of itssymbols'', mainReport, pointsDepartment isof thatMathematics, someUniversity importantof problems about itMontreal, such1967</ref> asThis [[satisfiabilityfragment (logics)|satisfiability]]is andusually [[finitestudied satisfiability (logics)|finite satisfiability]], arewithout [[decidabilityfunction (computer science)|decidablesymbol]]s.

== Decidability ==

What is more, the two-variable fragment of first-order logic with no function symbols is known to be decidable even with the addition of [[counting quantifiers]]. This is a more powerful result, as counting quantifiers for high numerical values are not expressible in that logic.

Some important problems about two-variable logic, such as [[satisfiability (logics)|satisfiability]] and [[finite satisfiability (logics)|finite satisfiability]], are [[decidability (computer science)|decidable]].<ref>E. Grädel, P.G. Kolaitis and M. Vardi, ''On the Decision Problem for Two-Variable First-Order Logic'', The Bulletin of Symbolic Logic, Vol.

3, No. 1 (Mar., 1997), pp. 53-69.</ref> This result generalizes results about the decidability of fragments of two-variable logic, such as certain [[description logic]]s; however, some fragments of two-variable logic enjoy a much lower [[Computational complexity theory|computational complexity]] for their satisfiability problems.

By contrast, for the three-variable fragment of first-order logic without function symbols, satisfiability is undecidable.<ref>A. S. Kahr, Edward F. Moore and Hao Wang. ''Entscheidungsproblem Reduced to the ∀ ∃ ∀ Case'', 1962, noting that their ∀ ∃ ∀ formulas use only three variables.</ref>

== Counting quantifiers ==

What is more, theThe two-variable fragment of first-order logic with no function symbols is known to be decidable even with the addition of [[counting quantifiers]],<ref>E. Grädel, M. Otto and E. Rosen. ''Two-Variable Logic with Counting is Decidable.'', Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, 1997.</ref> and thus of [[uniqueness quantification]]. 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 <math>n</math> neighbors, namely <math>\Phi = \exists x \exists^{\geq n} y E(x,y)</math>. Without counting quantifiers <math>n+1</math> 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 [[Colour refinement algorithm|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 <math>C^2</math> type, that is, they satisfy the same formulas in two-variable logic with counting.<ref>Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.</ref>

== References ==

<references />

[[Category:Model theory]]

[[Category:Systems of formal logic]]