AFTD Auto-Formalizing Theoretical Domains

partition_lift_57_injective

theoremverified

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.

  1. 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.

    lines 4–5

    uses Nat.Partition.ext

      intro p1 p2 h
      apply Nat.Partition.ext
  2. 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.

    lines 6–7

    uses congr_arg, Nat.Partition.parts

      have hparts := congr_arg Nat.Partition.parts h
      dsimp [partition_lift_57] at hparts
  3. 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.

    line 8

    uses add_right_cancel

      exact 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

/-- 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
See it in the graphDiscuss this resultChallenge it