License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2023.23
URN: urn:nbn:de:0030-drops-174846
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17484/
Go to the corresponding LIPIcs Volume Portal

Grange, Julien

Order-Invariance in the Two-Variable Fragment of First-Order Logic

pdf-format:
LIPIcs-CSL-2023-23.pdf (0.8 MB)

Abstract

We study the expressive power of the two-variable fragment of order-invariant first-order logic. This logic departs from first-order logic in two ways: first, formulas are only allowed to quantify over two variables. Second, formulas can use an additional binary relation, which is interpreted in the structures under scrutiny as a linear order, provided that the truth value of a sentence over a finite structure never depends on which linear order is chosen on its domain.
We prove that on classes of structures of bounded degree, any property expressible in this logic is definable in first-order logic. We then show that the situation remains the same when we add counting quantifiers to this logic.

BibTeX - Entry

@InProceedings{grange:LIPIcs.CSL.2023.23,
  author =	{Grange, Julien},
  title =	{{Order-Invariance in the Two-Variable Fragment of First-Order Logic}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17484},
  URN =		{urn:nbn:de:0030-drops-174846},
  doi =		{10.4230/LIPIcs.CSL.2023.23},
  annote =	{Keywords: Finite model theory, Two-variable logic, Order-invariance}
}

Keywords: Finite model theory, Two-variable logic, Order-invariance
Collection: 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI