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

Reindexing the outgoing directions at each vertex

Lax369799.DirectionReindexing · concepts/Lax369799/DirectionReindexing.lean · lax-369799

proven

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

    Theorem

    Replace the directions at every vertex by a finite set mapping surjectively onto the original directions. Successors and valuations are preserved after forgetting direction order and multiplicity. The resulting deterministic system has an isomorphic decoding, as used in the cloning and rerouting constructions of Lemma 108.

    Concept map
    5 concepts; 2 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.TransitionEncoding
    2
    3/-!
    4---
    5title: Reindexing the outgoing directions at each vertex
    6type: theorem
    7---
    8Replace the directions at every vertex by a finite set mapping
    9surjectively onto the original directions. Successors and valuations
    10are preserved after forgetting direction order and multiplicity. The
    11resulting deterministic system has an isomorphic decoding, as used in
    12the cloning and rerouting constructions of Lemma 108.
    13-/
    14
    15namespace Lax369799.DirectionReindexing
    16open RankedSystems TransitionEncoding
    17
    18structure Reindexing {P : Type} (S : System (TransitionAlphabet P) 0) where
    19 arity : S.val.Vertex → ℕ
    20 map : ∀ v, Fin (arity v) → Fin (S.val.graph.label v).1
    21 surjective : ∀ v, Function.Surjective (map v)
    22
    23def graph {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) :
    24 Presentation (TransitionAlphabet P) 0 S.val.Vertex where
    25 label := fun v => ⟨R.arity v, (S.val.graph.label v).2⟩
    26 initial := S.val.graph.initial
    27 root := ∅
    28 edge := fun v d t => ∃ i : Fin (R.arity v), d = i.val ∧ S.val.graph.edge v (R.map v i).val t
    29 direction_valid := by rintro v d t ⟨i, rfl, _⟩; exact i.isLt
    30
    31structure Realizes {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S)
    32 (T : System (TransitionAlphabet P) 0) where
    33 vertex : T.val.Vertex ≃ S.val.Vertex
    34 label : ∀ v, T.val.graph.label v = ⟨R.arity (vertex v), (S.val.graph.label (vertex v)).2⟩
    35 initial : ∀ v, T.val.graph.initial v ↔ S.val.graph.initial (vertex v)
    36 edge : ∀ v d t, T.val.graph.edge v d t ↔
    37 ∃ i : Fin (R.arity (vertex v)), d = i.val ∧
    38 S.val.graph.edge (vertex v) (R.map (vertex v) i).val (Sum.map vertex id t)
    39
    40/-- Canonical realization, retaining exactly the original vertex type. -/
    41def system {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) :
    42 System (TransitionAlphabet P) 0 := by
    43 let G := graph S R
    44 have hstep {v w : S.val.Vertex} (h : S.val.graph.Step v w) : G.Step v w := by
    45 obtain ⟨d, hd⟩ := h
    46 let i : Fin (S.val.graph.label v).1 := ⟨d, S.val.graph.direction_valid _ _ _ hd⟩
    47 obtain ⟨j, hj⟩ := R.surjective v i
    48 exact ⟨j.val, j, rfl, by simpa only [hj] using hd⟩
    49 have hreach (v : S.val.Vertex) : G.Reachable v := by
    50 obtain ⟨a, ha, hp⟩ := S.val.reachable v
    51 have hi : S.val.graph.initial a := ha.elim id (fun h => by rw [S.property.2.1] at h; exact h.elim)
    52 refine ⟨a, Or.inl hi, ?_⟩
    53 induction hp with
    54 | refl => exact .refl
    55 | @tail y z hp hyz ih => exact ih.tail (hstep hyz)
    56 let U : SetSystem (TransitionAlphabet P) 0 := ⟨S.val.size, G, hreach⟩
    57 have hdet : U.Deterministic := by
    58 refine ⟨S.property.1, rfl, ?_⟩
    59 intro v d hd
    60 let i : Fin (R.arity v) := ⟨d, hd⟩
    61 obtain ⟨t, ht, hu⟩ := S.property.2.2 v (R.map v i).val (R.map v i).isLt
    62 refine ⟨t, ⟨i, rfl, ht⟩, ?_⟩
    63 rintro t' ⟨j, hj, ht'⟩
    64 have hji : j = i := Fin.ext hj.symm
    65 subst j
    66 exact hu t' ht'
    67 exact ⟨U, hdet⟩
    68
    69/-- Its realization map is the identity on vertices. -/
    70def realizes {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) :
    71 Realizes S R (system S R) where
    72 vertex := Equiv.refl _
    73 label := fun _ => rfl
    74 initial := fun _ => Iff.rfl
    75 edge := by intro v d t; cases t <;> exact Iff.rfl
    76
    77
    78axiom zero_iff {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S)
    79 (v : S.val.Vertex) : R.arity v = 0 ↔ (S.val.graph.label v).1 = 0
    80
    81axiom realization {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) :
    82 ∃ T, Nonempty (Realizes S R T)
    83
    84axiom decode_isomorphic {P : Type} {S T : System (TransitionAlphabet P) 0}
    85 (R : Reindexing S) (h : Realizes S R T) : Isomorphic (decode T) (decode S)
    86
    87end Lax369799.DirectionReindexing
    88
    Show ProofShow ProofShow Proof
    Builds on
    Used by
    From Mathlib

    none

    Discussion

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

    Loading discussion…