The Cayley graph for the free group on two generators. In Mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph that encodes the structure of a Discrete group. Each vertex represents an element of the free group, and each edge represents multiplication by a or b.

In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses (disregarding trivial variations such as st^-1 = su^-1ut^-1). Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element

A related but different notion is free abelian group. In Abstract algebra, a free abelian group is an Abelian group that has a "basis" in the sense that every element of the group can be written in

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 In Mathematics, a Fuchsian group is a particular type of group of isometries of the Hyperbolic plane. For the Mechanical engineering and Architecture usage see Isometric projection. In In an 1882 paper, Walther von Dyck pointed out that these groups have the simplest possible presentations. Walther Franz Anton von Dyck ( December 6, 1856 - November 5, 1934) was a German Mathematician. In Mathematics, one method of defining a group is by a presentation. ^[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. For other people with similar names see Jakob Nielsen. Jakob Nielsen ( October 15, 1890 – August 3, ^[2][3][4] Max Dehn realized the connection with topology, and obtained the first proof of the full Nielsen-Schreier Theorem. Max Dehn ( November 13, 1878, Hamburg, Germany – June 27, 1952, Black Mountain, North Carolina, ^[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. Otto Schreier (born March 3, 1901 in Vienna, Austria; died June 2, 1929 in Hamburg, Germany) was Kurt Werner Friedrich Reidemeister ( October 13, 1893 - July 8, 1971) was a Mathematician born in Braunschweig (Brunswick ^[7] Later on in the 1930s, Wilhelm Magnus discovered the connection between the lower central series of free groups and free Lie algebras. Wilhelm Magnus ( February 5, 1907, Berlin, Germany – October 15, 1990) was a Mathematician. In Mathematics, especially in the fields of Group theory and Lie theory, a central series is a kind of Normal series of Subgroups or In Mathematics, a free Lie algebra, over a given field K, is a Lie algebra generated by a set X, without any imposed relations

Examples

The group (Z,+) of integers is free; we can take S = {1}. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French A free group on a two-element set S occurs in the proof of the Banach–Tarski paradox and is described there. The Banach–Tarski paradox is a Theorem in set theoretic Geometry which states that a solid ball in 3-dimensional space can be split into several

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. Algebraic topology is a branch of Mathematics which uses tools from Abstract algebra to study Topological spaces The basic goal is to find algebraic In Mathematics, the fundamental group is one of the basic concepts of Algebraic topology. In Mathematics, a rose (also known as a bouquet of circles) is a Topological space obtained by gluing together a collection of circles

Construction

The free group F_S with free generating set S can be constructed as follows. S is a set of symbols and we suppose for every c in S there is a corresponding "inverse" symbol, c^-1, in S. Define a word in S to be any written product of elements of S. In Group theory, a word is any written product of group elements and their inverses The empty word is the word with no symbols at all. For example, if S = {a, a^-1, b, b^-1, c, c^-1}, then

is a word in S. If an element of S lies immediately next to its inverse, the word may be simplified by omitting the s, s^-1 pair:

A word that cannot be simplified further is called reduced. The free group F_S is defined to be the group of all reduced words in S. The group operation in F_S is concatenation of words (followed by reduction if necessary). For concatenation of general lists see Append. In Computer programming, string concatenation is the operation of joining two character The identity is the empty word.

Universal property

The free group F_S is the universal group generated by the set S. In various branches of Mathematics, certain constructions are frequently defined or characterised by an abstract property which requires the existence of a unique Morphism This can be formalized by the following universal property: given any function ƒ from S to a group G, there exists a unique homomorphism φ: F_S → G making the following diagram commute:

That is, homomorphisms F_S → G are in one-to-one correspondence with functions S → G. In various branches of Mathematics, certain constructions are frequently defined or characterised by an abstract property which requires the existence of a unique Morphism In Mathematics, given two groups ( G, * and ( H, · a group homomorphism from ( G, * to ( H, · is a function In mathematics and especially in Category theory a commutative diagram is a Diagram of objects also known as vertices, and Morphisms also For a non-free group, the presence of relations would restrict the possible images of the generators under a homomorphism. In Mathematics, one method of defining a group is by a presentation.

The above property characterizes free groups up to isomorphism, and is sometimes used as an alternative definition. In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective It is known as the universal property of free groups, and the generating set S is called a basis for F_S. In various branches of Mathematics, certain constructions are frequently defined or characterised by an abstract property which requires the existence of a unique Morphism 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 Mathematics, the idea of a free object is one of the basic concepts of Abstract algebra. Universal algebra (sometimes called general algebra) is the field of Mathematics that studies Algebraic structures themselves not examples ("models" 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. In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets In Category theory, a branch of Mathematics, a functor is a special type of mapping between categories In Mathematics, the category of sets, denoted as Set, is the category whose objects are all sets and whose Morphisms are In Mathematics, the category Grp has the class of all groups for objects and Group homomorphisms for Morphisms As such This functor is left adjoint to the forgetful functor from groups to sets. In Mathematics, in the area of Category theory, a forgetful functor is a type of Functor.

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. In Abstract algebra, a generating set of a group G is a Subset S such that every element of G can be expressed as the 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). In Mathematics, given a group G and a Normal subgroup N of G, the quotient group, or factor group, of G The kernel of f is a set of relations in the presentation of G. In Mathematics, one method of defining a group is by a presentation. 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). An abelian group, also called a commutative group, is a group satisfying the additional requirement that the product of elements does not depend on their order (the In Abstract algebra, the center of a group G is the set Z ( G) of all elements in G which commute with all the
3. Two free groups F(S) and F(T) are isomorphic if and only if S and T have the same cardinality. In Mathematics, the cardinality of a set is a measure of the "number of elements of the set" 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. In Mathematics, the phrase " up to xxxx" indicates that members of an Equivalence class are to be regarded as a single entity for some purpose
4. A free group of finite rank n > 1 has an exponential growth rate of order 2n − 1. Exponential growth (including Exponential decay) occurs when the growth rate of a mathematical function is proportional to the function's current value In Group theory, the growth rate of a group with respect to a symmetric Generating set describes the size of balls in the group

A few other related results are:

1. The Nielsen–Schreier theorem: Any subgroup of a free group is free. For other people with similar names see Jakob Nielsen. Jakob Nielsen ( October 15, 1890 – August 3, Otto Schreier (born March 3, 1901 in Vienna, Austria; died June 2, 1929 in Hamburg, Germany) was In Group theory, given a group G under a Binary operation * we say that some Subset H of G is a subgroup of
2. A free group of rank k clearly has subgroups of every rank less than k. Less obviously, a free group of rank greater than 1 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 [a^m, bⁿ] for non-zero m and n. In Mathematics, more specifically in Abstract algebra, the commutator subgroup or derived subgroup of a group is the Subgroup In Mathematics, the commutator gives an indication of the extent to which a certain Binary operation fails to be Commutative.
4. The free group in two elements is SQ universal; the above follows as any SQ universal group has subgroups of all countable ranks. In Mathematics, in the realm of Group theory, a Countable group is said to be SQ universal if every countable group can be embedded in one of
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). In Algebra and Geometry, a group action is a way of describing symmetries of objects using groups. In Algebra and Geometry, a group action is a way of describing symmetries of objects using groups. In Mathematics and Computer science, a graph is the basic object of study in Graph theory. In Mathematics, and more specifically in Algebraic topology and Polyhedral combinatorics, the Euler characteristic is a Topological invariant In Algebra and Geometry, a group action is a way of describing symmetries of objects using groups. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects
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. In Mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph that encodes the structure of a Discrete group. In Graph theory, a tree is a graph in which any two vertices are connected by exactly one path.

Free abelian group

Further information: 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 φ: S → F is a function. In Abstract algebra, a free abelian group is an Abelian group that has a "basis" in the sense that every element of the group can be written in F is said to be the free abelian group on S with respect to φ if for any abelian group G and any function ψ: S → G, there exists a unique homomorphism f: F → G 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 Mathematics, more specifically in Abstract algebra, the commutator subgroup or derived subgroup of a group is the Subgroup 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. Alfred Tarski ( January 14, 1901, Warsaw, Russian ruled Poland – October 26, 1983, Berkeley California In Mathematics, model theory is the study of (classes of mathematical structures such as groups, Fields graphs or even models In Logic, the term decidable refers to the existence of an Effective method for determining membership in a set of formulas 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 (in 2008) question in free probability theory asks whether the von Neumann group algebras of any two non-abelian finitely generated free groups are isomorphic. Free probability is a mathematical theory which studies Non-commutative Random variables The "freeness" property is the analogue of the classical In Mathematics, a von Neumann algebra or W*-algebra is a *-algebra of bounded operators on a Hilbert space that is closed in the

Notes

References

• Kharlampovich, Olga & Myasnikov, Alexei (2006), “Elementary theory of free non-abelian groups”, J. Algebra 302 (2): 451-552, MR2293770, DOI doi:10. Mathematical Reviews is a journal and online database published by the American Mathematical Society that contains brief synopses (and occasionally evaluations of many 1016/j. jalgebra. 2006. 03. 033 
• W. Magnus, A. Karrass and D. Solitar, "Combinatorial Group Theory", Dover (1976).

• Sela, Z. (2006), “Diophantine geometry over groups. VI. The elementary theory of a free group. ”, Geom. Funct. Anal. 16 (no. 3): 707-730, MR2238945 
• J. Mathematical Reviews is a journal and online database published by the American Mathematical Society that contains brief synopses (and occasionally evaluations of many -P. Serre, Trees, Springer (2003) (english translation of "arbres, amalgames, SL₂", 3rd edition, astérisque 46 (1983))

See also

• Cayley graph
• Generating set of a group
• Presentation of a group