AFTD Auto-Formalizing Theoretical Domains

bmi_is_left_unit_b

theoremverifiedformalization

Let $(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 $x \in A$.

Statement

theorem bmi_is_left_unit_b {A : Type*} [Mul A] [Fintype A]
    (B I : A) (hB : bmi_is_b_element B) (hI : bmi_is_i_element I) :
    ∀ x : A, B * x = x
Formalizes
arXiv:2610.37108 Proposition 3.1 -- Finite BM-algebras and fixed-point combinators
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_i_elementAn element $I$ in a magma $(A, \cdot)$ is an $I$-element (a left unit) if $Ix = x$ for all $x \in A$.
Used by 3

Read back from the Lean

For any finite type $A$ equipped with a multiplication operation (*), and any elements $B, I \in A$, if $B$ is a B-element (that is, $((B * x) * y) * z = x * (y * z)$ for all $x, y, z \in A$) and $I$ is an I-element (that is, $I * x = x$ for all $x \in A$), then for all $x \in A$, $B * x = x$ (i.e., $B$ acts as a left identity on $A$).

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 considers the finite set $S = \{L(a) \mid a \in A\}$ of left-multiplication operators on $A$ and defines a transformation $\phi : S \to S$ by $\phi(L(a)) = L(a \cdot I)$. Using the defining property of the $B$-element, $\phi(L(B \cdot a)) = L(a)$, so $\phi$ is surjective. Because $A$ (and therefore $S$) is finite, surjectivity implies that $\phi$, and consequently $\phi \circ \phi$, is injective. Direct calculation using the axioms for $B$ and $I$ shows that $(\phi \circ \phi)(L(B))$ and $(\phi \circ \phi)(L(I))$ both evaluate to the identity function on $A$, so they are equal. By injectivity, $L(B) = L(I)$, which means $B \cdot x = I \cdot x = x$ for all $x \in A$.

  1. Define left multiplication, the set of left multiplications, and the operator $\phi$.

    For each $a \in A$, let $L(a) : A \to A$ be left multiplication by $a$, sending $x \mapsto a \cdot x$. Let $S$ be the range of $L$, consisting of all left-multiplication maps. Define an endofunction $\phi : S \to S$ sending each operator $f \in S$ to $L(f(I)) \in S$.

    lines 5–7

      let L : A → (A → A) := fun a x => a * x
      let S := Set.range L
      let phi : S → S := fun ⟨f, _⟩ => ⟨L (f I), ⟨f I, rfl⟩⟩
  2. The operator $\phi$ is surjective.

    Every element in $S$ is of the form $L(a)$ for some $a \in A$. We consider the candidate preimage $L(B \cdot a) \in S$. Under $\phi$, this maps to $L((B \cdot a) \cdot I)$. Evaluating on any $x \in A$, the definition of a $B$-element ($B \cdot a \cdot I \cdot x = a \cdot (I \cdot x)$) and of an $I$-element ($I \cdot x = x$) show that $((B \cdot a) \cdot I) \cdot x = a \cdot x = L(a)(x)$. Extensionality then gives $\phi(L(B \cdot a)) = L(a)$, proving surjectivity.

    lines 8–13

      have h_surj : Function.Surjective phi := by
        rintro ⟨g, ⟨a, rfl⟩⟩
        refine ⟨⟨L (B * a), ⟨B * a, rfl⟩⟩, ?_⟩
        ext x
        dsimp [phi, L]
        rw [hB a I x, hI x]
  3. Both $\phi$ and $\phi \circ \phi$ are injective.

    Since $A$ is finite, the range $S = \text{range } L$ is finite. For any self-map of a finite set, surjectivity implies injectivity (by `Finite.injective_iff_surjective.mpr`), so $\phi$ is injective. The composition of injective maps is injective, hence $\phi \circ \phi$ is also injective.

    lines 14–15

    uses Finite.injective_iff_surjective.mpr

      have h_inj : Function.Injective phi := Finite.injective_iff_surjective.mpr h_surj
      have h_inj2 : Function.Injective (phi ∘ phi) := h_inj.comp h_inj
  4. The second iterate $\phi \circ \phi$ agrees on $L(B)$ and $L(I)$.

    Let $v_B = L(B)$ and $v_I = L(I)$ in $S$. We evaluate $(\phi \circ \phi)(v_B)$ and $(\phi \circ \phi)(v_I)$ at an arbitrary $x \in A$. For $v_B$, unfolding definitions yields $((B \cdot I) \cdot I) \cdot x$, which rewrites by the $B$-property to $I \cdot (I \cdot x)$ and then by the $I$-property to $x$. For $v_I$, unfolding yields $((I \cdot I) \cdot I) \cdot x$, which reduces to $x$ by repeatedly applying the $I$-property. Since both evaluate to $x$ everywhere, extensionality gives $(\phi \circ \phi)(v_B) = (\phi \circ \phi)(v_I)$.

    lines 16–23

      let vB : S := ⟨L B, ⟨B, rfl⟩⟩
      let vI : S := ⟨L I, ⟨I, rfl⟩⟩
      have h_eq : (phi ∘ phi) vB = (phi ∘ phi) vI := by
        ext x
        change (phi (phi vB)).1 x = (phi (phi vI)).1 x
        dsimp [phi, L, vB, vI]
        rw [hB I I x]
        repeat rw [hI]
  5. For all $x \in A$, $B \cdot x = x$.

    Because $\phi \circ \phi$ is injective, $(\phi \circ \phi)(v_B) = (\phi \circ \phi)(v_I)$ implies $v_B = v_I$. Extracting the underlying functions via `Subtype.val` and evaluating at $x$ using `congr_arg` and `congr_fun` gives $L(B)(x) = L(I)(x)$, or $B \cdot x = I \cdot x$. Since $I$ is an $I$-element, $I \cdot x = x$, which establishes $B \cdot x = x$.

    lines 24–28

    uses congr_fun, congr_arg, Subtype.val

      have hv : vB = vI := h_inj2 h_eq
      intro x
      have hL : L B x = L I x := congr_fun (congr_arg Subtype.val hv) x
      dsimp [L] at hL
      rw [hL, hI x]
Finite.injective_iff_surjective.mpr
on a finite type, a surjective endofunction is injective
congr_fun
if two functions are equal, applying them to the same argument yields equal values
congr_arg
if two arguments are equal, applying a function to both yields equal values
Subtype.val
extracts the underlying element from a subtype

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 any finite magma with a B-element and an I-element, B is a left unit. -/theorem bmi_is_left_unit_b {A : Type*} [Mul A] [Fintype A]    (B I : A) (hB : bmi_is_b_element B) (hI : bmi_is_i_element I) :    ∀ x : A, B * x = x := by  let L : A → (A → A) := fun a x => a * x  let S := Set.range L  let phi : S → S := fun ⟨f, _⟩ => ⟨L (f I), ⟨f I, rfl⟩⟩  have h_surj : Function.Surjective phi := by    rintro ⟨g, ⟨a, rfl⟩⟩    refine ⟨⟨L (B * a), ⟨B * a, rfl⟩⟩, ?_⟩    ext x    dsimp [phi, L]    rw [hB a I x, hI x]  have h_inj : Function.Injective phi := Finite.injective_iff_surjective.mpr h_surj  have h_inj2 : Function.Injective (phi ∘ phi) := h_inj.comp h_inj  let vB : S := ⟨L B, ⟨B, rfl⟩⟩  let vI : S := ⟨L I, ⟨I, rfl⟩⟩  have h_eq : (phi ∘ phi) vB = (phi ∘ phi) vI := by    ext x    change (phi (phi vB)).1 x = (phi (phi vI)).1 x    dsimp [phi, L, vB, vI]    rw [hB I I x]    repeat rw [hI]  have hv : vB = vI := h_inj2 h_eq  intro x  have hL : L B x = L I x := congr_fun (congr_arg Subtype.val hv) x  dsimp [L] at hL  rw [hL, hI x]
See it in the graphDiscuss this resultChallenge it