AFTD Auto-Formalizing Theoretical Domains

young_lattice_rank_is_ranked_poset

theoremverified

For any m and n, the rank function young_lattice_rank makes L(m, n) into a ranked poset in the sense of is_ranked_poset.

Statement

theorem young_lattice_rank_is_ranked_poset (m n : ℕ) : is_ranked_poset (young_lattice_rank m n)
Source
arXiv:2610.24148, Section 2.7.4
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • is_ranked_posetA function rank : α → ℤ from a partially ordered type α to the integers ℤ is a ranked poset structure if it is monotone (for all a b : α,…
  • YoungLatticeThe Young lattice L(m, n) is the type of Young diagrams whose cells (i, j) satisfy i < m and j < n, ordered by inclusion.
  • young_lattice_rankThe centered rank of a Young diagram μ in L(m, n) is 2 * |cells(μ)| - m * n.
  • young_lattice_partial_orderThe Young lattice L(m, n) inherits the partial order on Young diagrams given by cell inclusion.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

Read back from the Lean

For all natural numbers $m$ and $n$, the rank function young_lattice_rank m n on the poset YoungLattice m n (Young diagrams fitting within an $m \times n$ grid) makes it a ranked poset in the sense of is_ranked_poset.

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

The proof establishes that the centered rank function young_lattice_rank m n μ = 2 * |μ.cells| - m * n satisfies the three defining axioms of is_ranked_poset on L(m, n). Monotonicity holds because the poset order is inclusion of cell sets, which preserves cardinality. For the covering property a ⋖ b, choosing a minimal cell x in the nonempty difference b \ a allows constructing an intermediate Young diagram γL = a ∪ {x}; the covering condition forces γL = b, which means b contains exactly one more cell than a and its rank increases by 2. Finally, the ranks of any two elements differ by an even integer 2(|b| - |a|), so all elements share the same rank parity modulo 2.

  1. To prove that young_lattice_rank makes L(m, n) a ranked poset, it suffices to prove monotonicity, that covering pairs increase rank by 2, and that all ranks have the same parity modulo 2.

    The definition of is_ranked_poset consists of three conjuncts: order preservation, the rank step condition rank(b) = rank(a) + 2 for covering pairs a ⋖ b, and rank(a) ≡ rank(b) [ZMOD 2]. The refine tactic splits the proof into these three independent subgoals.

    line 3

      refine ⟨?_, ?_, ?_⟩
  2. The rank function is monotonic: if a ≤ b, then young_lattice_rank m n a ≤ young_lattice_rank m n b.

    The partial order on L(m, n) is inclusion of cell sets, so a ≤ b implies a.cells ⊆ b.cells. By Finset.card_le_card, |a.cells| ≤ |b.cells|. Expanding the definition young_lattice_rank m n μ = 2 * |μ.cells| - m * n, the inequality follows by linear arithmetic.

    lines 4–9

    uses Finset.card_le_card

      · intro a b hab
        have hsub : a.1.cells ⊆ b.1.cells := hab
        have hcard : a.1.cells.card ≤ b.1.cells.card := Finset.card_le_card hsub
        have hcardZ : (a.1.cells.card : ℤ) ≤ (b.1.cells.card : ℤ) := by exact_mod_cast hcard
        simp only [young_lattice_rank]
        linarith
  3. If a ⋖ b, there is a minimal cell x in b.cells \ a.cells with respect to the coordinatewise order.

    Since a ⋖ b, we have a ≤ b and a ≠ b, so b.cells is not contained in a.cells. Thus the difference b.cells \ a.cells is nonempty by Finset.sdiff_nonempty.mpr. By Finset.exists_minimal, this finite nonempty set contains a minimal element x, which satisfies x ∈ b.cells and x ∉ a.cells by Finset.mem_sdiff.mp.

    lines 10–17

    uses Finset.sdiff_nonempty.mpr, Finset.exists_minimal, Finset.mem_sdiff.mp

      · intro a b hab
        have hab_le : a ≤ b := hab.1.le
        have hsub : a.1.cells ⊆ b.1.cells := hab_le
        have hnot_sub : ¬ b.1.cells ⊆ a.1.cells := hab.1.2
        have hne : (b.1.cells \ a.1.cells).Nonempty := Finset.sdiff_nonempty.mpr hnot_sub
        obtain ⟨x, hmin⟩ := Finset.exists_minimal hne
        have hx_b : x ∈ b.1.cells := (Finset.mem_sdiff.mp hmin.1).1
        have hx_not_a : x ∉ a.1.cells := (Finset.mem_sdiff.mp hmin.1).2
  4. Adjoining x to a.cells yields a lower set γcells in ℕ × ℕ.

    Let γcells = insert x a.cells. To verify it is a lower set, suppose u ∈ γcells and v ≤ u. If u ∈ a.cells, then v ∈ a.cells because a is a Young diagram. If u = x, then v ≤ x: either v ∈ a.cells or v ∉ a.cells. In the latter case, because b is a lower set containing x, v ∈ b.cells \ a.cells by Finset.mem_sdiff.mpr. By minimality of x in that difference, x ≤ v; by antisymmetry (le_antisymm), v = x ∈ γcells.

    lines 18–30

    uses Finset.mem_sdiff.mpr, le_antisymm

        let γcells : Finset (ℕ × ℕ) := insert x a.1.cells
        have hγlower : IsLowerSet (↑γcells : Set (ℕ × ℕ)) := by
          intro u v huv hu
          simp only [γcells, Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe] at hu ⊢
          rcases hu with hu | hu
          · rw [hu] at huv
            by_cases hv : v ∈ a.1.cells
            · exact Or.inr hv
            · have hvb : v ∈ b.1.cells := b.1.isLowerSet huv (by simpa using hx_b)
              have hvd : v ∈ b.1.cells \ a.1.cells := Finset.mem_sdiff.mpr ⟨hvb, hv⟩
              have hxle : x ≤ v := hmin.2 hvd huv
              exact Or.inl (le_antisymm huv hxle)
          · exact Or.inr (a.1.isLowerSet huv hu)
  5. The lower set γcells forms a Young diagram γ that fits in the m × n bounding box, defining an element γL ∈ L(m, n).

    We bundle γcells with the lower-set proof into a Young diagram γ. Every cell c in γ is either x or in a.cells by YoungDiagram.mem_cells and Finset.mem_insert. Since both x ∈ b and all cells of a satisfy the coordinate bounds c.1 < m and c.2 < n, all cells of γ do as well, forming an element γL of L(m, n).

    lines 31–40

    uses YoungDiagram.mem_cells, Finset.mem_insert

        let γ : YoungDiagram := ⟨γcells, hγlower⟩
        have hγbox : ∀ c ∈ γ, c.1 < m ∧ c.2 < n := by
          intro c hc
          have hc' : c ∈ γcells := (YoungDiagram.mem_cells c).mpr hc
          rw [show γcells = insert x a.1.cells from rfl, Finset.mem_insert] at hc'
          rcases hc' with hcx | hc'
          · rw [hcx]
            exact b.2 x (by simpa using hx_b)
          · exact a.2 c (by simpa using hc')
        let γL : YoungLattice m n := ⟨γ, hγbox⟩
  6. The diagram γL equals b, which implies b.cells = insert x a.cells.

    Clearly a.cells ⊆ γL.cells by Finset.mem_insert_of_mem, so a ≤ γL. Since x ∈ γL.cells by Finset.mem_insert_self but x ∉ a.cells, a ≠ γL (via congrArg), giving a < γL by lt_of_le_of_ne. Furthermore, γL ≤ b because both x ∈ b.cells and a.cells ⊆ b.cells (using Finset.mem_insert.mp). If γL ≠ b, then a < γL < b, contradicting the covering assumption a ⋖ b. Hence γL = b, and extracting the cell sets with congrArg yields b.cells = insert x a.cells.

    lines 41–65

    uses Finset.mem_insert_of_mem, Finset.mem_insert_self, congrArg, lt_of_le_of_ne, Finset.mem_insert.mp

        have hle_aγ : a ≤ γL := by
          change a.1.cells ⊆ γL.1.cells
          intro c hc
          exact Finset.mem_insert_of_mem hc
        have hne_aγ : a ≠ γL := by
          intro h
          have hxmem : x ∈ γL.1.cells := by
            change x ∈ insert x a.1.cells
            exact Finset.mem_insert_self _ _
          rw [← congrArg (fun z : YoungLattice m n => z.1.cells) h] at hxmem
          exact hx_not_a hxmem
        have hlt_aγ : a < γL := lt_of_le_of_ne hle_aγ hne_aγ
        have hle_γb : γL ≤ b := by
          change γL.1.cells ⊆ b.1.cells
          intro c hc
          change c ∈ insert x a.1.cells at hc
          rcases Finset.mem_insert.mp hc with hcx | hc
          · rw [hcx]; exact hx_b
          · exact hsub hc
        have hγb : γL = b := by
          by_contra h
          exact hab.2 hlt_aγ (lt_of_le_of_ne hle_γb h)
        have hcells : b.1.cells = insert x a.1.cells := by
          have hh := congrArg (fun z : YoungLattice m n => z.1.cells) hγb
          simpa [γL, γ, γcells] using hh.symm
  7. The rank of b is young_lattice_rank m n a + 2.

    Since b.cells = insert x a.cells with x ∉ a.cells, Finset.card_insert_of_notMem gives |b.cells| = |a.cells| + 1. Substituting into young_lattice_rank m n μ = 2 * |μ.cells| - m * n, we find rank(b) = 2(|a| + 1) - mn = (2|a| - mn) + 2 = rank(a) + 2 by linear arithmetic.

    lines 66–70

    uses Finset.card_insert_of_notMem

        have hcard : b.1.cells.card = a.1.cells.card + 1 := by
          rw [hcells, Finset.card_insert_of_notMem hx_not_a]
        have hcardZ : (b.1.cells.card : ℤ) = (a.1.cells.card : ℤ) + 1 := by exact_mod_cast hcard
        simp only [young_lattice_rank]
        linarith
  8. The ranks of any two diagrams in L(m, n) are congruent modulo 2.

    By Int.modEq_iff_dvd, rank(a) ≡ rank(b) [ZMOD 2] is equivalent to 2 dividing rank(b) - rank(a). Unfolding the definition of rank, the difference simplifies to 2 * (|b.cells| - |a.cells|), so |b.cells| - |a.cells| serves as the explicit witness of divisibility.

    lines 71–75

    uses Int.modEq_iff_dvd

      · intro a b
        rw [Int.modEq_iff_dvd]
        use ((b.1.cells.card : ℤ) - (a.1.cells.card : ℤ))
        simp only [young_lattice_rank]
        ring
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.sdiff_nonempty.mpr
If a finite set s is not a subset of t, their difference s \ t is nonempty.
Finset.exists_minimal
Every nonempty finite subset of a preordered set contains a minimal element.
Finset.mem_sdiff.mp
If an element x belongs to s \ t, then x ∈ s and x ∉ t.
Finset.mem_sdiff.mpr
If x ∈ s and x ∉ t, then x belongs to s \ t.
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
YoungDiagram.mem_cells
A coordinate belongs to a Young diagram if and only if it belongs to its underlying finite set of cells.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_insert_of_mem
If an element belongs to s, it also belongs to insert b s.
Finset.mem_insert_self
An element a is always an element of insert a s.
congrArg
Applying a function to equal inputs yields equal outputs.
lt_of_le_of_ne
In a partial order, if a ≤ b and a ≠ b, then a < b.
Finset.mem_insert.mp
If an element belongs to insert a s, then it equals a or belongs to s.
Finset.card_insert_of_notMem
Inserting an element not already in a finite set increases its cardinality by 1.
Int.modEq_iff_dvd
Two integers a and b are congruent modulo n if and only if n divides b - a.

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 centered rank function makes the Young lattice L(m, n) into a ranked poset. -/theorem young_lattice_rank_is_ranked_poset (m n : ℕ) : is_ranked_poset (young_lattice_rank m n) := by  refine ⟨?_, ?_, ?_⟩  · intro a b hab    have hsub : a.1.cells ⊆ b.1.cells := hab    have hcard : a.1.cells.card ≤ b.1.cells.card := Finset.card_le_card hsub    have hcardZ : (a.1.cells.card : ℤ) ≤ (b.1.cells.card : ℤ) := by exact_mod_cast hcard    simp only [young_lattice_rank]    linarith  · intro a b hab    have hab_le : a ≤ b := hab.1.le    have hsub : a.1.cells ⊆ b.1.cells := hab_le    have hnot_sub : ¬ b.1.cells ⊆ a.1.cells := hab.1.2    have hne : (b.1.cells \ a.1.cells).Nonempty := Finset.sdiff_nonempty.mpr hnot_sub    obtain ⟨x, hmin⟩ := Finset.exists_minimal hne    have hx_b : x ∈ b.1.cells := (Finset.mem_sdiff.mp hmin.1).1    have hx_not_a : x ∉ a.1.cells := (Finset.mem_sdiff.mp hmin.1).2    let γcells : Finset (ℕ × ℕ) := insert x a.1.cells    have hγlower : IsLowerSet (↑γcells : Set (ℕ × ℕ)) := by      intro u v huv hu      simp only [γcells, Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe] at hu ⊢      rcases hu with hu | hu      · rw [hu] at huv        by_cases hv : v ∈ a.1.cells        · exact Or.inr hv        · have hvb : v ∈ b.1.cells := b.1.isLowerSet huv (by simpa using hx_b)          have hvd : v ∈ b.1.cells \ a.1.cells := Finset.mem_sdiff.mpr ⟨hvb, hv⟩          have hxle : x ≤ v := hmin.2 hvd huv          exact Or.inl (le_antisymm huv hxle)      · exact Or.inr (a.1.isLowerSet huv hu)    let γ : YoungDiagram := ⟨γcells, hγlower⟩    have hγbox : ∀ c ∈ γ, c.1 < m ∧ c.2 < n := by      intro c hc      have hc' : c ∈ γcells := (YoungDiagram.mem_cells c).mpr hc      rw [show γcells = insert x a.1.cells from rfl, Finset.mem_insert] at hc'      rcases hc' with hcx | hc'      · rw [hcx]        exact b.2 x (by simpa using hx_b)      · exact a.2 c (by simpa using hc')    let γL : YoungLattice m n := ⟨γ, hγbox⟩    have hle_aγ : a ≤ γL := by      change a.1.cells ⊆ γL.1.cells      intro c hc      exact Finset.mem_insert_of_mem hc    have hne_aγ : a ≠ γL := by      intro h      have hxmem : x ∈ γL.1.cells := by        change x ∈ insert x a.1.cells        exact Finset.mem_insert_self _ _      rw [← congrArg (fun z : YoungLattice m n => z.1.cells) h] at hxmem      exact hx_not_a hxmem    have hlt_aγ : a < γL := lt_of_le_of_ne hle_aγ hne_aγ    have hle_γb : γL ≤ b := by      change γL.1.cells ⊆ b.1.cells      intro c hc      change c ∈ insert x a.1.cells at hc      rcases Finset.mem_insert.mp hc with hcx | hc      · rw [hcx]; exact hx_b      · exact hsub hc    have hγb : γL = b := by      by_contra h      exact hab.2 hlt_aγ (lt_of_le_of_ne hle_γb h)    have hcells : b.1.cells = insert x a.1.cells := by      have hh := congrArg (fun z : YoungLattice m n => z.1.cells) hγb      simpa [γL, γ, γcells] using hh.symm    have hcard : b.1.cells.card = a.1.cells.card + 1 := by      rw [hcells, Finset.card_insert_of_notMem hx_not_a]    have hcardZ : (b.1.cells.card : ℤ) = (a.1.cells.card : ℤ) + 1 := by exact_mod_cast hcard    simp only [young_lattice_rank]    linarith  · intro a b    rw [Int.modEq_iff_dvd]    use ((b.1.cells.card : ℤ) - (a.1.cells.card : ℤ))    simp only [young_lattice_rank]    ring
See it in the graphDiscuss this resultChallenge it