ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + claude-sonnet-5)audited 2026-08-17

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A Kleisli composite for the list monad computed by substitution and concatenation

Example

For the list monad, let $X = {0, 1, 2}$ and define

$f (0) = [a, b, a], f (1) = [], f (2) = [b],$

$g (a) = [p], g (b) = [q, p] .$

Then the Kleisli composite substitutes the $g$ -word for every letter of the $f$ -word and concatenates.

Facts & Assumptions

Given: The displayed list-valued functions $f : X \to {a, b}^{*}$ and $g : {a, b} \to {p, q}^{*}$ .

[L1]

A Kleisli arrow $A \to B$ for the list monad is a function $A \to B^{*}$ , and Kleisli composition uses the monad multiplication (Kleisli category of a monad; The free-monoid monad has monoids as its Eilenberg–Moore algebras).

[L2]

The multiplication of the list monad concatenates a list of lists (The free-monoid monad has monoids as its Eilenberg–Moore algebras).

Verification

technique · direct

1.1given

The data include an input with empty output, and all displayed values are finite words of the required types.

2.1L1L2step 1.1

Substitution and concatenation give $(g ⋆ f) (0) = [p, q, p, p]$ , $(g ⋆ f) (1) = []$ , and $(g ⋆ f) (2) = [q, p]$ .

3.1L1L2step 2.1∎

Define $h (p) = [r]$ and $h (q) = [s, r]$ . Then $(h ⋆ (g ⋆ f)) (0) = [r, s, r, r, r]$ , while $(h ⋆ g) (a) = [r]$ and $(h ⋆ g) (b) = [s, r, r]$ , so $((h ⋆ g) ⋆ f) (0)$ is the same word.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.