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