Abstract Algebra

Some notes from Abstract Algebra Session 2 (more info to appear soon, including link to the video).

Read More

Lesson 5 in Perceptive Mathematics: union of sets

If you love collecting shells from a beach, you surely have at your home shells collected from several different beaches. 

Let's say you have shells from three different beaches. Let B1 be the set of shells collected from the first beach, B2 the set of shells collected from the second beach, and B3 the set of shells collected from the third beach. Altogether, your collecting activity can be recorded by the set A={B1, B2, B3}. However, when you bring those shells at home, you will most likely mix them all up in one heap of shells. So if for instance, B1={S1, S2, S3}, B2={S4, S5} and B3={S6, S7, S8, S9}, where the symbols S1, ...., S9 represent the collected shells, then your collection at home, after the shells have been placed all together, is given by the set C={S1, S2, ..., S9}. Now, more generally, the union of a set A is the set C of all elements of individual elements of A. We write the union of A as UA, thus C=UA.

Exploration 5.1. Compute the following unions (i.e., write down what set they equal to by explicitly listing the elements enclosed between braces).  

• U{}=?
• U{{}}=?
• U{{{}}}=?
• U{{},{A}}=?
• U{{A, B}, {A, {}}, {C}}=?
• U{{A, B}, {A, C}, {{A, C, {}}}}=?

The union of a set can be seen as a reverse construction both to the singleton construction as well as the quotient construction. If we begin with a set A, then take its singleton, {A}, and then take the union, U{A}, we get back the same set A. Indeed, the elements of U{A} must be elements of elements of {A}. But {A} has only one element, it is A. So elements of U{A} are the same as elements of A, which means that the two sets are the same set. Similarly, if Q is a quotient of the set A, then elements of UQ are all elements of classes formed during partitioning. We know by the first axiom of partitioning that these elements must be elements of A. Moreover, by the second axiom of partitioning, no element of A will be missed (every element of A is an element of some class, i.e., of some element of Q). So the sets UQ and A are once again the same set. Intuitively, if partitioning separates a set into pieces, the union puts these pieces back together.

Exploration 5.2. 

• Draw several different tree diagrams for sets, ensuring in each case that every element of the set being considered is itself a set. Then, for each of these drawings, draw the tree diagram for the union of the corresponding set. 
• While busy with the task above, did you notice that the union construction shrinks the height of the tree? In contrast, the singleton and the quotient constructions grow the trees (make a few sketches to get convinced of this). 

Read More

Lesson 4 in Perceptive Mathematics: tree diagrams for sets

 A set can be pictured as a tree. 

We describe this by examples. Consider for instance the set {A, B, {A, C, D, E}}. It has three elements, A, B, and the set {A, C, D, E}, which in turn has four elements, A, C, D, and E. Let us call this set X, so X={A, B, {A, C, D, E}}. Note that by coincidence, X and one of its elements, namely, {A, C, D, E}, share a common element A. This is permissible and it does not mean that there are two copies of A -- the A that is an element of X is the same A that is an element of X. Of course, in notation, we are forced to write out the set with two copies of A, but the two are supposed to represent the same object A. Now, to represent the set X as a tree, we start X and branch it out in as many elements as X has. So there will be three branches going out of X. The first two branches terminate with labels A and B, respectively. The third branch branches out further into four branches, which terminate with labels A, C, D, and E. As a result, we get the following "tree":

If one of A, B, C, D, E in this example is itself a set, we can expand the diagram further. For instance, if A={C, D}, then we get the tree

Exploration 4.1. How would you represent a singleton and the empty set as a tree? Using this insight, represent the following sets as trees:

• {{}}
• {{{}}}
• {{},{{}}}
• {{A, {{}, B}}}

Note that representing a set as a tree introduces even more redundant information than in the symbolic notation of sets. First, let's list some redundancies in the symbolic notation:

• Repetition of elements: the set {A} is the same set as the set {A, A} since both sets have exactly one element, the object A (recall that just because we mention a symbol twice does not mean it has two separate meanings).
• Order of elements: the set {A, B} is the same set as the set {B, A} because both sets have the same elements.

With the tree notation, in addition to the redundancies inherited from the symbolic notation, there is also a redundancy of the shape of the drawing, such as the length of branches, for instance. For instance, the last diagram above represents the same set as the following one:

Exploration 4.2. Represent as trees each of the quotients of the set X from the example above.

Read More

Lesson 3 in Perceptive Mathematics: singletons

A singleton is a set having exactly one element. For instance, {R} is a singleton, where R is a rose. Now, we do want to think of a rose R as a different object to the singleton {R}. These objects even have different types. The first is a plant, and the second is a set. Here is an illustrative analogy: a rose is not the same thing as as a vase with a rose in it.

The empty set {} is not a singleton, since it does not have any elements. Neither is a set having two or more different elements a singleton. We can turn any object B into a singleton, by considering the set having B as its unique element, i.e., the set {B}. What happens when B={}? In notation, we get {B}={{}}. Now, what is the set {{}}? Is it still the empty set? Let us see. The empty set does not have any elements. What about the set {{}}? Does it have any elements? Well, this set is a singleton (remember, it is equal to {B}, where B={}), so yes, it has exactly one element, that element being the empty set B={}. So, since {} has no elements and {{}} has an element, these two sets cannot be the same set (if they were the same set, they would have the same elements).

Exploration 3.1. Decide whether the set {{{}}} is the same set as the set {{}}.

Consider again the set {R}. Is there a way to partition this set? Recall that during partitioning we arrange elements of a set in classes. Since a class cannot be empty (the third axiom for partitioning), there is only one class that can be formed, the class consisting of the unique element of the given set, so it is the class {R}. What is the corresponding quotient? Well, a quotient is the set of all classes formed during partitioning. Since there is only one class that can be formed, we get that the quotient is the singleton {{R}} (elements of the partition must be the classes). So if V={R} then the singleton of V is its quotient {V}={{R}}, which happens to be the only quotient that V={R} has.

