Free group

Last updated
Diagram showing what the Cayley graph for the free group on two generators would look like. Each vertex represents an element of the free group, and each edge represents multiplication by a or b. F2 Cayley Graph.png
Diagram showing what the Cayley graph for the free group on two generators would look like. Each vertex represents an element of the free group, and each edge represents multiplication by a or b.

In mathematics, the free groupFS over a given set S consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms (e.g. st = suu−1t, but st−1 for s,t,uS). The members of S are called generators of FS, and the number of generators is the rank of the free group. An arbitrary group G is called free if it is isomorphic to FS for some subset S of G, that is, if there is a subset S of G such that every element of G can be written in exactly one way as a product of finitely many elements of S and their inverses (disregarding trivial variations such as st = suu−1t).

Contents

A related but different notion is a free abelian group; both notions are particular instances of a free object from universal algebra. As such, free groups are defined by their universal property.

History

Free groups first arose in the study of hyperbolic geometry, as examples of Fuchsian groups (discrete groups acting by isometries on the hyperbolic plane). In an 1882 paper, Walther von Dyck pointed out that these groups have the simplest possible presentations. [1] The algebraic study of free groups was initiated by Jakob Nielsen in 1924, who gave them their name and established many of their basic properties. [2] [3] [4] Max Dehn realized the connection with topology, and obtained the first proof of the full Nielsen–Schreier theorem. [5] Otto Schreier published an algebraic proof of this result in 1927, [6] and Kurt Reidemeister included a comprehensive treatment of free groups in his 1932 book on combinatorial topology. [7] Later on in the 1930s, Wilhelm Magnus discovered the connection between the lower central series of free groups and free Lie algebras.

Examples

The group (Z,+) of integers is free of rank 1; a generating set is S = {1}. The integers are also a free abelian group, although all free groups of rank are non-abelian. A free group on a two-element set S occurs in the proof of the Banach–Tarski paradox and is described there.

On the other hand, any nontrivial finite group cannot be free, since the elements of a free generating set of a free group have infinite order.

In algebraic topology, the fundamental group of a bouquet of k circles (a set of k loops having only one point in common) is the free group on a set of k elements.

Construction

The free groupFS with free generating setS can be constructed as follows. S is a set of symbols, and we suppose for every s in S there is a corresponding "inverse" symbol, s1, in a set S1. Let T = S  S1, and define a word in S to be any written product of elements of T. That is, a word in S is an element of the monoid generated by T. The empty word is the word with no symbols at all. For example, if S = {a, b, c}, then T = {a, a1, b, b1, c, c1}, and

is a word in S.

If an element of S lies immediately next to its inverse, the word may be simplified by omitting the c, c1 pair:

A word that cannot be simplified further is called reduced.

The free group FS is defined to be the group of all reduced words in S, with concatenation of words (followed by reduction if necessary) as group operation. The identity is the empty word.

A word is called cyclically reduced if its first and last letter are not inverse to each other. Every word is conjugate to a cyclically reduced word, and a cyclically reduced conjugate of a cyclically reduced word is a cyclic permutation of the letters in the word. For instance b1abcb is not cyclically reduced, but is conjugate to abc, which is cyclically reduced. The only cyclically reduced conjugates of abc are abc, bca, and cab.

Universal property

The free group FS is the universal group generated by the set S. This can be formalized by the following universal property: given any function f from S to a group G, there exists a unique homomorphism φ: FS  G making the following diagram commute (where the unnamed mapping denotes the inclusion from S into FS):

Free Group Universal.svg

That is, homomorphisms FS  G are in one-to-one correspondence with functions S  G. For a non-free group, the presence of relations would restrict the possible images of the generators under a homomorphism.

To see how this relates to the constructive definition, think of the mapping from S to FS as sending each symbol to a word consisting of that symbol. To construct φ for the given f, first note that φ sends the empty word to the identity of G and it has to agree with f on the elements of S. For the remaining words (consisting of more than one symbol), φ can be uniquely extended, since it is a homomorphism, i.e., φ(ab) = φ(a) φ(b).

The above property characterizes free groups up to isomorphism, and is sometimes used as an alternative definition. It is known as the universal property of free groups, and the generating set S is called a basis for FS. The basis for a free group is not uniquely determined.

Being characterized by a universal property is the standard feature of free objects in universal algebra. In the language of category theory, the construction of the free group (similar to most constructions of free objects) is a functor from the category of sets to the category of groups. This functor is left adjoint to the forgetful functor from groups to sets.

Facts and theorems

