No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Definition
Distance logic extends first-order logic by two families of distance atoms — the distance between two variables is at most r, and the distance from a variable to a color class is smaller than r — and by local quantification, an existential quantifier that ranges only over the vertices within a given radius of a recorded set of the variables in scope. As a logic it is no stronger than first-order logic: over a fixed signature, "the distance between x and y is at most r" is already first-order expressible, and a local quantifier is an ordinary quantifier conjoined with such a distance test. What the extra syntax buys is a finer rank measure.
That measure is distance rank. A formula has distance rank (k, q) when it has at most k free variables, quantifier rank at most q, every distance atom in it has radius at most ρ⁻(k, q), and every local quantifier in it guards at radius at most ρ⁺(k+1, q−1), where ρ⁻ and ρ⁺ are the two horizon functions. The two functions decrease fast enough as one traverses the quantifiers of a formula inwards that the radii do too: the region a subformula can see shrinks strictly at every quantifier. This is exactly the control the locality theorem of needs — it rewrites a formula of distance rank (k, q) into a boolean combination of local formulas and scatter sentences of the same distance rank, which ordinary quantifier rank could not express.
This is the logic distFO of the source note (arXiv:2606.23180, §2.1), interpreted over the finite colored graphs of — see the discussion there for what fixing the signature does and does not cost. Its distance is the walk distance of that file, which for a colored graph is the distance in its Gaifman graph.
A formula is local when it never uses unrestricted quantification. Semantic locality is the corresponding property of meaning rather than of shape: a formula is semantically r-local when its truth on a tuple is unchanged by discarding every vertex further than r from that tuple.
Lean source view on GitHub
| 1 | import Lax3.ColoredGraphs |
| 2 | import Mathlib.Data.Fin.Tuple.Basic |
| 3 | import Mathlib.Data.Finset.Image |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Distance logic and distance rank |
| 8 | type: definition |
| 9 | --- |
| 10 | Distance logic extends first-order logic by two families of *distance |
| 11 | atoms* — the distance between two variables is at most *r*, and the |
| 12 | distance from a variable to a color class is smaller than *r* — and by |
| 13 | *local quantification*, an existential quantifier that ranges only over |
| 14 | the vertices within a given radius of a recorded set of the variables |
| 15 | in scope. As a logic it |
| 16 | is no stronger than first-order logic: over a fixed signature, "the |
| 17 | distance between *x* and *y* is at most *r*" is already first-order |
| 18 | expressible, and a local quantifier is an ordinary quantifier |
| 19 | conjoined with such a distance test. What the extra syntax buys is a |
| 20 | finer rank measure. |
| 21 | |
| 22 | That measure is *distance rank*. A formula has distance rank (*k*, *q*) |
| 23 | when it has at most *k* free variables, quantifier rank at most *q*, |
| 24 | every distance atom in it has radius at most ρ⁻(*k*, *q*), and every |
| 25 | local quantifier in it guards at radius at most ρ⁺(*k*+1, *q*−1), where |
| 26 | ρ⁻ and ρ⁺ are the two *horizon functions*. The two functions decrease |
| 27 | fast enough as one traverses the quantifiers of a formula inwards that |
| 28 | the radii do too: the region a subformula can see shrinks strictly at |
| 29 | every quantifier. This is exactly the control the locality theorem of |
| 30 | `Lax3.Locality` needs — it rewrites a formula of distance rank (*k*, |
| 31 | *q*) into a boolean combination of *local* formulas and scatter |
| 32 | sentences of the *same* distance rank, which ordinary quantifier rank |
| 33 | could not express. |
| 34 | |
| 35 | This is the logic distFO of the source note (arXiv:2606.23180, §2.1), |
| 36 | interpreted over the finite colored graphs of `Lax3.ColoredGraphs` — |
| 37 | see the discussion there for what fixing the signature does and does |
| 38 | not cost. Its distance is the walk distance of that file, which for a |
| 39 | colored graph is the distance in its Gaifman graph. |
| 40 | |
| 41 | A formula is *local* when it never uses unrestricted quantification. |
| 42 | Semantic locality is the corresponding property of meaning rather than |
| 43 | of shape: a formula is semantically *r*-local when its truth on a tuple |
| 44 | is unchanged by discarding every vertex further than *r* from that |
| 45 | tuple. |
| 46 | |
| 47 | # Formalization notes |
| 48 | |
| 49 | The horizon functions are the source's concrete pair, ρ⁻(*k*, *q*) = |
| 50 | 9^((*k*+*q*+1)*q*) and ρ⁺(*k*, *q*) = 9^((*k*+*q*)(*q*+1)), rather than |
| 51 | an arbitrary pair satisfying the source's inequalities (1). The |
| 52 | statements on this surface are then about a definite logic with |
| 53 | definite radii and can be read without carrying a parameter through |
| 54 | every one of them. The proofs behind those statements use nothing about |
| 55 | the pair beyond the two inequalities of (1), and are written against an |
| 56 | abstract bundle of them; that bundle is an implementation detail and is |
| 57 | not part of the concept surface. |
| 58 | |
| 59 | The distance rank is a *predicate* on formulas, not a second type |
| 60 | index. Its rank argument is independent of the type index: `DRank k' q |
| 61 | φ` may be asserted of a `φ : DistFO L k` for any `k' ` — the source's |
| 62 | "at most *k* free variables" is `k ≤ k'`, and demanding equality would |
| 63 | force a reindexing of the syntax at every step of every proof, for no |
| 64 | gain. The source's Observations 4 and 6, which say that rank is |
| 65 | preserved along the schedule, become monotonicity lemmas of this |
| 66 | predicate. |
| 67 | |
| 68 | **Deviation, deliberate: the local guard radius is bounded, not |
| 69 | pinned.** The source's grammar admits the local quantifier only at the |
| 70 | exact radius ρ⁺(*k*+1, *q*−1); here `DRank` requires `r ≤ ρ⁺(k'+1, q)` |
| 71 | at rank (`k'`, `q`+1). The source's own Observation 4 — every formula |
| 72 | of distance rank (*k*+1, *q*−1) with at most *k* free variables also |
| 73 | has distance rank (*k*, *q*) — is false for the exact reading as |
| 74 | stated: a local quantifier of a (*k*+1, *q*−1)-formula guards at |
| 75 | ρ⁺(*k*+2, *q*−2), which is not the radius ρ⁺(*k*+1, *q*−1) that a |
| 76 | (*k*, *q*)-formula is allowed. The source absorbs the mismatch |
| 77 | silently, by reading a guarded quantifier as an unrestricted quantifier |
| 78 | over a conjunction with binary distance atoms — a rewriting, not an |
| 79 | identity of formulas. With the bound in place the observation is a |
| 80 | plain monotonicity lemma about `DRank`, proved where it is used and not |
| 81 | here. The relaxation only adds sound inputs: a smaller guard radius |
| 82 | means the quantifier ranges over fewer vertices, so every syntactic |
| 83 | bound the locality proof draws from a guard still holds. |
| 84 | |
| 85 | Satisfaction is total, environments are `Fin k → Fin n`, and binders |
| 86 | extend the environment at the last position; see `Lax3.FirstOrder` for |
| 87 | that discussion, which applies verbatim. |
| 88 | |
| 89 | The guard of a local quantifier carries its variable set in the |
| 90 | syntax: `exL r g φ` ranges over the vertices within distance *r* of |
| 91 | the variables in the finite set `g`. This is the source's guard |
| 92 | dist(x̄, *y*) ≤ *r* = ⋁_{x ∈ x̄} dist(*x*, *y*) ≤ *r* read as the |
| 93 | source writes it: the set x̄ is chosen when the formula is formed |
| 94 | ("we write φ(x̄) to indicate that x̄ *contains* the free variables of |
| 95 | φ") and does not change when the formula later occurs inside a larger |
| 96 | one. Recording the set is what makes that stability true here as |
| 97 | well — placing a one-variable formula at a bound variable of a wider |
| 98 | formula, as the locality theorem's proof and the normal form's |
| 99 | written-out scatter sentences both do, keeps its guards reading that |
| 100 | one variable, and renaming is sound with no side conditions because |
| 101 | the guard set travels along. A guard over everything in scope is the |
| 102 | special case `g = univ`; the earlier revision of this file had only |
| 103 | that case, which widens a formula's guards whenever the context |
| 104 | grows, and under which the placement just described is unsound. With |
| 105 | `g = ∅` the guard is an empty disjunction, so the quantifier is |
| 106 | vacuously false — in particular a local quantifier over a sentence's |
| 107 | empty context has no vertex to be local to, and the locality |
| 108 | theorem's sentence case produces scatter sentences precisely because |
| 109 | local quantification cannot help there. |
| 110 | |
| 111 | The unary distance atom is strict, dist(*x*, *Y*) < *r*, as in the |
| 112 | source; the binary one is not. The asymmetry is the source's and is |
| 113 | kept — a translation that quietly aligned them would make the |
| 114 | statements here no longer the statements of the source note. Unary |
| 115 | distance atoms are carried at all only for faithfulness: the algorithm |
| 116 | never manufactures one, and its formulas stay in the fragment without |
| 117 | them. |
| 118 | |
| 119 | `SatWithin` is the source's relativization *A*[*N_r*(ā)] ⊨ φ(ā), |
| 120 | written with the carrier kept: the induced substructure lives on the |
| 121 | same vertex type `Fin n`, and the restriction to `D` is imposed by the |
| 122 | definition instead of by a subtype. That matches the uniform vertex |
| 123 | numbering every structure of this submission carries, and matches |
| 124 | Lax12's `deleteVerts`, which also isolates rather than removes. Inside |
| 125 | `D` the atoms are the induced ones: an edge survives only if both its |
| 126 | endpoints do, a color class is intersected with `D`, and a distance |
| 127 | atom measures along walks that stay in `D`. Satisfaction and |
| 128 | relativization to the full vertex set agree, but `SatWithin univ` is |
| 129 | *not* how `Sat` is defined — the agreement is a lemma, proved where the |
| 130 | two are compared, so that each definition can be read and audited on |
| 131 | its own. |
| 132 | |
| 133 | `rename` is here because the sentences of `Lax3.Locality` need to place |
| 134 | a one-variable formula at each of several bound variables. It is a |
| 135 | definition only; the lemmas relating it to satisfaction belong with the |
| 136 | proofs that use them. |
| 137 | -/ |
| 138 | |
| 139 | namespace Lax3.DistFO |
| 140 | |
| 141 | open Lax3.ColoredGraphs |
| 142 | |
| 143 | /-- The lower horizon function ρ⁻ of the source: the largest radius a |
| 144 | distance atom of distance rank `(k, q)` may carry. -/ |
| 145 | def rhoMinus (k q : ℕ) : ℕ := 9 ^ ((k + q + 1) * q) |
| 146 | |
| 147 | /-- The upper horizon function ρ⁺ of the source: the largest radius a |
| 148 | local quantifier may guard at, one rank level in. -/ |
| 149 | def rhoPlus (k q : ℕ) : ℕ := 9 ^ ((k + q) * (q + 1)) |
| 150 | |
| 151 | -- the logic and the module carrying it have the same name on purpose |
| 152 | set_option linter.dupNamespace false in |
| 153 | /-- Formulas of distance logic over `L`-colored graphs, with `k` free |
| 154 | variables. Variables are `Fin k`, and both quantifiers bind the *new |
| 155 | last* index. Beyond the atoms of first-order logic there are colors and |
| 156 | the two distance atoms, and beyond unrestricted quantification there is |
| 157 | local quantification, which ranges over the vertices within a given |
| 158 | radius of the free variables. -/ |
| 159 | inductive DistFO (L : ℕ) : ℕ → Type |
| 160 | /-- The vertices `i` and `j` are adjacent. -/ |
| 161 | | adj {k : ℕ} (i j : Fin k) : DistFO L k |
| 162 | /-- The vertices `i` and `j` are equal. -/ |
| 163 | | eq {k : ℕ} (i j : Fin k) : DistFO L k |
| 164 | /-- The vertex `i` has color `c`. -/ |
| 165 | | color {k : ℕ} (c : Fin L) (i : Fin k) : DistFO L k |
| 166 | /-- Binary distance atom: the distance between `i` and `j` is at most |
| 167 | `r`. -/ |
| 168 | | distLe {k : ℕ} (r : ℕ) (i j : Fin k) : DistFO L k |
| 169 | /-- Unary distance atom: the distance from `i` to the color class `c` |
| 170 | is smaller than `r`. -/ |
| 171 | | distColorLt {k : ℕ} (r : ℕ) (c : Fin L) (i : Fin k) : DistFO L k |
| 172 | /-- Negation. -/ |
| 173 | | not {k : ℕ} (φ : DistFO L k) : DistFO L k |
| 174 | /-- Conjunction. -/ |
| 175 | | and {k : ℕ} (φ ψ : DistFO L k) : DistFO L k |
| 176 | /-- Unrestricted quantification: there is a vertex satisfying `φ`, |
| 177 | bound at the last index. -/ |
| 178 | | exU {k : ℕ} (φ : DistFO L (k + 1)) : DistFO L k |
| 179 | /-- Local quantification: there is a vertex within distance `r` of |
| 180 | some variable in the guard set `g` satisfying `φ`, bound at the last |
| 181 | index. The radius and the guard set are part of the syntax; which |
| 182 | radii are admissible at a given distance rank is the business of |
| 183 | `DRank`, and the guard set is unconstrained there, as in the |
| 184 | source. -/ |
| 185 | | exL {k : ℕ} (r : ℕ) (g : Finset (Fin k)) (φ : DistFO L (k + 1)) : DistFO L k |
| 186 | |
| 187 | variable {L n : ℕ} |
| 188 | |
| 189 | /-- Satisfaction of a formula in the `L`-colored graph `(G, col)` under |
| 190 | the environment `m`. A binary distance atom is a walk-length bound, a |
| 191 | unary one asks for a color-class vertex strictly nearer than `r`, and a |
| 192 | local quantifier ranges over the vertices within `r` of some variable |
| 193 | in its guard set — an empty condition, hence unsatisfiable, when the |
| 194 | set is empty. -/ |
| 195 | def Sat (G : SimpleGraph (Fin n)) (col : Coloring n L) : |
| 196 | {k : ℕ} → (Fin k → Fin n) → DistFO L k → Prop |
| 197 | | _, m, .adj i j => G.Adj (m i) (m j) |
| 198 | | _, m, .eq i j => m i = m j |
| 199 | | _, m, .color c i => m i ∈ col c |
| 200 | | _, m, .distLe r i j => WithinDist G r (m i) (m j) |
| 201 | | _, m, .distColorLt r c i => ∃ y ∈ col c, ∃ w : G.Walk (m i) y, w.length < r |
| 202 | | _, m, .not φ => ¬ Sat G col m φ |
| 203 | | _, m, .and φ ψ => Sat G col m φ ∧ Sat G col m ψ |
| 204 | | _, m, .exU φ => ∃ v : Fin n, Sat G col (Fin.snoc m v) φ |
| 205 | | _, m, .exL r g φ => |
| 206 | ∃ v : Fin n, (∃ i ∈ g, WithinDist G r (m i) v) ∧ Sat G col (Fin.snoc m v) φ |
| 207 | |
| 208 | /-- Renaming of variables along `f`. Under a binder the renaming is |
| 209 | lifted to `Fin (k + 1) → Fin (k' + 1)` by sending the bound variable — |
| 210 | the last index — to the new last index. The guard set of a local |
| 211 | quantifier is mapped along `f`, so a guard keeps naming the same |
| 212 | variables it named before. -/ |
| 213 | def rename : {k k' : ℕ} → (Fin k → Fin k') → DistFO L k → DistFO L k' |
| 214 | | _, _, f, .adj i j => .adj (f i) (f j) |
| 215 | | _, _, f, .eq i j => .eq (f i) (f j) |
| 216 | | _, _, f, .color c i => .color c (f i) |
| 217 | | _, _, f, .distLe r i j => .distLe r (f i) (f j) |
| 218 | | _, _, f, .distColorLt r c i => .distColorLt r c (f i) |
| 219 | | _, _, f, .not φ => .not (rename f φ) |
| 220 | | _, _, f, .and φ ψ => .and (rename f φ) (rename f ψ) |
| 221 | | _, k', f, .exU φ => .exU (rename (Fin.snoc (fun i => (f i).castSucc) (Fin.last k')) φ) |
| 222 | | _, k', f, .exL r g φ => |
| 223 | .exL r (g.image f) (rename (Fin.snoc (fun i => (f i).castSucc) (Fin.last k')) φ) |
| 224 | |
| 225 | /-- `DRank k' q φ` says that `φ` has distance rank `(k', q)`: its |
| 226 | quantifier rank is at most `q`, every distance atom in it has radius at |
| 227 | most `ρ⁻` of the rank in force there, and every local quantifier guards |
| 228 | at radius at most `ρ⁺` of the rank one level in. The rank argument |
| 229 | `k'` is a bound on the number of free variables and is independent of |
| 230 | the type index. -/ |
| 231 | inductive DRank {L : ℕ} : ℕ → ℕ → {k : ℕ} → DistFO L k → Prop |
| 232 | /-- An adjacency atom has every distance rank. -/ |
| 233 | | adj {k' q k : ℕ} (i j : Fin k) : DRank k' q (.adj i j) |
| 234 | /-- An equality atom has every distance rank. -/ |
| 235 | | eq {k' q k : ℕ} (i j : Fin k) : DRank k' q (.eq i j) |
| 236 | /-- A color atom has every distance rank. -/ |
| 237 | | color {k' q k : ℕ} (c : Fin L) (i : Fin k) : DRank k' q (.color c i) |
| 238 | /-- A binary distance atom has distance rank `(k', q)` when its |
| 239 | radius is at most `ρ⁻(k', q)`. -/ |
| 240 | | distLe {k' q k : ℕ} {r : ℕ} (i j : Fin k) (hr : r ≤ rhoMinus k' q) : |
| 241 | DRank k' q (.distLe r i j) |
| 242 | /-- A unary distance atom has distance rank `(k', q)` when its radius |
| 243 | is at most `ρ⁻(k', q)`. -/ |
| 244 | | distColorLt {k' q k : ℕ} {r : ℕ} (c : Fin L) (i : Fin k) (hr : r ≤ rhoMinus k' q) : |
| 245 | DRank k' q (.distColorLt r c i) |
| 246 | /-- Negation preserves the distance rank. -/ |
| 247 | | not {k' q k : ℕ} {φ : DistFO L k} (h : DRank k' q φ) : DRank k' q (.not φ) |
| 248 | /-- Conjunction preserves the distance rank. -/ |
| 249 | | and {k' q k : ℕ} {φ ψ : DistFO L k} (h : DRank k' q φ) (h' : DRank k' q ψ) : |
| 250 | DRank k' q (.and φ ψ) |
| 251 | /-- An unrestricted quantifier has distance rank `(k', q + 1)` when |
| 252 | its body has distance rank `(k' + 1, q)`. -/ |
| 253 | | exU {k' q k : ℕ} {φ : DistFO L (k + 1)} (h : DRank (k' + 1) q φ) : |
| 254 | DRank k' (q + 1) (.exU φ) |
| 255 | /-- A local quantifier has distance rank `(k', q + 1)` when its body |
| 256 | has distance rank `(k' + 1, q)` and it guards at radius at most |
| 257 | `ρ⁺(k' + 1, q)`. The guard set is unconstrained. -/ |
| 258 | | exL {k' q k : ℕ} {r : ℕ} {g : Finset (Fin k)} {φ : DistFO L (k + 1)} |
| 259 | (h : DRank (k' + 1) q φ) (hr : r ≤ rhoPlus (k' + 1) q) : DRank k' (q + 1) (.exL r g φ) |
| 260 | |
| 261 | /-- A formula is local when it uses no unrestricted quantification. -/ |
| 262 | def IsLocal : {k : ℕ} → DistFO L k → Prop |
| 263 | | _, .adj _ _ => True |
| 264 | | _, .eq _ _ => True |
| 265 | | _, .color _ _ => True |
| 266 | | _, .distLe _ _ _ => True |
| 267 | | _, .distColorLt _ _ _ => True |
| 268 | | _, .not φ => IsLocal φ |
| 269 | | _, .and φ ψ => IsLocal φ ∧ IsLocal ψ |
| 270 | | _, .exU _ => False |
| 271 | | _, .exL _ _ φ => IsLocal φ |
| 272 | |
| 273 | /-- The vertices `u` and `v` are within distance `d` *inside* `D`: some |
| 274 | walk from `u` to `v` has length at most `d` and stays in `D`. This is |
| 275 | the walk distance of the substructure induced on `D`, with the carrier |
| 276 | kept. -/ |
| 277 | def WithinDistIn {V : Type*} (D : Set V) (G : SimpleGraph V) (d : ℕ) (u v : V) : Prop := |
| 278 | ∃ w : G.Walk u v, w.length ≤ d ∧ ∀ x ∈ w.support, x ∈ D |
| 279 | |
| 280 | /-- Satisfaction in the substructure induced on `D`, with the carrier |
| 281 | kept: quantifiers range over `D`, an edge counts only if both endpoints |
| 282 | lie in `D`, color classes are intersected with `D`, and distances are |
| 283 | measured along walks inside `D`. -/ |
| 284 | def SatWithin (D : Set (Fin n)) (G : SimpleGraph (Fin n)) (col : Coloring n L) : |
| 285 | {k : ℕ} → (Fin k → Fin n) → DistFO L k → Prop |
| 286 | | _, m, .adj i j => G.Adj (m i) (m j) ∧ m i ∈ D ∧ m j ∈ D |
| 287 | | _, m, .eq i j => m i = m j |
| 288 | | _, m, .color c i => m i ∈ col c ∧ m i ∈ D |
| 289 | | _, m, .distLe r i j => WithinDistIn D G r (m i) (m j) |
| 290 | | _, m, .distColorLt r c i => |
| 291 | ∃ y, y ∈ col c ∧ y ∈ D ∧ ∃ w : G.Walk (m i) y, w.length < r ∧ ∀ x ∈ w.support, x ∈ D |
| 292 | | _, m, .not φ => ¬ SatWithin D G col m φ |
| 293 | | _, m, .and φ ψ => SatWithin D G col m φ ∧ SatWithin D G col m ψ |
| 294 | | _, m, .exU φ => ∃ v ∈ D, SatWithin D G col (Fin.snoc m v) φ |
| 295 | | _, m, .exL r g φ => |
| 296 | ∃ v ∈ D, (∃ i ∈ g, WithinDistIn D G r (m i) v) ∧ SatWithin D G col (Fin.snoc m v) φ |
| 297 | |
| 298 | /-- A formula is semantically `r`-local when its truth on a tuple never |
| 299 | depends on the vertices further than `r` from that tuple: satisfaction |
| 300 | in the graph and satisfaction in the substructure induced on the union |
| 301 | of the `r`-balls around the tuple agree, in every colored graph and at |
| 302 | every tuple. -/ |
| 303 | def SemanticallyLocal (r : ℕ) {k : ℕ} (φ : DistFO L k) : Prop := |
| 304 | ∀ (n : ℕ) (G : SimpleGraph (Fin n)) (col : Coloring n L) (m : Fin k → Fin n), |
| 305 | Sat G col m φ ↔ SatWithin (⋃ i, ball G r (m i)) G col m φ |
| 306 | |
| 307 | end Lax3.DistFO |
| 308 |
Formalization notes
The horizon functions are the source's concrete pair, ρ⁻(k, q) = 9^((k+q+1)q) and ρ⁺(k, q) = 9^((k+q)(q+1)), rather than an arbitrary pair satisfying the source's inequalities (1). The statements on this surface are then about a definite logic with definite radii and can be read without carrying a parameter through every one of them. The proofs behind those statements use nothing about the pair beyond the two inequalities of (1), and are written against an abstract bundle of them; that bundle is an implementation detail and is not part of the concept surface.
The distance rank is a predicate on formulas, not a second type index. Its rank argument is independent of the type index: may be asserted of a for any — the source's "at most k free variables" is , and demanding equality would force a reindexing of the syntax at every step of every proof, for no gain. The source's Observations 4 and 6, which say that rank is preserved along the schedule, become monotonicity lemmas of this predicate.
Deviation, deliberate: the local guard radius is bounded, not pinned. The source's grammar admits the local quantifier only at the exact radius ρ⁺(k+1, q−1); here requires at rank (, +1). The source's own Observation 4 — every formula of distance rank (k+1, q−1) with at most k free variables also has distance rank (k, q) — is false for the exact reading as stated: a local quantifier of a (k+1, q−1)-formula guards at ρ⁺(k+2, q−2), which is not the radius ρ⁺(k+1, q−1) that a (k, q)-formula is allowed. The source absorbs the mismatch silently, by reading a guarded quantifier as an unrestricted quantifier over a conjunction with binary distance atoms — a rewriting, not an identity of formulas. With the bound in place the observation is a plain monotonicity lemma about , proved where it is used and not here. The relaxation only adds sound inputs: a smaller guard radius means the quantifier ranges over fewer vertices, so every syntactic bound the locality proof draws from a guard still holds.
Satisfaction is total, environments are , and binders extend the environment at the last position; see for that discussion, which applies verbatim.
The guard of a local quantifier carries its variable set in the syntax: ranges over the vertices within distance r of the variables in the finite set . This is the source's guard dist(x̄, y) ≤ r = ⋁_{x ∈ x̄} dist(x, y) ≤ r read as the source writes it: the set x̄ is chosen when the formula is formed ("we write φ(x̄) to indicate that x̄ contains the free variables of φ") and does not change when the formula later occurs inside a larger one. Recording the set is what makes that stability true here as well — placing a one-variable formula at a bound variable of a wider formula, as the locality theorem's proof and the normal form's written-out scatter sentences both do, keeps its guards reading that one variable, and renaming is sound with no side conditions because the guard set travels along. A guard over everything in scope is the special case ; the earlier revision of this file had only that case, which widens a formula's guards whenever the context grows, and under which the placement just described is unsound. With the guard is an empty disjunction, so the quantifier is vacuously false — in particular a local quantifier over a sentence's empty context has no vertex to be local to, and the locality theorem's sentence case produces scatter sentences precisely because local quantification cannot help there.
The unary distance atom is strict, dist(x, Y) < r, as in the source; the binary one is not. The asymmetry is the source's and is kept — a translation that quietly aligned them would make the statements here no longer the statements of the source note. Unary distance atoms are carried at all only for faithfulness: the algorithm never manufactures one, and its formulas stay in the fragment without them.
is the source's relativization A[N_r(ā)] ⊨ φ(ā), written with the carrier kept: the induced substructure lives on the same vertex type , and the restriction to is imposed by the definition instead of by a subtype. That matches the uniform vertex numbering every structure of this submission carries, and matches Lax12's , which also isolates rather than removes. Inside the atoms are the induced ones: an edge survives only if both its endpoints do, a color class is intersected with , and a distance atom measures along walks that stay in . Satisfaction and relativization to the full vertex set agree, but is not how is defined — the agreement is a lemma, proved where the two are compared, so that each definition can be read and audited on its own.
is here because the sentences of need to place a one-variable formula at each of several bound variables. It is a definition only; the lemmas relating it to satisfaction belong with the proofs that use them.
Builds on
Used by
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments