poset_delete_isolated_lt_pair_count_iff
In 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 every other element.
Statement
theorem poset_delete_isolated_lt_pair_count_iff (P : Type) [Fintype P] [PartialOrder P] (x : P) : poset_lt_pair_count {y : P // y ≠ x} = poset_lt_pair_count P ↔ (∀ y : P, ¬ (x < y ∨ y < x))
- 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 proof sets up the canonical injection f sending strictly ordered pairs from P ∖ {x} into P. Because P is finite, this injection preserves the count of comparable pairs if and only if it is surjective. Surjectivity means that every comparable pair in P avoids x, which is equivalent to x being incomparable with every element of P.
The count of comparable pairs is reformulated in terms of the cardinalities of finite types.
Unfolding the definition of `poset_lt_pair_count` replaces the pair counts with `Nat.card` applied to the subtypes of strictly ordered pairs (p.1 < p.2). Rewriting with `Nat.card_eq_fintype_card` converts both counts into `Fintype.card`.
uses
Nat.card_eq_fintype_cardclassical unfold poset_lt_pair_count rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card]
Define the canonical inclusion map f on strictly ordered pairs.
We define a map f sending each strictly ordered pair ((a, ha), (b, hb)) of elements in P ∖ {x} to the pair (a, b) in P, preserving the condition a < b while forgetting that the coordinates are distinct from x.
let f : {p : {y : P // y ≠ x} × {y : P // y ≠ x} // p.1 < p.2} → {p : P × P // p.1 < p.2} := fun p => ⟨(p.1.1.1, p.1.2.1), p.2⟩
The canonical map f is injective.
Assuming f(p) = f(q), their underlying coordinates in P agree. Projecting onto the first and second coordinates using `Prod.fst` and `Prod.snd`, and applying extensionality for subtypes (`Subtype.ext`, `Subtype.ext_iff.mp`) and products (`Prod.ext`), we conclude that p = q.
uses
Subtype.ext_iff.mp,Subtype.ext,congrArg,Prod.fst,Prod.snd,Prod.exthave hf : Function.Injective f := by intro p q hpq have h := Subtype.ext_iff.mp hpq simp only [f] at h have h1 : p.1.1 = q.1.1 := Subtype.ext (congrArg Prod.fst h) have h2 : p.1.2 = q.1.2 := Subtype.ext (congrArg Prod.snd h) exact Subtype.ext (Prod.ext h1 h2)
If the pair counts are equal, f is bijective.
Splitting the equivalence (`constructor`), we first assume that the pair sets have the same cardinality (`intro hcard`). Since f is an injection between two finite sets of the same size, the pigeonhole principle (`Fintype.bijective_iff_injective_and_card`) implies that f is bijective.
uses
Fintype.bijective_iff_injective_and_cardconstructor · -- (equal card) -> isolated intro hcard have hbij : Function.Bijective f := (Fintype.bijective_iff_injective_and_card f).mpr ⟨hf, hcard⟩
If f is bijective, x is incomparable with every element of P.
Assume for contradiction that some y ∈ P satisfies x < y or y < x. Since f is bijective, it is surjective. If x < y, the pair (x, y) must be the image under f of some pair p in P ∖ {x}, which implies (f(p)).1 = x; but by construction, the first coordinate of p cannot equal x, a contradiction. The case y < x is symmetric on the second coordinate.
intro y hcon rcases hcon with hlt | hlt · obtain ⟨p, hp⟩ := hbij.2 ⟨(x, y), hlt⟩ have h1 : (f p).val.1 ≠ x := by simpa [f] using p.1.1.property have : (f p).val.1 = x := by rw [hp] exact h1 this · obtain ⟨p, hp⟩ := hbij.2 ⟨(y, x), hlt⟩ have h2 : (f p).val.2 ≠ x := by simpa [f] using p.1.2.property have : (f p).val.2 = x := by rw [hp] exact h2 this
If x is incomparable with every element of P, then f is surjective.
Assume x is isolated (`intro hiso`). For any strictly ordered pair (a, b) in P with a < b, we cannot have a = x, since x < b contradicts isolation (`Or.inl`). Similarly, b ≠ x, as a < x also contradicts isolation (`Or.inr`). Hence both a and b belong to P ∖ {x}, so (a, b) is the image of a pair in the domain.
uses
Or.inl,Or.inr· -- isolated -> equal card intro hiso have hsurj : Function.Surjective f := by rintro ⟨⟨a, b⟩, hab⟩ have ha : a ≠ x := by rintro rfl; exact hiso b (Or.inl hab) have hb : b ≠ x := by rintro rfl; exact hiso a (Or.inr hab) refine ⟨⟨(⟨a, ha⟩, ⟨b, hb⟩), hab⟩, ?_⟩ rfl
When x is isolated, the pair counts in P ∖ {x} and P are equal.
Since f is injective and surjective, it is a bijection. By `Fintype.card_of_bijective`, the finite cardinalities of its domain and codomain are equal.
uses
Fintype.card_of_bijectiveexact Fintype.card_of_bijective ⟨hf, hsurj⟩
Nat.card_eq_fintype_card- For any finite type α, its cardinality as a natural number (Nat.card α) equals Fintype.card α.
Subtype.ext_iff.mp- If two elements of a subtype are equal, their underlying values are equal.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
congrArg- Applying a function to equal arguments yields equal values: if a₁ = a₂, then f a₁ = f a₂.
Prod.fst- The first coordinate projection of an ordered pair (a, b), yielding a.
Prod.snd- The second coordinate projection of an ordered pair (a, b), yielding b.
Prod.ext- Two ordered pairs are equal if their first coordinates are equal and their second coordinates are equal.
Fintype.bijective_iff_injective_and_card- A map between finite types of equal cardinality is bijective if and only if it is injective.
Or.inl- Constructs a proof of a disjunction a ∨ b from a proof of the left disjunct a.
Or.inr- Constructs a proof of a disjunction a ∨ b from a proof of the right disjunct b.
Fintype.card_of_bijective- A bijection between finite types implies that their cardinalities are equal.
- The formalization defines the comparable pairs in the sub-poset using nested subtypes: a pair in {y : P // y ≠ x} × {y : P // y ≠ x} satisfying p.1 < p.2. Steps establishing injectivity and component inequalities require unpacking these nested subtype projections, which are invisible in standard mathematical notation.
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.
/-- Deleting a point preserves the comparable-pair count exactly when that point is isolated. -/theorem poset_delete_isolated_lt_pair_count_iff (P : Type) [Fintype P] [PartialOrder P] (x : P) : poset_lt_pair_count {y : P // y ≠ x} = poset_lt_pair_count P ↔ (∀ y : P, ¬ (x < y ∨ y < x)) := by classical unfold poset_lt_pair_count rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card] let f : {p : {y : P // y ≠ x} × {y : P // y ≠ x} // p.1 < p.2} → {p : P × P // p.1 < p.2} := fun p => ⟨(p.1.1.1, p.1.2.1), p.2⟩ have hf : Function.Injective f := by intro p q hpq have h := Subtype.ext_iff.mp hpq simp only [f] at h have h1 : p.1.1 = q.1.1 := Subtype.ext (congrArg Prod.fst h) have h2 : p.1.2 = q.1.2 := Subtype.ext (congrArg Prod.snd h) exact Subtype.ext (Prod.ext h1 h2) constructor · -- (equal card) -> isolated intro hcard have hbij : Function.Bijective f := (Fintype.bijective_iff_injective_and_card f).mpr ⟨hf, hcard⟩ intro y hcon rcases hcon with hlt | hlt · obtain ⟨p, hp⟩ := hbij.2 ⟨(x, y), hlt⟩ have h1 : (f p).val.1 ≠ x := by simpa [f] using p.1.1.property have : (f p).val.1 = x := by rw [hp] exact h1 this · obtain ⟨p, hp⟩ := hbij.2 ⟨(y, x), hlt⟩ have h2 : (f p).val.2 ≠ x := by simpa [f] using p.1.2.property have : (f p).val.2 = x := by rw [hp] exact h2 this · -- isolated -> equal card intro hiso have hsurj : Function.Surjective f := by rintro ⟨⟨a, b⟩, hab⟩ have ha : a ≠ x := by rintro rfl; exact hiso b (Or.inl hab) have hb : b ≠ x := by rintro rfl; exact hiso a (Or.inr hab) refine ⟨⟨(⟨a, ha⟩, ⟨b, hb⟩), hab⟩, ?_⟩ rfl exact Fintype.card_of_bijective ⟨hf, hsurj⟩