AFTD Auto-Formalizing Theoretical Domains

poset_lt_pair_count_eq_of_order_iso

theoremverified

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.

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

    line 3

      unfold poset_lt_pair_count
  2. The 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.

    lines 4–6

    uses Nat.card_congr, Equiv.subtypeEquiv

      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))
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

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