partition_lift_57_injective
For t ≥ 1, the lifting map that adds t - 1 ones to a partition of 57 is injective.
Statement
theorem partition_lift_57_injective (t : ℕ) (ht : 1 ≤ t) :
Function.Injective (partition_lift_57 t ht)- Source
- arXiv:2610.01747, Corollary 6.2 proof
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- partition_lift_57For t ≥ 1, the lifting map sends a partition p of 57 to a partition of t + 56 by adding t - 1 ones to its multiset of parts.
Read back from the Lean
For every natural number $t$ satisfying $1 \le t$, the function partition_lift_57 t ht (mapping each partition of 57 to a partition of $t + 56$ by adding $t - 1$ parts equal to 1) is injective.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the lifting map is injective, we assume two partitions of 57 produce the same lifted partition. By partition extensionality, it suffices to show that their underlying multisets of parts are equal. Since lifting acts by adding t - 1 ones to the multiset of parts, the assumption equates the two original multisets each augmented by t - 1 ones. Right cancellation in the additive monoid of multisets eliminates the added ones, completing the proof.
To prove injectivity, it suffices to show that p₁ and p₂ have the same parts: p₁.parts = p₂.parts.
Assume p₁ and p₂ are partitions of 57 whose images under partition_lift_57 are equal. By partition extensionality (Nat.Partition.ext), two partitions are equal whenever their multisets of parts are equal, reducing the goal to showing p₁.parts = p₂.parts.
uses
Nat.Partition.extintro p1 p2 h apply Nat.Partition.ext
p₁.parts + replicate (t - 1) 1 = p₂.parts + replicate (t - 1) 1
Applying the parts projection Nat.Partition.parts to both sides of the equality h via congr_arg shows that the parts of the two lifted partitions are equal. Unfolding the definition of partition_lift_57 reveals that each lifted partition's parts are formed by adding t - 1 copies of 1 to the original partition's parts.
uses
congr_arg,Nat.Partition.partshave hparts := congr_arg Nat.Partition.parts h dsimp [partition_lift_57] at hparts
p₁.parts = p₂.parts, which closes the goal.
Because multiset addition satisfies right cancellation (add_right_cancel), cancelling the common term replicate (t - 1) 1 from the right-hand side of both expressions leaves p₁.parts = p₂.parts.
uses
add_right_cancelexact add_right_cancel hparts
Nat.Partition.ext- Two partitions of the same natural number are equal if their multisets of parts are equal.
congr_arg- Equality is preserved under applying a function: if a₁ = a₂, then f a₁ = f a₂.
Nat.Partition.parts- The multiset of parts belonging to a partition.
add_right_cancel- In an additive structure with right cancellation (such as multisets under addition), a + b = c + b implies a = c.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The lifting map on partitions adding t - 1 ones is injective. -/theorem partition_lift_57_injective (t : ℕ) (ht : 1 ≤ t) : Function.Injective (partition_lift_57 t ht) := by intro p1 p2 h apply Nat.Partition.ext have hparts := congr_arg Nat.Partition.parts h dsimp [partition_lift_57] at hparts exact add_right_cancel hparts