Orbit-Stabilizer Theorem

There are a lot of things about group theory that we can prove through group actions. We could take that route if we wanted, but I'm not going to do that now. For now, though, I'm going to prove a result of group actions, called the Orbit-Stabilizer Theorem. On the list of important theorems in group theory the Orbit-Stabilizer Theorem isn't very high, but it does have its usefullness and it is an interesting and unexpected result. I'm now going to state the theorem and then spend the rest of the entry proving it.

Theorem:Orbit-Stabilizer Theorem

Suppose that a group, $G$, acts on a set, $S$, and that $i \in S$. Then $\left | G \right | = \left | \text{orb}_G(i) \right | \left | \text{stab}_G(i) \right |$.

Proof:

Let $G$ be a group acting on a set, $S$, and choose $i \in S$. Since $\text{stab}_G(i)$ is a subgroup of $G$, Lagrange's Theorem gives us that $\left | G / \text{stab}_G(i) \right | = \left | G \right | / \left | \text{stab}_G(i) \right |$, or that $\left | G \right | / \left | \text{stab}_G(i) \right |$ is the number of distinct left cosets of $\text{stab}_G(i)$ in $G$. I now wish to extablish a bijection between the left cosets of $\text{stab}_G(i)$ and the elements of $\text{orb}_G(i)$.

Define $\theta : G/\text{stab}_G(i) \to \text{orb}_G(i)$ by $\theta(g \; \text{stab}_G(i)) = g \cdot i$ for $g \; \text{stab}_G(i) \in G/\text{stab}_G(i)$. It is clear that $g \cdot i$ is in $\text{orb}_G(i)$ but it is not clear that $\theta$ is well defined - that is that the image of $\theta$ is independent of the choice of coset representative meaning that if $H \in G/\text{stab}_G(i)$ and $g,h \in H$ then $\theta ( g \; \text{stab}_G (i) ) = \theta ( h \; \text{stab}_G (i) )$.

To show that $\theta$ is well-defined, suppose that $g \; \text{stab}_G(i) = h \; \text{stab}_G(i)$ for $g,h \in G$. Then from our properties of cosets we have that $g^{-1} h \in \text{stab}_G(i)$ which means that $\left ( g^{-1} h \right ) \cdot i = i$ so that $g \cdot i = h \cdot i$. We now have that $g \; \text{stab}_G(i) = h \; \text{stab}_G(i)$ implies $\theta ( g \; \text{stab}_G (i) ) = \theta ( h \; \text{stab}_G (i) )$. Thus $\theta$ is well-defined.

To show that $\theta$ is injective we can use the reverse of the previous argument. Indeed, suppose that $g \cdot i = h \cdot i$ for $g,h \in G$. We then have that $\left ( g^{-1} h \right ) \cdot i = i$ so that $g^{-1} h \in \text{stab}_G(i)$ and by the properties of cosets, $g \; \text{stab}_G(i) = h \; \text{stab}_G(i)$. This gives that $\theta$ is injective.

To show that $\theta$ is surjective, choose $j \in \text{orb}_G(i)$. By definition, $\exists g \in G$ such that $g \cdot i = j$ and so clearly $\theta (g \; \text{stab}_G(i) ) = g \cdot i = j$. This gives that $\theta$ is surjective and finally that $\theta$ is bijective.

Since $\theta$ is a bijection, we have that $\left | G/\text{stab}_G(i) \right | = \left | \text{orb}_G(i) \right |$ and so $\left | G \right | / \left | \text{stab}_G(i) \right | = \left | \text{orb}_G(i) \right |$ and finally $\left | G \right | = \left | \text{orb}_G(i) \right | \left | \text{stab}_G(i) \right |$ as desired.

This is an interesting theorem since it does not seem at first glance like orbits and stabilizers should be related to one another.

References

Previous Related Post: Group Action Attributes

Text Reference: Gallain Chapter 7

Wikipedia: Group Action - Orbits and Stabilizers

Group Action Attributes

This is going to be a rather boring post. There are a few definitions that I need to get out of the way. After we get done with group actions I'm going to put group theory on hold for a while so that I can go through a crash course in linear algebra (and maybe start some topology) but later, when we revisit group theory, we're going to learn about representations and characters (which need linear algebra, hence the break) and at that point we'll need group actions and the definitions that I'm going to introduce here.

Kernel

We've already defined the kernel of a homomorphism and the kernel of a group action is very similar.

Definition:Kernel of an Action

Let $G$ be a group and $S$ a set and suppose $G$ acts on $S$. We call the kernel of the action the set of all elements in $G$ that fix every element of $S$, or $\left \{ g \in G : g \cdot \alpha = \alpha \; \forall \alpha \in S \right \}$.

This definition actually would have been unnecessary if we'd defined group actions in a different way. I didn't do it this way, but an equivalent definition of a group action of $G$ on $S$ would have been a homomorphism $\theta : G \to Perm \left( S \right )$ where $Perm \left( S \left)$ is the group of all permutations on the set, $S$. Then the kernel of the group action is equal to the kernel of $\theta$.

However, since we didn't define a group action as a homomorphism (in hindsight, maybe I should have but what do we do), the definition of a kernel needs some explanation. When a group element, $g \in G$, acts like the identity element on a particular set element, $s \in S$, in that $g \cdot s = s$ we say that $g$ fixes $s$. The kernel of the action is then the set of every group element that fixes every set element. In general, when we talk about the kernel of anything, what we mean is all the elements of a group that work like the identity element in a certain context, and this is the same for group actions.

Orbits and Stabilizers

The next two definitions introduce two important sets, the orbit and stabilizer of a set element. I'm going to spoil a surprise, but there's a cool theorem that we're going to learn soon called the Orbit Stabilizer Theorem which says that if $G$ acts on $S$ and $s \in S$ then $\left | G \right | = \left | \text{orb}_G \left ( s \right ) \right | \left | \text{stab}_G \left ( s \right ) \right |$.

Definition:Orbit

Let $G$ be a group and $S$ a set and suppose $G$ acts on $S$. Then if $s \in S$ we define the orbit of $s$ by $\text{orb}_G \left(s \right ) = \left \{ g \cdot s : g \in G \right \}$.

It might not be obvious from the definition, but $\text{orb}_G \left ( s \right )$ is actually a subset of $S$. Here's the way I think of it - if $s \in S$ then the orbit of $s$ is all of the elements of $S$ that you can get to using any element of $G$. More technically, as the definition says, the orbit is the set of all $g \cdot s$ where $g \in G$.

As it turns out, the orbits are a partition of $S$. It should be clear that $s \in \text{orb}_G \left ( s \right )$ since $e \cdot s = s$ so every orbit is non-empty. We also get that if $t \in \text{orb}_G \left ( s \right )$ then $\text{orb}_G \left ( s \right ) = \text{orb}_G \left ( t \right )$ (which is less clear but not so hard to prove). This gives us that each element of $S$ belongs to one and only one orbit, meaning that we have our partition.

The partition helps to explain the term "orbit." The orbits are isolated and if you start at $s$ and walk your way through $\text{orb}_G \left ( s \right )$ using the elements of $G$, you'll eventually get back to $s$.

Definition:Stabilizer

Let $G$ be a group and $S$ a set and suppose $G$ acts on $S$. Then if $s \in S$ we define the stabilizer of $s$ by $\text{stab}_G \left( s \right ) = \left \{ g \in G : g \cdot s = s \right \}$.

Orbits were subsets of $S$, but stabilizers are subsets of $G$. When we defined kernels, we defined them as all of the elements of $G$ that fix every single element of $S$ and stabilizers are similar in that the stabilizer of a particular element, $s \in S$ is the set of elements of $G$ that fix $s$.

Suppose $K$ is the kernel of the action. Based on the definitions, we get that $K \subseteq \text{stab}_G (s)$ for each $s \in S$. In fact, it is not hard to prove that

\[ K = \bigcap_{s \in S} \text{stab}_G (s) \]

and its also easy to prove that stabilizers are in fact subgroups of $G$.

Faithful and Transitive Actions

Shortly after we defined groups we defined all sorts of adjectives that we can use to describe groups like abelian, finite, and cyclic, and each of these adjective serve to add some extra axioms to our definition of a group. I'm now going to define some adjectives that we can use to add some extra axioms to the definition of group actions.

Definition:Faithful

Let $G$ be a group and $S$ a set and suppose $G$ acts on $S$. Then the action is called faithful if the kernel of the action is the trivial subgroup.

You can notice that the trivial action that we defined in the last entry is the opposite of faithful. The trivial action defines every element of the group to fix every element of the set so the kernel of the trivial action is the entire group. It turns out that the kernel of an action serves as a sort of measurement as to the triviality of the action which is meaningful since we learned that every group acts on every set. A small kernel means that the action is interesting and a large kernel gives us that the action is less inventive. When an action is faithful we know that we're dealing with a "good" action.

Definition:Transitive

Let $G$ be a group and $S$ a set and suppose $G$ acts on $S$. Then the action is called transitive if it has only one orbit.

We noted earlier that orbits form a partition of $S$. In transitive actions, this the orbits form the most boring possible partition in that there is only one orbit and $\text{orb}_G (s) = \text{orb}_G (t)$ for every $s,t \in S$. This may seem kind of unfortunate, but actually its very cool and useful. If an action is transitive then for any $s$ and $t$ in $S$ there is some $g \in G$ such that $g \cdot s = t$, which is useful from time to time.

References

Previous Related Post: Group Action Examples

Text Reference: Gallain Chapter 7

Wikipedia: Group Action

Wolfram Mathworld: Group Orbit

Wolfram Mathworld: Stabilizer

Wolfram Mathworld: Faithful Group Action

Wolfram Mathworld: Transitive Group Action

Group Action Examples

Now that we know about group actions, I'm going to give a few examples of some of the more important group actions. I'm not going to prove all of them, but its a good exercise to prove them yourself if you're feeling ambitious.

Example:Trivial Action

Consider any group, $G$, and any set, $S$. Define the binary operation $G \times S \to S$ by $g \cdot s = s$ for $g \in G$ and $s \in S$. Then this operation defines a group action of $G$ on $S$ called the trivial action.

The trivial action is the most boring action that there is, but it is a group action. We don't really get anything exciting from the trivial action, except that it serves to show that any group acts on any set, which further emphasizes the fact that an action of a group on a set is defined by the particular operation.

In the last post, I mentioned that there were two important actions of groups on themselves, which I will give below. These actions are confusing to define, though, because the "group" and the "set" from the definition of group actions are the same thing.

Example:Regular Action of G

Let $G$ be any group and let $S = G$. Define the binary operation $G \times S \to S$ by $g \cdot s = g s$ for $g \in G$ and $s \in S$ where $g s$ is computed according to the operation of $G$ (which is legal since $S = G$). This operation defines a group action of $G$ on itself called the left regular action.

This is kind of the second most boring action we can define after the trivial action. It is a group action because it follows the rules of group actions, but its a really obvious group action. It may not seem like this is a useful thing to do because the regular action does not work any differently than the standard group operation. However, soon we're going to derive some useful theorems about group actions and the fact that the group operation defines a group action means that the theorems about group actions also apply to the group operation. The next action, though, is more interesting.

Example:Conjugation Action

Let $G$ be any group and let $S = G$. Define the binary operation $G \times S \to S$ by $g \cdot s = s g s^{-1}$ for $g \in G$ and $s \in S$ where $s g s^{-1}$ is computed according to the operation of $G$ (which is legal since $S = G$). This operation defines a group action of $G$ on itself and is called conjugation.

Proof:

Choose $g,h \in G$ and $x \in S$. Then we have

\[ (g h) \cdot x = (g h) x (g h)^{-1} = g h x h^{-1} g^{-1} = g (h \cdot x) g^{-1} = g \cdot (h \cdot x) \]

so that $(g h) \cdot x = g \cdot (h \cdot x)$.

Choose $x \in S$. Since $x \in S$ then we clearly have that $e \cdot x = e x = x$ by the definition of $e$.

Both of the conditions of a group action are satisfied, so the operation is a group action.

This conjugation action is very important. I don't want to underplay this. The conjugation action is extremely important. The conjugation action is important in the same way that LeBron James is important to the Cavaliers chances at an NBA title. The conjugation action is important in the same way that the Beatles and Elvis helped the success of rock music. I can't exactly explain why this is yet because we don't have the theorems, but as a sneak peak, conjugation partitions groups similar to the partition that we get from cosets except in a more interesting way. In the next few posts we'll learn some things that will help us eventually work some serious magic on the conjugation action.

I've got one last example that I'm going to throw in for fun, although it doesn't get used all that often.

Example:

Let $G$ be a group and suppose $N \triangleleft G$. For the purpose of this example, $G/N$ is going to be the set. Define the binary operation $G \times G/N \to G/N$ by $g \cdot h N = (g h) N$ for $g \in G$ and $h N \in G/N$. This operation defines a group action of $G$ on $G/N$.

Hopefully the examples cleared up group actions a little. Next we're going to learn about some of the various properties of group actions

References

Previous Related Post: Group Actions

Text Reference: Gallain Chapter 7 and Chapter 29

Wikipedia: Group Action

Wolfram Mathworld: Trivial Group Action

Wolfram Mathworld: Faithful Group Action

Group Actions

We're finally going to get back to some group theory today. Group actions give us ways for potentially unrelated things to interact with each other. If $G$ is a group and $S$ is any arbitrary set then a group action gives a way to combine an element of the group and an element of a set - that is if $g \in G$ and $s \in S$ then group actions define $g \cdot s$. The question, now, is what sort of thing should $g \cdot s$ equal? More specifically, should $g \cdot s$ equal an element of $S$ or an element of $G$? The way it works out is that it makes much more sense to make this operation map to an element of $S$.

Before I write out the definition (which is right below) I want to talk about some of the language used in the definition. The definition is going to talk about a binary function $G \times S \to S$ denoted by $\left ( g , s \right ) \mapsto g \cdot s$. We've seen lots of binary operations before, we just haven't called them that - the term "binary" tells us that the function needs two elements. Then the notation $G \times S$ means that the two elements we need are an element of $G$ and an element of $S$ (in that order) and the notation $\to S$ means that these two elements are mapped to an element of $S$. The last part of the notation just tells us how two write down this operation. If $g \in G$ and $s \in S$ then this binary function maps $G \times S$ to an element of $S$ that we denote by $g \cdot s$.

I think we are now ready to define group actions.

Definition:Group Action

If $G$ is a group and $S$ is a set then a group action of $G$ on $S$ is a binary function $G \times S \to S$ denoted by $\left ( g , s \right ) \mapsto g \cdot s$ that satisfies the following two axioms:

• $\left ( g h \right ) \cdot s = g \cdot \left ( h \cdot s \right ) \; \forall g,h \in G \; \text{and} \; \forall s \in S$
• $e \cdot s = s \; \forall s \in S$

If there exists a group action of $G$ on $S$ then we say that $G$ acts on $S$ and we call $S$ a $G$-set.

The definition of a group action tells us the rules that the operation must follow, but it doesn't tell us what this operation does or how exactly it maps the elements. This is okay, though, because when you start with a group, $G$, and a set, $S$, and you want to define a group action of $G$ on $S$, you need to specify and define the particular operation that you claim creates a group action and then show that it follows the rules in the definition. The best way to see how these group actions really work is through an example, and shown below is maybe the most "natural" example of a group action.

Example:S_n acts on Ω_n

Choose $n \in \mathbb{N}$ and consider the group $S_n$ and the set $\Omega_n$. Define the binary operation $S_n \times \Omega_n \to \Omega_n$ by $\pi \cdot k = \pi(k)$ for $\pi \in S_n$ and $k \in \Omega_n$. Let $\epsilon$ be the identity element of $S_n$. Now, observe the following:

