💻 computer science

Locality in Residuated-Lattice Structures

This paper investigates the validity of classical Hanf and Gaifman locality theorems in the context of first-order substructural logics modeled by residuated lattices, demonstrating that while Hanf’s theorem requires specific algebraic conditions and alternative definitions of locality, the core lemma of Gaifman’s theorem can be recovered for well-behaved algebras through a syntactic encoding of back-and-forth systems enabled by an order-interpreting connective.

Original authors: James Carr

Published 2026-06-18

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: James Carr

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Logic with Shades of Gray

Imagine you are trying to describe the world using logic. In Classical Logic (the kind you might learn in high school), everything is black and white. A statement is either True or False. There is no middle ground.

However, the real world is often messy. Is it "raining"? Maybe it’s drizzling. Is this person "tall"? Maybe they are average. Many-Valued Logic allows for these shades of gray. Instead of just True/False, we use a scale (like 0 to 1, or a complex algebraic structure) to measure how true something is.

The paper focuses on a specific type of mathematical structure called a Residuated Lattice. Think of this as the "rulebook" for how these shades of gray interact. It’s a sophisticated system used to model non-classical logics (like fuzzy logic or substructural logics).

The Core Concept: "Locality"

The central theme of the paper is Locality.

The Analogy: Imagine you are a detective trying to solve a mystery in a huge city.

Global Property: "Is the entire city connected by roads?" To answer this, you need a map of the whole city.
Local Property: "Is there a coffee shop within 5 blocks of my house?" To answer this, you only need to look at your immediate neighborhood. You don’t need to know what’s happening on the other side of town.

In classical logic, there is a famous limitation: First-order logic is local. It can only "see" what is happening nearby. It cannot express global properties like "the whole graph is connected." This is known as Hanf’s Theorem and Gaifman’s Theorem.

The author asks: Do these "locality" rules still hold when we move from black-and-white logic to gray-scale (many-valued) logic?

Part 1: Hanf’s Theorem (Counting Neighborhoods)

Hanf’s theorem basically says: If two cities look the same in their local neighborhoods (and they have roughly the same number of those neighborhoods), then any logical question you can ask about them will have the same answer.

The Problem:
In the gray-scale world, the author found that the standard way of defining "neighborhoods" fails.

Why? In classical logic, if two people aren't connected, they are just "not connected." In gray-scale logic, they might have a connection strength of 0.1 or 0.9. The standard "distance" metric doesn't capture enough detail to make Hanf’s theorem work.

The Solution:
The author discovered that if we change how we define "distance," we can save the theorem.

