poset_hypomorphic_isolated_iff
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
- 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…
- poset_hypomorphic_card_lt_pairs_eqThe number of comparable pairs is reconstructible: if finite ordered sets P and Q with |P| ≥ 3 have the same deck, they have the same…
- poset_delete_isolated_lt_pair_count_iffIn a finite ordered set, the one-element deletion P − x has the same number of comparable pairs as P if and only if x is incomparable with…
- poset_lt_pair_count_eq_of_order_isoOrder-isomorphic ordered sets have the same number of comparable pairs.
- poset_lt_pair_countThe number of comparable pairs (ordered pairs a < b) of an ordered set, as a natural number.
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.
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.
uses
Nat.card_eq_fintype_card,Fintype.card_subtype,poset_hypomorphic_card_lt_pairs_eqclassical 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σ⟩
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.
uses
poset_lt_pair_count_eq_of_order_isohave 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
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.
uses
poset_delete_isolated_lt_pair_count_iffrw [← 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).
- The knowledge base represents the count of strictly ordered pairs in two ways: `poset_lt_pair_count` uses `Nat.card` on a subtype, whereas `poset_hypomorphic_card_lt_pairs_eq` uses `Finset.card` on a filtered product set. Lines 5–10 explicitly bridge between these two representations.
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.
/-- 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]