Note that the singleton {R} and its quotient {{R}} are different sets, since, they do have different elements. The element of the first singleton is R, the rose, while the element of the second singleton is the set {R}, and we already agreed that R and {R} are different from each other. 

Exploration 3.2. How many quotients does the empty set have? Is the quotient of the empty set {} the singleton {{}}? Revisit the axioms for partitioning to get help with answering this question.

Here is another way of understanding singletons and sets in general. The thought of a rose is different from the actual rose. The thought of the thought of a rose is different from both. Every time we add "the thought of" we can interpret this as a process of taking a singleton:

• R is the actual rose
• {R} is the thought of a rose
• {{R}} is the thought of the thought of a rose, etc. 

In this analogy, the empty set can be interpreted as the thought of "nothing". Nothing does not exist, but the thought of nothing does.

Read More

Lesson 2 in Perceptive Mathematics: quotient of a set

Elements in a set do not have to have any similar features. For instance, we can have a set {A1, A2, M1, M2, M3} where A1, A2 are apples and M1, M2, M3 are mountains. When we have a set whose elements are of different types, we often like to sort these elements by grouping elements of the same type together. Thus, for instance, in the set {A1, A2, M1, M2, M3} we may wish to group the apples together into one set {A1, A2} and group the mountains together into another set {M1, M2, M3}. This process is called a partitioning of a set, and the groupings we get as a result of partitioning are called classes. Note that the classes are themselves sets, such as the class {A1, A2} and the class {M1, M2, M3} for the partitioning just discussed.

Exploration 2.1. Come up with real-life examples of partitioning and in each case, describe what the classes are. Here is a picture for inspiration:

In the example we discussed, can we partition {A1, A2, M1, M2, M3} into the classes {A1, A2, M1} and {M2, M3}? From the first look, it does not seem like apples and the mountain are of the same type, right? But of course, it very much depends on the rule of sorting. For instance, the apples A1, A2, and M1 can come from one country, while M2 and M3 can come from another country. Then if we sort according to which country these entities come from, we will get indeed the classes {A1, A2, M1} and {M2, M3}. In general, partitioning does not restrict the rule of sorting in any way, as long as the classes fulfill the following axioms ("axiom" is a scientific word for a "rule"):

• Every element of each class must be an element in the set that is being partitioned.
• Every element in the set that is being partitioned must belong to exactly one class.
• A class of a partition cannot be the empty set.

We can organize the classes created during partitioning into one set: the elements of this new set are all classes created during the partitioning of the old set. This new set is called a quotient (or a partition) of the old set. For instance, for the partitioning of {A1, A2, M1, M2, M3} where the classes are {A1, A2} and {M1, M2, M3}, the quotient is {{A1, A2}, {M1, M2, M3}}. In our second example of partitioning, where the classes were {A1, A2, M1} and {M2, M3}, the corresponding quotient is {{A1, A2, M1}, {M2, M3}}. Thus, both {{A1, A2}, {M1, M2, M3}} and {{A1, A2, M1}, {M2, M3}} are quotients of the set {A1, A2, M1, M2, M3}.

Exploration 2.2. List all possible quotients of the set {A, B, C}. Make sure that the partitioning used for each quotient satisfies the three axioms stated above. Furthermore, to ensure that your list does contain all possible quotients of {A, B, C}, verify that every possible outcome of partitioning that satisfies these three axioms has been considered. How many quotients does the set {A, B} have?

Here are some notes on terminology. The terms "partition" and "quotient" are interchangeable. Note that in the English language, "partition" is both a verb and a noun, while "quotient" is only a noun (so we will never say "quotienting"). The quotient of a set is often called a quotient set, to distinguish it from the quotient of numbers.

Read More

Lesson 1 in Perceptive Mathematics: the concept of a set

 Look at this photo of eight apples.

How many apples are there in the photo? Eight. How many photos are there? One. Several objects or entities seen as one thing is called a set. The objects that make up the set are called its elements. Unlike in a photo, the arrangement of these objects among each other, or any information about the elements of the set apart from knowing what these elements are, is not considered to be part of the information about the set. Thus, for instance, the set of the eight apples that we see in the photo would be the same as the set of the same apples shown in a different photo, where these apples have been rearranged.

If A1, A2, ..., A8 are symbolic representations of the apples shown in the photo, then {A1, A2, A3, A4, A5, A6, A7, A8} is how we symbolically represent the set of those apples. 

Exploration 1.1. According to your interpretation of the definition of a set given above, which of the following sets should be the same set as the set {A1, A2, A3, A4, A5, A6, A7, A8}?

• {A1, A3, A2, A4, A5, A6, A7, A8}
• {A1, A2, A3, A4, A5, A6, A7}
• {A1, A2, A3, A4, A4, A6, A7, A8}
• {A1, A2, A3, A4, A4, A5, A6, A7, A8}

Just like we could add apples to a photo, or take some away, we can add elements to a set, or take them away. For instance, let us start with the set {A1, A2, A3}. If we take A3 away from this set, we get the set {A1, A2}. What happens if we take away A1 and A2 as well? Can we do that? Well, taking away A2 gives us {A1}, and taking away A1 from this set should perhaps give us {}? Such a set, that is, a set having no elements, is also allowed to be a set. It is called the empty set.

Exploration 1.2. Start with a set of three apples and a set of three mountains (represent the mountains by M1, M2, M3). Take away one element from each set, and do this three times. Will the resulting sets be the same set or will they be different sets? More generally, is there only one empty set, or are there many empty sets?

Read More