IB Mathematics (HL)/Group Theory

The aims of this option are to provide the opportunity to study some important mathematical concepts, and introduce the principles of proof through abstract algebra. For this topic, you do not need any background knowledge of a core topic.

Naive Set Theory

Sets can be used as a foundation for constructing all the rest of mathematics. This is called axiomatic set theory. But axiomatic set theory is a very formal theory, too cumbersome for everyday mathematical use. On the other hand, sets are too useful a mathematical construct to be reserved for specialists investigating the foundations of mathematics. Naive set theory refers to using the framework of sets without formally defining them. This in what we will be doing.

A set is defined (informally) as any collection of things

Ex: The set of primary colors, the set of my siblings, the set of positive integers.

Some sets can be described by listing the things in them

We list the things separated by commas, and use curly braces to indicate that the belong to a set.

Ex: {red, yellow, blue}, {Donna, Linda, Bobbi, Julie, Steve}

If we can completely list (enumerate) all the things in a set, the set is said to be finite. The set of primary colors and the set of my siblings are finite sets. If a set isn’t finite, it is said to be infinite. The set of all positive integers is an infinite set.

Some sets can be described by a rule for enumerating them

The set of positive even integers is infinite, so we can’t list them all. But, we can write it as {2, 4, 6, …}. The “…” says that there is a rule for constructing a list that contains every member of the set, even though the list can't be completed in a finite amount of time.

Problem:

1. Explicitly state a rule for constructing the set of positive even integers.

An interesting aside: some infinite sets are so “big” that it isn't possible to write a rule that constructs a list of all its members. The set of real numbers is one such set.

Some common mathematical sets

Here are some common mathematical sets you are familiar with. You need to be able to recognize the symbols.

$\mathbb {N}$

the set of positive integers, $\{1,2,\ldots \}$

$\mathbb {Z}$

the set of integers

$\mathbb {Z} ^{+}$

the set of positive integers, $\{1,2,3,\ldots \}$

$\mathbb {Q}$

the set of rational numbers

$\mathbb {Q} ^{+}$

the set of positive rational numbers

$\mathbb {R}$

the set of real numbers

$\mathbb {R} ^{+}$

the set of positive real numbers

$\mathbb {C}$

the set of complex numbers

The “things” in a set are called elements of the set

If something (say “x”) is in some particular set (say “S”), we say “x is an element of S.” To say this concisely, we write

$x\in S$

Mathematicians often use the word member as a synonym for element. For example, you’ll hear things like “2 is a member of the set of positive integers”.

Definition of equality for sets

Two sets S and T are equal if every element of S is also an element of T and every element of T is also an element of S. Not surprisingly, we write this as

$S\mathbf {=} T$

Here are some implications of this definition.

The ordering of elements in a set is not important

The set {red, yellow, blue} equals (i.e. is the same as) the set {yellow, blue, red}. Why? Look at the definition of equality. Every element in the first set is an element of the second, and every element in the second set is an element of the first. So the two sets are equal.

Something is either an element of a set or not; it doesn’t make any difference if you list it multiple times

The set {red, red, yellow, blue, red} is the same as (i.e. is equal to) the set {red, yellow, blue}, even though “red” is listed multiple times in the first set. Don’t take my word for it; check the definition of equals.

Definition of subsets

What would happen if we broke up the definition of equal sets into its two parts? Suppose we required only that every element of S is also an element of T, without requiring the “vice versa”? For example, every element of the set {red, yellow, blue} is in the set {red, orange, yellow, green, blue, purple}, but not vice versa. This kind of thing happens often enough that we give it a name. We say that S is a subset of T if every element of S is also an element of T. To say this concisely, we write

$S\subseteq T$

Not surprisingly, we’ll also make up a definition for the “vice versa” part. That is, we say that S is a superset of T if every element of T is an element of S. We write this as

$S\supseteq T$

