poset_lt_pair_count_eq_of_order_iso
Order-isomorphic ordered sets have the same number of comparable pairs.
Statement
theorem poset_lt_pair_count_eq_of_order_iso (P Q : Type) [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q] (e : P ≃o Q) : poset_lt_pair_count P = poset_lt_pair_count Q
- Source
- step towards poset_height_one_reconstructible
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- poset_lt_pair_countThe number of comparable pairs (ordered pairs a < b) of an ordered set, as a natural number.
- 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 number of strictly ordered pairs in a poset is defined as the cardinality of the subtype of pairs (x, y) with x < y. An order isomorphism e : P ≃o Q induces a bijection on the product types P × P ≃ Q × Q that preserves and reflects the strict ordering. Restricting this bijection gives an equivalence between the subtypes of comparable pairs, so their cardinalities are equal.
The goal reduces to showing that the subtypes of strictly ordered pairs in P × P and in Q × Q have the same cardinality.
Unfolding the definition of `poset_lt_pair_count` replaces both sides with the cardinality of the subtype of pairs (x, y) satisfying x < y.
unfold poset_lt_pair_countThe order isomorphism induces an equivalence between the subtypes of strictly ordered pairs, so their cardinalities are equal.
The order isomorphism e : P ≃o Q induces a product bijection (e, e) : P × P ≃ Q × Q. Because an order isomorphism preserves and reflects the strict ordering (a.1 < a.2 ↔ e a.1 < e a.2), this bijection restricts to an equivalence between the subtypes of strictly ordered pairs via `Equiv.subtypeEquiv`. Finally, `Nat.card_congr` concludes that these equivalent subtypes have the same cardinality.
uses
Nat.card_congr,Equiv.subtypeEquivexact Nat.card_congr (Equiv.subtypeEquiv (e.toEquiv.prodCongr e.toEquiv) (fun a => by show a.1 < a.2 ↔ e a.1 < e a.2 exact e.lt_iff_lt.symm))
Nat.card_congr- If two types are in bijection (equivalent), then their cardinalities as natural numbers are equal.
Equiv.subtypeEquiv- Given an equivalence between two types and a predicate on each that is preserved across the equivalence, the corresponding subtypes are equivalent.
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.
/-- `poset_lt_pair_count` is an invariant of order isomorphism. -/theorem poset_lt_pair_count_eq_of_order_iso (P Q : Type) [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q] (e : P ≃o Q) : poset_lt_pair_count P = poset_lt_pair_count Q := by unfold poset_lt_pair_count exact Nat.card_congr (Equiv.subtypeEquiv (e.toEquiv.prodCongr e.toEquiv) (fun a => by show a.1 < a.2 ↔ e a.1 < e a.2 exact e.lt_iff_lt.symm))