AFTD Auto-Formalizing Theoretical Domains

poset_hypomorphic_isolated_iff

theoremverified

Let 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 x ∈ P, x is incomparable with everything in P if and only if σ(x) is incomparable with everything in Q. In particular the isolated points of P correspond exactly to those of Q.

Statement

theorem poset_hypomorphic_isolated_iff (P Q : Type) [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q] (hn : 3 ≤ Fintype.card P) (σ : P ≃ Q) (hσ : ∀ x : P, Nonempty ({y : P // y ≠ x} ≃o {y : Q // y ≠ σ x})) (x : P) : (∀ y : P, ¬ (x < y ∨ y < x)) ↔ (∀ z : Q, ¬ (σ x < z ∨ z < σ x))
Source
step towards poset_height_one_reconstructible
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

An element in a finite poset is isolated (incomparable with all other elements) if and only if removing it leaves the total number of strictly ordered pairs unchanged. Since P and Q have size at least 3 and share the same deck of single-element deletions, Kelly's lemma for posets implies they have the same total number of strictly ordered pairs. Furthermore, the deletion subposets P ∖ {x} and Q ∖ {σ(x)} are order-isomorphic by hypothesis, so they have the same number of strictly ordered pairs as well. Matching these equalities proves that x is isolated in P if and only if σ(x) is isolated in Q.

  1. P and Q have the same total number of strictly ordered pairs: `poset_lt_pair_count P = poset_lt_pair_count Q`.

    Enabling classical logic so that relations are decidable, we unfold `poset_lt_pair_count` on P and Q into the cardinality of the filtered Finset of pairs (p₁, p₂) with p₁ < p₂ using `Nat.card_eq_fintype_card` and `Fintype.card_subtype`. Since |P| ≥ 3 and P, Q have the same deck witnessed by σ, `poset_hypomorphic_card_lt_pairs_eq` guarantees that these counts are equal.

    lines 3–12

    uses Nat.card_eq_fintype_card, Fintype.card_subtype, poset_hypomorphic_card_lt_pairs_eq

      classical
      have h_count_PQ : poset_lt_pair_count P = poset_lt_pair_count Q := by
        have hP : poset_lt_pair_count P = (Finset.univ.filter (fun p : P × P => p.1 < p.2)).card := by
          unfold poset_lt_pair_count
          rw [Nat.card_eq_fintype_card, Fintype.card_subtype]
        have hQ : poset_lt_pair_count Q = (Finset.univ.filter (fun p : Q × Q => p.1 < p.2)).card := by
          unfold poset_lt_pair_count
          rw [Nat.card_eq_fintype_card, Fintype.card_subtype]
        rw [hP, hQ]
        exact poset_hypomorphic_card_lt_pairs_eq P Q hn ⟨σ, hσ⟩
  2. The deleted subposets P ∖ {x} and Q ∖ {σ(x)} have the same number of strictly ordered pairs: `poset_lt_pair_count {y : P // y ≠ x} = poset_lt_pair_count {y : Q // y ≠ σ x}`.

    By the deck hypothesis `hσ x`, there exists an order isomorphism between the subposets obtained by deleting x from P and σ(x) from Q. Applying `poset_lt_pair_count_eq_of_order_iso`, order-isomorphic posets have identical counts of strictly ordered pairs.

    lines 13–15

    uses poset_lt_pair_count_eq_of_order_iso

      have h_iso_count : poset_lt_pair_count {y : P // y ≠ x} = poset_lt_pair_count {y : Q // y ≠ σ x} := by
        obtain ⟨e⟩ := hσ x
        exact poset_lt_pair_count_eq_of_order_iso _ _ e
  3. An element x ∈ P is isolated if and only if σ(x) ∈ Q is isolated.

    By `poset_delete_isolated_lt_pair_count_iff`, an element is isolated (incomparable with every other element) if and only if deleting it preserves the total number of strictly ordered pairs. Applying this equivalence to x in P and σ(x) in Q transforms the goal into `poset_lt_pair_count (P ∖ {x}) = poset_lt_pair_count P ↔ poset_lt_pair_count (Q ∖ {σ(x)}) = poset_lt_pair_count Q`. Rewriting with the equalities established in the previous steps (`h_iso_count` and `h_count_PQ`) makes both sides identical, closing the goal.

    lines 16–18

    uses poset_delete_isolated_lt_pair_count_iff

      rw [← poset_delete_isolated_lt_pair_count_iff P x]
      rw [← poset_delete_isolated_lt_pair_count_iff Q (σ x)]
      rw [h_iso_count, h_count_PQ]
Nat.card_eq_fintype_card
For a finite type α, its cardinality as a natural number (`Nat.card`) equals its Fintype cardinality (`Fintype.card`).
Fintype.card_subtype
The cardinality of a subtype `{ x // p x }` equals the cardinality of the filtered finset `{x | p x}` of elements satisfying p.
poset_hypomorphic_card_lt_pairs_eq
If two finite posets P and Q with at least 3 elements have the same deck (are hypomorphic), then they have the same number of strictly ordered pairs (a, b) with a < b.
poset_lt_pair_count_eq_of_order_iso
An order isomorphism between two finite posets preserves the count of strictly ordered pairs.
poset_delete_isolated_lt_pair_count_iff
In a finite poset, deleting an element x preserves the count of strictly ordered pairs if and only if x is isolated (incomparable with every element).

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

/-- A deck bijection carries isolated points to isolated points (both directions). -/theorem poset_hypomorphic_isolated_iff (P Q : Type) [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q] (hn : 3 ≤ Fintype.card P) (σ : P ≃ Q) (hσ : ∀ x : P, Nonempty ({y : P // y ≠ x} ≃o {y : Q // y ≠ σ x})) (x : P) : (∀ y : P, ¬ (x < y ∨ y < x)) ↔ (∀ z : Q, ¬ (σ x < z ∨ z < σ x)) := by  classical  have h_count_PQ : poset_lt_pair_count P = poset_lt_pair_count Q := by    have hP : poset_lt_pair_count P = (Finset.univ.filter (fun p : P × P => p.1 < p.2)).card := by      unfold poset_lt_pair_count      rw [Nat.card_eq_fintype_card, Fintype.card_subtype]    have hQ : poset_lt_pair_count Q = (Finset.univ.filter (fun p : Q × Q => p.1 < p.2)).card := by      unfold poset_lt_pair_count      rw [Nat.card_eq_fintype_card, Fintype.card_subtype]    rw [hP, hQ]    exact poset_hypomorphic_card_lt_pairs_eq P Q hn ⟨σ, hσ⟩  have h_iso_count : poset_lt_pair_count {y : P // y ≠ x} = poset_lt_pair_count {y : Q // y ≠ σ x} := by    obtain ⟨e⟩ := hσ x    exact poset_lt_pair_count_eq_of_order_iso _ _ e  rw [← poset_delete_isolated_lt_pair_count_iff P x]  rw [← poset_delete_isolated_lt_pair_count_iff Q (σ x)]  rw [h_iso_count, h_count_PQ]
See it in the graphDiscuss this resultChallenge it