• Choose $\pi,\tau \in S_n$ and $k \in \Omega_n$. Then
  \[ \left ( \pi \tau \right ) \cdot k = \left ( \pi \circ \tau \right )\left (k\right ) = \pi \left (\tau (k) \right ) = \pi \left (\tau \cdot k \right ) = \pi \cdot \left ( \tau \cdot k \right ) \]
  so that we have $\left ( \pi \tau \right ) \cdot k = \pi \cdot \left ( \tau \cdot k \right )$ and the first condition is satisfied.
• Choose $k \in \Omega_n$. Then $\epsilon \cdot k = \epsilon \left ( k \right ) = k$ so that $\epsilon \cdot k = k$ and the second condition is satisfied.
Thus this operation defines an action of $S_n$ on $\Omega_n$.

You can see how in the example with the symmetric groups, the action is extremely natural and, in fact, the definition of the symmetric group is basically built to support the action of $S_n$ on $\Omega_n$. Below gives another extremely natural example of a group action, but it requires some linear algebra, so if you haven't had any experience with matrix multiplication feel free to skip it.

Example:GL(n,R) acts on Rⁿ

Choose $n \in \mathbb{N}$, let $GL \left ( n,\mathbb{R} \right )$ be the general linear group over $\mathbb{R}$, and consider $\mathbb{R}^n$, the standard $n$-dimensional vector space over $\mathbb{R}$. Define the binary operation $GL \left ( n,\mathbb{R} \right ) \times \mathbb{R}^n \to \mathbb{R}^n$ by $M \cdot \mathbf{v} = M \mathbf{v}$ for $M \in GL \left ( n,\mathbb{R} \right )$ and $\mathbf{v} \in \mathbb{R}^n$ where $M \mathbf{v}$ represents standard matrix multiplication. Recall that the identity matrix, $I_n$, is the identity element of $GL \left ( n,\mathbb{R} \right )$ and observe the following:

• Choose $M,N \in GL \left ( n,\mathbb{R} \right )$ and $\mathbf{x} \in \mathbb{R}^n$. By definition, matrix multiplication is associative, so
  \[ \left ( M N \right ) \cdot \mathbf{x} = \left ( M N \right ) \mathbf{x} = M \left ( N \mathbf{x} \right ) = M \left ( N \cdot \mathbf{x} \right ) = M \cdot \left ( N \cdot \mathbf{x} \right ) \]
  and we have that $\left ( M N \right ) \cdot \mathbf{x} = M \cdot \left ( N \cdot \mathbf{x} \right )$ so the first condition is satisfied.
• Choose $\mathbf{x} \in \mathbb{R}^n$. Then we have $I_n \cdot \mathbf{x} = I_n \mathbf{x} = \mathbf{x}$ so that $I_n \cdot \mathbf{x} = \mathbf{x}$ and the second condition is satisfied.

Thus this operation defines an action of $GL \left ( n,\mathbb{R} \right )$ on $\mathbb{R}^n$.

The definition of a group action says that if $G$ acts on $S$ then $G$ must be a group but $S$ can be any arbitrary set. In the last example, the set was $\mathbb{R}^n$ which is a group (under vector addition) which is perfectly fine and actually happens a lot. In fact, we use actions of groups on themselves quite a bit - there are two important ones that we'll explore soon.

Group actions crop up a lot and get us a lot of fun properties that we'll keep exploring in future posts.

References

Previous Related Post: More About Homomorphisms

Text Reference: Gallain Chapter 29

Wikipedia: Group Action

Wolfram: Group Action

Planet Math: Group Action

Hairy-Ball Theorem

I've been getting a lot of questions from readers as to whether the Hairy-Ball Theorem is actually a real thing - or, more to the point, whether its a real thing that is actually useful or if its just an obscure theorem with a funny name. Well, not only is it useful, but its actually quite cool.

Theorem:Hairy-Ball Theorem

Let $n$ be an odd integer and let $S$ be the $n-1$ dimensional unit sphere in $\mathbb{R}^n$. If $V:S \to \mathbb{R}^n$ is a continuous tangent vector field then $V(p) = \mathbf{0}$ for some $p \in S$.

So, that's confusing, right? The theorem talks about even dimensional unit spheres, right? Well, lets just think about the regular two-dimensional sphere. I don't mean two-dimensional as in flat and fits on a piece of paper, I mean the surface of a soccer-ball or something. We can also define it as the set of all points in $\mathbb{R}^3$ such that they are a distance of $1$ away from the origin, or $S = \left \{ \left ( a,b,c \right ) \in \mathbb{R}^3 : \sqrt{a^2 + b^2 + c^2} = 1 \right \}$. Now we let $V:S \to \mathbb{R}^n$ be some continuous tangent vector field. By tangent, I mean that if $p \in S$ is some point on the sphere and $V(p) = \mathbf{v}$ then $\mathbf{v}$ lies tangent to $S$ at the point $p$. So then $V$ places a vector on every point of the sphere such that the vectors are all tangent to the sphere and $V$ must be continuous - the continuity of $V$ is actually very important.

Now, the Hairy-Ball Theorem tells us that no matter how we pick the vectors on the sphere (that is for any continuous tangent vector field, $V$) there has to be a zero vector somewhere on the sphere. That's very cool and not very obvious. As it turns out, if your surface is a doughnut instead of a sphere, its very easy to form a continuous tangent vector field that doesn't have a zero. Then, once you have the Hairy-Ball Theorem, some topology gets you that every two-dimensional differentiable manifold that's homeomorphic to a sphere also has the property that continuous tangent vector fields must vanish somewhere, and there are a lot of two-dimensional differentiable manifolds that are homeomorphic to a sphere.

I kind of glossed over everything, so if you want a little more info on the Hairy-Ball Theorem, the wikipedia page that I put in the references is pretty good. Also, I had every intention of proving it, but in the course of researching it I found someone that had written up basically the exact proof that I would have given, so instead of retyping it I put it in the references. Don't worry if you don't understand it - it takes some real analysis (surprisingly it only takes real analysis) that we haven't touched.

References

Wikipedia: Hairy-Ball Theorem

Topological Musings: Proof of the Hairy-Ball Theorem

More Layout

I'm going to change my formatting a little bit just for fun. I'm going to start formatting my theorems, definitions, and examples as shown in the theorem below except that the colors will be the same as always.

Theorem:Uniqueness of Inverses

If G is a group, then ∀a∈G there is a unique a^-1∈G such that a∙a^-1 = e = a^-1∙a where e is the identity of G.

Also, proofs look like the following.

Proof:

Choose an element a∈G. From the definition of a group there exists at least one inverse of a. To show that the inverse is unique, suppose that both b and c are inverses of G. Then a∙b = e and a∙c = e so a∙b = a∙c and canelation gives us that b = c so the inverse of a is unique, as desired.

If the theorem and proof aren't formatted as in the images below (except for maybe the size), you should let me know. I checked them in Chrome, Firefox, Internet Explorer, Safari, and Opera, but if you have an issue let me know so I can check it out. Also, if you use Lynx, I don't care what it all looks like.

I'm hoping it gives the visual distinction that I'm looking for with a little more readability.

Connecting Algebra and Numbers

In the last two entries, we've seen some of the most common number systems and the rules that each of them get us, and then some of the more common algebraic structures. Now we'll talk a little about how they fit together and along the way we'll learn a little bit more about algebra.

Before this mathematical adventure, there is something worth mentioning, and that is that we're looking for the exact algebraic structure to describe each number system. What I mean is that, as an example, the integers are both a group and a ring, but neither of those structures fully describe all of the algebraic properties that we get from the integers. Ideally we could find the exact list of properties that describe everything that we get to do in each number system, which is what I will now venture to do.

Natural Numbers

Our smallest number system that we had was the natural numbers. Now the natural numbers have both addition and multiplication which suggests the structure of a ring, but they don't have any inverses, so they're not even a group. We do have a structure for groups without inverses, and its called a monoid.

Definition: Monoid
Let $M$ be a set and let $\cdot$ be a binary operation defined on the elements of $M$. Then $M$ is a monoid if it satisfies the following three axioms:

Closure

$a \cdot b \in M \; \forall a,b \in M$

Associativity

$\left ( a \cdot b \right ) \cdot c = a \cdot \left ( b \cdot c \right ) \; \forall a,b,c \in M$

Identity

$\exists e \in M \; \text{such that} \; a \cdot e = a = e \cdot a \; \forall a \in M$

A monoid with the additional condition of commutivity is called a commutative monoid.

The natural numbers are indeed a monoid, but it turns out that they're a monoid under both addition and multiplication and we still have the distributive laws in the natural numbers. In fact, the natural numbers look just like a ring except they have a multiplicative identity and lack additive inverses. This algebraic concept is called a semiring.

Definition: Semiring
Let $S$ be a set and let $+$ and $\cdot$ be different binary operations on $S$ (called addition and multiplication) such that $S$ is a monoid under both addition and multiplication. Then $S$ is a semiring if it satisfies the following axioms in addition to the additive and multiplicative monoid axioms:

Additive Commutivity

$a + b = b + a \; \forall a,b \in S$

Left Distribution

$a \cdot \left ( b + c \right ) = \left ( a \cdot b \right ) + \left ( a \cdot c \right ) \; \forall a,b,c \in S$

Right Distribution

$\left ( a + b \right ) \cdot c = \left ( a \cdot c \right ) + \left ( b \cdot c \right ) \; \forall a,b,c \in S$

Annihilation

$0 \cdot a = 0 = a \cdot 0 \; \forall a \in S$

A semiring with the additional condition of multiplicative commutivity is called a commutative semiring.

The natural numbers form the stereotypical commutative semiring. This is not a common algebraic structure. You find group theorists in the world, you find people that spend their lives studying rings, and there are plenty of people that love fields because they need them for vector spaces or modules or algebras or plenty of other things. To my knowledge, there are not hoardes of people who dedicate their time to the mathematical advances of the semiring. We just don't get nearly as much usefulness out of semirings as we do from some of the other algebraic structures.

Integers

The integers form a ring. No long suspensful introduction or lengthy suspense this time, the integers form a ring. But wait, there's more! The integers aren't just a ring, they get some bonus properties. I mention first that they're a ring because they are actually very close to a ring and they are one of the first and best examples that you get of a ring. However, the integers are also commutative, they have a multiplicative identity, and they get one extra unexpected property. This structure is called an integral domain.

Definition: Integral Domain
Let $R$ be a commutative ring. Then $R$ is an integral domain if it follows the following axioms in addition to the ring axioms:

Multiplicative Identity (Unity)

$\exists 1 \in R \; \text{such that} \; 1 \neq 0 \; \text{and} \; a \cdot 1 = a = 1 \cdot a \; \forall a \in R$

No Zero Divisors

$\forall a,b \in R \; a \cdot b = 0 \; \text{implies that either} \; a = 0 \; \text{or} \; b = 0$

Integral domains are the structure that get us the exact properties of the integers. It is, in fact, that last property regarding zero divisors that generally defines integral domains - without it we would describe $R$ as "a commutative ring with unity." In fact, in many books that need rings but don't explicitly study rings, there is a sentence in the beginning that says something to the effect of "for the remainder of this text every ring will be assumed to be a commutative ring with unity." My point is to greatly emphasise here the importance of this final property. It may seem obvious, and it is obvious when regarding the numbers that we've used since we were five years old, but in arbitrary rings it is not obvious. As an example, suppose we're considering $\mathbf{Z}_p$ and we want to define multiplication similarly to the way we define addition - that is $a \cdot b = a \cdot p \; \text{mod p}$. Then in $\mathbf{Z}_8$ we have that $2 \cdot 4 = 0$ but there are no two non-zero numbers in $\mathbf{Z}_7$ that multiply to zero. That is the property that is really of interest in an integral domain.

Rational, Real, and Complex Numbers

Believe it or not, from an algebra standpoint there's no difference between the rational and real numbers. Topologists know the difference and analysts definitely know the difference, but even the most well-trained algebraist can only barely tell the difference between the real numbers and the rational numbers. If you remember, the bonus that we get from the reals is that all sequences in $\mathbf{R}$ converge in $\mathbf{R}$ but sequences and convergence is not really a concern in the world of algebra. The reals are "larger" than the rationals, as we've already seen, in that the rationals are countable and the reals are uncountable and there are times when this fact concerns a diligent algebraist, but in fact they are both identical in algebraic structure. That structure is the structure of a field. Both the real numbers and the rational numbers have the exact algebraic structure of a field.

The complex numbers also form a field, but as you probably guessed, they have exactly one extra property that turns out to be extremely important.

Definition: Algebraically Closed Field
A field, $F$, is algebraically closed if every polynomial with one variable of degree at least 1 with coefficients in $F$ has a root in $F$.

Consider the polynomial $p \left ( x \right ) = x^2 + 1$. The coefficients of $p$ live in any of the number systems that we've discussed so far, but as we may remember from calculus, there is no real number that is a root of $p$, but there are two complex numbers - namely $i$ and $-i$ - that are roots of $p$. As it turns out any polynomial

\[ p \left ( x \right ) = \sum_{k=0}^{n} \alpha_k x^k \]

of degree $n \geq 1$ with $\alpha_k \in \mathbf{C}$ has some root in $\mathbf{C}$. This is not true, though, in fields that are not algebraically closed like $\mathbf{R}$ and $\mathbf{Q}$.

Other Thoughts

There's a lesson to be learned here. We have all sorts of obvious uses for all of the various number systems that we have in calculus and analysis and topology and all sorts of other places and we have developed some algebraic language and ideas with which to talk about the most common numeric universes. It is obvious, though, that the most common algebraic structures don't really represent our number systems very well, which further justifies the study of algebra because the things that are accurately represented by algebraic structures cannot accurately be represented by the numbers that we've studied since the dawn of mathematics.

I should also mention that, as strange as it seems, all these definitions aren't necessarily concrete. Authors sometimes define things slightly differently depending on what they plan on doing with their structures. For example, semirings aren't always defined with either identity elements because that makes the analogy betweem ring:semiring and group:semigroup more accurate (even though we didn't define a semigroup). The definition of a ring can also sometime include an identity element. I know its confusing and sort of counter-intuitive to the rigidity of mathematics, but usually the context makes it clear.

This is a blog about algebra (for now at least), so I don't expect that my readers are worrying that I'll start a rigorous study calculus after glossing over the real numbers. On the other hand, I introduced rings, fields, monoids, semirings, integral domains, and algebraically closed fields without really explaining them or giving examples or anything. Don't feel too guilty if you don't understand how any of those things work - I don't plan on delving into the inner workings of any of these structures any time soon and if I do, I promise to reintroduce them later.

References

Previous Related Post: Algebraic Structures

Wikipedia: Monoid

Wikipedia: Semiring

Wikipedia: Integral Domain

Wikipedia: Algebraically Closed Field

Algebraic Structures

To this point in the blog, most of the work has been concentrated on group theory, but really there are a lot of algebraic structures. What differentiates algebraic structures are the axioms (or rules) that we used to define them. The definition of a group provided four axioms - closure, associativity, identity, and inverses - and every other algebraic structure is defined similarly. Really, you can start with an arbitrary set and define any axioms that you want on the set and work with it and see where you get, and abstract algebra does just that but with the most useful and lucrative sets of axioms.

In my opinion, there are three important elementary algebraic structures, which are groups, rings, and fields. I'm going to define them and discuss some examples, but I'm not going to work through them as rigorously as we've covered groups - at least not yet.

Groups

We've already discussed groups in depth, but for reference I'm going to include a more formal definition below.

Definition: Group
Let $G$ be any set and let $\cdot$ be a binary operation defined on the elements of $G$. Then $G$ is a group if it satisfies the following four axioms:

Closure

$a \cdot b \in G \; \forall a,b \in G$

Associativity

$\left ( a \cdot b \right ) \cdot c = a \cdot \left ( b \cdot c \right ) \; \forall a,b,c \in G$

Identity

$\exists e \in G \; \text{such that} \; a \cdot e = a = e \cdot a \; \forall a \in G$

Inverses

$\forall a \in G \; \exists a^{-1} \in G \; \text{such that} \; a \cdot a^{-1} = e = a^{-1} \cdot a$

Rings

Rings are a step up from groups in that rings have two binary operations - addition and multiplication. The definition is given below.

Definition: Ring
Let $R$ be any set with two binary operations on the elements of $R$, called addition (denoted by $+$) and multiplication (denoted by $\cdot$). Then $R$ is a ring if it satisfies the following nine axioms.

Additive Closure

$a + b \in R \; \forall a,b \in R$

Additive Associativity

$\left ( a + b \right ) + c = a + \left ( b + c \right ) \; \forall a,b,c \in R$

Additive Identity

$\exists 0 \in R \; \text{such that} \; a + 0 = a = 0 + a \; \forall a \in R$

Additive Inverses

$\forall a \in R \; \exists -a \in R \; \text{such that} \; a + \left ( -a \right ) = 0 = \left ( -a \right ) + a$

Additive Commutivity

$a + b = b + a \; \forall a,b \in R$

Multiplicative Closure

$a \cdot b \in R \; \forall a,b \in R$

Multiplicative Associativity

$\left ( a \cdot b \right ) \cdot c = a \cdot \left ( b \cdot c \right ) \; \forall a,b,c \in R$

Left Distribution

$a \cdot \left ( b + c \right ) = \left ( a \cdot b \right ) + \left ( a \cdot c \right ) \; \forall a,b,c \in R$

Right Distribution

$\left ( a + b \right ) \cdot c = \left ( a \cdot c \right ) + \left ( b \cdot c \right ) \; \forall a,b,c \in R$

I know that it looks like a big nasty definition and nine axioms seem like a lot, but its not so bad when you break it down. The five additive axioms tell us that $R$ is an abelian group under addition. The multiplicative axioms give us what we're allowed to do with the multiplication operator. Notice that $R$ does not include either a multiplicative identity or multiplicative inverses. The two distributive laws give the ways that addition and multiplication interact. A ring is called commutative if elements of $R$ commute under multiplication.

Fields

Fields are very important in many areas of mathematics, including some advanced group theory, linear algebra, and some areas of topology. Fields - especially algebraically closed fields like $\mathbf{C}$ - give basically all of the properties that we need to support other, more complicated systems like vector spaces, modules, or polynomials. The definition is given below.

Definition: Field
Let $F$ be a ring. Then $F$ is a field if, in addition to the ring axioms, it also satisfies the following axioms.

Multiplicative Commutivity

$a \cdot b = b \cdot a \; \forall a,b \in F$

Unity (Multiplicative Identity)

$\exists 1 \in F \; \text{such that} \; 0 \neq 1 \; \text{and} \; a \cdot 1 = a = 1 \cdot a \; \forall a \in F$

Multiplicative Inverses

$\forall a \in F \; \text{with} \; a \neq 0, \; \exists a^{-1} \in F \; \text{such that} \; a \cdot a^{-1} = 1 = a^{-1} \cdot a$

A field, $F$, is automatically an abelian additive group since it inherits the ring axioms (from the first line of the definition) and the field axioms give a multiplicative identity, multiplicative commutivity, and multiplicative inverses (except that $0$ has no inverse). This gives the abelian multiplicative group structure of $F\setminus \left \{ 0 \right \}$ (the field without the additive identity). And, of course, $F$ still has the distributive properties. Now that we're in a field we get all of the addition, subtraction, multiplication, and division properties as well as commutivity and distribution. This means that with respect to the usual operations of addition and multiplication we finally get to do all the things that we think we should be able to do, which is nice in vector spaces, topological spaces, and modules.

In the last entry we looked at a few number systems, and now we know some of the basic algebraic structures, and next time we'll see how they fit together - or rather how they fail to fit together.

References

Previous Related Post: Numbers

Wikipedia: Group

Wikipedia: Ring

Wikipedia: Field

Numbers

For the next three entries, I want to talk about numbers. Now, us theoretical mathematicians don't like numbers all that much, but as they are a necessary part of the world, I'd like to show how they relate to our theoretical adventures. Actually, its not really true that we don't like numbers - we like the complex numbers quite a bit because they're a nice (algebraically closed) field and we do like to count things and look at the sizes of things - we just don't really like the primary focus to be on numbers. At any rate, below is an overview of the systems of numbers that we're going to talk about.

Natural Numbers

$\mathbf{N} = \left \{ 0 , 1 , 2 , \cdots \right \}$

Integers

$\mathbf{Z} = \left \{ \cdots , -2 , -1 , 0 , 1 , 2 , \cdots \right \}$

Rational Numbers

$\mathbf{Q} = \left \{ \frac{p}{q} : p,q\in \mathbf{Z} \;\text{and}\; q\neq 0 \right \}$

Real Numbers

$\mathbf{R}$ is the set of all decimal numbers - even non-terminating and non-repeating decimals

Complex Numbers

$\mathbf{C} = \left \{ a + b i : a,b\in \mathbf{R} \;\text{and}\; -1=i^2 \right \}$

Number System Advantages

This covers most of your basic number systems and whether you know it or not, every time you work on a problem you have to choose a number system to live in. Induction problems use the natural numbers, calculus problems probably use the reals, and solving polynomials usually requires the complex numbers. You'll notice the nice relationship where

\[ \mathbf{N} \subset \mathbf{Z} \subset \mathbf{Q} \subset \mathbf{R} \subset \mathbf{C} \]

and the way it works is that every time you move to a "larger" number system you get a new property that you get to work with.

Natural Numbers

We're going to start our journey in the natural numbers, $\mathbf{N}$. First what we need to know is what we're allowed to do in $\mathbf{N}$. You can multiply numbers in $\mathbf{N}$ and you can add numbers in $\mathbf{N}$, but what you can't do is subtract or divide and still stay in $\mathbf{N}$. Clearly neither $6-8$ nor $\frac{5}{4}$ are natural numbers.

Integers

So then we move to $\mathbf{Z}$ and, as promised, we gain a property. In $\mathbf{Z}$ we get negative numbers, which means we get subtraction and, in the language of abstract algebra, we get additive inverses. However, you still don't get to divide integers.

Rational Numbers

You don't get division until you move to the rationals, $\mathbf{Q}$, which gives us fractions and multiplicative inverses. It may seem like all we need to do, we can do in $\mathbf{Q}$, but that's not true yet.

Real Numbers

The sequence $3, 3.1, 3.14, 3.141, \cdots$ contains only rational numbers and will converge to $\pi$, but $\pi \notin \mathbf{Q}$. What we gain in the real numbers, $\mathbf{R}$, is the limits of sequences. Every convergent sequence of real numbers converges inside $\mathbf{R}$ (we call $\mathbf{R}$ "complete" in topological terms).

Complex Numbers

The largest number system we've got (for now) is the complex numbers, $\mathbf{C}$, and the benefits that come from the complex numbers make it very useful for the purposes of abstract algebra. The particular benifit is that its "algebraically closed." If we're just living in $\mathbf{R}$, then the polynomial $p(x)=x^2 + 1$ has no roots - that is it has no real roots. In $\mathbf{C}$, every polynomial of degree greater than 1 with complex coefficients has a complex root.

Number System Disadvantages

Now, we just learned that we have all these number systems, and as the number systems gets larger we gain more and more properties. As it turns out, though, as the number systems get larger we also lose properties from some added complications.

Natural Numbers

Again, we're going to start in the natural numbers and then show how at each step we lose something. There are a lot of restrictions on $\mathbf{N}$, as we already learned, but it turns out that $\mathbf{N}$ has a lot of nice properties, too. The first of which is called the Well Ordering Principle which says that any subset of the natural numbers has a smallest element.

Integers

It is not difficult to see that the integers do not have the Well Ordering Principle. Indeed the set $\left \{ k \in \mathbf{Z} : k < 0 \right \}$ does not have a smallest element.

Rational Numbers

The cost in moving from the integers to the rationals is a little more complicated. The integers have something called a "discrete topology." What that really means is that there is some space between the integers and there's not that space between rationals. In $\mathbf{Z}$, you can pick two numbers (say 2 and 3) such that there's no integer between them, but this can't be done in $\mathbf{Q}$ (for any $a,b \in \mathbf{Q}$ with $a<b$, $\frac{a+b}{2} \in \mathbf{Q}$ and $a < \frac{a+b}{2} < b$). Also, bounded subsets of $\mathbf{Z}$ have a maximum and a minimum and are finite, but on the other hand, bounded subsets of $\mathbf{Q}$ don't have to have maximums or minimums and can be infinite (such as the interval $(a,b) \subset \mathbf{Q}$).

Real Numbers

The rational numbers are countable (meaning that there's a bijection between $\mathbf{N}$ and $\mathbf{Q}$) and when you move to the reals you lose this. In fact, this is one of the defining properties of the reals.

Complex Numbers

Finally, when you leave the comforts of the reals and move to the wide world of algebraic completeness afforded by the complex numbers you lose order. If $x,y \in \mathbf{R}$ then either $a < b$, $a > b$, or $a = b$. If $a,b \in \mathbf{C}$ then we can talk about what it means for them to be equal, but the statement $a < b$ doesn't make any sense.

Most of the time the set of numbers that we use is implied or is obvious, but at times, its important to be careful which set you're using or at least to be aware of the properties at your disposal in each of them. Next time we'll take a look at where these numbers fall in the world of abstract algebra. It turns out that although most of these form groups in one way or another, none of them are only groups.

References

Wikipedia: Natural Numbers

Wikipedia: Integers

Wikipedia: Rational Numbers

Wikipedia: Real Numbers

Wikipedia: Complex Numbers

New LaTeX Formatting

I have hopefully found a new (and better!) way to format math and equations in my blog using $\LaTeX$. I'm going to try and integrate this as seemlessly as possible, but I can't really imagine it happening without some format hiccups, so try and bear with me. To demonstrate my newfound power I'm going to try and write out one of my old examples.

Example: Homomorphism

Choose $n \in \mathbf{N}$ and let $\phi:\mathbf{Z}\to \mathbf{Z}$ be given by $\phi(x)=x\; \text{mod}\; n$. Now, suppose $x,y \in \mathbf{Z}$. We can write $x = h n + p$ and $y = k n + q$ where $p,q \in \mathbf{Z}_n$ and $h,k \in \mathbf{Z}$. Then

\[ \phi(x + y) = x + y\; \text{mod}\; n = (h n + p) + (k n + q)\; \text{mod}\; n = p + q\; \text{mod}\; n \]

and also

\[ \phi(x) + \phi(y) = (h n + p\; \text{mod}\; n) + (k n + q\; \text{mod}\; n) = p + q\; \text{mod}\; n \]

so $\phi(x + y) = \phi(x) + \phi(y)$. Thus $\phi$ is operation preserving and is a homomorphism.

The image of $\phi$ should be fairly obvious. Indeed, $\mathbf{Z}_n \subseteq \mathbf{Z}$ and if $x \in \mathbf{Z}_n$ the $\phi(x) = x$ giving that $\mathbf{Z}_n \subseteq \text{Im}(\phi)$ but by the definition of modular division, nothing in $\text{Im}(\phi)$ can be outside of $\mathbf{Z}_n$ and so $\text{Im}(\phi) = \mathbf{Z}_n$. The kernel of $\phi$, however, is a little more interesting. Suppose that $x \in \text{Ker}(\phi)$. We can write $x = h n + p$ as before but then $\phi(x) = p = 0$ so $x = h n$ giving that the elements in the kernel of $\phi$ are the multiples of $n$, or $\text{Ker}(\phi) = n \mathbf{Z} = {k n : k \in \mathbf{Z}}$.

If you're wondering what's going on, I added some javascript (that I found thanks to WatchMath) that renders standard LaTeX into the images you see above. If you'd like to learn how to do it (its very easy), you can read about it in this journal entry on my personal blog.

Dr. Perelman and an Introduction to Topology

I know I promised an entry on group actions today, and we'll get to that soon enough, but I think for a couple of posts I'm going to go in a slightly different direction - partially because group actions are hard to explain, partially because I'm getting a little bored with writing about group theory, and mostly because opportunity has struck in the form of Dr. Perelman's idiocy.

Grigori Perelman is a Russian topologist (from what I can tell) and quite the eccentric to say the least. In 2002 he solved a very old and very difficult math problem called the Poincare Conjecture which happens to be one of the seven Millennium Problems. In 2000 the Clay Institute of Mathematics commissioned a $1 million award for a solution to any of seven of the most difficult and important problems that mathematicians were facing at the time, which they called the seven Millennium Problems. Then, two years later, Perelman presented a solution to the Poincare conjecture which has taken until now to verify. As promised, the Clay Institute awarded Perelman the $1 million prize. Also, in 2006 he was awarded the Fields Medal, which is the most prestigious award offered to mathematicians and comes with a $15,000 prize.

Now, the most interesting part of these accomplishments is that Perelman refused both the $15,000 Fields Medal award as well as the $1 million Millennium Prize award. He says its because he hates the intellectual and moral shortcomings of the mathematical community and does not want to be seen as its figurehead. Since his proof in 2002, Perelman tried teaching for a brief while at American universities, but has ultimately given up math completely. He now lives in a flat with his mother and enjoys playing table tennis against his wall in his basement. When a journalist asked him to comment he replied, "You are disturbing me. I am picking mushrooms."

The problem that Perelman solved, the Poincare Conjecture, is extremely difficult, but surprisingly accessible. Suppose you stretch a rubber band over the circumference of a sphere - or really around a sphere in any way. You can then slowly and carefully (the math terms are continuously and uniformly) move the rubber band along the surface of the sphere such that the rubber band shrinks down into a single point. Now, suppose that we try to do the same thing with a doughnut (mathematically a torus) instead of a sphere. If we can imagine that the rubber band has been stretched around the donut in an appropriate way, then the rubber band cannot be reduced to a point without either tearing the rubber band or breaking the doughnut. In topological terms, the sphere is "simply connected" and the doughnut is not. This is considered the three dimensional case and the Poincare Conjecture, in essence, asked for a way to classify four-dimensional simply connected objects.

This brings us to a nice way of introducing topology. The difference between a doughnut and a sphere is more than simple-connectedness. If you imagine that a sphere were made of clay, then there is no way to deform that sphere into a doughnut without poking a hole in the clay. However, if you had a clay coffee cup, you can imagine how it is possible to deform the coffee cup into a doughnut because the coffee cup already has a hole. If you're having trouble visualizing that, wikipedia has a nice animation of this transformation. In topological terms, we call the coffee cup and the doughnut homeomorphic (note that the words homomorphism and homeomorphism are not the same). Topology, from my point of view, is basically an in-depth study of what it means and how to tell when two things are homeomorphic. That being said, though, if you took a first semester in topology or read an introductory topology text, you would find yourself pretty far removed from that idea of homeomorphism and, in fact, the definition of a topological space does not really resemble anything I've mentioned here.

Topology is extremely interesting and it often forms a gateway to other ideas in other branches of mathematics. I think I might start to work though some topology during some breaks in the group theory stuff even though topology does not help me in my character theory goals. Topology will most likely be in a lower capacity since I do not understand it, myself, as well as I would like, but sometimes I feel like the barrage of group theory has been pretty intense lately and topology might provide a nice break from that at times.

References

Text Reference: Davis

Wikipedia: Grigori Perelman

Wikipedia: Topology

The Clay Institute of Mathematics

Huffington Post: Grigori Perelman, Reclusive Russian Math Genius, Refuses $1 Million Prize

More About Homomorphisms

Before we talk about the first group isomorphism theorem, I suppose a few examples of homomorphisms are in order. They are often very similar to isomorphisms, as to be expected, but make sepcial notes of their kernels and images.

Example:

Choose n∈N and let φ:Z→Z be given by φ(x) = x mod n ∀x∈Z. Now, suppose x,y∈Z. We can write x = hn + p and y = kn + q where p,q∈Z_n and h,k∈Z. Then

φ(x + y) = x + y mod n = (hn + p) + (kn + q) mod n = p + q mod n

and also

φ(x) + φ(y) = (hn + p mod n) + (kn + q mod n) = p + q mod n

so φ(x+y) = φ(x)+φ(y). Thus φ is operation preserving and is a homomorphism.

The image of φ should be fairly obvious. Indeed, Z_n⊆Z and if x∈Z_n then φ(x) = x giving that Z_n⊆Imφ but by the definition of modular division, nothing in Imφ can be outside of Z_n and so Imφ = Z_n. The kernel of φ, however, is a little more interesting. Suppose that x∈Kerφ. We can write x = hn + p as before but then φ(x) = p = 0 so x = hn giving that the elements in the kernel of φ are the multiples of n, or Kerφ = nZ = {kn : k∈Z}.

Example:

Let G be any group and let N be a normal subgroup of G. Then we can form the factor group, G/N. Let σ:G→G/N be defined by σ(g) = gN ∀g∈G. Choose x,y∈G and note that

σ(ab) = abN = aNbN = σ(a)σ(b)

so σ is operation preserving and thus a homomorphism.

We see that σ is surjective (if K∈G/N simply choose k∈K and σ(k) = K) so that Imσ = G/N. It is also not hard to see the kernel of σ either. Since g→gN, the only elements of G that map to the coset, N, are the elements inside of N, giving that Kerσ = N.

This particular homomorphism crops up quite a bit and as such is given its own special name.

Definition: Canonical Homomorphism
Let G be a group and N a normal subgroup of G. The map σ:G→G/N defined by σ(g) = gN ∀g∈G is called the canonical homomorphism.

Example:

You might recall that the determinant is a homomorphism. Let G = GL(n,R) and let θ:G→R* be defined by θ(A) = det(A) ∀A∈G. (R* is the multiplicative group of real numbers without zero.) You should recall from linear algebra that det(AB) = det(A)det(B) when A and B are square matrices of the same size. Now, choose A,B∈G and observe that

θ(AB) = det(AB) = det(A)det(B) = θ(A)θ(B),

so θ is a homomorphism.

It is not hard to see that θ is surjective, although it may take a little bit of extra linear algebra knowledge. Choose α∈R and let A = α^1/nI_n where I_n is the identity matrix in G. Then φ(A) = det(A) = α. Thus θ is surjective and Imθ = R*. The kernel of θ is a little more complicated. Kerθ consists of all the matrices with determinant equal to one. There is no nice, explicit form for these matrices, but they are used quite a lot and as such this group has its own name.

Definition: Special Linear Group
Let n be an integer and define the set SL(n,R) = {A∈GL(n,R) : det(A) = 1}. Then SL(n,R) forms a subgroup of GL(n,R) and is called the special linear group.

The first group isomorphism theorem gives a relationship between isomorphisms, homomorphisms, kernels, and images. It is an interesting way to find an isomorphism between often unrelated groups.

Theorem: First Group Isomorphism Theorem
Let φ:G→G* be a group homomorphism. Then G/Kerφ ≈ Imφ.

Proof:

Let φ:G→G* be any group homomorphism, let K = Kerφ, and define θ:G/K→Imφ by θ(gK) = φ(g) ∀gK∈G/K. Also call e the identity element of G*

First we must be sure that this is actually a function, that is that the mapping of θ is independent of coset representative. Choose H∈G/K and then choose g,h∈H. Since g∈hK ∃k∈K such that g = hk. Now observe that

θ(gK) = φ(g) = φ(hk) = φ(h)φ(k) = φ(h)e = φ(h) = θ(hK)

so finally θ(gK) = θ(hK) and θ is independent of the choice of coset representative, therefor making it a function.

To show that θ is surjective, choose q∈Imφ. Then clearly ∃p∈G such that φ(p) = q. Finally, θ(pK) = φ(p) = q giving that θ is surjective.

To show that θ is injective, it suffices to show that Kerθ is trivial, or that it contains only the identity of G/K. If we recall, this identity is simply K. Choose gK∈Kerθ. Observe that

e = θ(gK) = φ(g)

which means that g∈K and gK = K. Finally, Kerθ = {K} and θ is injetcive.

Choose aK,bK∈G/K and observe that

θ(aKbK) = φ(ab) = φ(a)φ(b) = &theta(aK)θ(bK)

so that θ is operation preserving.

Finally, we see that θ is an isomorphism and that G/Kerφ ≈ Imφ.

This is a pretty cool theorem and from our examples we arrive at a couple of interesting results. First, Z/nZ ≈ Z_n which can actually be shown without the use of the first isomorphism theorem. The second example gives us that for N⊳G, G/N ≈ G/N which is obvious. The first isomorphism theorem, however, does give a very interesting result from the third example that we saw - that is that GL(n,R)/SL(n,R) ≈ R*, which is pretty cool and rather unexpected.

There is one last thing that I should mention about homomorphisms for the time being, and that is that they can be used as a sort of subgroup test. From the way I introduced and defined SL(n,R) it is very obvious that its a normal subgroup of GL(n,R). However, suppose I'd defined SL(n,R) immediately after defining GL(n,R) and asked you to prove that SL(n,R)⊳GL(n,R) (instead of inventing the special linear group from the kernel of the determinant homomorphism like I did above). It can be done using the normal subgroup test, but its a giant pain with tons of pointless symbol chasing. The easiest way to prove it would be to discover a homomorphism (namely the determinant homomorphism) for which GL(n,R) is the domain and SL(n,R) is the kernel, which automatically gives that SL(n,R)⊳GL(n,R) since all kernels are normal. This is a very common technique for finding normal subgroups.

In the next post, I'm going to be taking a detour from homomorphisms and subgroups and talk about group actions.

References

Previous Related Post: Homomorphisms

Text Reference: Gallain Chapter 10

Wikipedia: First Isomorphism Theorem

The Unapologetic Mathematician: The First Isomorphism Theorem

Homomorphisms

Group homomorphisms are very closely related to group isomorphisms. In fact, it turns out that every isomorphism is a homomorphism and as such, homomorphisms can be viewed as a generalization of isomorphisms. These very important functions are fundamental in the world of algebra and are one of the most important tools that we have. As we'll see in this and in upcoming posts, the application of homomorphisms to various groups gives a lot of useful results.

Definition: Group Homomorphism
A function, φ, from a group G to a group G* is a group homomorphism if it preserves the group operation - that is if ∀a,b∈G, φ(ab) = φ(a)φ(b).

A homomorphism is a function that has the operation preserving property that we described for isomorphisms without regard to bijectiveness. Of course, homomorphisms can be bijective, explaining why each isomorphism is a homomorphism. This means that it is easier for a function to be a homomorphism than an isomorphism, but it also means that homomorphisms have more interesting properties. Isomorphisms are used to identify groups as isomorphic, but not for much else, whereas homomorphisms provide us with a lot of usefullness, mostly as a result of the following sets.

Definition: Kernel
The kernel of a homomorphism, φ:G→G*, is the set {g∈G : φ(g)=e} and it is denoted by Ker(φ) or Kerφ.

Definition: Image
The image of a homomorphism, φ:G→G*, is the set {φ(x) : x∈G} and is denoted by Im(φ) or Imφ.

The first thing to notice here is that if φ:G→G* is a homomorphism, then Kerφ⊆G and Imφ⊆G*. The kernel is all of the things in G that are mapped to the identity, and the image is all of the things in G* that can be attained by a mapping of φ. It is important to note that these sets are trivial in the case that φ is actually an isomorphism - that is that in this case, Kerφ={e} and Imφ=G*. This does give another convenient way to check if a function is an isomorphism. Instead of proving that φ is bijective, it suffices to show that Kerφ={e} and Imφ=G* (and, of course, that φ is operation preserving). However, we get much more than that. It turns out that both the image and the kernel are subgroups.

Theorem: Kernels are Subgroups
Let φ:G→G* be a group homomorphism. Then Kerφ is a subgroup of G.

Proof:

Let φ:G→G* be a group homomorphism and choose a,b∈Kerφ. We then have that φ(ab^-1) = φ(a)φ(b)^-1 = e(e^-1) = e and thus ab^-1∈Kerφ. Therefore, by the one-step subgroup test, Kerφ is a subgroup of G.

Theorem: Images are Subgroups
Let φ:G→G* be a group homomorphism. Then Imφ is a subgroup of G*.

Proof:

Let φ:G→G* be a group homomorphism and choose x,y∈Imφ. Then ∃a,b∈G such that φ(a)=x and φ(b)=y. Now, φ(ab^-1) = φ(a)φ(b)^-1 = xy^-1 and thus xy^-1∈Imφ. Therefore, by the one-step subgroup test, Imφ is a subgroup of G*.

In those proofs I used a fact that I have not yet proved - specifically that φ(b^-1 = φ(b)^-1. This is true, though, and is an easy thing to prove. The fact that these two sets are subgroups is important and very convenient, but we get even more than that.

Theorem: Kernels are Normal
Let φ:G→G* be a group homomorphism. Then Kerφ⊳G.

Proof:

Let φ:G→G* be a group homomorphism and choose g∈G and n∈Kerφ. Then φ(gng^-1) = φ(g)φ(n)φ(g)^-1 = φ(g)eφ(g)^-1 = φ(g)φ(g)^-1 = e thus giving that gng^-1∈Kerφ. Since the choice of n∈Kerφ was arbitrary, gKerφg^-1⊆Kerφ for g∈G. Thus, by the normal subgroup test, Kerφ⊳G

It turns out that images are not normal subgroups. This is not all that surprising when you really think about what an image is in relation to a codomain. However, the fact that kernels are normal subgroups is a surprisingly wonderful fact and we get a lot of mileage out of it. In the next post, we'll see a very useful result called the first group isomorphism theorem that uses the normality of kernels in a very natural way.

References

Previous Related Post: Properties of Isomorphisms

Text Reference: Gallain Chapter 10

Wikipedia: Group Homomorphism

Wolfram Mathworld: Group Homomorphism

Planet Math: Group Homomorphism

A Fork in the Road

This is the point where we have enough background to go in a lot of different directions. There is a lot more to be learned about groups. From here we could move on to group actions, Sylow Theory, and the various different ways to combine groups and make new groups. However, we have also learned a sufficient amount of group theory to move onto the theory of integral domains, rings, and then fields which are all new structures that are similar to groups but with more rules. This would be the direction that you'd want to go if you were interested in studying polynomials and algebraic topology. A third option would be to work on linear algebra, which is the study of vector spaces, matrices, and linear functions.

My personal area of research (at this point) is in character theory, which is a very cool and useful way of looking at groups and extracting all of their information. Character theory, at least from what I can tell so far, is a cool new 21^st century tool that we've developed to study groups after running dry the well of standard group theory. I think I'm going to try to move in a direction that gets us toward understanding character theory. The problem with that, though, is that the path to character theory is nowhere near a straight line. When I learned it myself it was a frustrating process of patching together bits and pieces of a lot of different topics and it is my goal to keep you from that experience. The problem is, though, that even though I'm going to try and keep you away from the frustrating process, its still going to take the combination of a couple different branches of mathematics. First, we need a significant amount of group theory - including homomorphisms, group actions, conjugacy classes, and simple groups. Then we need to learn something called representation theory which is the study of functions that take arbitrary groups into groups of matrices. That means that before we can learn representation theory we need to understand these matrix groups which requires some linear algebra.

So, as you can see, there is quite a lot of work ahead of us before we get to character theory. And on top of that, I did not choose this path because its better or more important than any of the other topics - I only chose it because its what I'm familiar with, so even if we get to character theory there's quite a bit ahead of that. For now, though, I'm going to continue pushing along with group theory.

Lagrange's Theorem

A big part of the hard work and the research in group theory is in finding specific types of subgroups inside of finite groups. If you have an arbitrary finite group of order n, then the number of distinct subsets is 2ⁿ. For reference, consider |G|=9. Then the number of subsets of G is 2⁹=512 and each of these is a possible subgroup of G. As you can see, this gets very large very quickly. Lagrange's Theorem, however, gives us a way to drastically cut down the number of possible subgroups of any group. You should read the proof of Lagrange's Theorem, because it makes use of some of the things we've already learned.

Theorem: Lagrange's Theorem
If G is a finite group and H is a subgroup of G, then |H| divides |G|.

Proof:

Let G be a finite group and let H be a subgroup of G. Now, consider the set of all left cosets of H in G, {gH : g∈G}. Note, this set does not necessarily form a factor group because H is not normal, but we still have the cosets. Now choose one representative from each coset such that {g₁H, g₂H,...,g_kH} is the set of distinct left cosets. Then we have that each element of G is a member of one of these cosets, or that

G = g₁H∪g₂H∪⋯∪g_kH.

We know that this union is disjoint - that is if i≠j then g_iH∩g_jH=∅. From this we get that

|G| = |g₁H|+|g₂H|+⋯+|g_kH|.

Also, we know that every coset contains the same number of elements, or |g_iH| = |H|. Finally, this gives us that |G| = k|H| so then k = |G|/|H| and |H| divides |G| as desired.

Lagrange's Theorem gives us that the order of every single subgroup must be a divisor of the order of the original group. What this does is immediately cuts down the number of possible subgroups of any finite group. Earlier I mentioned that if |G|=9 then there are 512 unique subsets of G. Lagrange's Theorem, though, tells us that of these 512 choices, the only subsets that could possibly be subgroups are the ones of order 3, which cuts the choices down to only 84. This might not seem like that big of a deal at this point, but Lagrange's Theorem is definitely the most important and most useful theorem in all of group theory.

I must make a point to emphasise what it is that Lagrange's Theorem does not say. It is easy to think that if k is some divisor of a group, G, then G has some subgroup of order k. This is not at all the case. Lagrange's Theorem only tells us a list of possible group orders and a criteria for when a subset cannot be a subgroup, it is in no way a subgroup test. It would be convenient if the converse of Lagrange's Theorem were true, but it is not. In fact, there are lots of groups that fail the converse. For example, A₄ has no subgroup of order 6.

I've written a lot of group theory proofs and I think about 90% of them use Lagrange's Theorem in one form or another - there are definitely a lot of places where we'd get stuck without it. For now, though, I'm going to give some of the immediate results of Lagrange's Theorem without proving them.

Theorem: |G/N|
Let G be a group and N⊳G. Then |G/N| = |G|/|N|.

Theorem: |a| divides |G|
In a finite group, the order of each element divides the order of the group.

Theorem: Prime Order Groups
Any group of a prime order is cyclic.

Theorem: a^|G| = e
If G is a finite group and a∈G then a^|G| = e.

Theorem: Fermat's Little Theorem
Let a be an integer and p be any prime number. Then a^p mod p = a mod p.

Theorem: Groups of order 2p
Let G be any finite group such that |G| = 2p where p is a prime number greater than 2. Then either G≈Z_2p or G≈D_p.

A few of these things seem to be very far away from Lagrange's Theorem and maybe they are, but I promise that they're all direct consequences. I didn't give the proofs because some of them are quite complicated, but I can write them if someone needs. There are a lot of proofs that start with "Suppose H is a subgroup with the property that..." and ends with "...but then the order of H does not divide the order of G hence contradicting Lagrange's Theorem." It is a very useful, very powerful tool.

References

Previous Related Post: Examples of Factor Groups

Text Reference: Gallain Chapter 7

Wikipedia: Lagrange's Theorem

Wolfram Mathworld: Lagrange's Theorem