Group with solvable word problem: Difference between revisions

Revision as of 02:51, 1 February 2012

This term is related to: combinatorial group theory
View other terms related to combinatorial group theory | View facts related to combinatorial group theory

This term is related to: geometric group theory
View other terms related to geometric group theory | View facts related to geometric group theory

Definition

A group with solvable word problem is a finitely generated group $G$ satisfying the following equivalent conditions:

There is a finite generating set and an algorithm that, given any word in terms of the generators, can determine in finite time whether or not that word equals the identity element of $G$ .
There is a finite generating set and an algorithm that, given any word in terms of the generators, can determine in finite time whether or not that word equals the identity element of $G$ .
For any algebraically closed group $K$ , $G$ is isomorphic to some subgroup of $K$ .

Note that the finite time that the algorithm takes to terminate depends on the word itself. However, since the generating set is finite, there are only finitely many words of a given length, and we can hence obtain a bound on the time the algorithm takes, that depends only on the length of the word. However, that bound may not in general be a computable function of the length.

This article defines a group property: a property that can be evaluated to true/false for any given group, invariant under isomorphism
View a complete list of group properties
VIEW RELATED: Group property implications | Group property non-implications |Group metaproperty satisfactions | Group metaproperty dissatisfactions | Group property satisfactions | Group property dissatisfactions

Relation with other properties

Stronger properties

Property	Meaning	Proof of implication	Proof of strictness (reverse implication failure)	Intermediate notions
finitely generated free group				\|FULL LIST, MORE INFO
finitely generated abelian group				\|FULL LIST, MORE INFO
finitely generated nilpotent group				\|FULL LIST, MORE INFO
polycyclic group				\|FULL LIST, MORE INFO
word-hyperbolic group				\|FULL LIST, MORE INFO
automatic group				Template:Intermediate notion short
biautomatic group				\|FULL LIST, MORE INFO
group with solvable conjugacy problem				\|FULL LIST, MORE INFO
group with a finite complete rewriting system				\|FULL LIST, MORE INFO

Weaker properties

Property	Meaning	Proof of implication	Proof of strictness (reverse implication failure)	Intermediate notions
finitely generated group

@@ Line 3: / Line 3: @@
 ==Definition==
-===Symbol-free definition===
+A '''group with solvable word problem''' is a [[finitely generated group]] <math>G</math> satisfying the following equivalent conditions:
-A '''group with solvable word problem''' is a [[finitely presented group]] with a finite presentation having the following property: there is an algorithm that, given any word in the generators, can, in finite time, test whether or not that word equals the identity element of the group.
+# There is a finite [[generating set]] and an algorithm that, given any word in terms of the generators, can determine in finite time whether or not that word equals the identity element of <math>G</matH>.
+# There is a finite [[generating set]] and an algorithm that, given any word in terms of the generators, can determine in finite time whether or not that word equals the identity element of <math>G</math>.
+# For any [[algebraically closed group]] <math>K</math>, <math>G</math> is isomorphic to some [[subgroup]] of <math>K</math>.
-Note that the finite time that the algorithm takes to terminate depends on the word itself. However, since the generating set is finite, there are only finitely many words of a given length, and we can hence obtain a bound on the time the algorithm takes, that depends only on the length of the word.
+Note that the finite time that the algorithm takes to terminate depends on the word itself. However, since the generating set is finite, there are only finitely many words of a given length, and we can hence obtain a bound on the time the algorithm takes, that depends only on the length of the word. However, that bound may not in general be a computable function of the length.
+{{group property}}
 ==Relation with other properties==
@@ Line 40: / Line 44: @@
 ! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
 |-
-| [[Stronger than::Finitely presented group]] || || || ||
+| [[Stronger than::finitely generated group]] || || || ||
 |}