AFTD Auto-Formalizing Theoretical Domains

poset_delete_isolated_lt_pair_count_iff

theoremverified

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.

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

    lines 3–5

    uses Nat.card_eq_fintype_card

      classical
      unfold poset_lt_pair_count
      rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card]
  2. 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.

    lines 6–7

      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⟩
  3. 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.

    lines 8–14

    uses Subtype.ext_iff.mp, Subtype.ext, congrArg, Prod.fst, Prod.snd, Prod.ext

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

    lines 15–18

    uses Fintype.bijective_iff_injective_and_card

      constructor
      · -- (equal card) -> isolated
        intro hcard
        have hbij : Function.Bijective f := (Fintype.bijective_iff_injective_and_card f).mpr ⟨hf, hcard⟩
  5. 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.

    lines 19–28

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

    lines 29–36

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

    line 37

    uses Fintype.card_of_bijective

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

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

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