Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax3.DistFO

Distance logic and distance rank

concepts/Lax3/DistFO.lean · lax-3

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    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 Lax3.LocalityLax3.Locality 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 Lax3.ColoredGraphsLax3.ColoredGraphs — 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

    1import Lax3.ColoredGraphs
    2import Mathlib.Data.Fin.Tuple.Basic
    3import Mathlib.Data.Finset.Image
    4
    5/-!
    6---
    7title: Distance logic and distance rank
    8type: definition
    9---
    10Distance logic extends first-order logic by two families of *distance
    11atoms* — the distance between two variables is at most *r*, and the
    12distance from a variable to a color class is smaller than *r* — and by
    13*local quantification*, an existential quantifier that ranges only over
    14the vertices within a given radius of a recorded set of the variables
    15in scope. As a logic it
    16is no stronger than first-order logic: over a fixed signature, "the
    17distance between *x* and *y* is at most *r*" is already first-order
    18expressible, and a local quantifier is an ordinary quantifier
    19conjoined with such a distance test. What the extra syntax buys is a
    20finer rank measure.
    21
    22That measure is *distance rank*. A formula has distance rank (*k*, *q*)
    23when it has at most *k* free variables, quantifier rank at most *q*,
    24every distance atom in it has radius at most ρ⁻(*k*, *q*), and every
    25local quantifier in it guards at radius at most ρ⁺(*k*+1, *q*−1), where
    26ρ⁻ and ρ⁺ are the two *horizon functions*. The two functions decrease
    27fast enough as one traverses the quantifiers of a formula inwards that
    28the radii do too: the region a subformula can see shrinks strictly at
    29every 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
    32sentences of the *same* distance rank, which ordinary quantifier rank
    33could not express.
    34
    35This is the logic distFO of the source note (arXiv:2606.23180, §2.1),
    36interpreted over the finite colored graphs of `Lax3.ColoredGraphs` —
    37see the discussion there for what fixing the signature does and does
    38not cost. Its distance is the walk distance of that file, which for a
    39colored graph is the distance in its Gaifman graph.
    40
    41A formula is *local* when it never uses unrestricted quantification.
    42Semantic locality is the corresponding property of meaning rather than
    43of shape: a formula is semantically *r*-local when its truth on a tuple
    44is unchanged by discarding every vertex further than *r* from that
    45tuple.
    46
    47# Formalization notes
    48
    49The horizon functions are the source's concrete pair, ρ⁻(*k*, *q*) =
    509^((*k*+*q*+1)*q*) and ρ⁺(*k*, *q*) = 9^((*k*+*q*)(*q*+1)), rather than
    51an arbitrary pair satisfying the source's inequalities (1). The
    52statements on this surface are then about a definite logic with
    53definite radii and can be read without carrying a parameter through
    54every one of them. The proofs behind those statements use nothing about
    55the pair beyond the two inequalities of (1), and are written against an
    56abstract bundle of them; that bundle is an implementation detail and is
    57not part of the concept surface.
    58
    59The distance rank is a *predicate* on formulas, not a second type
    60index. 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
    63force a reindexing of the syntax at every step of every proof, for no
    64gain. The source's Observations 4 and 6, which say that rank is
    65preserved along the schedule, become monotonicity lemmas of this
    66predicate.
    67
    68**Deviation, deliberate: the local guard radius is bounded, not
    69pinned.** The source's grammar admits the local quantifier only at the
    70exact radius ρ⁺(*k*+1, *q*−1); here `DRank` requires `r ≤ ρ⁺(k'+1, q)`
    71at rank (`k'`, `q`+1). The source's own Observation 4 — every formula
    72of distance rank (*k*+1, *q*−1) with at most *k* free variables also
    73has distance rank (*k*, *q*) — is false for the exact reading as
    74stated: 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
    77silently, by reading a guarded quantifier as an unrestricted quantifier
    78over a conjunction with binary distance atoms — a rewriting, not an
    79identity of formulas. With the bound in place the observation is a
    80plain monotonicity lemma about `DRank`, proved where it is used and not
    81here. The relaxation only adds sound inputs: a smaller guard radius
    82means the quantifier ranges over fewer vertices, so every syntactic
    83bound the locality proof draws from a guard still holds.
    84
    85Satisfaction is total, environments are `Fin k → Fin n`, and binders
    86extend the environment at the last position; see `Lax3.FirstOrder` for
    87that discussion, which applies verbatim.
    88
    89The guard of a local quantifier carries its variable set in the
    90syntax: `exL r g φ` ranges over the vertices within distance *r* of
    91the variables in the finite set `g`. This is the source's guard
    92dist(x̄, *y*) ≤ *r* = ⋁_{x ∈ x̄} dist(*x*, *y*) ≤ *r* read as the
    93source 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
    96one. Recording the set is what makes that stability true here as
    97well — placing a one-variable formula at a bound variable of a wider
    98formula, as the locality theorem's proof and the normal form's
    99written-out scatter sentences both do, keeps its guards reading that
    100one variable, and renaming is sound with no side conditions because
    101the guard set travels along. A guard over everything in scope is the
    102special case `g = univ`; the earlier revision of this file had only
    103that case, which widens a formula's guards whenever the context
    104grows, and under which the placement just described is unsound. With
    105`g = ∅` the guard is an empty disjunction, so the quantifier is
    106vacuously false — in particular a local quantifier over a sentence's
    107empty context has no vertex to be local to, and the locality
    108theorem's sentence case produces scatter sentences precisely because
    109local quantification cannot help there.
    110
    111The unary distance atom is strict, dist(*x*, *Y*) < *r*, as in the
    112source; the binary one is not. The asymmetry is the source's and is
    113kept — a translation that quietly aligned them would make the
    114statements here no longer the statements of the source note. Unary
    115distance atoms are carried at all only for faithfulness: the algorithm
    116never manufactures one, and its formulas stay in the fragment without
    117them.
    118
    119`SatWithin` is the source's relativization *A*[*N_r*(ā)] ⊨ φ(ā),
    120written with the carrier kept: the induced substructure lives on the
    121same vertex type `Fin n`, and the restriction to `D` is imposed by the
    122definition instead of by a subtype. That matches the uniform vertex
    123numbering every structure of this submission carries, and matches
    124Lax12's `deleteVerts`, which also isolates rather than removes. Inside
    125`D` the atoms are the induced ones: an edge survives only if both its
    126endpoints do, a color class is intersected with `D`, and a distance
    127atom measures along walks that stay in `D`. Satisfaction and
    128relativization to the full vertex set agree, but `SatWithin univ` is
    129*not* how `Sat` is defined — the agreement is a lemma, proved where the
    130two are compared, so that each definition can be read and audited on
    131its own.
    132
    133`rename` is here because the sentences of `Lax3.Locality` need to place
    134a one-variable formula at each of several bound variables. It is a
    135definition only; the lemmas relating it to satisfaction belong with the
    136proofs that use them.
    137-/
    138
    139namespace Lax3.DistFO
    140
    141open Lax3.ColoredGraphs
    142
    143/-- The lower horizon function ρ⁻ of the source: the largest radius a
    144distance atom of distance rank `(k, q)` may carry. -/
    145def rhoMinus (k q : ℕ) : ℕ := 9 ^ ((k + q + 1) * q)
    146
    147/-- The upper horizon function ρ⁺ of the source: the largest radius a
    148local quantifier may guard at, one rank level in. -/
    149def rhoPlus (k q : ℕ) : ℕ := 9 ^ ((k + q) * (q + 1))
    150
    151-- the logic and the module carrying it have the same name on purpose
    152set_option linter.dupNamespace false in
    153/-- Formulas of distance logic over `L`-colored graphs, with `k` free
    154variables. Variables are `Fin k`, and both quantifiers bind the *new
    155last* index. Beyond the atoms of first-order logic there are colors and
    156the two distance atoms, and beyond unrestricted quantification there is
    157local quantification, which ranges over the vertices within a given
    158radius of the free variables. -/
    159inductive 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
    187variable {L n : ℕ}
    188
    189/-- Satisfaction of a formula in the `L`-colored graph `(G, col)` under
    190the environment `m`. A binary distance atom is a walk-length bound, a
    191unary one asks for a color-class vertex strictly nearer than `r`, and a
    192local quantifier ranges over the vertices within `r` of some variable
    193in its guard set — an empty condition, hence unsatisfiable, when the
    194set is empty. -/
    195def 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
    209lifted to `Fin (k + 1) → Fin (k' + 1)` by sending the bound variable —
    210the last index — to the new last index. The guard set of a local
    211quantifier is mapped along `f`, so a guard keeps naming the same
    212variables it named before. -/
    213def 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
    226quantifier rank is at most `q`, every distance atom in it has radius at
    227most `ρ⁻` of the rank in force there, and every local quantifier guards
    228at 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
    230the type index. -/
    231inductive 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. -/
    262def 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
    274walk from `u` to `v` has length at most `d` and stays in `D`. This is
    275the walk distance of the substructure induced on `D`, with the carrier
    276kept. -/
    277def 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
    281kept: quantifiers range over `D`, an edge counts only if both endpoints
    282lie in `D`, color classes are intersected with `D`, and distances are
    283measured along walks inside `D`. -/
    284def 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
    299depends on the vertices further than `r` from that tuple: satisfaction
    300in the graph and satisfaction in the substructure induced on the union
    301of the `r`-balls around the tuple agree, in every colored graph and at
    302every tuple. -/
    303def 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
    307end 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: DRankkqφDRank k' q φ may be asserted of a φ:DistFOLkφ : DistFO L k for any kk' — the source's "at most k free variables" is kkk ≤ k', 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 DRankDRank requires rρ+(k+1,q)r ≤ ρ⁺(k'+1, q) at rank (kk', qq+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 DRankDRank, 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 FinkFinnFin k → Fin n, and binders extend the environment at the last position; see Lax3.FirstOrderLax3.FirstOrder for that discussion, which applies verbatim.

    The guard of a local quantifier carries its variable set in the syntax: exLrgφexL r g φ ranges over the vertices within distance r of the variables in the finite set gg. 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 g=univg = univ; 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 g=g = ∅ 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.

    SatWithinSatWithin is the source's relativization A[N_r(ā)] ⊨ φ(ā), written with the carrier kept: the induced substructure lives on the same vertex type FinnFin n, and the restriction to DD 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 deleteVertsdeleteVerts, which also isolates rather than removes. Inside DD the atoms are the induced ones: an edge survives only if both its endpoints do, a color class is intersected with DD, and a distance atom measures along walks that stay in DD. Satisfaction and relativization to the full vertex set agree, but SatWithinunivSatWithin univ is not how SatSat 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.

    renamerename is here because the sentences of Lax3.LocalityLax3.Locality 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.

    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

    Loading discussion…