Quotients by polynomial acceptance tests
Lax369799.PolynomialQuotient · concepts/Lax369799/PolynomialQuotient.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Testing all closed polynomial contexts against an accepting set defines an algebra congruence. Evaluation descends to the quotient, the quotient preserves recognition, and finite sorts remain finite.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.PolynomialContexts |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Quotients by polynomial acceptance tests |
| 6 | type: theorem |
| 7 | --- |
| 8 | Testing all closed polynomial contexts against an accepting set defines |
| 9 | an algebra congruence. Evaluation descends to the quotient, the quotient |
| 10 | preserves recognition, and finite sorts remain finite. |
| 11 | -/ |
| 12 | namespace Lax369799.PolynomialQuotient |
| 13 | open RankedSystems Algebras PolynomialContexts |
| 14 | |
| 15 | abbrev Carrier {B : RankedSet} (E : Algebra B) (F : Set (B 0)) : RankedSet := |
| 16 | fun n => Quot (@Equivalent B E F n) |
| 17 | |
| 18 | def classMap {B : RankedSet} (E : Algebra B) (F : Set (B 0)) : RankedMap B (Carrier E F) := |
| 19 | fun _ => Quot.mk _ |
| 20 | |
| 21 | def Accepting {B : RankedSet} (E : Algebra B) (F : Set (B 0)) (a : Carrier E F 0) : Prop := |
| 22 | ∃ b, classMap E F 0 b = a ∧ b ∈ F |
| 23 | |
| 24 | axiom algebra {B : RankedSet} (E : Algebra B) (F : Set (B 0)) : |
| 25 | ∃ Q : Algebra (Carrier E F), ∀ n (S : System B n), |
| 26 | Q.eval n (relabelSystem (classMap E F) S) = classMap E F n (E.eval n S) |
| 27 | |
| 28 | axiom finite_carrier {B : RankedSet} (E : Algebra B) (F : Set (B 0)) |
| 29 | (hB : RankwiseFinite B) : RankwiseFinite (Carrier E F) |
| 30 | |
| 31 | axiom accepting_class {B : RankedSet} (E : Algebra B) (F : Set (B 0)) (b : B 0) : |
| 32 | Accepting E F (classMap E F 0 b) ↔ b ∈ F |
| 33 | |
| 34 | axiom recognition {A B : RankedSet} (E : Algebra B) (F : Set (B 0)) |
| 35 | (Q : Algebra (Carrier E F)) |
| 36 | (hQ : ∀ n (S : System B n), Q.eval n (relabelSystem (classMap E F) S) = classMap E F n (E.eval n S)) |
| 37 | (η : RankedMap A B) (L : Language A) (hL : Recognizes E η F L) : |
| 38 | Recognizes Q (fun n a => classMap E F n (η n a)) (Accepting E F) L |
| 39 | |
| 40 | end Lax369799.PolynomialQuotient |
| 41 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments