Skip to main content
added 72 characters in body
Source Link
Francesco Polizzi
  • 66.3k
  • 5
  • 180
  • 283

The answer isdecidability of the word problem does yesnot imply the decidability of the order problem, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

  • the word problem for $L$ is of degree $\mathbf{a};$
  • the power problem for $L$ is of degree $\mathbf{b};$
  • the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in "Word Problems, Decision Problems and the Burnside Problem in Group Theory", Studies in Logic and Fundations of Mathematics 71 (1973).

The answer is yes, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

  • the word problem for $L$ is of degree $\mathbf{a};$
  • the power problem for $L$ is of degree $\mathbf{b};$
  • the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in "Word Problems, Decision Problems and the Burnside Problem in Group Theory", Studies in Logic and Fundations of Mathematics 71 (1973).

The decidability of the word problem does not imply the decidability of the order problem, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

  • the word problem for $L$ is of degree $\mathbf{a};$
  • the power problem for $L$ is of degree $\mathbf{b};$
  • the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in "Word Problems, Decision Problems and the Burnside Problem in Group Theory", Studies in Logic and Fundations of Mathematics 71 (1973).

added 117 characters in body
Source Link
Francesco Polizzi
  • 66.3k
  • 5
  • 180
  • 283

The answer is yes, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

  • the word problem for $L$ is of degree $\mathbf{a};$
  • the power problem for $L$ is of degree $\mathbf{b};$
  • the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in "Word Problems, Decision Problems and the Burnside Problem in Group Theory", Studies in Logic and Fundations of Mathematics 71 (Word Problems), North-Holland (1973).

The answer is yes, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

  • the word problem for $L$ is of degree $\mathbf{a};$
  • the power problem for $L$ is of degree $\mathbf{b};$
  • the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in Studies in Logic and Fundations of Mathematics 71 (Word Problems), North-Holland (1973).

The answer is yes, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

  • the word problem for $L$ is of degree $\mathbf{a};$
  • the power problem for $L$ is of degree $\mathbf{b};$
  • the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in "Word Problems, Decision Problems and the Burnside Problem in Group Theory", Studies in Logic and Fundations of Mathematics 71 (1973).

Source Link
Francesco Polizzi
  • 66.3k
  • 5
  • 180
  • 283

The answer is yes, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

  • the word problem for $L$ is of degree $\mathbf{a};$
  • the power problem for $L$ is of degree $\mathbf{b};$
  • the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in Studies in Logic and Fundations of Mathematics 71 (Word Problems), North-Holland (1973).