Notice the similarity between the symbols $\subseteq$ and $\supseteq$, which are defined for sets, and $\leq$ and $\geq$, which are defined for numbers. This is not an accident. The subset relation between sets is not the same thing as the less-than-or-equal relation between the integers, but the two relations do have many similarities. (How many can you think of?) Good mathematical notation will often be suggestive of such similarities.

Problems:

1) Is $\mathbb {N} \supseteq \mathbb {Z}$? Is $\mathbb {Z} \supseteq \mathbb {N}$? Is $\mathbb {Z} \subseteq \mathbb {Z} ^{+}$? Is $\mathbb {Z} \subseteq \mathbb {Z}$?

2) If S, T and U are sets with

$S\subseteq T$

and

$T\subseteq U$,

what can you say about the relationship between S and U? Show it using the definition of $\subseteq$. Do you remember what this property is called?

3) Put as many as you can of the common mathematical sets listed above into a single order of subsets, that is

? $\subseteq$ ? $\subseteq$ ? $\subseteq$ …

The relationship between subsets, supersets and equality

Reviewing the definitions, we see that for two sets $S$ and $T$,

$S\mathbf {=} T$

is true whenever both

$S\subseteq T$ and $S\supseteq T$

are true.

Problems:

1) What is the analogous statement for $\leq$ and $\geq$ with respect to real numbers? Is this statement true?

2) For x and y in $\mathbb {N}$, either x $\leq$ y or x $\geq$ y. Does the same hold true for $\subseteq$ and $\supseteq$ with respect to sets?

“Proper” subsets

Sometimes we have $S\subseteq T$ and we want to rule out the possibility that $S\mathbf {=} T$. To do this, we write

$S\subset T$

i.e. we omit the bar below the $\subset$. To say this in words, we say that S is a proper subset of T. The use of the word “proper” here is kind of funny. It doesn’t mean that there is something more accurate, or more polite, about being a proper subset. It is just the term that mathematicians have come to use to avoid having to say, “S is a subset of T but it isn’t equal to T.” Similarly,

$S\supset T$

is read “S is a proper superset of T ” and is a shorter way of writing

$S\supseteq T$ and $S\neq T$

Problems:

1. For any set S, which of the following are true?

$S\subseteq S$

$S\subset S$

$S\mathbf {=} S$

$S\supseteq S$

$S\supset S$

2. Suppose S = {2, 4, 6}. For each of the following sets T, list all the relationships that hold between S and T .

T = {6, 4, 2}

T = {2, 4, 4}

T = {2, 6, 10}

T = {2, 4, 6, 10}

T = {1, 3, 5}

The smallest possible set

Is there a set X that is a subset of every possible set S? Yes. We can have a set with no elements at all. The definition of subset says that X is a subset of S if every element of X is also an element of S. If X has no elements, this statement is true regardless of what elements S contains.

We call the set containing no elements the null set. It sometimes is written as

{ }

but more often we write it as

$\emptyset$

Again, note the similarity between the notations for the set $\emptyset$ and the number 0. Just as $0\leq n$ for any natural number n, $\emptyset \subseteq S$ for any set S.

Combining sets: union and intersection

So far, we have defined various relations on pairs of sets $(=,\subset ,\subseteq ,$etc.) in terms of membership. It is also useful to define operations that take two sets and form a third set. Once again, we will define these operations in terms of membership.

We’ll start by defining the intersection of two sets S and T to be the set containing anything that is both an element of S and an element of T. We’ll write the intersection operation as

$S\cap T$

Similarly, we’ll define the union of two sets S and T to be the set containing anything that is either an element of S or an element of T. We’ll write the union operation as

$S\cup T$

If you have any trouble getting mixed up between $\cap$ and $\cup$, try remembering that $\cup$looks like U, which stands for Union.

Problems:

1. If S = {1, 2, 3} and T = {2, 3, 4}, what is $S\cap T$? What is $S\cup T$?

2. Are the following statements true for any sets S and T?

$S=(S\cap S)$

$S\subseteq (S\cup S)$

$S\subseteq (S\cup T)$

$S\subset (S\cap T)$

$S\supset (S\cup T)$

Is so, explain why. If not, give a counter-example.

Venn diagrams

When doing math, it is often useful to draw a picture to help visualize a problem. For elementary set operations, there is a conventional method of drawing pictures called Venn diagrams, named after the British mathematician John Venn. To draw a set S, we simply draw a circle, with the name of the set inside the circle.

The intent of this drawing is that the inside of the circle represents all the elements in S. The outside of the circle represents everything that isn’t in the set S. There isn’t any significance to the fact that we use circles in Venn diagrams. We could just as well draw

or File:Trivial Pentagonal Venn Diagram

Now, to represent an operation on two sets, we draw two overlapping circles, like this:

File:Simple Venn Diagram

If you have colored pencils, you could color the inside of S red and the inside of T blue, like this:

File:Colored Simple Venn Diagram

We can now describe all the area that is colored as . The purple overlap between the circles represents . If you don’t have colored pencils, you can draw the circles and shade in the area you want to describe. For example, you can draw something like

to represent . To represent , you would shade in only the overlap of the two circles. (I would show this, but the word processor I am using to write this can’t do this easily.) If we never combined more than two sets, Venn diagrams wouldn’t be useful enough to bother learning about. But they are very useful when we want to illustrate relationships between three sets. In this case, we draw three overlapping circles, like this:

Problems: Illustrate the following set operations by drawing 3 overlapping circles for S, T and U and then shading in only the area described

Once we get more than three sets, Venn diagrams aren’t so useful. The problem is that we can’t simply draw four circles that show every possible combination of intersections. So Venn diagrams are mostly an introductory learning tool. Problems: Draw a Venn diagram (not limited to circles) that depicts every possible combination of intersections between four sets. What is the best you can do?

Set complement (first try)

There is one more operation we want to define for sets – the complement. This operation is a unary operation, meaning it takes only one set as an argument. (Intersection and union are called binary operations, because they take two sets as arguments.) The idea behind the complement of a set S is that it should contain exactly those elements that the set S doesn’t contain. We’ll write the complement of S as S′ (Another notation that you’ll often see is .) Thus, we might try to define the complement of S as “the set of all elements that are not elements of S”. For example, if S were the set of odd integers, than the complement of S would include all the even integers. But according to our definition, the complement of S would also contain my sister Donna, the color red and Valentine’s Day, since they aren’t in S either. So the complement is going to have all kinds of useless junk in it. If this were an everyday discourse, we could just dismiss the junk as being irrelevant to our conversation and ignore it. But in mathematics, we like to be more precise than that. Our solution will be to introduce the notion of a “universal set”.

Universal set

A set consisting of all elements under consideration is called the universal set.It is usually by the capital English Letter U. The universal set is simply the set of all things that we are currently talking about. The name “universal set” is misleading. It is not a set that contains everything in the universe. Nor is it universal in the sense that everyone has agreed to use it. Perhaps a better term would be “universe of discourse”. If we are making statements about the real numbers, then we say our universal set is the set of real numbers. If, on the other hand, we were discussing the natural numbers, our universe of discourse would be the set of all natural numbers. Another way to think of this is with a Venn diagram. We can draw the set S as

where the shaded area represents the elements in S. But how would we shade the diagram to represent the complement of S? We would want to shade the outside of the circle. But where would we stop? A “little ways” out? To the edge of the paper? Maybe the back of the paper as well? The universal set makes it clear where to stop:

Keep in mind that the only reason for defining a universal set is to remove ambiguity when we’re taking a set complement. If we’re not going to be using set complements, we don’t need to worry about what our universal set is.

Set complement (the real thing)

Now that we have the concept of a universal set, we’ll give the real definition for set complement: The complement of a set T is the set of all elements that are in the universal set but not in T. Problems: Assume that R, S, and T are subsets of some universal set U. Draw Venn Diagrams to determine whether the following statements are always true.

