Assigning labels block by block: a ranked family of injections completed to a bijection
ProvedPlasticity.SetTheory.exists_bijective_of_rank_assignmentLet , , be sets with nonempty, , , and for each labelling let be injective with , where depends only on the labels with . Suppose that for every and the set has the cardinality of . Then for some the map given by on and on is a bijection.
import Mathlib.SetTheory.Cardinal.Basic
universe u v
namespace Plasticity
theorem SetTheory.exists_bijective_of_rank_assignment {P : Type v} {T K : Type u} [Nonempty T]
(Φ : (ℕ × K → T) → P → T) (r : P → ℕ) (ρ : T → ℕ)
(hdep : ∀ y y' p, (∀ m k, m < r p → y (m, k) = y' (m, k)) → Φ y p = Φ y' p)
(hrank : ∀ y p, ρ (Φ y p) = r p)
(hinj : ∀ y, Function.Injective (Φ y))
(hcard : ∀ y n, Cardinal.mk ↥({t | ρ t = n} \ Φ y '' {p | r p = n}) = Cardinal.mk K) :
∃ y : ℕ × K → T, Function.Bijective (Sum.elim (Φ y) y) := by sorry
end PlasticityRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data: a type in a universe , and two types and in a common universe (possibly different from ), with assumed nonempty. There is a map which assigns to every function a function . There are "rank" functions and .
Hypotheses:
- (Dependence on lower ranks.) For all and : if for every and every , then . In particular, if then does not depend on at all.
- (Rank preservation.) For all and : .
- (Injectivity.) For every , the map is injective.
- (Cardinality of complements.) For every and every , the set
has cardinality exactly . This is required for every function , not only for some particular one.
Conclusion: there exists such that the map which is on and on is a bijection. Equivalently, and are both injective, their images are disjoint, and together they cover .
Edge cases:
- If is empty, hypotheses 1 to 3 are trivial and hypothesis 4 says every level set has cardinality ; the conclusion then asks for a bijection , which follows.
- If is empty, hypothesis 4 says maps onto for every and every , so is already a bijection ; the conclusion is then the statement for the unique empty .
- The hypotheses are satisfiable (for example empty, nonempty, , the first projection), so the statement is not vacuous.
- No hypothesis set appears satisfiable with a failing conclusion: a level-by-level choice of as a bijection of onto the level- complement is permitted by hypotheses 1 and 4.
- The nonemptiness of is an extra assumption; it excludes only the case empty (which with hypothesis 4 forces and empty).