The unary semigroup and its action
Lax369799.UnaryComposition · concepts/Lax369799/UnaryComposition.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Unary values compose by evaluating a two-vertex chain. Associativity of the algebra makes this composition associative, and the same operation acts on every sort. This supplies the finite semigroup used to factor infinite unary branch words in Section 6.3.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteBranchWords |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The unary semigroup and its action |
| 6 | type: theorem |
| 7 | --- |
| 8 | Unary values compose by evaluating a two-vertex chain. Associativity of |
| 9 | the algebra makes this composition associative, and the same operation |
| 10 | acts on every sort. This supplies the finite semigroup used to factor |
| 11 | infinite unary branch words in Section 6.3. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.UnaryComposition |
| 15 | open RankedSystems (RankedSet) |
| 16 | open FinitePresentations FiniteSyntacticAlgebra |
| 17 | |
| 18 | def application {A : RankedSet} {n : ℕ} (b : A 1) (a : A n) : FiniteSystem A n where |
| 19 | size := 2 |
| 20 | graph := { |
| 21 | label := Fin.cases ⟨1, b⟩ (fun _ => ⟨n, a⟩) |
| 22 | initial := {0} |
| 23 | root := ∅ |
| 24 | edge := fun v d t => |
| 25 | (v = 0 ∧ d = 0 ∧ t = .inl 1) ∨ |
| 26 | (v = 1 ∧ ∃ j : Fin n, d = j.val ∧ t = .inr j) |
| 27 | direction_valid := by |
| 28 | rintro v d t (⟨rfl, rfl, _⟩ | ⟨rfl, j, rfl, _⟩) |
| 29 | · exact Nat.zero_lt_one |
| 30 | · exact j.isLt } |
| 31 | |
| 32 | def act {A : RankedSet} (E : Algebra A) {n : ℕ} (b : A 1) (a : A n) : A n := |
| 33 | E.eval n (application b a) |
| 34 | |
| 35 | def product {A : RankedSet} (E : Algebra A) (a b : A 1) : A 1 := act E a b |
| 36 | |
| 37 | axiom action_law {A : RankedSet} (E : Algebra A) {n : ℕ} |
| 38 | (a b : A 1) (c : A n) : act E (product E a b) c = act E a (act E b c) |
| 39 | |
| 40 | axiom associative {A : RankedSet} (E : Algebra A) (a b c : A 1) : |
| 41 | product E (product E a b) c = product E a (product E b c) |
| 42 | |
| 43 | axiom nullary_action {A : RankedSet} (E : Algebra A) (b : A 1) (a : A 0) : |
| 44 | act E b a = FiniteBranchWords.act E b a |
| 45 | |
| 46 | end Lax369799.UnaryComposition |
| 47 |
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