Extending supported algebras and preserving recognition
Lax369799.SupportedCompletion · concepts/Lax369799/SupportedCompletion.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The quotient of arbitrary systems by their supported-evaluation profiles is an algebra. Evaluation chooses inner representatives and flattens; substitution congruence and the deterministic substitution laws make it well defined and associative. The construction preserves finite sorts and closed recognition. Recognizability using the fully supported systems of Definition 6 is therefore equivalent to recognizability using arbitrary deterministic presentations.
Concept map
Evidence
This concept declares 8 statements. Each proof establishes one of them relative to its assumptions.
1 algebra proven
2 eval_letters proven
3 legacy_recognizable proven
4 profile_morphism proven
5 profile_unfold proven
6 recognizable_iff proven
7 regular_completion proven
8 unary_card_bound proven
Lean source view on GitHub
| 1 | import Lax369799.SupportEvaluation |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Extending supported algebras and preserving recognition |
| 6 | type: theorem |
| 7 | --- |
| 8 | The quotient of arbitrary systems by their supported-evaluation profiles |
| 9 | is an algebra. Evaluation chooses inner representatives and flattens; |
| 10 | substitution congruence and the deterministic substitution laws make it |
| 11 | well defined and associative. The construction preserves finite sorts |
| 12 | and closed recognition. Recognizability using the fully supported systems |
| 13 | of Definition 6 is therefore equivalent to recognizability using arbitrary |
| 14 | deterministic presentations. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax369799.SupportedCompletion |
| 18 | open RankedSystems Morphisms |
| 19 | open SupportEvaluation (Carrier classMap) |
| 20 | |
| 21 | axiom algebra {B : RankedSet} (E : SupportedAlgebras.Algebra B) : |
| 22 | ∃ D : Algebras.Algebra (Carrier E), ∀ n (P : System (System B) n) (U : System B n), |
| 23 | Lax369799.Flattening.SystemFlattening P U → |
| 24 | D.eval n (relabelSystem (classMap E) P) = classMap E n U |
| 25 | |
| 26 | axiom legacy_recognizable {A : RankedSet} (L : Algebras.Language A) |
| 27 | (hL : SupportedAlgebras.Recognizable L) : Algebras.Recognizable L |
| 28 | |
| 29 | axiom recognizable_iff {A : RankedSet} (L : Algebras.Language A) : |
| 30 | SupportedAlgebras.Recognizable L ↔ Algebras.Recognizable L |
| 31 | |
| 32 | /-- Map a letter to the class of its atomic presentation. -/ |
| 33 | def letter {B : RankedSet} (E : SupportedAlgebras.Algebra B) : RankedMap B (Carrier E) := |
| 34 | fun n b => classMap E n (atomicSystem b) |
| 35 | |
| 36 | open SupportEvaluation (Equivalent) |
| 37 | |
| 38 | axiom profile_morphism {B : RankedSet} (E : SupportedAlgebras.Algebra B) |
| 39 | (hE : SupportedAlgebras.UnfoldInvariant E) {n : ℕ} (S T : System B n) |
| 40 | (f : Morphism S.val T.val) : Equivalent E S T |
| 41 | |
| 42 | axiom profile_unfold {B : RankedSet} (E : SupportedAlgebras.Algebra B) |
| 43 | (hE : SupportedAlgebras.UnfoldInvariant E) {n : ℕ} (S T : System B n) |
| 44 | (h : UnfoldEquivalent S.val T.val) : Equivalent E S T |
| 45 | |
| 46 | axiom eval_letters {B : RankedSet} (E : SupportedAlgebras.Algebra B) |
| 47 | (D : Algebras.Algebra (Carrier E)) |
| 48 | (hD : ∀ n (P : System (System B) n) (U : System B n), |
| 49 | Flattening.SystemFlattening P U → D.eval n (relabelSystem (classMap E) P) = classMap E n U) |
| 50 | {n : ℕ} (S : System B n) : |
| 51 | D.eval n (relabelSystem (letter E) S) = classMap E n S |
| 52 | |
| 53 | axiom regular_completion {B : RankedSet} (E : SupportedAlgebras.Algebra B) |
| 54 | (hE : SupportedAlgebras.UnfoldInvariant E) : |
| 55 | ∃ D : Algebras.Algebra (Carrier E), Algebras.UnfoldInvariant D ∧ |
| 56 | ∀ n (S : System B n), D.eval n (relabelSystem (letter E) S) = classMap E n S |
| 57 | |
| 58 | axiom unary_card_bound {B : RankedSet} (E : SupportedAlgebras.Algebra B) |
| 59 | (hB : RankwiseFinite B) : Nat.card (Carrier E 1) ≤ Nat.card (B 0) + Nat.card (B 1) |
| 60 | |
| 61 | end Lax369799.SupportedCompletion |
| 62 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments