CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-08-29

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.

Enumerating relator consequences does not decide nontriviality

Statement refuted

Enumerating all relator consequences of a recursive presentation decides nontriviality of words in that presentation.

Facts & Assumptions

Given: The recursive presentation $⟨ a ∣ \emptyset ⟩$ and the word $a$ .

[L1]

The trivial words of a recursively presented group form a recursively enumerable language. (The trivial words of a recursively presented group form a recursively enumerable language)

[L2]

A reduced nonempty word in a free group is nonidentity. (The word problem for a finitely generated free group is solvable by free reduction)

Counterexample

technique · direct

1.1L2given

The presentation $⟨ a ∣ \emptyset ⟩$ presents the free group on $a$ . The word $a$ is reduced and nonempty, so [L2] says that it is nontrivial.

2.1L1step 1.1

By [L1], enumerating relator consequences lists precisely the trivial words. Since $a$ is nontrivial by step 1.1, it never appears, and waiting for it gives no halting certificate of nontriviality.

3.1step 2.1∎

Hence the asserted decision procedure is false, and the claimed principle is refuted.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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

Sources

Charles F. Miller III, Decision Problems for Groups - Survey and Reflections (standard reference, not scraped)