Local-Order-Invariant Logic on Classes of Bounded Degree

Derek R. Aoki · 2025

Read Local-Order-Invariant Logic on Classes of Bounded Degree by Derek R. Aoki (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-02039.txt.

Introduction

Logicians extend first-order logic by letting formulas consult an ordering of nearby elements, as long as the answer does not depend on which ordering was picked. Derek Aoki's 2025 paper studies this local-order-invariant logic on classes of structures whose connections stay bounded in degree.

The questions trace back to work by Weinstein about how much extra power order-invariance buys, on bounded-degree structures, on finite structures generally, and on locally finite ones. Expressive power questions decide what properties computers can even state, let alone check, about networks and data. Aoki's results map where this polite fiction of an ordering actually adds strength.

Catalog record

CREATORDerek R. Aoki
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-02039

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Local-Order-Invariant Logic on Classes of Bounded Degree Derek R. Aoki Abstract Local-order-invariant (first-order) logic is an extension of first-order logic where formulae have access to a ternary local order relation on the Gaifman graph, provided that the truth value does not depend on the specific order relation chosen. Weinstein asked a number of questions about the expressive power of order-invariant and local-order-invariant logics on classes of finite structures of bounded degree, classes of finite structures in general, and classes of locally finite structures. We answer four of his five questions, including showing that local-order-invariant logic collapses to first-order logic on classes of bounded degree. We also investigate epsilon-invariant logic. We show that epsilon-invariant logic collapses to first-order logic on classes of bounded degree by containing it in local-order-invariant logic in this setting, and we give an upper bound for epsilon-invariant logic in terms of local-order-invariant logic on general finite structures. Finally, in the process of proving these theorems, we demonstrate some principles which suggest further directions for showing upper bounds on invariant logics, including an upper bound on epsilon-invariant logic in general. Proof School, USA and https://derekaoki.com/ [email protected]://orcid.org/0000-0003-0352-1963 The author would like to thank Noah Schweber for introducing him to the question of capturing epsilon-invariant logic with other invariant logics. ccs Theory of computation Finite Model Theory keywords Model theory, Finite model theory, Order-invariance, Invariant logics, Locality † † runningauthor: J. Open Access and J. R. Public † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Finite model theory is the study of the descriptions of finite structures, or databases, in formal languages. Generally, questions of concern are about the expressivity or computational complexity of these languages. These languages are known to capture various aspects of computation, such as the seminal result of Fagin [ 11 ] equating the queries in \mathrm{NP} to those expressible in existential second-order logic. In standard logics like first-order logic, fixed-point and transitive closure logics, or the aforementioned existential second-order logic, one can only refer to the relations of the model itself—the semantics. One might wish, though, to be able to reference predicates not in the vocabulary of the input databases, such as the order in which the elements of the database are stored, or the successor relation corresponding to that order. A logic must treat isomorphic structures in the same way; to make this use of orderings or successors meaningful, we must say that the query must return the same answer regardless of ordering. The queries which reference orderings but for which changing the ordering does not change the truth value are called order-invariant. From here, when we discussion invariant logics, we will specifically refer to invariant first-order logic (as opposed to, for instance, fixed-point logic). By the result of classical model theory known as the Craig Interpolation Theorem, any query defined over arbitrary (possibly infinite) structures which is invariant in this way must be first-order definable. However, the Interpolation Theorem fails in the finite, and this collapse does not occur in the finite either. Thus, there has been a research program investigating the expressivity and computational complexity of such invariant logics on finite structures, of which we will describe the most relevant strands. One strand of investigation has been into finding examples which separate various invariant logics from first-order logic [ 23 , 24 ] . A second has been into computational and descriptive complexity of invariant logics [ 6 , 9 , 25 ] . A third has been into demonstrating collapse in specific instances, such as for successor-invariant logic on classes of bounded degree [ 14 ] or for order-invariant logic on trees, strings, and hollow trees [ 5 , 13 ] . A final one has been into attempting to apply more general techniques of finite and classical model theory to these logics, such as methods using types [ 4 ] and locality [ 16 , 18 , 22 ] . A specific logic of interest for databases is epsilon-invariant logic, based on Hilbert’s epsilon calculus [ 20 ] of classical model theory, as discussed in [ 23 ] . This is where, for each first-order formula \varphi(\vec{x},y) and tuple \vec{a} , we choose a specific element b of the universe such that \varphi(\vec{a},b) holds and fix that, referring to this chosen element in formulae by a term \epsilon_{y}(\vec{x},y) . This is of interest in databases because it is in fact equal in expressiveness to the frozen-witness-invariant logic \mathrm{FO}[witness]^{+} discussed in [ 2 , 3 ] . Another logic of interest, whose relationship with prior work is instead primarily through locality, is local-order-invariant logic. A local order on a simple graph is a ternary relation \preceq(x,y,z) such that when x is fixed, \preceq(x,y,z) orders the neighbors of x . Such local orders have been mentioned in finite model theory before, such as in [ 5 , 7 ] , but as a basis for an invariant logic were first introduced in [ 22 ] . This notion can be easily generalized to arbitrary finite structures by considering instead the Gaifman graph of the structure. Our contribution : 1. In Section 3, we bound local-order-invariant logic on classes of bounded degree, following in the direction of [ 14 ] and answering a question of [ 22 ] . In Section 4, answering all but one of the remaining questions of Weinstein in [ 8 ] , we show that both order- and local-order-invariant logics do not collapse to first-order logic on arbitrary finite or arbitrary locally finite structures. We also show that in many cases of concern, classes with Gaifman graphs of bounded diameter, local-order-invariant logic is just as expressive as order-invariant logic. In Section 5, we bound epsilon-invariant logic by local-order-invariant logic on classes of bounded degree, demonstrating that it collapses to first-order logic on such classes. 2. We believe that this is the first use of Hanf threshold locality to upper bound invariant logics. Previous upper bound results have followed from actually constructing the invariant structure, such as the explicit construction of a successor in [ 14 ] or of orderings in [ 5 , 15 ] . Ours, however, make use of locality theorems in [ 22 ] which have not been applied concretely until now. We also introduce a method to decompose an invariant logic into simpler ones, applying this to epsilon-invariant logic and indicating that similar decompositions could hold for other invariant logics. 2 Preliminaries From here, \sigma will be a finite relational vocabulary. We denote by \mathfrak{F}_{\sigma} the finite \sigma structures. For \mathcal{A}\in\mathfrak{F}_{\sigma} and B\subseteq A , we use the notation \mathcal{A}\upharpoonright\mathcal{B} to denote the restriction of \mathcal{A} to B ; i.e., the substructure of \mathcal{A} with underlying set B such that for a tuple \vec{v} of elements of B and R\in\sigma , R(\vec{v}) in \mathcal{A}\upharpoonright B if and only if R(\vec{v}) in \mathcal{A} . If \rho\supseteq\sigma

Read the complete text