(You had this last problem before, in the section titled Combining sets: union and intersection. Did you get the same answer this time? If not, did the Venn diagram mislead you? You have to be careful when interpreting Venn diagrams with proper subsets.)

DeMorgan’s laws

In mathematics, the term “law” describes a statement that can be proved from more fundamental mathematics. There are a number of synonyms: postulate, theorem, corollary, etc. The term “law” is often used in conjunction with statements that were discovered a long time ago, typically before that area of mathematics was formalized. DeMorgan’s laws, named after Augustus De Morgan, are

and

Note the symmetry between these two statements. If you take one and interchange the and , you get the other. DeMorgan’s laws are important because they provide a method for moving the complement from the “outside” to the “inside” of a complex expression. By applying DeMorgan’s laws repeatedly, we can transform any complex expression containing complements into an equivalent expression that has only complements of simple sets. Ex:

In the last step, we made use of the fact that taking the complement a second time returns us to the original set, i.e. for any set S,

Problems: Use Venn diagrams to show that DeMorgan’s laws are true. Use DeMorgan’s laws to transform these expressions into equivalent expressions that have complements only of basic sets.

Other useful laws

There are numerous laws relating various combinations of intersection, union and complement operations. Laws of the form X = Y are especially useful because we can use them for translating an expression into other, equivalent expressions. Here are some useful laws of this having this form. To the right of each law is a verbal description. union is commutative intersection is commutative When operations are commutative, we don’t have to be concerned about the order of the operands. union is associative intersection is associative When operations are associative, we can remove unnecessary parentheses. For example, we can write because there is no difference between and .

	intersection distributes over union

This is analogous to the fact that for real numbers, multiplication distributes over addition. That is, . If we exchange for * and for +, we get the law above. Notice also that union does not distribute over intersection, such as addition does not distribute over multiplication for real numbers. The next two laws include U, the universal set. law of the excluded middle This is called the law of the excluded middle because any element in the universal set either is an element of S or isn’t an element of S. There is no middle ground. universal set is an identity for intersection This says that taking the intersection with the universal set makes no change, just as multiplying a real number by 1 makes no change. Problems: Verify each of the above laws using Venn diagrams.

Union-of-intersections form

A good start in determining how two set expressions are related is to reduce them both to union-of-intersections form. This is an expression of the form (? ? … ?) (? ? … ?) (? ? … ?) … (? ? … ?) where all the question marks are either a named set or its complement. For example, the expression

is in union-of-intersections form. This is analogous to the sum-of-products form for expressions over R, such as

or, following the common conventions for omitting multiplication symbols and extra parentheses,

Question: What mathematical properties and/or notational conventions are needed to get the previous line from the one before it? Here’s a general technique for transforming any set expression into union-of-intersections form, Apply DeMorgan’s laws repeatedly to move all complements to named sets. Apply the distributive law repeatedly to change intersection of unions into unions of intersections. Make free use the associative laws to get rid of unnecessary parentheses and the commutative laws to put things in a nice order. Here’s a simple example.

