AFTD Auto-Formalizing Theoretical Domains

poset_iso_of_iso_delete_of_isolated

theoremverified

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.

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

    lines 3–19

    uses lt_or_eq_of_le, le_of_eq, Or.inl, Or.inr

      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⟩
  2. 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⟩).

    lines 20–22

    uses dif_neg

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

    lines 23–37

    uses Subtype.ext, congrArg, Subtype.val

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

    lines 38–46

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

    lines 47–62

    uses le_refl, iff_of_false, Subtype.coe_le_coe, Subtype.mk_le_mk

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

    lines 63–65

    uses RelIso.mk, Equiv.ofBijective

      refine ⟨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

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

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