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

Planted normal contexts and deterministic witnesses

Lax369799.ExtremalContexts · concepts/Lax369799/ExtremalContexts.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

    Definition

    A planted normal context records the hole's root mark and self-loop directions, together with its unary pieces. Planting merges the original initial and root marks. The unary components of the witness construction retain these loops; its outer presentation retains the root mark. This extends the construction of Section 5 to ordinary holes with arbitrary boundary data. The extremal choice and comparison inequalities require separate proofs.

    Concept map
    8 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.AutomatonProperty
    2
    3/-!
    4---
    5title: Planted normal contexts and deterministic witnesses
    6type: definition
    7---
    8A planted normal context records the hole's root mark and self-loop
    9directions, together with its unary pieces. Planting merges the original
    10initial and root marks. The unary components of the witness construction
    11retain these loops; its outer presentation retains the root mark. This
    12extends the construction of Section 5 to ordinary holes with arbitrary
    13boundary data. The extremal choice and comparison inequalities require
    14separate proofs.
    15-/
    16
    17namespace Lax369799.ExtremalContexts
    18open RankedSystems Flattening SetAlgebras AutomatonProperty
    19
    20structure Boundary (k : ℕ) where
    21 root : Prop
    22 loops : Set (Fin k)
    23
    24/-- The root piece has index zero; direction i uses piece i+1. -/
    25def normalPresentation {A : RankedSet} {k : ℕ} (B : Boundary k)
    26 (m : Fin (k + 1) → A 1) : Presentation (WithHole A k) 0 (Fin (k + 2)) where
    27 label := Fin.cases ⟨k, Sum.inr ⟨rfl⟩⟩ (fun i => ⟨1, Sum.inl (m i)⟩)
    28 initial := ∅
    29 root := fun v => v = (0 : Fin (k + 1)).succ ∨ (v = 0 ∧ B.root)
    30 edge := fun v d t => Fin.cases
    31 ((∃ i : Fin k, d = i.val ∧ t = .inl i.succ.succ) ∨
    32 (∃ i : Fin k, i ∈ B.loops ∧ d = i.val ∧ t = .inl 0))
    33 (fun _ => d = 0 ∧ t = .inl 0) v
    34 direction_valid := by
    35 intro v d t
    36 refine Fin.cases ?_ (fun i => ?_) v
    37 · rintro (⟨i, rfl, _⟩ | ⟨i, _, rfl, _⟩) <;> exact i.isLt
    38 · rintro ⟨rfl, _⟩; exact Nat.zero_lt_one
    39
    40def normalSystem {A : RankedSet} {k : ℕ} (B : Boundary k)
    41 (m : Fin (k + 1) → A 1) : SetSystem (WithHole A k) 0 where
    42 size := k + 2
    43 graph := normalPresentation B m
    44 reachable := by
    45 let G := normalPresentation B m
    46 have h1 : G.Reachable (0 : Fin (k + 1)).succ :=
    47 ⟨_, Or.inr (Or.inl rfl), .refl⟩
    48 have h0 : G.Reachable 0 := by
    49 obtain ⟨r, hr, hp⟩ := h1
    50 exact ⟨r, hr, hp.tail ⟨0, rfl, rfl⟩⟩
    51 intro v
    52 refine Fin.cases h0 (fun i => ?_) v
    53 refine Fin.cases h1 (fun j => ?_) i
    54 obtain ⟨r, hr, hp⟩ := h0
    55 exact ⟨r, hr, hp.tail ⟨j.val, Or.inl ⟨j, rfl, rfl⟩⟩⟩
    56
    57def normalContext {A : RankedSet} {k : ℕ} (B : Boundary k)
    58 (m : Fin (k + 1) → A 1) : SetContext A k 0 where
    59 system := normalSystem B m
    60 one_hole := by
    61 change ∃! v : Fin (k + 2), IsHole ((normalPresentation B m).label v)
    62 refine ⟨0, ⟨⟨rfl⟩, rfl⟩, ?_⟩
    63 intro v
    64 refine Fin.cases (fun _ => rfl) (fun i h => ?_) v
    65 obtain ⟨h, he⟩ := h
    66 cases he
    67
    68/-- Unary component U_i, with the retained loop directions at its a-vertex. -/
    69def component {A : RankedSet} {k : ℕ} (B : Boundary k)
    70 (m : Fin (k + 1) → A 1) (a : A k) (i : Fin k) : SetSystem A 1 where
    71 size := k + 1
    72 graph := {
    73 label := Fin.cases ⟨k, a⟩ (fun j => ⟨1, m j.succ⟩)
    74 initial := {0}
    75 root := ∅
    76 edge := fun v d t => Fin.cases
    77 ((∃ j : Fin k, d = j.val ∧ t = .inl j.succ) ∨
    78 (∃ j : Fin k, j ∈ B.loops ∧ d = j.val ∧ t = .inl 0) ∨
    79 (d = i.val ∧ t = .inr 0))
    80 (fun _ => d = 0 ∧ t = .inl 0) v
    81 direction_valid := by
    82 intro v d t
    83 refine Fin.cases ?_ (fun j => ?_) v
    84 · rintro (⟨j, rfl, _⟩ | ⟨j, _, rfl, _⟩ | ⟨rfl, _⟩)
    85 · exact j.isLt
    86 · exact j.isLt
    87 · exact i.isLt
    88 · rintro ⟨rfl, _⟩; exact Nat.zero_lt_one }
    89 reachable := by
    90 intro v
    91 refine ⟨0, Or.inl rfl, ?_⟩
    92 refine Fin.cases Relation.ReflTransGen.refl (fun j => ?_) v
    93 exact Relation.ReflTransGen.refl.tail ⟨j.val, Or.inl ⟨j, rfl, rfl⟩⟩
    94
    95/-- The outer presentation uses only unary labels. -/
    96def deltaPattern {A : RankedSet} {k : ℕ} (B : Boundary k)
    97 (m : Fin (k + 1) → A 1) (a : A k) : SetSystem (SetSystem A) k where
    98 size := k + 1
    99 graph := {
    100 label := Fin.cases ⟨1, atomic (m 0)⟩ (fun i => ⟨1, component B m a i⟩)
    101 initial := fun v => v ≠ 0
    102 root := fun v => v = 0 ∨ B.root
    103 edge := fun v d t => d = 0 ∧ Fin.cases
    104 (∃ i : Fin k, t = .inl i.succ)
    105 (fun i => t = .inr i) v
    106 direction_valid := by
    107 rintro v d t ⟨rfl, _⟩
    108 refine Fin.cases Nat.zero_lt_one (fun _ => Nat.zero_lt_one) v }
    109 reachable := by
    110 intro v
    111 refine ⟨v, ?_, .refl⟩
    112 refine Fin.cases (Or.inr (Or.inl rfl)) (fun i => Or.inl (Fin.succ_ne_zero i)) v
    113
    114noncomputable def delta {A : RankedSet} {k : ℕ} (B : Boundary k)
    115 (m : Fin (k + 1) → A 1) (a : A k) : SetSystem A k :=
    116 flatten (deltaPattern B m a)
    117
    118axiom delta_deterministic {A : RankedSet} (E : SetAlgebra A) {k : ℕ}
    119 (B : Boundary k) (m : Fin (k + 1) → A 1) (a : A k) :
    120 Deterministic E (E.eval k (delta B m a))
    121
    122abbrev Data (A : RankedSet) (k : ℕ) := Boundary k × (Fin (k + 1) → A 1)
    123
    124/-- Smaller data have more boundary marks and smaller unary values. -/
    125def DataBelow {A : RankedSet} (E : SetAlgebra A) {k : ℕ} (x y : Data A k) : Prop :=
    126 (y.1.root → x.1.root) ∧ y.1.loops ⊆ x.1.loops ∧ ∀ i, Below E (x.2 i) (y.2 i)
    127
    128noncomputable def value {A : RankedSet} (E : SetAlgebra A) {k : ℕ}
    129 (a : A k) (x : Data A k) : A 0 :=
    130 E.eval 0 (plug (normalContext x.1 x.2) (atomic a))
    131
    132def Accepts {A : RankedSet} (E : SetAlgebra A) (f : A 0) {k : ℕ}
    133 (a : A k) (x : Data A k) : Prop := Below E f (value E a x)
    134
    135def IsExtremal {A : RankedSet} (E : SetAlgebra A) (f : A 0) {k : ℕ}
    136 (a : A k) (x : Data A k) : Prop :=
    137 Accepts E f a x ∧ ∀ y, DataBelow E y x → Accepts E f a y → DataBelow E x y
    138
    139/-- Finite minimization over boundary data as well as the unary pieces. -/
    140axiom extremal_choice {A : RankedSet} (E : SetAlgebra A) (hA : RankwiseFinite A)
    141 (f : A 0) {k : ℕ} (a : A k) (x : Data A k) (hx : Accepts E f a x) :
    142 ∃ y : Data A k, DataBelow E y x ∧ Accepts E f a y ∧
    143 ∀ z : Data A k, DataBelow E z y → Accepts E f a z → DataBelow E y z
    144
    145axiom data_monotone {A : RankedSet} (E : SetAlgebra A) {k : ℕ}
    146 (x y : Data A k) (h : DataBelow E x y) (a : A k) :
    147 Below E (E.eval 0 (plug (normalContext x.1 x.2) (atomic a)))
    148 (E.eval 0 (plug (normalContext y.1 y.2) (atomic a)))
    149
    150axiom delta_in_context {A : RankedSet} (E : SetAlgebra A) {k : ℕ}
    151 (x : Data A k) (a : A k) :
    152 Below E (value E a x) (value E (E.eval k (delta x.1 x.2 a)) x)
    153
    154axiom delta_boundary_comparison {A : RankedSet} (E : SetAlgebra A) (f : A 0)
    155 {k : ℕ} (hk : 1 ≤ k) (x y : Data A k) (a : A k)
    156 (hx : IsExtremal E f a x) (hy : Accepts E f (E.eval k (delta x.1 x.2 a)) y) :
    157 (y.1.root → x.1.root) ∧ y.1.loops ⊆ x.1.loops
    158
    159axiom delta_piece_comparison {A : RankedSet} (E : SetAlgebra A) (f : A 0)
    160 {k : ℕ} (hk : 1 ≤ k) (x y : Data A k) (a : A k)
    161 (hx : IsExtremal E f a x) (hy : Accepts E f (E.eval k (delta x.1 x.2 a)) y) :
    162 ∀ j, Below E (x.2 j) (y.2 j)
    163
    164axiom delta_below {A : RankedSet} (E : SetAlgebra A) (f : A 0)
    165 (hp : PlantInvariant E f) (hs : OrderSeparating E f) {k : ℕ} (hk : 2 ≤ k)
    166 (x : Data A k) (a : A k) (hx : IsExtremal E f a x) :
    167 Below E (E.eval k (delta x.1 x.2 a)) a
    168
    169end Lax369799.ExtremalContexts
    170
    Show ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…