Factoring out unused output variables
Lax369799.SupportCompaction · concepts/Lax369799/SupportCompaction.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Every deterministic presentation is an injective renaming of a system whose output variables all occur. Renaming a fully supported system has full support precisely when the variable map is surjective.
Concept map
Evidence
This concept declares 6 statements. Each proof establishes one of them relative to its assumptions.
1 compact_exists proven
2 compact_unique proven
3 rename_set_injective proven
4 rename_supported_iff proven
5 rename_system_injective proven
6 support_image proven
Lean source view on GitHub
| 1 | import Lax369799.SupportedSystems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Factoring out unused output variables |
| 6 | type: theorem |
| 7 | --- |
| 8 | Every deterministic presentation is an injective renaming of a system |
| 9 | whose output variables all occur. Renaming a fully supported system has |
| 10 | full support precisely when the variable map is surjective. |
| 11 | -/ |
| 12 | |
| 13 | namespace Lax369799.SupportCompaction |
| 14 | open RankedSystems Renaming Resolutions |
| 15 | |
| 16 | axiom compact_exists {A : RankedSet} {n : ℕ} (S : RankedSystems.System A n) : |
| 17 | ∃ (m : ℕ) (σ : Fin m → Fin n) (T : SupportedSystems.System A m), |
| 18 | Function.Injective σ ∧ renameSystem σ T.val = S |
| 19 | |
| 20 | axiom rename_supported_iff {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 21 | (T : SupportedSystems.System A m) : |
| 22 | SupportedSystems.FullySupported (renameSystem σ T.val) ↔ Function.Surjective σ |
| 23 | |
| 24 | axiom rename_set_injective {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 25 | (hσ : Function.Injective σ) : Function.Injective (@Resolutions.rename A m n σ) |
| 26 | |
| 27 | axiom rename_system_injective {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 28 | (hσ : Function.Injective σ) : Function.Injective (@renameSystem A m n σ) |
| 29 | |
| 30 | axiom support_image {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 31 | (T : SupportedSystems.System A m) (j : Fin n) : |
| 32 | (∃ v d, (renameSystem σ T.val).val.graph.edge v d (.inr j)) ↔ j ∈ Set.range σ |
| 33 | |
| 34 | axiom compact_unique {A : RankedSet} {m k n : ℕ} |
| 35 | (σ : Fin m → Fin n) (τ : Fin k → Fin n) |
| 36 | (hσ : Function.Injective σ) (hτ : Function.Injective τ) |
| 37 | (S : SupportedSystems.System A m) (T : SupportedSystems.System A k) |
| 38 | (h : renameSystem σ S.val = renameSystem τ T.val) : |
| 39 | ∃ e : Fin m ≃ Fin k, (∀ i, τ (e i) = σ i) ∧ renameSystem e S.val = T.val |
| 40 | |
| 41 | end Lax369799.SupportCompaction |
| 42 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments