Tour:Verifying the group axioms

From Groupprops
Revision as of 15:11, 29 July 2008 by Vipul (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

This article adapts material from the main article: verifying the group axioms

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Trivial group| UP: Introduction one (beginners)| NEXT: Understanding the definition of a group
Expected time for this page: 20 minutes
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part
PREREQUISITES: Definition of group. Review Tour:Group if you don't remember the definition clearly.
WHAT YOU NEED TO DO: Read this article carefully, keeping in mind the definition of a group. This should give you a better idea of how to verify whether a set with a given binary operation forms a group. Try applying this procedure with the examples of groups you've seen so far. (If certain techniques mentioned here use ideas you haven't yet encountered, make a note of them and proceed).


This survey article deals with the question: given a set, and a binary operation, how do we verify that the binary operation gives the set a group structure? This article views the definition of a group as a checklist of conditions.

The general procedure

Define the set and binary operation clearly

First, identify the set clearly; in other words, have a clear criterion such that any element is either in the set or not in the set. For convenience, we'll call the set G.

Second, obtain a clear definition for the binary operation. The binary operation is a map:

*:G \times G \to G

In particular, this means that:

  • g * h is well-defined for any elements g,h \in G
  • The value of g * h is again an element in G

Thus, for instance, the operation which sends real numbers x,y to x^y is not well-defined when x is negative and y is not an integer; hence, it does not qualify as a binary operation.

Verify associativity

Associativity requires one to pick three arbitrary elements g,h,k \in G, and show that:

g * (h * k) = (g * h) * k

There are various strategies for proving this:

  • If G is a finite set, this may reduce to checking it on all possible triples of elements in G
  • If * is described by means of a mathematical expression, we may be able to simplify the expressions on both sides in terms of variables g,h,k, and show that both sides are equal.
  • If G is described as a collection of maps from some set S to itself, and the binary operation in G is by composition of maps, then associativity is automatic because function composition is associative

Find an identity element

An identity element (also called neutral element)is an element e \in G such that, for all a \in G:

a * e = e * a = a

Again, we have some strategies:

  • If G is a finite set, this may reduce to checking by inspection.
  • If * is described by means of a mathematical expression, we may be able to simultaneously solve two generic equations of the form a * e = a and e * a = a. Note that we are trying to solve this as an equation in e and identity in a, i.e., it should be true for all a \in G. After solving the equation. Note further that if solving just one equation already gives a unique solution for e, we still need to check that that value of e works for the other equation as well.
  • If G is described as a collection of maps from some set S to itself, and the binary operation in G is by composition of maps, the identity element is the identity map

Find an inverse map

Next, we need to demonstrate that for every element a \in G, there exists b \in G such that:

a * b = b * a = e

Again, we have some strategies:

  • If G is a finite set, this may reduce to checking by inspection.
  • If * is described by means of a mathematical expression, we may be able to solve a generic equation of the form a* b = e for b in terms of a
  • If G is described as a collection of maps from some set S to itself, and the binary operation in G is by composition of maps, the inverse of an element is its inverse as a function

NOTE: Due to the somewhat nontrivial fact that monoid where every element is left-invertible equals group, it suffices to actually find a left inverse for every group element; if every element has a left inverse, we automatically get a two-sided inverse. Equivalently, it suffices to find a right inverse for every group element; if every element has a right inverse, we automatically get a two-sided inverse.

In some special cases

In some special cases, we can by-pass checking various conditions for being a group. We discuss two special cases here:

When the binary operation is commutative

When * is commutative, then it suffices to find a left identity element (or right identity element), and it suffices to compute just a left inverse (or just a right inverse).

Actually, even for groups in general, it suffices to find just a left inverse, due to the fact that monoid where every element is left-invertible equals group, so we don't really save anything on inverses, but we still make a genuine saving on the identity element checking.

Subset of a group

Suppose G is given to be a subset of a group K, and the binary operation on G is the restriction to G of the multiplication in K. Then:

  • We need to verify that the binary operation induces a well-defined binary operation in G: the product of two elements in G is also in G.
  • We do not need to check associativity of the binary operation, because it holds in K
  • Instead of trying to find the identity element of G, we can simply verify that the identity element in K, actually lies inside G
  • Instead of trying to compute the inverse map in G, we can simply verify that the inverse map in K, sends G to within itself.

Quotient of a group by an equivalence relation

Suppose G is obtained as the quotient of a group K by an equivalence relation. We want to see whether this equips G with the structure of a group. In this case, the only thing we need to check is that the equivalence relation is a congruence. In other words, if \sim is the equivalence relation, we need to check that:

a \sim b, c \sim d \implies ac \sim bd

Some worked-out examples

An abelian group

Here is one example. Consider G = \mathbb{R} \setminus \{ -1 \} and define, for x,y \in G:

x * y := x + y + xy

We want to show that (G,*) is a group. (Note: The group is really coming from a concrete realization of the multiplicative formal group law, but we aren't supposed to use that and instead do the proof from first principles).

Verifying that the binary operation is well-defined

First, we check the closure of G under *. Namely, we need to check that if x,y \in G then x * y \in G. Suppose not. Then, we have:

x + y + xy = - 1 \implies (x+1)(y+1) = 0

which would force either x = -1 or y = -1, a contradiction to x,y \in G.

Associativity

Next, we need to check associativity. We do this using the generic formula. We get:

(x * y) * z = (x + y + xy) + z + (x + y + xy)z = x + y + z + xy + yz + xz + xyz

and we also have:

x * (y * z) = x + (y + z + yz) + x(y + z + yz) = x + y + z + xy + yz + xz + xyz

Now, observe that * is commutative (it is symmetric in x and y). So it suffices to compute a one-sided identity element and verify the existence of one-sided inverses.

Identity element

First, we need to find the identity element. In other words, for any x \in G, we want:

x * e = x \iff x + e + xe = x \iff e (1 + x) = 0

Since x \ne -1, we get e = 0. Note that e \ne -1, so e \in G.

Inverse map

Finally, we need to compute the inverse map:

x * y = 0 \iff x + y + xy = 0 \iff y = -\frac{x}{1 + x}

This gives a formula for the inverse map. Note first that the formula makes sense, because x \ne -1, so 1 + x \ne 0. Further, the output is not -1, because solving -1 = -\frac{x}{1 + x} gives 1 = 0, a contradiction. The inverse map is thus a well defined map from G to G.

Thus, (G,*) is a group with identity element 0 and inverse map:

x \mapsto \frac{-x}{1 + x}

A group of symmetries

Here's another example. Suppose S is a finite set of points in \mathbb{R}^3. Suppose G is the set of all maps f: S \to S such that for any x,y \in S, the distance between f(x) and f(y) equals the distance between x and y. Define a binary operation in G by composition:

(f * g)(x) = (f \circ g)(x) = f(g(x))

We want to show that (G,*) is a group. Note that G is realized as a set of functions under composition.

  • Closure of G under * follows from the transitivity of the relation of distances being equal.
  • Associativity follows from the fact that function composition is associative. Explicitly:

(f * (g * h))(x) = f((g * h)(x)) = f(g(h(x)))

and similarly:

((f * g) * h)(x) = (f * g)(h(x)) = f(g(h(x)))

Since this equality holds for every x \in S, we have:

f * (g * h) = (f * g) * h

  • The identity element is the identity map from S to S. This clearly satisfies the condition for being an element of G.
  • To show that every map has an inverse, we first observe that any f:S \to S that preserves distances must be injective. That's because if f(x) = f(y), then the distance between f(x) and f(y) is zero, so the distance between x and y is zero, so x = y. Since S is a finite set, f must be bijective, so it has a unique inverse map. It is clear that this inverse map also preserves distances, so is in G.
This page is part of the Groupprops Guided tour for beginners (Jump to beginning of tour). If you found anything difficult or unclear, make a note of it; it is likely to be resolved by the end of the tour.
PREVIOUS: Trivial group | UP: Introduction one (beginners) | NEXT: Understanding the definition of a group