While this submission is a draft, it cannot be used by other submissions.

Second-order transitive closure without an order

Lax134656.OrderFreeTransitiveClosure · concepts/Lax134656/OrderFreeTransitiveClosure.lean · lax-134656

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.

    Natural Language Statement

    Definition

    An order-free second-order transitive-closure specification over a vocabulary LL is a specification whose three sentences are over LL and the copies of the block alone, with no order symbol. It defines, on any LL-structure, the same graph on the assignments of the block and the same acceptance condition. A decision problem PP over LL is order-free SO(TC) definable when some such specification accepts, for every nonempty finite LL-structure AA, exactly when AA is a yes-instance of PP: no linear order appears in the statement.

    Concept map
    6 concepts; 15 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.ModelTheory.Order
    2import Mathlib.ModelTheory.Semantics
    3import Mathlib.Logic.Relation
    4import Lax904597.Problems
    5import Lax904597.SecondOrder
    6import Lax535992.InflationaryFixedPoint
    7import Lax134656.SecondOrderTransitiveClosure
    8
    9/-!
    10---
    11title: Second-order transitive closure without an order
    12type: definition
    13---
    14An order-free second-order transitive-closure specification over a
    15vocabulary LL is a specification whose three sentences are over LL and
    16the copies of the block alone, with no order symbol. It defines, on any
    17LL-structure, the same graph on the assignments of the block and the same
    18acceptance condition. A decision problem PP over LL is order-free SO(TC)
    19definable when some such specification accepts, for every nonempty finite
    20LL-structure AA, exactly when AA is a yes-instance of PP: no linear
    21order appears in the statement.
    22-/
    23
    24namespace Lax134656.OrderFreeTransitiveClosure
    25
    26open Lax904597.Problems Lax904597.SecondOrder Lax535992.InflationaryFixedPoint
    27open Lax134656.SecondOrderTransitiveClosure
    28
    29open FirstOrder
    30
    31open Language Structure
    32
    33/-- An SO(TC) specification that does **not** see a linear order: as in
    34`SOTCSpec`, the states of the walk are the assignments of
    35a block, but the three sentences live over the bare vocabulary expanded by
    36copies of the block, with no order symbol available. -/
    37structure SOTCSpecFree (L : Language.{0, 0}) : Type 1 where
    38 /-- The block whose assignments are the states of the walk. -/
    39 B : SOBlock
    40 /-- The transition sentence, over two copies of the block: the current state
    41 reads the first copy, the next state the second. -/
    42 step : ((L.sum B.lang).sum B.lang).Sentence
    43 /-- The sentence defining the admissible starting states. -/
    44 src : (L.sum B.lang).Sentence
    45 /-- The sentence defining the accepting states. -/
    46 tgt : (L.sum B.lang).Sentence
    47
    48namespace SOTCSpecFree
    49
    50section Semantics
    51
    52variable {L : Language.{0, 0}} (spec : SOTCSpecFree L) {A : Type} [L.Structure A]
    53
    54variable (A) in
    55/-- A state of the walk: an assignment of the block. -/
    56abbrev State : Type := spec.B.Assignment A
    57
    58/-- One step of the walk: the transition sentence, read with the current state
    59in the first copy of the block and the next state in the second. -/
    60def Step (ρ σ : spec.State A) : Prop :=
    61 @Sentence.Realize _ A (SOBlock.structure₂ (L := L) spec.B ρ σ) spec.step
    62
    63/-- Reachability in the walk: the reflexive-transitive closure of
    64`SOTCSpecFree.Step`. -/
    65abbrev Reach : spec.State A → spec.State A → Prop :=
    66 Relation.ReflTransGen spec.Step
    67
    68/-- A state is a starting state when it satisfies the source sentence. -/
    69def IsSrc (ρ : spec.State A) : Prop :=
    70 @Sentence.Realize _ A (SOBlock.structure₁ (L := L) spec.B ρ) spec.src
    71
    72/-- A state is accepting when it satisfies the target sentence. -/
    73def IsTgt (ρ : spec.State A) : Prop :=
    74 @Sentence.Realize _ A (SOBlock.structure₁ (L := L) spec.B ρ) spec.tgt
    75
    76variable (A) in
    77/-- The structure is accepted: some accepting state is reachable from some
    78starting state. No order on `A` is involved. -/
    79def Accepts : Prop :=
    80 ∃ ρ σ : spec.State A, spec.IsSrc ρ ∧ spec.IsTgt σ ∧ spec.Reach ρ σ
    81
    82end Semantics
    83
    84end SOTCSpecFree
    85
    86/-- A decision problem is *order-free SO(TC) definable* if it is defined by an
    87`SOTCSpecFree` on nonempty finite structures – with **no linear order in the
    88statement at all**, unlike `SOTCDefinable`. -/
    89def SOTCDefinableFree {L : Language.{0, 0}} [L.IsRelational] (P : DecisionProblem L) : Prop :=
    90 ∃ spec : SOTCSpecFree L,
    91 ∀ (A : Type) [L.Structure A] [Finite A] [Nonempty A], P A ↔ spec.Accepts A
    92
    93end Lax134656.OrderFreeTransitiveClosure
    94

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…