While this submission is a draft, it cannot be used by other submissions.

Provable simplification of rational terms

Lax149335.ProvableSimplification · concepts/Lax149335/ProvableSimplification.lean · lax-149335

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Theorem 7.7 (Provable simplification of rational terms). Consider rational terms f,g:A→N∗f, g : A \to N^*, where NN is a finite alphabet. There is a type BB and a surjective rational term π:B→A\pi : B \to A, such that π;f\pi \mathbin{;} f and π;g\pi \mathbin{;} g 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 π\pi is the provable notion of Definition 5.4, and the equivalences are provable.

    Concept map
    7 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax149335.InjectiveSurjectiveTerms
    2import Lax149335.SimpleRationalWithinSyntax
    3
    4/-!
    5---
    6title: Provable simplification of rational terms
    7type: theorem
    8---
    9**Theorem 7.7 (Provable simplification of rational terms).** Consider rational terms
    10f,g:A→N∗f, g : A \to N^*, where NN is a finite alphabet. There is a type BB and a surjective
    11rational term π:B→A\pi : B \to A, such that π;f\pi \mathbin{;} f and π;g\pi \mathbin{;} g are
    12equivalent to simple rational terms.
    13
    14This is a strengthening of Theorem 2.9 in which the decomposition is carried out within
    15the equational system: surjectivity of π\pi is the provable notion of Definition 5.4, and
    16the equivalences are provable.
    17-/
    18
    19namespace Lax149335.ProvableSimplification
    20
    21open Lax149335.Types Lax149335.Terms Lax149335.EquationalTheory Lax149335.InjectiveSurjectiveTerms
    22 Lax149335.SimpleRationalWithinSyntax
    23
    24/-- **Theorem 7.7.** Two terms `A → N*` into the
    25lists over a finite alphabet become provably equivalent to simple rational terms after
    26precomposing with a common surjective term `π : B → A`. -/
    27axiom 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
    32end Lax149335.ProvableSimplification
    33
    Show Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…