Group with solvable word problem: Difference between revisions

Latest revision as of 03:18, 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$ .
For any finite generating set there is 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	Intermediate notions
finitely generated free group			\|FULL LIST, MORE INFO
one-relator group	finitely presented with only one relation	one-relator implies solvable word problem	\|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
finitely presented residually finite group		finitely presented and residually finite implies solvable word problem	\|FULL LIST, MORE INFO
finitely presented conjugacy-separable group		(via finitely presented residually finite)	\|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
combable group			\|FULL LIST, MORE INFO
group with polynomial-time solvable word problem			\|FULL LIST, MORE INFO

Weaker properties

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

@@ Line 1: / Line 1: @@
 {{term related to|combinatorial group theory}}
+{{term related to|geometric group theory}}
 ==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>.
+# For any finite [[generating set]] there is 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 12: / Line 17: @@
 ===Stronger properties===
-* [[Weaker than::Finitely generated free group]]
+{| class="sortable" border="1"
-* [[Weaker than::Word-hyperbolic group]]
+! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
-* [[Weaker than::Group with solvable conjugacy problem]]
+|-
+| [[Weaker than::finitely generated free group]] || || || || {{intermediate notions short|group with solvable word problem|finitely generated free group}}
+|-
+| [[Weaker than::one-relator group]] || finitely presented with only one relation || [[one-relator implies solvable word problem]] || || {{intermediate notions short|group with solvable word problem|one-relator group}}
+|-
+| [[Weaker than::finitely generated abelian group]] || || || || {{intermediate notions short|group with solvable word problem|finitely generated abelian group}}
+|-
+| [[Weaker than::finitely generated nilpotent group]] || || || || {{intermediate notions short|group with solvable word problem|finitely generated nilpotent group}}
+|-
+| [[Weaker than::polycyclic group]] || || || || {{intermediate notions short|group with solvable word problem|polycyclic group}}
+|-
+| [[Weaker than::finitely presented residually finite group]] || || [[finitely presented and residually finite implies solvable word problem]]|| || {{intermediate notions short|group with solvable word problem|finitely presented residually finite group}}
+|-
+| [[Weaker than::finitely presented conjugacy-separable group]] || || (via finitely presented residually finite) || || {{intermediate notions short|group with solvable word problem|finitely presented conjugacy-separable group}}
+|-
+| [[Weaker than::word-hyperbolic group]] || || || || {{intermediate notions short|group with solvable word problem|word-hyperbolic group}}
+|-
+| [[Weaker than::automatic group]] || || || || {{intermediate notion short|group with solvable word problem|automatic group}}
+|-
+| [[Weaker than::biautomatic group]] || || || || {{intermediate notions short|group with solvable word problem|biautomatic group}}
+|-
+| [[Weaker than::group with solvable conjugacy problem]] || || || || {{intermediate notions short|group with solvable word problem|group with solvable conjugacy problem}}
+|-
+| [[Weaker than::group with a finite complete rewriting system]] || || || || {{intermediate notions short|group with solvable word problem|group with a finite complete rewriting system}}
+|-
+| [[Weaker than::combable group]] || || || || {{intermediate notions short|group with solvable word problem|combable group}}
+|-
+| [[Weaker than::group with polynomial-time solvable word problem]] || || || || {{intermediate notions short|group with solvable word problem|group with polynomial-time solvable word problem}}
+|}
 ===Weaker properties===
-* [[Stronger than::Finitely presented group]]
+{| class="sortable" border="1"
+! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
+|-
+| [[Stronger than::finitely generated group]] || || || ||
+|}