Some properties of free groups follow readily from the definition:

  1. Any group G is the homomorphic image of some free group F(S). Let S be a set of generators of G. The natural map f: F(S) → G is an epimorphism, which proves the claim. Equivalently, G is isomorphic to a quotient group of some free group F(S). The kernel of φ is a set of relations in the presentation of G. If S can be chosen to be finite here, then G is called finitely generated.
  2. If S has more than one element, then F(S) is not abelian, and in fact the center of F(S) is trivial (that is, consists only of the identity element).
  3. Two free groups F(S) and F(T) are isomorphic if and only if S and T have the same cardinality. This cardinality is called the rank of the free group F. Thus for every cardinal number k, there is, up to isomorphism, exactly one free group of rank k.
  4. A free group of finite rank n > 1 has an exponential growth rate of order 2n − 1.

A few other related results are:

  1. The Nielsen–Schreier theorem: Every subgroup of a free group is free.
  2. A free group of rank k clearly has subgroups of every rank less than k. Less obviously, a (nonabelian!) free group of rank at least 2 has subgroups of all countable ranks.
  3. The commutator subgroup of a free group of rank k > 1 has infinite rank; for example for F(a,b), it is freely generated by the commutators [am, bn] for non-zero m and n.
  4. The free group in two elements is SQ universal; the above follows as any SQ universal group has subgroups of all countable ranks.
  5. Any group that acts on a tree, freely and preserving the orientation, is a free group of countable rank (given by 1 plus the Euler characteristic of the quotient graph).
  6. The Cayley graph of a free group of finite rank, with respect to a free generating set, is a tree on which the group acts freely, preserving the orientation.
  7. The groupoid approach to these results, given in the work by P.J. Higgins below, is kind of extracted from an approach using covering spaces. It allows more powerful results, for example on Grushko's theorem, and a normal form for the fundamental groupoid of a graph of groups. In this approach there is considerable use of free groupoids on a directed graph.
  8. Grushko's theorem has the consequence that if a subset B of a free group F on n elements generates F and has n elements, then B generates F freely.

Free abelian group

The free abelian group on a set S is defined via its universal property in the analogous way, with obvious modifications: Consider a pair (F, φ), where F is an abelian group and φ: SF is a function. F is said to be the free abelian group on S with respect to φ if for any abelian group G and any function ψ: SG, there exists a unique homomorphism f: FG such that

f(φ(s)) = ψ(s), for all s in S.

The free abelian group on S can be explicitly identified as the free group F(S) modulo the subgroup generated by its commutators, [F(S), F(S)], i.e. its abelianisation. In other words, the free abelian group on S is the set of words that are distinguished only up to the order of letters. The rank of a free group can therefore also be defined as the rank of its abelianisation as a free abelian group.

Tarski's problems

Around 1945, Alfred Tarski asked whether the free groups on two or more generators have the same first-order theory, and whether this theory is decidable. Sela (2006) answered the first question by showing that any two nonabelian free groups have the same first-order theory, and Kharlampovich & Myasnikov (2006) answered both questions, showing that this theory is decidable.

A similar unsolved (as of 2011) question in free probability theory asks whether the von Neumann group algebras of any two non-abelian finitely generated free groups are isomorphic.

See also

Notes

  1. von Dyck, Walther (1882). "Gruppentheoretische Studien (Group-theoretical Studies)". Mathematische Annalen . 20 (1): 1–44. doi:10.1007/BF01443322. S2CID   179178038.
  2. Nielsen, Jakob (1917). "Die Isomorphismen der allgemeinen unendlichen Gruppe mit zwei Erzeugenden". Mathematische Annalen . 78 (1): 385–397. doi:10.1007/BF01457113. JFM   46.0175.01. MR   1511907. S2CID   119726936.
  3. Nielsen, Jakob (1921). "On calculation with noncommutative factors and its application to group theory. (Translated from Danish)". The Mathematical Scientist. 6 (1981) (2): 73–85.
  4. Nielsen, Jakob (1924). "Die Isomorphismengruppe der freien Gruppen". Mathematische Annalen. 91 (3): 169–209. doi:10.1007/BF01556078. S2CID   122577302.
  5. See Magnus, Wilhelm; Moufang, Ruth (1954). "Max Dehn zum Gedächtnis". Mathematische Annalen. 127 (1): 215–227. doi:10.1007/BF01361121. S2CID   119917209.
  6. Schreier, Otto (1928). "Die Untergruppen der freien Gruppen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 5: 161–183. doi:10.1007/BF02952517. S2CID   121888949.
  7. Reidemeister, Kurt (1972 (1932 original)). Einführung in die kombinatorische Topologie. Darmstadt: Wissenschaftliche Buchgesellschaft.Check date values in: |date= (help)

Related Research Articles

Abelian group Commutative group (mathematics)

In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after early 19th century mathematician Niels Henrik Abel.

Group (mathematics) Algebraic structure with one binary operation

In mathematics, a group is a set equipped with a binary operation that combines any two elements to form a third element in such a way that three conditions called group axioms are satisfied, namely associativity, identity and invertibility. One of the most familiar examples of a group is the set of integers together with the addition operation, but groups are encountered in numerous areas within and outside mathematics, and help focusing on essential structural aspects, by detaching them from the concrete nature of the subject of the study.

