poset_height_one_bool
The two-element chain false < true has height one.
Statement
theorem poset_height_one_bool : poset_height_one Bool- Source
- Sanity lemma for poset_height_one (arXiv:2610.12690).
- Verified
- 13 Oct 2026
- Axioms
propext- Built on 1
- poset_height_oneAn ordered set has height one when its longest chains have exactly two elements: some two elements are comparable and there is no chain a…
The proof, explained
A partially ordered set has height one if it contains at least one strict inequality and no chain of two consecutive strict inequalities. For the two-element boolean poset, the pair $\text{false} < \text{true}$ provides the required strict inequality. The impossibility of a length-two chain $a < b < c$ is then verified by exhaustively checking all eight triples of booleans.
There exist booleans $a < b$, witnessed by $\text{false} < \text{true}$.
By definition, a poset has height one if it contains a strict inequality and has no chain of two consecutive strict inequalities. Providing $\text{false}$ and $\text{true}$ as witnesses reduces the first condition to $\text{false} < \text{true}$, which is verified by direct evaluation. This leaves the goal of showing that no three booleans form a strict chain.
refine ⟨⟨false, true, by decide⟩, ?_⟩
No three booleans $a, b, c$ satisfy $a < b$ and $b < c$.
Since $\text{Bool}$ contains only two elements, there are only $2^3 = 8$ triples $(a, b, c)$ to consider. The `decide` tactic tests all eight cases by computation and confirms that the condition $a < b \wedge b < c$ never holds.
decide
- The `decide` tactic automatically verifies both the inequality `false < true` and the universal statement by exhaustive computation over the finite type `Bool`.
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.
theorem poset_height_one_bool : poset_height_one Bool := by refine ⟨⟨false, true, by decide⟩, ?_⟩ decide