(I had originally intended to take this topic farther, that is to develop a complete algorithm for deciding whether two set expressions were equivalent (or had a subset relationship). But I decided it was going to get into too many details, so I’m just going to stop here. Problems: Determine whether each of the following relationships is always true. Start by transform both sides of the expression into union-of-intersections form.

Sets of sets

At the beginning of this topic, I said that sets could be used for constructing all of mathematics. This is possible because the elements of sets can be sets themselves. For example, consider the set S = {1, {1}, {1, {1}}}. This set has three elements, the number 1, the set {1}, and the set {1, {1}}. When dealing with sets of sets, it is important not to get confused between a element of the set and a subset of the set. For example, if S = {1, {1}, {1, {1}}}, then the number 1 is an element of S, and not a subset of S. On the other hand, the set {1} is both an element of S and a subset of S. How can this be? Let me write each of the elements of S in a different color. S = {1, {1}, {1, {1}}} Now {1} is clearly an element of S. But in addition, {1} is a subset of S, but for a different reason. Questions: Is the set {1, {1}} an element of S? A subset of S? Problems: Is the set {1, {1, {1}}} an element of S? A subset of S? How many subsets does the set S have? List them. Suppose we start with nothing but the null set, Ø. If that is the only thing in the mathematical universe, what other sets could we possibly build out of it? There is only one possibility, and that is to put it into a set, i.e. {Ø}. Is Ø really different than {Ø}? How many elements does Ø have. How many elements does {Ø} have? So now we have two sets, Ø and {Ø}. What new sets can we build from these? Well, one possibility would be to have a set containing only {Ø}, that is Template:Ø. (The sets Template:Ø and {Ø} each have just one element; how can we be sure that they aren’t the same set? Hint: use the definition of set equality.) But from Ø and {Ø}, we can also build the set (Ø, {Ø}}. This is clearly a new set, because it has two elements – our biggest set yet! Problems: How many new sets can you build by making sets of the four sets we know about so far, i.e. Ø, {Ø}, Template:Ø and (Ø, {Ø}}? List them. Make up a procedure that will take any set (including the null set) and produce a new (different) set. Starting with the null set, write the first 6 sets your procedure produces if you repeatedly apply it to the previously produced set. Will your procedure ever produce the same set a second time? If so, write a second procedure that never repeats. If your first procedure never repeats, write a second one that does. Constructing the natural numbers from sets It probably will come as a surprise to you, but you constructed the natural numbers in the previous problem set! You probably didn’t recognize them because you wrote them in an unfamiliar notation. But how we write (or pronounce) numbers doesn’t have any effect on their meaning. In English, we say “zero, one, two, three, …” while in French, we say “zéro, un, deux, trois, …”, but the numbers aren’t any different. Similarly , we could use different mathematical notations, say 0, 1, 2, 3, … or <nothing>, I, II, III, …, and the underlying numbers themselves wouldn’t be any different. What is important is what properties the numbers have. For the natural numbers, the important properties are: For any n N, there is a function (we’ll call it a “successor” function and write it as succ) whose value is another natural number. There is a single n N that is not the successor of any other natural number. We’ll call this number “zero” and write it as “0”. For any n N that isn’t 0, there is only one m N such that n = succ(m). That’s it. Any set of objects satisfying those properties is essentially the natural numbers. (Later, we’ll get more precise about what we mean as “essentially”.) Everything else you know about the natural numbers (the properties of addition, multiplication, …) follow as a natural consequence. Cool, huh? We’re not going to actually show this right now, but we will later in the Discrete Math topic.

Russell’s paradox

Russell’s paradox, named after philosopher/mathematician Bertrand Russell is the standard example of how naïve set theory can get into trouble by accepting anything as a set. To see this, let’s let our universal set U be the set of all sets, and we’ll consider those sets that don’t contain themselves as members. (Interlude: None of the sets we have seen so far contain themselves as members. In fact, it isn’t possible for a finite set to contain itself as a member. But what about the infinite set Ц = …{{{{{{ Ø }}}}}}… This is an infinite set, the limit of the sequence Ø, { Ø }, Template:Ø, {{{ Ø }}}, … . Every set in this sequence has only one element. In the case of Ц, it’s element is …{{{{{{ Ø }}}}}}… which is just Ц. So Ц Ц which is to say that Ц contains itself. End of interlude.) Let’s call sets that don’t contain themselves to be “reasonable” sets. Clearly, there are lots of reasonable sets. We’ll define R to be the set of all the reasonable sets. (You can’t get much more reasonable than that. ) So . But it turns out that R embodies a contradiction. To see this, ask yourself the question Is R a reasonable set?” If your answer is “yes”, then R contains R because we defined R as the set of all reasonable sets. On the other hand, R does not contain R by the definition of reasonable. It doesn’t do any good to answer “no” to the question. You’ll still conclude both that R contains R and R does not contain R. Axiomatic set theory resolves this paradox by being more careful about defining what a set is. It turns out that the “set of all sets” is not something that can be constructed in axiomatic set theory.