Semidirect product Operation in group theory

In mathematics, specifically in group theory, the concept of a semidirect product is a generalization of a direct product. There are two closely related concepts of semidirect product:

Cyclic group Mathematical group that can be generated as the set of powers of a single element

In group theory, a branch of abstract algebra, a cyclic group or monogenous group is a group that is generated by a single element. That is, it is a set of invertible elements with a single associative binary operation, and it contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse. Each element can be written as a power of g in multiplicative notation, or as a multiple of g in additive notation. This element g is called a generator of the group.

In mathematics, a presentation is one method of specifying a group. A presentation of a group G comprises a set S of generators—so that every element of the group can be written as a product of powers of some of these generators—and a set R of relations among those generators. We then say G has presentation

In the theory of abelian groups, the torsion subgroupAT of an abelian group A is the subgroup of A consisting of all elements that have finite order. An abelian group A is called a torsion group if every element of A has finite order, and is called torsion-free if every element of A except the identity is of infinite order.

In mathematics, a free abelian group or free Z-module is an abelian group with a basis, or, equivalently, a free module over the integers. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subset such that every element of the group can be uniquely expressed as a linear combination of basis elements with integer coefficients. For instance, the integers with addition form a free abelian group with basis {1}. Free abelian groups have properties which make them similar to vector spaces. They have applications in algebraic topology, where they are used to define chain groups, and in algebraic geometry, where they are used to define divisors. Integer lattices also form examples of free abelian groups, and lattice theory studies free abelian subgroups of real vector spaces.

Glossary of group theory

A group is a set together with an associative operation which admits an identity element and such that every element has an inverse.

Module (mathematics) Generalization of vector space, with scalars in a ring instead of a field

In mathematics, a module is one of the fundamental algebraic structures used in abstract algebra. A module over a ring is a generalization of the notion of vector space over a field, wherein the corresponding scalars are the elements of an arbitrary given ring and a multiplication is defined between elements of the ring and elements of the module. A module taking its scalars from a ring R is called an R-module.

In mathematics, specifically group theory, the free product is an operation that takes two groups G and H and constructs a new group GH. The result contains both G and H as subgroups, is generated by the elements of these subgroups, and is the “universal” group having these properties, in the sense that any two homomorphisms from G and H into a group K factor uniquely through a homomorphism from GH to K. Unless one of the groups G and H is trivial, the free product is always infinite. The construction of a free product is similar in spirit to the construction of a free group.

Order (group theory)

In group theory, a branch of mathematics, the order of a group is its cardinality, that is, the number of elements in its set. If the group is seen multiplicatively, the order of an elementa of a group, sometimes also called the period length or period of a, is the smallest positive integer m such that am = e, where e denotes the identity element of the group, and am denotes the product of m copies of a. If no such m exists, a is said to have infinite order.

Finitely generated group

In algebra, a finitely generated group is a group G that has some finite generating set S so that every element of G can be written as the combination of finitely many elements of the finite set S and of inverses of such elements.

In universal algebra, a variety of algebras or equational class is the class of all algebraic structures of a given signature satisfying a given set of identities. For example, the groups form a variety of algebras, as do the abelian groups, the rings, the monoids etc. According to Birkhoff's theorem, a class of algebraic structures of the same signature is a variety if and only if it is closed under the taking of homomorphic images, subalgebras and (direct) products. In the context of category theory, a variety of algebras, together with its homomorphisms, forms a category; these are usually called finitary algebraic categories.

In mathematics, the Grothendieck group construction constructs an abelian group from a commutative monoid M in the most universal way, in the sense that any abelian group containing a homomorphic image of M will also contain a homomorphic image of the Grothendieck group of M. The Grothendieck group construction takes its name from a specific case in category theory, introduced by Alexander Grothendieck in his proof of the Grothendieck–Riemann–Roch theorem, which resulted in the development of K-theory. This specific case is the monoid of isomorphism classes of objects of an abelian category, with the direct sum as its operation.

Direct product of groups

In mathematics, specifically in group theory, the direct product is an operation that takes two groups G and H and constructs a new group, usually denoted G × H. This operation is the group-theoretic analogue of the Cartesian product of sets and is one of several important notions of direct product in mathematics.

Bass–Serre theory is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated applications of the operations of free product with amalgamation and HNN extension, via the notion of the fundamental group of a graph of groups. Bass–Serre theory can be regarded as one-dimensional version of the orbifold theory.

In the mathematical subject of group theory, the rank of a groupG, denoted rank(G), can refer to the smallest cardinality of a generating set for G, that is

In the mathematical subject of group theory, a co-Hopfian group is a group that is not isomorphic to any of its proper subgroups. The notion is dual to that of a Hopfian group, named after Heinz Hopf.

References