poset_hypomorphic_card_lt_pairs_eq
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.
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|.
uses
Fintype.card_congrclassical obtain ⟨σ, hσ⟩ := h have hcard : Fintype.card Q = Fintype.card P := (Fintype.card_congr σ).symm
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.
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.mprhave 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]
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.
uses
Finset.card_bij,Finset.mem_filter,Finset.mem_univ,true_and,Prod.mk.injEq,Subtype.exthave 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
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.
uses
Finset.card_bij,Finset.mem_filter,Finset.mem_univ,true_and,Prod.mk.injEqhave 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
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.
uses
Equiv.sum_comp,Finset.sum_congrhave 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]
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.
uses
Nat.eq_of_mul_eq_mul_leftrw [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.
- The definition of hypomorphic posets in this formalization explicitly provides a bijection between the elements along with order isomorphisms between corresponding deleted subposets, rather than equality of cards as an unlabelled multiset.
- To count pairs in subposets, the formal proof repeatedly moves between pairs of subtype elements and pairs in the ambient product type avoiding an element via explicit bijections.
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.
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