PropositionStatement: Literature-sourcedProof: AI-generatedSession-authored (Fable 5 assisted)precheck 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.

Solvability of the word problem does not depend on the chosen finite generating set

Statement

Let $P = ⟨ X ∣ R ⟩$ and $Q = ⟨ Y ∣ S ⟩$ be finite presentations of isomorphic groups. Then the word problem is solvable for $P$ if and only if it is solvable for $Q$ .

Facts & Assumptions

Given: Finite presentations $P = ⟨ X ∣ R ⟩$ and $Q = ⟨ Y ∣ S ⟩$ that present isomorphic groups.

[L1]

Two finite presentations present isomorphic groups if and only if a finite sequence of Tietze transformations and inverses connects them. (Two finite presentations define isomorphic groups if and only if a finite sequence of Tietze transformations and inverses connects them)

[L2]

In a presentation, equality of represented elements is equivalent to membership of the difference word in the normal closure of the relators. (In $⟨ X ∣ R ⟩$ , the words $u$ and $v$ represent the same element if and only if $u^{- 1} v \in ⟨ ⁣ ⟨ R ⟩ ⁣ ⟩$ )

Proof

technique · direct

1.1

By [L1], it is enough to show that each single Tietze transformation preserves solvability of the word problem.

L1given

2.1

A relator-addition or relator-deletion Tietze move does not change which words are trivial in the presented group, by the equality criterion [L2]. So the same decision procedure works before and after such a move.

L2step 1.1

2.2

A generator-addition move introduces one new generator $y$ together with a defining word $u (X)$ . To decide whether a word in the enlarged alphabet is trivial, replace each $y^{\pm 1}$ by $u (X)^{\pm 1}$ and run the original algorithm on the resulting word. The inverse generator-deletion move is the same transport in the opposite direction.

L2step 1.1algebra

3.1

Every finite Tietze chain transports a decision procedure step by step, so solvability for $P$ is equivalent to solvability for $Q$ .

step 2.1step 2.2L1∎

Depends on

Used by

FALSE: Tietze-equivalent finite presentations can differ on whether their word problem is solvable False statement

Dependency tree · two levels

13 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)