Provable simplification of rational terms
Lax149335.ProvableSimplification · concepts/Lax149335/ProvableSimplification.lean · lax-149335
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem 7.7 (Provable simplification of rational terms). Consider rational terms , where is a finite alphabet. There is a type and a surjective rational term , such that and are equivalent to simple rational terms.
This is a strengthening of Theorem 2.9 in which the decomposition is carried out within the equational system: surjectivity of is the provable notion of Definition 5.4, and the equivalences are provable.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax149335.InjectiveSurjectiveTerms |
| 2 | import Lax149335.SimpleRationalWithinSyntax |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Provable simplification of rational terms |
| 7 | type: theorem |
| 8 | --- |
| 9 | **Theorem 7.7 (Provable simplification of rational terms).** Consider rational terms |
| 10 | , where is a finite alphabet. There is a type and a surjective |
| 11 | rational term , such that and are |
| 12 | equivalent to simple rational terms. |
| 13 | |
| 14 | This is a strengthening of Theorem 2.9 in which the decomposition is carried out within |
| 15 | the equational system: surjectivity of is the provable notion of Definition 5.4, and |
| 16 | the equivalences are provable. |
| 17 | -/ |
| 18 | |
| 19 | namespace Lax149335.ProvableSimplification |
| 20 | |
| 21 | open Lax149335.Types Lax149335.Terms Lax149335.EquationalTheory Lax149335.InjectiveSurjectiveTerms |
| 22 | Lax149335.SimpleRationalWithinSyntax |
| 23 | |
| 24 | /-- **Theorem 7.7.** Two terms `A → N*` into the |
| 25 | lists over a finite alphabet become provably equivalent to simple rational terms after |
| 26 | precomposing with a common surjective term `π : B → A`. -/ |
| 27 | axiom provable_simplification {A N : Ty} (hN : Ty.IsFinAlph N) (f g : Term A N⋆) : |
| 28 | ∃ (B : Ty) (π : Term B A), ProvablySurjective π ∧ |
| 29 | (∃ f' : Term B N⋆, IsSimple N f' ∧ (π ⨟ f) ≡ₜ f') ∧ |
| 30 | (∃ g' : Term B N⋆, IsSimple N g' ∧ (π ⨟ g) ≡ₜ g') |
| 31 | |
| 32 | end Lax149335.ProvableSimplification |
| 33 |
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments