AFTD Auto-Formalizing Theoretical Domains

poset_hypomorphic_card_lt_pairs_eq

theoremverifiedformalization

The number of comparable pairs is reconstructible: if finite ordered sets P and Q with |P| ≥ 3 have the same deck, they have the same number of pairs a < b. (Each such pair survives in exactly |P| − 2 of the cards, so the count is the sum over the deck divided by |P| − 2.)

Statement

theorem poset_hypomorphic_card_lt_pairs_eq (P Q : Type) [Fintype P] [Fintype Q]
    [PartialOrder P] [PartialOrder Q] [DecidableRel ((· < ·) : P → P → Prop)]
    [DecidableRel ((· < ·) : Q → Q → Prop)] (hn : 3 ≤ Fintype.card P)
    (h : poset_hypomorphic P Q) :
    (Finset.univ.filter (fun p : P × P => p.1 < p.2)).card =
      (Finset.univ.filter (fun p : Q × Q => p.1 < p.2)).card
Formalizes
The standard counting lemma of reconstruction theory, applied to comparabilities; serves the height-one reconstruction question of arXiv:2610.12690 (Reconstruction of Finite Posets of Width Three), Sec. 9. The bound |P| ≥ 3 is needed: the 2-chain and the 2-antichain have the same deck.
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • poset_hypomorphicTwo ordered sets P and Q are hypomorphic (have the same deck) when there is a bijection σ : P → Q such that for every x the…
Used by 1
  • poset_hypomorphic_isolated_iffLet finite ordered sets P, Q have |P| ≥ 3 and the same deck, witnessed by the bijection σ with P − x ≅ Q − σ(x) for all x. Then for every…

The proof, explained

The proof proceeds by double counting comparable pairs across the deck of single-element deleted subposets. In any finite poset R, each strict inequality a < b survives in exactly |R| − 2 cards (namely those excluding neither a nor b), so summing the comparable pairs over all cards yields (|R| − 2) times the total number of comparable pairs. Because P and Q are hypomorphic, each card of P is order-isomorphic to the corresponding card of Q and therefore contains the same number of comparable pairs. Since |P| = |Q| ≥ 3, the factor |P| − 2 is strictly positive, and cancelling it establishes that P and Q have the same total number of comparable pairs.

  1. The posets P and Q have equal cardinality, and their deck of deleted subposets is matched by a bijection σ : P ≃ Q.

    Unpacking the hypomorphism hypothesis yields a bijection σ : P ≃ Q such that for every x ∈ P, the single-element deleted subposet P \ {x} is order-isomorphic to Q \ {σ x}. By Fintype.card_congr, the existence of σ implies |Q| = |P|.

    lines 7–9

    uses Fintype.card_congr

      classical
      obtain ⟨σ, hσ⟩ := h
      have hcard : Fintype.card Q = Fintype.card P := (Fintype.card_congr σ).symm
  2. For any finite poset R, the sum over x ∈ R of the number of comparable pairs avoiding x equals (|R| − 2) times the total number of comparable pairs in R.

    Rewriting set cardinalities as sums of indicators and exchanging the order of summation reduces the identity to evaluating the inner sum for each pair p = (a, b). If a < b, strict inequality ensures a ≠ b, so x avoids both a and b for every element of R except a and b; erasing these two elements leaves |R| − 2 choices. If a ≮ b, the indicator is 0. Summing |R| − 2 over all comparable pairs yields the result.

    lines 10–32

    uses Finset.card_filter, Finset.sum_comm, Finset.mul_sum, Finset.sum_congr, true_and, if_true, mul_one, Finset.mem_filter, Finset.mem_univ, Finset.mem_erase, and_true, Finset.card_erase_of_mem, Finset.card_univ, Finset.mem_erase.mpr

      have sumP : ∀ (R : Type) [Fintype R] [PartialOrder R] [DecidableRel ((· < ·) : R → R → Prop)],
          ∑ x : R, (Finset.univ.filter (fun p : R × R => p.1 < p.2 ∧ p.1 ≠ x ∧ p.2 ≠ x)).card =
            (Fintype.card R - 2) * (Finset.univ.filter (fun p : R × R => p.1 < p.2)).card := by
        intro R _ _ _
        simp only [Finset.card_filter]
        rw [Finset.sum_comm, Finset.mul_sum]
        apply Finset.sum_congr rfl
        intro p _
        by_cases hp : p.1 < p.2
        · simp only [hp, true_and, if_true, mul_one]
          rw [← Finset.card_filter]
          have hfil : Finset.univ.filter (fun x => p.1 ≠ x ∧ p.2 ≠ x) =
              (Finset.univ.erase p.1).erase p.2 := by
            ext x
            simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true]
            constructor
            · rintro ⟨h1, h2⟩; exact ⟨fun h' => h2 h'.symm, fun h' => h1 h'.symm⟩
            · rintro ⟨h1, h2⟩; exact ⟨fun h' => h2 h'.symm, fun h' => h1 h'.symm⟩
          rw [hfil, Finset.card_erase_of_mem, Finset.card_erase_of_mem (Finset.mem_univ _),
            Finset.card_univ]
          · omega
          · exact Finset.mem_erase.mpr ⟨hp.ne', Finset.mem_univ _⟩
        · simp [hp]
  3. For any x ∈ R, the comparable pairs in the subposet R \ {x} correspond bijectively to pairs (a, b) in R satisfying a < b with a ≠ x and b ≠ x.

    Using Finset.card_bij, the canonical projection sending a pair of subtype elements ((a, ha), (b, hb)) to the pair of their underlying elements in R is shown to be a bijection: it maps into pairs avoiding x, is injective by Subtype.ext, and is surjective because every avoiding pair lifts to the subtype.

    lines 33–49

    uses Finset.card_bij, Finset.mem_filter, Finset.mem_univ, true_and, Prod.mk.injEq, Subtype.ext

      have subcount : ∀ (R : Type) [Fintype R] [PartialOrder R]
          [DecidableRel ((· < ·) : R → R → Prop)] (x : R),
          (Finset.univ.filter (fun p : {y : R // y ≠ x} × {y : R // y ≠ x} => p.1 < p.2)).card =
            (Finset.univ.filter (fun p : R × R => p.1 < p.2 ∧ p.1 ≠ x ∧ p.2 ≠ x)).card := by
        intro R _ _ _ x
        apply Finset.card_bij (fun p _ => ((p.1 : R), (p.2 : R)))
        · rintro ⟨a, b⟩ hab
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hab ⊢
          exact ⟨hab, a.2, b.2⟩
        · rintro ⟨a, b⟩ _ ⟨c, d⟩ _ hh
          simp only [Prod.mk.injEq] at hh
          rw [Subtype.ext hh.1, Subtype.ext hh.2]
        · rintro ⟨a, b⟩ hab
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hab
          refine ⟨(⟨a, hab.2.1⟩, ⟨b, hab.2.2⟩), ?_, rfl⟩
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          exact hab.1
  4. For each x ∈ P, the card P \ {x} has the same number of comparable pairs as the corresponding card Q \ {σ x}.

    By the hypomorphism assumption, there exists an order isomorphism e between P \ {x} and Q \ {σ x}. Mapping each comparable pair (a, b) to (e a, e b) defines a bijection via Finset.card_bij, because e is an order isomorphism and thus preserves strict inequality in both directions and is injective.

    lines 50–67

    uses Finset.card_bij, Finset.mem_filter, Finset.mem_univ, true_and, Prod.mk.injEq

      have isoc : ∀ x : P,
          (Finset.univ.filter (fun p : {y : P // y ≠ x} × {y : P // y ≠ x} => p.1 < p.2)).card =
            (Finset.univ.filter
              (fun p : {y : Q // y ≠ σ x} × {y : Q // y ≠ σ x} => p.1 < p.2)).card := by
        intro x
        obtain ⟨e⟩ := hσ x
        apply Finset.card_bij (fun p _ => (e p.1, e p.2))
        · rintro ⟨a, b⟩ hab
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hab ⊢
          exact e.lt_iff_lt.mpr hab
        · rintro ⟨a, b⟩ _ ⟨c, d⟩ _ hh
          simp only [Prod.mk.injEq] at hh
          rw [e.injective hh.1, e.injective hh.2]
        · rintro ⟨a, b⟩ hab
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hab
          refine ⟨(e.symm a, e.symm b), ?_, by simp⟩
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          exact e.symm.lt_iff_lt.mpr hab
  5. The sum over x ∈ P of the counts of comparable pairs in P \ {x} equals the corresponding sum over Q.

    Using Equiv.sum_comp, the sum over Q is reindexed via the bijection σ : P ≃ Q. By the subtype equivalence and the isomorphism between cards, the summand at each x ∈ P equals the summand at σ x in Q, so the two sums are identical by Finset.sum_congr.

    lines 68–73

    uses Equiv.sum_comp, Finset.sum_congr

      have hsum : ∑ x : P, (Finset.univ.filter (fun p : P × P => p.1 < p.2 ∧ p.1 ≠ x ∧ p.2 ≠ x)).card =
          ∑ y : Q, (Finset.univ.filter (fun p : Q × Q => p.1 < p.2 ∧ p.1 ≠ y ∧ p.2 ≠ y)).card := by
        rw [← Equiv.sum_comp σ]
        apply Finset.sum_congr rfl
        intro x _
        rw [← subcount P x, ← subcount Q (σ x), isoc x]
  6. The total number of comparable pairs in P equals the total number of comparable pairs in Q.

    Rewriting both sides of the sum equality with the double-counting formula gives (|P| − 2) * card(P's pairs) = (|P| − 2) * card(Q's pairs), since |Q| = |P|. Because |P| ≥ 3, the factor |P| − 2 is strictly positive (verified by linear arithmetic), and cancelling it via Nat.eq_of_mul_eq_mul_left concludes the proof.

    lines 74–75

    uses Nat.eq_of_mul_eq_mul_left

      rw [sumP P, sumP Q, hcard] at hsum
      exact Nat.eq_of_mul_eq_mul_left (by omega) hsum
Fintype.card_congr
A bijection between two finite types implies they have the same cardinality.
Finset.card_filter
The cardinality of a filtered finset equals the sum of indicator values of the predicate over the finset.
Finset.sum_comm
Double summation over finite sets can be interchanged.
Finset.mul_sum
Multiplication distributes over a finite sum from the left.
Finset.sum_congr
Two finite sums are equal if their domains are equal and their summands agree at every point.
true_and
Conjunction with True simplifies to the second conjunct.
if_true
An if-then-else expression whose condition is True evaluates to the then-branch.
mul_one
Multiplying by 1 leaves an element unchanged.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.mem_erase
An element belongs to s with b removed if and only if it is not equal to b and belongs to s.
and_true
Conjunction with True on the right simplifies to the first conjunct.
Finset.card_erase_of_mem
Erasing an element from a finset decreases its cardinality by 1.
Finset.card_univ
The cardinality of the universal finset equals the cardinality of the underlying finite type.
Finset.mem_erase.mpr
If an element is not equal to b and belongs to s, it belongs to s with b removed.
Finset.card_bij
A map between two finsets that is well-defined, injective, and surjective establishes that the finsets have equal cardinality.
Prod.mk.injEq
Two pairs are equal if and only if their first and second components are respectively equal.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Equiv.sum_comp
Reindexing a finite sum by an equivalence does not change the sum.
Nat.eq_of_mul_eq_mul_left
If n is strictly positive and n * m = n * k, then m = k.

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

theorem poset_hypomorphic_card_lt_pairs_eq (P Q : Type) [Fintype P] [Fintype Q]    [PartialOrder P] [PartialOrder Q] [DecidableRel ((· < ·) : P → P → Prop)]    [DecidableRel ((· < ·) : Q → Q → Prop)] (hn : 3 ≤ Fintype.card P)    (h : poset_hypomorphic P Q) :    (Finset.univ.filter (fun p : P × P => p.1 < p.2)).card =      (Finset.univ.filter (fun p : Q × Q => p.1 < p.2)).card := by  classical  obtain ⟨σ, hσ⟩ := h  have hcard : Fintype.card Q = Fintype.card P := (Fintype.card_congr σ).symm  have sumP : ∀ (R : Type) [Fintype R] [PartialOrder R] [DecidableRel ((· < ·) : R → R → Prop)],      ∑ x : R, (Finset.univ.filter (fun p : R × R => p.1 < p.2 ∧ p.1 ≠ x ∧ p.2 ≠ x)).card =        (Fintype.card R - 2) * (Finset.univ.filter (fun p : R × R => p.1 < p.2)).card := by    intro R _ _ _    simp only [Finset.card_filter]    rw [Finset.sum_comm, Finset.mul_sum]    apply Finset.sum_congr rfl    intro p _    by_cases hp : p.1 < p.2    · simp only [hp, true_and, if_true, mul_one]      rw [← Finset.card_filter]      have hfil : Finset.univ.filter (fun x => p.1 ≠ x ∧ p.2 ≠ x) =          (Finset.univ.erase p.1).erase p.2 := by        ext x        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true]        constructor        · rintro ⟨h1, h2⟩; exact ⟨fun h' => h2 h'.symm, fun h' => h1 h'.symm⟩        · rintro ⟨h1, h2⟩; exact ⟨fun h' => h2 h'.symm, fun h' => h1 h'.symm⟩      rw [hfil, Finset.card_erase_of_mem, Finset.card_erase_of_mem (Finset.mem_univ _),        Finset.card_univ]      · omega      · exact Finset.mem_erase.mpr ⟨hp.ne', Finset.mem_univ _⟩    · simp [hp]  have subcount : ∀ (R : Type) [Fintype R] [PartialOrder R]      [DecidableRel ((· < ·) : R → R → Prop)] (x : R),      (Finset.univ.filter (fun p : {y : R // y ≠ x} × {y : R // y ≠ x} => p.1 < p.2)).card =        (Finset.univ.filter (fun p : R × R => p.1 < p.2 ∧ p.1 ≠ x ∧ p.2 ≠ x)).card := by    intro R _ _ _ x    apply Finset.card_bij (fun p _ => ((p.1 : R), (p.2 : R)))    · rintro ⟨a, b⟩ hab      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hab ⊢      exact ⟨hab, a.2, b.2⟩    · rintro ⟨a, b⟩ _ ⟨c, d⟩ _ hh      simp only [Prod.mk.injEq] at hh      rw [Subtype.ext hh.1, Subtype.ext hh.2]    · rintro ⟨a, b⟩ hab      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hab      refine ⟨(⟨a, hab.2.1⟩, ⟨b, hab.2.2⟩), ?_, rfl⟩      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      exact hab.1  have isoc : ∀ x : P,      (Finset.univ.filter (fun p : {y : P // y ≠ x} × {y : P // y ≠ x} => p.1 < p.2)).card =        (Finset.univ.filter          (fun p : {y : Q // y ≠ σ x} × {y : Q // y ≠ σ x} => p.1 < p.2)).card := by    intro x    obtain ⟨e⟩ := hσ x    apply Finset.card_bij (fun p _ => (e p.1, e p.2))    · rintro ⟨a, b⟩ hab      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hab ⊢      exact e.lt_iff_lt.mpr hab    · rintro ⟨a, b⟩ _ ⟨c, d⟩ _ hh      simp only [Prod.mk.injEq] at hh      rw [e.injective hh.1, e.injective hh.2]    · rintro ⟨a, b⟩ hab      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hab      refine ⟨(e.symm a, e.symm b), ?_, by simp⟩      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      exact e.symm.lt_iff_lt.mpr hab  have hsum : ∑ x : P, (Finset.univ.filter (fun p : P × P => p.1 < p.2 ∧ p.1 ≠ x ∧ p.2 ≠ x)).card =      ∑ y : Q, (Finset.univ.filter (fun p : Q × Q => p.1 < p.2 ∧ p.1 ≠ y ∧ p.2 ≠ y)).card := by    rw [← Equiv.sum_comp σ]    apply Finset.sum_congr rfl    intro x _    rw [← subcount P x, ← subcount Q (σ x), isoc x]  rw [sumP P, sumP Q, hcard] at hsum  exact Nat.eq_of_mul_eq_mul_left (by omega) hsum
See it in the graphDiscuss this resultChallenge it