AFTD Auto-Formalizing Theoretical Domains

poset_upset_subset_max

theoremverified

In a poset of height two, every element strictly above any element u is maximal.

Statement

theorem poset_upset_subset_max {P : Type*} [PartialOrder P]
    (hP : poset_height_two P) (u : P) {y : P} (hy : y ∈ poset_upset u) :
    IsMax y
Source
arXiv:2610.24774 Section 3.3
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • poset_upsetFor a poset P and an element u in P, the strict upset U_P(u) is the set of all elements y in P strictly greater than u.
  • poset_height_twoA poset has height two when it contains no chain of three elements.

Read back from the Lean

Let $P$ be a partially ordered type. Assume that $P$ has height at most 2, in the sense that there do not exist $a, b, c \in P$ with $a < b$ and $b < c$. Then for any $u \in P$ and any $y \in P$ strictly above $u$ ($y \in \{y' \mid u < y'\}$), $y$ is a maximal element of $P$ (IsMax y).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that any element y strictly above u is maximal, we consider an arbitrary element b with y ≤ b. In a partial order, this means either y = b or y < b. The case y = b immediately implies b ≤ y, while the case y < b creates a strict three-element chain u < y < b, directly contradicting the hypothesis that the poset has height two.

  1. To show y is maximal, it suffices to show b ≤ y for any b ≥ y, which reduces to the two cases y = b and y < b.

    By definition, an element y is maximal (IsMax y) if any b ≥ y satisfies b ≤ y. We introduce such an element b with hypothesis y ≤ b, and split this inequality into the alternatives y = b or y < b using eq_or_lt_of_le.

    lines 5–6

    uses eq_or_lt_of_le

      intro b hyb
      rcases eq_or_lt_of_le hyb with h | h
  2. In the case y = b, the inequality b ≤ y holds.

    By symmetry of equality we have b = y, from which b ≤ y follows immediately by le_of_eq.

    line 7

    uses le_of_eq

      · exact le_of_eq h.symm
  3. The case y < b is impossible.

    Since y is in the upset of u, we have u < y. Together with y < b, this yields a chain u < y < b of three strictly increasing elements, contradicting the hypothesis hP that P has height two (meaning no three elements satisfy a < b < c).

    line 8

      · exact absurd ⟨hy, h⟩ (hP u y b)
eq_or_lt_of_le
In a partial order, if a ≤ b, then either a = b or a < b.
le_of_eq
In a preorder, if a = b, then a ≤ b.

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

/-- In a poset of height two, every element in the upset of u is maximal. -/theorem poset_upset_subset_max {P : Type*} [PartialOrder P]    (hP : poset_height_two P) (u : P) {y : P} (hy : y ∈ poset_upset u) :    IsMax y := by  intro b hyb  rcases eq_or_lt_of_le hyb with h | h  · exact le_of_eq h.symm  · exact absurd ⟨hy, h⟩ (hP u y b)
See it in the graphDiscuss this resultChallenge it