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

Extremal unary data for finite presentations

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

    Unary values, the planted hole mark, and its loop directions form a finite space when the unary quotient sort is finite. Choose an accepting datum minimal below a given datum, with boundary inclusions reversed.

    Concept map
    20 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.FiniteNormalForms
    2
    3/-!
    4---
    5title: Extremal unary data for finite presentations
    6type: theorem
    7---
    8Unary values, the planted hole mark, and its loop directions form a finite
    9space when the unary quotient sort is finite. Choose an accepting datum
    10minimal below a given datum, with boundary inclusions reversed.
    11-/
    12namespace Lax369799.FiniteExtremal
    13open RankedSystems (RankedSet)
    14open FinitePresentations FiniteContexts FiniteContextualOrder FiniteSyntacticAlgebra
    15open ExtremalContexts (Data)
    16open FiniteNormalForms (normalContext)
    17
    18def DataBelow {A : RankedSet} (F : ClosedProperty A) {k : ℕ}
    19 (x y : Data (Carrier F) k) : Prop :=
    20 (y.1.root → x.1.root) ∧ y.1.loops ⊆ x.1.loops ∧ ∀ i, ClassBelow F (x.2 i) (y.2 i)
    21
    22noncomputable def value {A : RankedSet} {F : ClosedProperty A} (E : Algebra (Carrier F)) {k : ℕ}
    23 (a : Carrier F k) (x : Data (Carrier F) k) : Carrier F 0 :=
    24 E.eval 0 (plug (normalContext x.1 x.2) (atomic a))
    25
    26def Accepts {A : RankedSet} (F : ClosedProperty A) (E : Algebra (Carrier F)) {k : ℕ}
    27 (a : Carrier F k) (x : Data (Carrier F) k) : Prop := AcceptingClass F (value E a x)
    28
    29def IsExtremal {A : RankedSet} (F : ClosedProperty A) (E : Algebra (Carrier F)) {k : ℕ}
    30 (a : Carrier F k) (x : Data (Carrier F) k) : Prop :=
    31 Accepts F E a x ∧ ∀ y, DataBelow F y x → Accepts F E a y → DataBelow F x y
    32
    33axiom extremal_choice {A : RankedSet} (F : ClosedProperty A) (E : Algebra (Carrier F))
    34 (hfinite : Finite (Carrier F 1)) {k : ℕ} (a : Carrier F k) (x : Data (Carrier F) k)
    35 (hx : Accepts F E a x) :
    36 ∃ y : Data (Carrier F) k, DataBelow F y x ∧ Accepts F E a y ∧
    37 ∀ z : Data (Carrier F) k, DataBelow F z y → Accepts F E a z → DataBelow F y z
    38
    39axiom data_monotone {A : RankedSet} (L : Algebras.Language A)
    40 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    41 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    42 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    43 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    44 {k : ℕ} (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    45 (h : DataBelow (FiniteAcceptance.Accepting L) x y) (a : Carrier (FiniteAcceptance.Accepting L) k) :
    46 ClassBelow (FiniteAcceptance.Accepting L) (value E a x) (value E a y)
    47
    48def Deterministic {A : RankedSet} (E : Algebra A) {n : ℕ} (a : A n) : Prop :=
    49 ∃ S : FiniteSystem A n, (∀ v, (S.graph.label v).1 ≤ 1) ∧ E.eval n S = a
    50
    51def deltaPattern {A : RankedSet} {k : ℕ} (B : ExtremalContexts.Boundary k)
    52 (m : Fin (k + 1) → A 1) (a : A k) : FiniteSystem (FiniteSystem A) k :=
    53 relabel (fun _ => ofSetSystem) (ofSetSystem (ExtremalContexts.deltaPattern B m a))
    54
    55noncomputable def delta {A : RankedSet} {k : ℕ} (B : ExtremalContexts.Boundary k)
    56 (m : Fin (k + 1) → A 1) (a : A k) : FiniteSystem A k := flatten (deltaPattern B m a)
    57
    58axiom delta_deterministic {A : RankedSet} (E : Algebra A) {k : ℕ}
    59 (B : ExtremalContexts.Boundary k) (m : Fin (k + 1) → A 1) (a : A k) :
    60 Deterministic E (E.eval k (delta B m a))
    61
    62axiom delta_in_context {A : RankedSet} (L : Algebras.Language A)
    63 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    64 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    65 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    66 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    67 {k : ℕ} (x : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    68 (a : Carrier (FiniteAcceptance.Accepting L) k) :
    69 ClassBelow (FiniteAcceptance.Accepting L) (value E a x)
    70 (value E (E.eval k (delta x.1 x.2 a)) x)
    71
    72axiom delta_boundary_comparison {A : RankedSet} (L : Algebras.Language A)
    73 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    74 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    75 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    76 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    77 {k : ℕ} (hk : 1 ≤ k) (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    78 (a : Carrier (FiniteAcceptance.Accepting L) k)
    79 (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x)
    80 (hy : Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y) :
    81 (y.1.root → x.1.root) ∧ y.1.loops ⊆ x.1.loops
    82
    83axiom delta_piece_comparison {A : RankedSet} (L : Algebras.Language A)
    84 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    85 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    86 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    87 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    88 {k : ℕ} (hk : 1 ≤ k) (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    89 (a : Carrier (FiniteAcceptance.Accepting L) k)
    90 (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x)
    91 (hy : Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y) :
    92 ∀ j, ClassBelow (FiniteAcceptance.Accepting L) (x.2 j) (y.2 j)
    93
    94axiom delta_below {A : RankedSet} (L : Algebras.Language A)
    95 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    96 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    97 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    98 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    99 {k : ℕ} (hk : 2 ≤ k) (x : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    100 (a : Carrier (FiniteAcceptance.Accepting L) k)
    101 (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) :
    102 ClassBelow (FiniteAcceptance.Accepting L) (E.eval k (delta x.1 x.2 a)) a
    103
    104end Lax369799.FiniteExtremal
    105
    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…