AFTD Auto-Formalizing Theoretical Domains

is_morphic_image

def

An infinite word z is the morphic image of an infinite word w under f : α → List β if for every n, applying f to the prefix of length n of w yields the prefix of z of that length.

Statement

def is_morphic_image {α β : Type*} (z : ℕ → β) (f : α → List β) (w : ℕ → α) : Prop
Defined in
arXiv:2611.13676
Verified
12 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given types α and β, a sequence z : ℕ → β, a function f : α → List β, and a sequence w : ℕ → α, is_morphic_image z f w asserts that for every natural number n, the list obtained by mapping w over [0, ..., n - 1] and flat-mapping f (i.e., concatenating f (w 0) ++ f (w 1) ++ ... ++ f (w (n - 1))) is equal to the prefix of z of length equal to the length of that concatenated list (i.e., [z 0, z 1, ..., z (L - 1)], where L is the length of the concatenated list).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- An infinite word z is the morphic image of an infinite word w under a morphism f if every prefix of w maps under f to the corresponding prefix of z. -/
def is_morphic_image {α β : Type*} (z : ℕ → β) (f : α → List β) (w : ℕ → α) : Prop := ∀ n : ℕ, ((List.range n).map w).flatMap f = (List.range (((List.range n).map w).flatMap f).length).map z
See it in the graphDiscuss this resultChallenge it