AFTD Auto-Formalizing Theoretical Domains

finite_bmi_algebra_has_y_element

theoremverifiedformalization

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.

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

    line 5

    uses bmi_is_left_unit_b

      have hBunit : ∀ x : A, B * x = x := bmi_is_left_unit_b B I hB hI
  2. Multiplication 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.

    lines 6–7

    uses bmi_assoc_of_is_b_of_left_unit

      have hassoc : ∀ x y z : A, (x * y) * z = x * (y * z) :=
        bmi_assoc_of_is_b_of_left_unit B hB hBunit
  3. Every 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.

    line 8

    uses bmi_idempotent_of_assoc_of_is_m_of_is_i

      have hidem : ∀ x : A, x * x = x := bmi_idempotent_of_assoc_of_is_m_of_is_i hassoc M I hM hI
  4. There 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.

    line 9

    uses bmi_is_y_element_of_is_i_element_of_idempotent

      exact ⟨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.

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

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