AFTD Auto-Formalizing Theoretical Domains

poset_height_one_bool

theoremverified

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.

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

    line 2

      refine ⟨⟨false, true, by decide⟩, ?_⟩
  2. 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.

    line 3

      decide

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

theorem poset_height_one_bool : poset_height_one Bool := by  refine ⟨⟨false, true, by decide⟩, ?_⟩  decide
See it in the graphDiscuss this resultChallenge it