Hanf Locality and Invariant Elementary Definability
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909691872804864 |
|---|---|
| author | Lindell, Steven Towsner, Henry Weinstein, Scott |
| author_facet | Lindell, Steven Towsner, Henry Weinstein, Scott |
| contents | We introduce some notions of invariant elementary definability which extend the notions of first-order order-invariant definability, and, more generally, definability invariant with respect to arbitrary numerical relations. In particular, we study invariance with respect to expansions which depend not only on (an ordering of) the universe of a structure, but also on the particular relations which determine the structure; we call such expansions \emph{presentations} of a structure. We establish two locality results in this context. The first is an extension of the original Hanf Locality Theorem to boolean queries which are invariantly definable over classes of locally finite structures with respect to \emph{elementary, neighborhood-bounded} presentations. The second is a non-uniform version of the Fagin-Stockmeyer-Vardi Hanf Threshold Locality Theorem to boolean queries which are invariantly definable over classes of bounded degree structures with respect to elementary, neighborhood-bounded, \emph{local} presentations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12450 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hanf Locality and Invariant Elementary Definability Lindell, Steven Towsner, Henry Weinstein, Scott Logic We introduce some notions of invariant elementary definability which extend the notions of first-order order-invariant definability, and, more generally, definability invariant with respect to arbitrary numerical relations. In particular, we study invariance with respect to expansions which depend not only on (an ordering of) the universe of a structure, but also on the particular relations which determine the structure; we call such expansions \emph{presentations} of a structure. We establish two locality results in this context. The first is an extension of the original Hanf Locality Theorem to boolean queries which are invariantly definable over classes of locally finite structures with respect to \emph{elementary, neighborhood-bounded} presentations. The second is a non-uniform version of the Fagin-Stockmeyer-Vardi Hanf Threshold Locality Theorem to boolean queries which are invariantly definable over classes of bounded degree structures with respect to elementary, neighborhood-bounded, \emph{local} presentations. |
| title | Hanf Locality and Invariant Elementary Definability |
| topic | Logic |
| url | https://arxiv.org/abs/2507.12450 |