The Fix: We use a "strict threshold." Imagine we only care about connections that are stronger than the absolute bottom value (let's call it "zero"). If a connection is anything above zero, we treat it as a link. If it’s zero, it’s a wall.
The Result: If we use this specific "strict zero" distance, Hanf’s theorem works again, but only for certain types of rulebooks (algebras) that are "bounded" (they have a clear top and bottom limit).

Part 2: Gaifman’s Theorem (Local Formulas)

Gaifman’s theorem is more technical. It says that any logical sentence can be rewritten so that it only talks about local neighborhoods. It’s like saying, "You don’t need a global map; you can describe the whole city by stitching together descriptions of small neighborhoods."

The Problem:
This is harder to fix. To rewrite sentences this way, you need to be able to say things like "The distance between A and B is greater than 5." In many gray-scale systems, you don’t have a clean way to say "greater than" or "not equal to" in the logic itself.

The Solution:
The author had to restrict the types of rulebooks he was looking at.

The Fix: He focused on Residuated Chains with a Co-atom.
- Chain: The truth values are lined up in a single straight line (like a thermometer), not a complex web.
- Co-atom: There is a specific "almost false" value that sits just below "true." This allows the logic to mimic classical "negation" (saying "not").
The Result: Under these strict conditions, the author proved a version of Gaifman’s Lemma. This lemma is the engine that drives the theorem. It shows that if two models agree on all local sentences, they are logically equivalent.

The Key Tool: The "Bridge" Connective

Throughout the paper, the author highlights a crucial mathematical tool: the Residuum (often written as $\to$ or $/$ ).

The Analogy: Think of this as a translator between two languages:

The Syntax Language: The written formulas.
The Semantic Language: The actual truth values in the algebra.

In classical logic, these two are tightly linked. In gray-scale logic, they can drift apart. The Residuum acts as a bridge that forces them to stay aligned. It allows the logic to "check" if one value is less than or equal to another. Without this bridge, you can't encode the "back-and-forth" games (a method used to prove logical equivalence) that are essential for proving locality.

Comparison with Other Work (Semirings)

The author compares his work to previous research on Semirings (another type of algebraic structure used in logic).

Semiring logic is like a simplified version of gray-scale logic. It handles "and" and "or" well but lacks a proper "implies" or "negation" operator.
The author shows that his Residuated Lattice approach is richer. It can handle more complex logical operations, but it requires stricter conditions (like the "co-atom") to make the locality theorems work.

Practical Application: Database Queries

Why does this matter? The paper mentions Queries.

The Analogy: Imagine a database of a social network.

A Global Query: "Is the entire network one single connected group?"
A Local Query: "Who are my friends' friends?"

Locality theorems help us prove that certain queries cannot be written in first-order logic. If a query depends on global structure (like connectivity), and logic is only local, then that query is "inexpressible."

The author shows that in the gray-scale world:

If a query is definable in this logic, it must be Hanf Local (it only cares about local counts).
If a query is definable, it must be Gaifman Local (it only cares about local neighborhoods).

He gives examples of queries (like "Is the graph connected?" or "Is there a path from A to B?") that are not local, and therefore not definable in this logic. This is a powerful tool for computer scientists: it tells them, "Stop trying to write this query in first-order logic; it’s impossible."

Summary

Goal: Extend classical "locality" theorems (Hanf and Gaifman) to many-valued (gray-scale) logic using Residuated Lattices.
Hanf’s Theorem: Failed with standard definitions, but recovered if we use a "strict threshold" distance metric and bounded algebras.
Gaifman’s Theorem: Required stricter conditions (linear chains with a specific "co-atom" element) to define local formulas properly. A key lemma was proven under these conditions.
Key Mechanism: The "Residuum" connective acts as a bridge, allowing the logic to encode local distances and equivalence.
Use Case: These results help prove that certain complex database queries (like global connectivity) cannot be expressed in this type of logic.

Technical Summary: Locality in Residuated Lattice Structures

Problem and Context
The paper investigates the extent to which classical locality theorems—specifically Hanf locality and Gaifman locality—hold in the context of many-valued model theory defined over residuated lattices. In classical first-order logic, locality results demonstrate that the truth of a formula depends only on the local structure of a model, implying that global properties (such as connectivity or acyclicity in graphs) are inexpressible. While previous work has explored locality for models over ordered semirings [BGN23] and fuzzy modal logics [WSPK18], this paper focuses on residuated lattices, which provide the algebraic semantics for substructural logics. The central challenge is that the validity of locality theorems in this generalized setting is sensitive to both the definition of locality (distance metrics) and the algebraic properties of the truth-defining algebra.

Methodology
The investigation proceeds by generalizing classical concepts to the many-valued setting and identifying the minimal algebraic constraints required to recover classical proofs. Key methodological components include:

Algebraic Semantics: The models are defined over residuated lattices. The paper distinguishes between general residuated lattices and specific subclasses, notably well-connected lattices (where $a \vee b \ge 1$ iff $a \ge 1$ or $b \ge 1$ ) and bounded lattices. The presence of an order-interpreting connective (the residuum, $\backslash$ or $/$ ) is identified as critical, as it links the modeling relation ( $\models$ ) to the valuation function ( $||\cdot||$ ).
Syntactic Encodings: The authors utilize standard expansions of models, adding nullary relation symbols for each element of the algebra, to encode truth values syntactically. They define k-isomorphism types as formulas that encode partial isomorphisms and back-and-forth systems, generalizing the classical notion of diagrams.
Distance Metrics: Several variants of the Gaifman graph distance are considered, including the naive modeling-based distance and threshold distance metrics ( $d_{\ge t}$ and $d_{>t}$ ), where adjacency is determined by whether relation values exceed a specific threshold $t$ in the algebra.
Back-and-Forth Systems: The paper employs back-and-forth systems to establish elementary equivalence, adapting definitions from [DGCN18] to the residuated lattice context.

Key Contributions and Results

1. Hanf Locality

Failure of Natural Locality: The paper demonstrates that Hanf’s theorem fails for the natural understanding of local neighborhoods (based on the naive Gaifman graph) in any residuated lattice with at least two distinct elements not above the unit. A counterexample is provided using weighted graphs where local isomorphism does not imply elementary equivalence due to the inability of the naive distance metric to capture specific algebraic values.
Recovery via Threshold Metrics: Hanf locality is recovered for models defined over well-connected bounded residuated lattices using the strict $\bot$ -threshold distance metric ( $d_{>\bot}$ ). In this metric, non-adjacency implies that relation values are exactly $\bot$ , allowing the combination of local isomorphisms.
Theorem: If two finite models over a well-connected bounded residuated lattice have the same number of elements realizing each $r$ -sphere type (or sufficiently many such elements) for a radius $r$ dependent on quantifier rank $k$ , they are $k$ -strongly equivalent.
Corollary: This yields a Fagin-Stockmeyer-Vardi style result: if two models are $3k$ -Hanf local (have the same distribution of $3k$ -sphere types), they are $k$ -strongly equivalent.

2. Gaifman Locality

Focus on Gaifman’s Lemma: Rather than proving the full Gaifman theorem (which relies on compactness, a property that fails for finite models in this setting), the paper focuses on Gaifman’s Lemma: models satisfying the same basic local sentences are elementarily equivalent.
Restrictions: The recovery of this lemma requires stricter conditions than Hanf locality. The algebra must be a residuated chain with a co-atom (an element $c$ such that $a \le c$ iff $1 \not\le a$ ). This allows for the definition of a classical-like negation and the encoding of "far" distance formulas. Additionally, models must be witnessed (quantifiers achieve their supremum/infimum), which is guaranteed for finite models over chains.
Local Formulas: The authors define local formulas by relativizing quantifiers to local neighborhoods using distance formulas. This requires the algebra to support the encoding of distance and the manipulation of quantifiers via monotone/antitone connectives.
Theorem: For finite witnessed models over a residuated chain with a co-atom, if two models satisfy the same basic local sentences and agree on local formulas up to a certain rank, they are strongly equivalent.

3. Comparison with Semiring Semantics
The paper contrasts its results with [BGN23], which studied locality over ordered semirings. Key differences include:

Semiring semantics lacks primitive implication/negation, focusing on conjunction/disjunction generalizations.
The residuated lattice setting allows for richer syntax (residuated connectives) but requires the order-interpreting connective to link syntax and semantics for Gaifman locality.
The paper shows that while a weaker Gaifman lemma (equivalence at the level of $\models$ ) holds for min-max semirings, the strong equivalence result fails without the residuated structure.

4. Applications to Query Definability
The locality results are applied to prove the inexpressibility of queries:

Hanf Locality: Used to show that the $\bot$ -connectivity query (whether a weighted graph is connected via edges with weight $>\bot$ ) is not definable in finite models over well-connected bounded residuated lattices.
Gaifman Locality: Used to show that the $t$ -transitive closure query (whether there is a path with edge weights $\ge t$ ) is not definable in finite models over residuated chains with co-atoms.

Significance and Claims
The paper claims to identify the precise algebraic features necessary for locality theorems in non-classical model theory. It highlights the critical role of the residuum in linking the modeling relation to the valuation function, enabling the syntactic encoding of back-and-forth systems. The work establishes that while Hanf locality can be recovered in relatively broad settings (bounded well-connected lattices) with appropriate distance metrics, Gaifman locality requires significantly more restrictive algebraic structures (chains with co-atoms) and witnessed models. The paper positions this investigation as a step toward understanding the boundaries of classical model theory techniques in substructural logics, noting that the full Gaifman theorem remains an open question for residuated lattices due to the non-monotonicity of residuated connectives.