poset_iso_of_iso_delete_of_isolated
If x ∈ P and y ∈ Q are each incomparable with every other element and the complements P − x and Q − y are order-isomorphic, then P ≅ Q.
Statement
theorem poset_iso_of_iso_delete_of_isolated (P Q : Type) [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q] (x : P) (y : Q) (hx : ∀ z : P, ¬ (x < z ∨ z < x)) (hy : ∀ z : Q, ¬ (y < z ∨ z < y)) (e : {z : P // z ≠ x} ≃o {z : Q // z ≠ y}) : Nonempty (P ≃o Q)
- Source
- step towards poset_height_one_reconstructible
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
The proof, explained
To extend an order isomorphism e : (P ∖ {x}) ≃o (Q ∖ {y}) to the entire posets P and Q, we define f : P → Q by sending x to y and agreeing with e elsewhere. Since x and y are isolated, comparability with either element collapses to equality with it. This isolation ensures that f is a bijection and that no new relations are created between x (or y) and the rest of the poset, so f preserves and reflects the order and gives an order isomorphism P ≃o Q.
For any element, being comparable to x (respectively, y) is equivalent to being equal to x (respectively, y). Specifically, x ≤ z ↔ x = z and z ≤ x ↔ z = x for all z ∈ P, and similarly for y ∈ Q.
Because x is isolated in P, it cannot satisfy x < z or z < x for any z. If x ≤ z, then either x < z or x = z by `lt_or_eq_of_le`; since strict inequality contradicts isolation, we must have x = z. Conversely, x = z implies x ≤ z by reflexivity (`le_of_eq`). The same case analysis proves z ≤ x ↔ z = x, as well as the dual characterizations y ≤ z ↔ y = z and z ≤ y ↔ z = y for y in Q.
uses
lt_or_eq_of_le,le_of_eq,Or.inl,Or.inrclassical have hxle : ∀ z : P, x ≤ z ↔ x = z := by intro z exact ⟨fun h => (lt_or_eq_of_le h).elim (fun hlt => absurd hlt (fun hh => (hx z) (Or.inl hh))) (fun he => he), fun h => le_of_eq h⟩ have hxge : ∀ z : P, z ≤ x ↔ z = x := by intro z exact ⟨fun h => (lt_or_eq_of_le h).elim (fun hlt => absurd hlt (fun hh => (hx z) (Or.inr hh))) (fun he => he), fun h => le_of_eq h⟩ have hyle : ∀ z : Q, y ≤ z ↔ y = z := by intro z exact ⟨fun h => (lt_or_eq_of_le h).elim (fun hlt => absurd hlt (fun hh => (hy z) (Or.inl hh))) (fun he => he), fun h => le_of_eq h⟩ have hyge : ∀ z : Q, z ≤ y ↔ z = y := by intro z exact ⟨fun h => (lt_or_eq_of_le h).elim (fun hlt => absurd hlt (fun hh => (hy z) (Or.inr hh))) (fun he => he), fun h => le_of_eq h⟩
The extension f : P → Q is defined, satisfying f(x) = y and f(z) = e(z) for all z ≠ x.
We define f(z) piecewise: if z = x then f(z) = y, and otherwise f(z) = e(⟨z, h⟩) where h is the witness that z ≠ x. By definition, f(x) simplifies to y. For any element z with a proof hz that z ≠ x, `dif_neg` evaluates the conditional to its else-branch, yielding f(z) = e(⟨z, hz⟩).
uses
dif_neglet f : P → Q := fun z => if h : z = x then y else e ⟨z, h⟩ have hf_x : f x = y := by simp [f] have hf_ne : ∀ z (hz : z ≠ x), f z = e ⟨z, hz⟩ := by intro z hz; simp only [f, dif_neg hz]
The extended map f is injective.
Suppose f(a) = f(b). We split into cases depending on whether a and b equal x. If both equal x, then a = b. If a = x but b ≠ x, then y = f(a) = f(b) = e(b), which is impossible because every value in the codomain of e is distinct from y. The case where a ≠ x and b = x is symmetrically impossible. If neither equals x, then e(a) = e(b) as values in Q; by `Subtype.ext` they are equal in the subtype, and because e is an isomorphism (hence injective), ⟨a, ha⟩ = ⟨b, hb⟩. Taking the underlying values with `congrArg Subtype.val` gives a = b.
uses
Subtype.ext,congrArg,Subtype.valhave hinj : Function.Injective f := by intro a b hab by_cases ha : a = x · by_cases hb : b = x · rw [ha, hb] · have hfa : f a = y := by rw [ha, hf_x] rw [hfa, hf_ne b hb] at hab exact absurd hab.symm (e ⟨b, hb⟩).property · by_cases hb : b = x · have hfb : f b = y := by rw [hb, hf_x] rw [hf_ne a ha, hfb] at hab exact absurd hab (e ⟨a, ha⟩).property · rw [hf_ne a ha, hf_ne b hb] at hab have hsub := e.injective (Subtype.ext hab) exact congrArg Subtype.val hsub
The extended map f is surjective.
Given any q ∈ Q, if q = y then x is a pre-image since f(x) = y. If q ≠ y, then q belongs to the subtype {z : Q // z ≠ y}. Since the order isomorphism e is surjective, there is some p in the domain subtype {z : P // z ≠ x} mapped to q by e. Then the underlying element p.val is not x, so f(p.val) = e(p) = q, providing the required pre-image.
have hsurj : Function.Surjective f := by intro q by_cases hq : q = y · exact ⟨x, by rw [hf_x, hq]⟩ · obtain ⟨p, hp⟩ := e.surjective ⟨q, hq⟩ refine ⟨p.val, ?_⟩ have hpe : f p.val = e p := by rw [hf_ne p.val p.property] rw [hpe, hp]
The map f preserves and reflects the order: for all a, b ∈ P, f(a) ≤ f(b) ↔ a ≤ b.
We analyze whether a = x and b = x. If both equal x, both sides are reflexive comparisons (y ≤ y and x ≤ x) and thus hold by `le_refl`. If a = x and b ≠ x, the left-hand side f(x) ≤ f(b) becomes y ≤ e(b), which by the earlier characterization means y = e(b), impossible since e takes values in Q ∖ {y}; the right-hand side x ≤ b similarly requires x = b, which is false since b ≠ x. By `iff_of_false`, two false statements are equivalent. The case a ≠ x and b = x is completely symmetric. Finally, if neither equals x, f(a) ≤ f(b) is e(a) ≤ e(b) in Q; by `Subtype.coe_le_coe` and `Subtype.mk_le_mk` this inequality matches the subtype order, where it is equivalent to a ≤ b because e is an order isomorphism.
uses
le_refl,iff_of_false,Subtype.coe_le_coe,Subtype.mk_le_mkhave hord : ∀ a b : P, f a ≤ f b ↔ a ≤ b := by intro a b by_cases ha : a = x · by_cases hb : b = x · rw [ha, hb, hf_x] exact ⟨fun _ => le_refl x, fun _ => le_refl y⟩ · rw [ha, hf_x, hf_ne b hb, hyle] have hne : ¬ (y = e ⟨b, hb⟩) := fun h => (e ⟨b, hb⟩).property h.symm have hxb : ¬ (x ≤ b) := by rw [hxle]; exact fun h => hb h.symm exact iff_of_false hne hxb · by_cases hb : b = x · rw [hb, hf_ne a ha, hf_x, hyge] have hne : ¬ (e ⟨a, ha⟩ = y) := (e ⟨a, ha⟩).property have hax : ¬ (a ≤ x) := by rw [hxge]; exact ha exact iff_of_false hne hax · rw [hf_ne a ha, hf_ne b hb, Subtype.coe_le_coe, e.le_iff_le, Subtype.mk_le_mk]
There exists an order isomorphism between P and Q, establishing Nonempty (P ≃o Q).
Promoting the injection and surjection to a bijection via `Equiv.ofBijective`, and combining this bijection with the order-preservation equivalence `hord`, `RelIso.mk` constructs an order isomorphism P ≃o Q, demonstrating that the type of isomorphisms is nonempty.
uses
RelIso.mk,Equiv.ofBijectiverefine ⟨RelIso.mk (Equiv.ofBijective f ⟨hinj, hsurj⟩) (fun {a b} => ?_)⟩ change f a ≤ f b ↔ a ≤ b exact hord a b
lt_or_eq_of_le- in a partial order, if a ≤ b then either a < b or a = b
le_of_eq- in a preorder, equality implies weak inequality (a = b → a ≤ b)
Or.inl- a disjunction a ∨ b holds if its left disjunct a holds
Or.inr- a disjunction a ∨ b holds if its right disjunct b holds
dif_neg- a dependent if-then-else expression evaluates to its else-branch when the condition is false
Subtype.ext- two subtype elements are equal if their underlying values are equal
congrArg- applying a function to equal arguments yields equal values
Subtype.val- the projection extracting the underlying value from a subtype element
le_refl- weak inequality in a preorder is reflexive (a ≤ a)
iff_of_false- two propositions are logically equivalent if both are false
Subtype.coe_le_coe- elements of an induced subtype order are ordered if and only if their underlying values are ordered
Subtype.mk_le_mk- explicit subtype terms ⟨x, hx⟩ and ⟨y, hy⟩ are ordered if and only if x ≤ y
RelIso.mk- constructs an order (relation) isomorphism from a bijection that preserves and reflects the relation
Equiv.ofBijective- a bijective function induces an equivalence (bijection) between types
- Although the theorem statement includes `[Fintype P]` and `[Fintype Q]` typeclass assumptions, the proof never uses the finiteness of either set; the construction and argument hold for arbitrary partially ordered sets.
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.
/-- An order isomorphism of the complements of two isolated points extends to an isomorphism of the whole ordered sets. -/theorem poset_iso_of_iso_delete_of_isolated (P Q : Type) [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q] (x : P) (y : Q) (hx : ∀ z : P, ¬ (x < z ∨ z < x)) (hy : ∀ z : Q, ¬ (y < z ∨ z < y)) (e : {z : P // z ≠ x} ≃o {z : Q // z ≠ y}) : Nonempty (P ≃o Q) := by classical have hxle : ∀ z : P, x ≤ z ↔ x = z := by intro z exact ⟨fun h => (lt_or_eq_of_le h).elim (fun hlt => absurd hlt (fun hh => (hx z) (Or.inl hh))) (fun he => he), fun h => le_of_eq h⟩ have hxge : ∀ z : P, z ≤ x ↔ z = x := by intro z exact ⟨fun h => (lt_or_eq_of_le h).elim (fun hlt => absurd hlt (fun hh => (hx z) (Or.inr hh))) (fun he => he), fun h => le_of_eq h⟩ have hyle : ∀ z : Q, y ≤ z ↔ y = z := by intro z exact ⟨fun h => (lt_or_eq_of_le h).elim (fun hlt => absurd hlt (fun hh => (hy z) (Or.inl hh))) (fun he => he), fun h => le_of_eq h⟩ have hyge : ∀ z : Q, z ≤ y ↔ z = y := by intro z exact ⟨fun h => (lt_or_eq_of_le h).elim (fun hlt => absurd hlt (fun hh => (hy z) (Or.inr hh))) (fun he => he), fun h => le_of_eq h⟩ let f : P → Q := fun z => if h : z = x then y else e ⟨z, h⟩ have hf_x : f x = y := by simp [f] have hf_ne : ∀ z (hz : z ≠ x), f z = e ⟨z, hz⟩ := by intro z hz; simp only [f, dif_neg hz] have hinj : Function.Injective f := by intro a b hab by_cases ha : a = x · by_cases hb : b = x · rw [ha, hb] · have hfa : f a = y := by rw [ha, hf_x] rw [hfa, hf_ne b hb] at hab exact absurd hab.symm (e ⟨b, hb⟩).property · by_cases hb : b = x · have hfb : f b = y := by rw [hb, hf_x] rw [hf_ne a ha, hfb] at hab exact absurd hab (e ⟨a, ha⟩).property · rw [hf_ne a ha, hf_ne b hb] at hab have hsub := e.injective (Subtype.ext hab) exact congrArg Subtype.val hsub have hsurj : Function.Surjective f := by intro q by_cases hq : q = y · exact ⟨x, by rw [hf_x, hq]⟩ · obtain ⟨p, hp⟩ := e.surjective ⟨q, hq⟩ refine ⟨p.val, ?_⟩ have hpe : f p.val = e p := by rw [hf_ne p.val p.property] rw [hpe, hp] have hord : ∀ a b : P, f a ≤ f b ↔ a ≤ b := by intro a b by_cases ha : a = x · by_cases hb : b = x · rw [ha, hb, hf_x] exact ⟨fun _ => le_refl x, fun _ => le_refl y⟩ · rw [ha, hf_x, hf_ne b hb, hyle] have hne : ¬ (y = e ⟨b, hb⟩) := fun h => (e ⟨b, hb⟩).property h.symm have hxb : ¬ (x ≤ b) := by rw [hxle]; exact fun h => hb h.symm exact iff_of_false hne hxb · by_cases hb : b = x · rw [hb, hf_ne a ha, hf_x, hyge] have hne : ¬ (e ⟨a, ha⟩ = y) := (e ⟨a, ha⟩).property have hax : ¬ (a ≤ x) := by rw [hxge]; exact ha exact iff_of_false hne hax · rw [hf_ne a ha, hf_ne b hb, Subtype.coe_le_coe, e.le_iff_le, Subtype.mk_le_mk] refine ⟨RelIso.mk (Equiv.ofBijective f ⟨hinj, hsurj⟩) (fun {a b} => ?_)⟩ change f a ≤ f b ↔ a ≤ b exact hord a b