Small profiles of finite presentations
Lax369799.FiniteProfiles · concepts/Lax369799/FiniteProfiles.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Initial and root profiles observe the reachable restriction of a finite presentation. Their small versions range over a finite set when every sort of the observing algebra is finite. Every contextual class also has a reachable representative.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteMorphisms |
| 2 | import Lax369799.SyntacticAlgebraTheorems |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Small profiles of finite presentations |
| 7 | type: theorem |
| 8 | --- |
| 9 | Initial and root profiles observe the reachable restriction of a finite |
| 10 | presentation. Their small versions range over a finite set when every |
| 11 | sort of the observing algebra is finite. Every contextual class also has |
| 12 | a reachable representative. |
| 13 | -/ |
| 14 | namespace Lax369799.FiniteProfiles |
| 15 | open RankedSystems (RankedSet RankwiseFinite) |
| 16 | open FinitePresentations FiniteContextualOrder FiniteAcceptance |
| 17 | |
| 18 | def SmallProfileEquivalent {A B : RankedSet} |
| 19 | (ρ : ∀ n, RankedSystems.System A n → B n) {n : ℕ} (S T : FiniteSystem A n) : Prop := |
| 20 | Resolutions.SmallProfileEquivalent ρ (RankedSystems.trim S.graph) (RankedSystems.trim T.graph) |
| 21 | |
| 22 | axiom small_profile_finite {A B : RankedSet} (hB : RankwiseFinite B) |
| 23 | (ρ : ∀ n, RankedSystems.System A n → B n) (n : ℕ) : |
| 24 | Finite (Quot (@SmallProfileEquivalent A B ρ n)) |
| 25 | |
| 26 | /-- A bound independent of the algebra permits an additional identity continuation. -/ |
| 27 | def BoundedProfile {A B : RankedSet} (bound : ℕ) |
| 28 | (ρ : ∀ n, RankedSystems.System A n → B n) {n : ℕ} |
| 29 | (S : RankedSystems.SetSystem A n) : Set (Resolutions.ProfileEntry B n) := |
| 30 | {e | e ∈ Resolutions.Profile ρ S ∧ ∀ j, Nat.card {i // e.2.2 i = j} ≤ bound} |
| 31 | |
| 32 | def BoundedProfileEquivalent {A B : RankedSet} (bound : ℕ) |
| 33 | (ρ : ∀ n, RankedSystems.System A n → B n) {n : ℕ} (S T : FiniteSystem A n) : Prop := |
| 34 | BoundedProfile bound ρ (RankedSystems.trim S.graph) = |
| 35 | BoundedProfile bound ρ (RankedSystems.trim T.graph) ∧ |
| 36 | BoundedProfile bound ρ (RankedSystems.uproot (RankedSystems.trim S.graph)) = |
| 37 | BoundedProfile bound ρ (RankedSystems.uproot (RankedSystems.trim T.graph)) |
| 38 | |
| 39 | axiom bounded_profile_finite {A B : RankedSet} (hB : RankwiseFinite B) (bound : ℕ) |
| 40 | (ρ : ∀ n, RankedSystems.System A n → B n) (n : ℕ) : |
| 41 | Finite (Quot (@BoundedProfileEquivalent A B bound ρ n)) |
| 42 | |
| 43 | axiom reachable_representative {A : RankedSet} (L : Algebras.Language A) {n : ℕ} |
| 44 | (a : Carrier (Accepting L) n) : |
| 45 | ∃ S : RankedSystems.SetSystem A n, quotientMap (Accepting L) n (ofSetSystem S) = a |
| 46 | |
| 47 | end Lax369799.FiniteProfiles |
| 48 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments