Direction projections of extremal elements
Lax369799.DirectionProjections · concepts/Lax369799/DirectionProjections.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
In Section 5.3 the ith direction of a rank-k element is evaluated by retaining only its edge to the ith variable and renaming that variable to the single output. Extremal elements of positive rank equal the parallel family of their direction projections (Lemma 92), and each projection is itself an extremal unary element (Lemma 93).
Concept map
Evidence
This concept declares 5 statements. Each proof establishes one of them relative to its assumptions.
1 extremal_decomposition proven
2 extremal_direction proven
3 monotone proven
4 parallel_projection_bound proven
5 reconstruction_bound proven
Lean source view on GitHub
| 1 | import Lax369799.ExtendedContexts |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Direction projections of extremal elements |
| 6 | type: theorem |
| 7 | --- |
| 8 | In Section 5.3 the ith direction of a rank-k element is evaluated by |
| 9 | retaining only its edge to the ith variable and renaming that variable |
| 10 | to the single output. Extremal elements of positive rank equal the |
| 11 | parallel family of their direction projections (Lemma 92), and each |
| 12 | projection is itself an extremal unary element (Lemma 93). |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.DirectionProjections |
| 16 | open RankedSystems (RankedSet) |
| 17 | open FinitePresentations FiniteContextualOrder FiniteSyntacticAlgebra FiniteAcceptance |
| 18 | open ExpandedSyntacticAlgebra |
| 19 | |
| 20 | def projection {A : RankedSet} {k : ℕ} (a : A k) (i : Fin k) : FiniteSystem A 1 where |
| 21 | size := 1 |
| 22 | graph := { |
| 23 | label := fun _ => ⟨k, a⟩ |
| 24 | initial := Set.univ |
| 25 | root := ∅ |
| 26 | edge := fun _ d t => d = i.val ∧ t = .inr 0 |
| 27 | direction_valid := by rintro _ d t ⟨rfl, _⟩; exact i.isLt } |
| 28 | |
| 29 | def direction {A : RankedSet} (E : Algebra A) {k : ℕ} (a : A k) (i : Fin k) : A 1 := |
| 30 | E.eval 1 (projection a i) |
| 31 | |
| 32 | def parallel {A : RankedSet} {k : ℕ} (b : Fin k → A 1) : FiniteSystem A k := |
| 33 | ofSetSystem (DeterministicElements.parallel b) |
| 34 | |
| 35 | axiom monotone {A : RankedSet} (L : Algebras.Language A) |
| 36 | (E : SyntacticAlgebra L) {k : ℕ} (a b : Carrier (Accepting L) k) |
| 37 | (hab : ClassBelow (Accepting L) a b) (i : Fin k) : |
| 38 | ClassBelow (Accepting L) (direction E.algebra a i) (direction E.algebra b i) |
| 39 | |
| 40 | axiom reconstruction_bound {A : RankedSet} (L : Algebras.Language A) |
| 41 | (E : SyntacticAlgebra L) {k : ℕ} (a : Carrier (Accepting L) k) : |
| 42 | ClassBelow (Accepting L) a (E.algebra.eval k (parallel (direction E.algebra a))) |
| 43 | |
| 44 | axiom parallel_projection_bound {A : RankedSet} (L : Algebras.Language A) |
| 45 | (E : SyntacticAlgebra L) {k : ℕ} (b : Fin k → Carrier (Accepting L) 1) (i : Fin k) : |
| 46 | ClassBelow (Accepting L) (direction E.algebra (E.algebra.eval k (parallel b)) i) (b i) |
| 47 | |
| 48 | axiom extremal_decomposition {A : RankedSet} (L : Algebras.Language A) |
| 49 | (E : SyntacticAlgebra L) {k : ℕ} (hk : 1 ≤ k) (a : Carrier (Accepting L) k) |
| 50 | (ha : ExtendedContexts.ExtremalElement L E a) : |
| 51 | E.algebra.eval k (parallel (direction E.algebra a)) = a |
| 52 | |
| 53 | axiom extremal_direction {A : RankedSet} (L : Algebras.Language A) |
| 54 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 55 | (E : SyntacticAlgebra L) {k : ℕ} (a : Carrier (Accepting L) k) |
| 56 | (ha : ExtendedContexts.ExtremalElement L E a) (i : Fin k) : |
| 57 | ExtendedContexts.ExtremalElement L E (direction E.algebra a i) |
| 58 | |
| 59 | end Lax369799.DirectionProjections |
| 60 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments