finite_bmi_algebra_has_y_element
Every finite $\mathbf{BMI}$-algebra has a $Y$-element: let $(A, \cdot)$ be a finite magma equipped with elements $B, M, I \in A$ such that $B$ is a $B$-element, $M$ is an $M$-element, and $I$ is an $I$-element; then there exists an element $Y \in A$ such that $Yx = x(Yx)$ for all $x \in A$.
Statement
theorem finite_bmi_algebra_has_y_element {A : Type*} [Mul A] [Fintype A] (B M I : A) (hB : bmi_is_b_element B) (hM : bmi_is_m_element M) (hI : bmi_is_i_element I) : ∃ Y : A, bmi_is_y_element Y
- Formalizes
- arXiv:2610.37108 Corollary 3.5 -- Finite BM-algebras and fixed-point combinators
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- bmi_is_b_elementAn element $B$ in a magma $(A, \cdot)$ is a $B$-element if $((Bx)y)z = x(yz)$ for all $x, y, z \in A$.
- bmi_is_m_elementAn element $M$ in a magma $(A, \cdot)$ is an $M$-element if $Mx = xx$ for all $x \in A$ .
- bmi_is_i_elementAn element $I$ in a magma $(A, \cdot)$ is an $I$-element (a left unit) if $Ix = x$ for all $x \in A$.
- bmi_is_y_elementAn element $Y$ in a magma $(A, \cdot)$ is a $Y$-element (fixed-point element) if $Yx = x(Yx)$ for all $x \in A$.
- bmi_is_left_unit_bLet $(A, \cdot)$ be a finite magma equipped with a $B$-element $B$ and an $I$-element $I$. Then $B$ is a left unit: $Bx = x$ for all…
- bmi_assoc_of_is_b_of_left_unitLet $(A, \cdot)$ be a magma with a $B$-element $B$. If $B$ is a left unit ($Bx = x$ for all $x$), then the operation is associative:…
- bmi_idempotent_of_assoc_of_is_m_of_is_iLet $(A, \cdot)$ be an associative magma with an $M$-element $M$ and an $I$-element $I$. Then every element $x \in A$ is idempotent:…
- bmi_is_y_element_of_is_i_element_of_idempotentIn any idempotent magma, every left unit $I$ (satisfying $Ix = x$ for all $x$) is a $Y$-element: $Ix = x(Ix)$ for all $x$.
Read back from the Lean
For every finite type $A$ equipped with a multiplication operation, and given elements $B, M, I \in A$, if $B$ is a B-combinator (i.e., bmi_is_b_element B), $M$ is an M-combinator (i.e., bmi_is_m_element M), and $I$ is an identity combinator (i.e., bmi_is_i_element I), then there exists an element $Y \in A$ that is a fixed-point/Y-combinator (i.e., bmi_is_y_element 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
The proof demonstrates that in any finite BMI-algebra, the identity element I itself is a fixed-point combinator (a Y-element). Finiteness together with the B and I axioms implies that B acts as a left identity, which in turn forces multiplication to be associative. In an associative magma with an M-element and an I-element, every element is idempotent, from which Ix = x(Ix) follows immediately for the identity element I.
B is a left identity: Bx = x for all x ∈ A
Applying bmi_is_left_unit_b, the finiteness of A alongside the B-element and I-element axioms implies that left multiplication by B acts as the identity on A.
uses
bmi_is_left_unit_bhave hBunit : ∀ x : A, B * x = x := bmi_is_left_unit_b B I hB hIMultiplication on A is associative: (x * y) * z = x * (y * z) for all x, y, z ∈ A
Because B is a B-element (Bxyz = x(yz)) and B is a left unit (Bx = x), bmi_assoc_of_is_b_of_left_unit shows that multiplication in A is associative.
uses
bmi_assoc_of_is_b_of_left_unithave hassoc : ∀ x y z : A, (x * y) * z = x * (y * z) := bmi_assoc_of_is_b_of_left_unit B hB hBunitEvery element in A is idempotent: x * x = x for all x ∈ A
By bmi_idempotent_of_assoc_of_is_m_of_is_i, in any associative magma equipped with an M-element (Mx = xx) and an I-element (Ix = x), every element is idempotent.
uses
bmi_idempotent_of_assoc_of_is_m_of_is_ihave hidem : ∀ x : A, x * x = x := bmi_idempotent_of_assoc_of_is_m_of_is_i hassoc M I hM hIThere exists a Y-element in A, namely I
Since I is an identity element (Ix = x) and every element is idempotent (xx = x), we have Ix = x = xx = x(Ix). By bmi_is_y_element_of_is_i_element_of_idempotent, I satisfies the defining property of a Y-element, providing the required witness.
uses
bmi_is_y_element_of_is_i_element_of_idempotentexact ⟨I, bmi_is_y_element_of_is_i_element_of_idempotent I hI hidem⟩
bmi_is_left_unit_b- In a finite magma with a B-element and an I-element, B acts as a left identity: Bx = x for all x.
bmi_assoc_of_is_b_of_left_unit- If B is a B-element and a left identity, then multiplication is associative: (x * y) * z = x * (y * z) for all x, y, z.
bmi_idempotent_of_assoc_of_is_m_of_is_i- In an associative magma with an M-element and an I-element, every element is idempotent: x * x = x for all x.
bmi_is_y_element_of_is_i_element_of_idempotent- If I is an I-element and multiplication is idempotent, then I is a Y-element: Ix = x * (Ix) for all x.
- The finiteness hypothesis is used exclusively in the first step via bmi_is_left_unit_b; the remainder of the proof consists of equational reasoning.
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.
/-- Every finite BMI-algebra has a Y-element (fixed-point combinator element). -/theorem finite_bmi_algebra_has_y_element {A : Type*} [Mul A] [Fintype A] (B M I : A) (hB : bmi_is_b_element B) (hM : bmi_is_m_element M) (hI : bmi_is_i_element I) : ∃ Y : A, bmi_is_y_element Y := by have hBunit : ∀ x : A, B * x = x := bmi_is_left_unit_b B I hB hI have hassoc : ∀ x y z : A, (x * y) * z = x * (y * z) := bmi_assoc_of_is_b_of_left_unit B hB hBunit have hidem : ∀ x : A, x * x = x := bmi_idempotent_of_assoc_of_is_m_of_is_i hassoc M I hM hI exact ⟨I, bmi_is_y_element_of_is_i_element_of_idempotent I hI hidem⟩