Lesson Six - Set Theory

A lot of the techniques we have learned so far to help us solve complex problems have focused on ways to simplify the problems by break them into groups. Set theory, which you will learn about in this lesson, is a continuation on that. Set theory allows us to group many elements into just a few categories (called sets) in order to more easily see relationships.

Elements are data points which we’re interested in analyzing. An element can be a person, an object, or just a number. A set is a group of elements which all have something in common.

Most things have specific properties and characteristics that allow us to place them into categories or sets. Girl, for example, can be a set, just as wears glasses can be another set. Look at the figure below to see how the two sets can interact with one another.

This kind of figure is called a venn diagram and it is very helpful for visualizing sets. As you can see, there are two sets: Girls and Wears Glasses. The people who fall into both sets (they wear glasses and they’re girls) go in the middle where the two sets overlap.

You will see that sets can take various forms. Regardless of the form, the ability to recognize similarities and differences between things and to place them into sets can be a helpful skill. The formal study of sets and its relation to logic is called set theory. Set theory has one fundamental assumption – that an element is either inside the set or outside the set. Unclear or ambiguous elements must take one side or the other. Thus, you have to decide, wears glasses or not. Look at the example below.

You see that A is outside of the set, B and D are inside the set, but what about C? Is it inside or outside the set? In set theory, like Boolean Logic, there is a clear yes or no, true or false answer. Therefore, something like C that is in between is not allowed. Also, set theory does not apply to statements like “ He is a good person” or “She is beautiful.”

This single fundamental assumption is extremely important because you evaluate whether or not an element is in the set. Specifically you answer the question “Is the element in the set?” true or false. For example, using the previous example, element A is in the set. False. So how can we use sets to evaluate statements?

How can we use sets to organize information? Look at the set and elements below.

1. Set Unions

This example also shows two subsets and one superset. Set A and Set B are subsets of Set C, which is a superset. There is also a Cardinal Number of a set. This is simply the number of elements in each set. For example the cardinal number of Set A and Set B is 6. It is written: |A| = 6. The Cardinal Number for Set C would be 2. |C| = 2.

2. Set Intersections

Therefore if you are trying to solve for C with the equation C = A  B, your answer is C = {f,g}. In other words, C equals the intersection of A & B, which are the points {f,g}.

Example 1

A = {1,2,3,4}; B = {2,4,5,6}

  1. Find A  B
  2. Find A  B

Answers

  1. A  B incorporates all the elements of A and B. {1,2,3,4,5,6}
  2. A  B is only the common elements of A and B. {2,4}

3. Set Difference

Set difference isolates elements from one or more sets.

For example:

4. Subset

Subsets are sets within a larger set, like the example with A, B, and C on the previous page. Below we have Set X and Set Y. You see that Y is within Set X.

Y  X (Y is a subset of X).

5. Not Subset

It is occasionally important to establish when a set is NOT part of another set. For this we use the not subset symbol.

T is not a subset of S.                  T  S

6. Symmetric Difference

The symmetric difference of two or more sets refers to the items not in both groups.

Symmetric difference = A[horse, pig, sheep, cow], B[giraffe, elephant, lion, monkey]
Or
Symmetric difference = A  B – A  B

7. Set Product

Set product is like distribution. It multiples each element in one set with all the elements of the other sets. Imagine we wanted to know the product of the Set A and Set B.

The product of Set A and Set B
= {(1 • 1) + (1 • 10) + (1 • 100) + (1 • 1000)}
+ {(2 • 1) + (2 • 10) + (2 • 100) + (2 • 1000)}
+ {(3 • 1) + (3 • 10) + (3 • 100) + (3 • 1000)}
+ {(4 • 1) + (4 • 10) + (4 • 100) + (4 • 1000)}

As you can see, even a few simple numbers can create a complicated algorithm. This is complicated because it encompasses all possible combinations of all the elements of all the groups.

The idea behind graphing is to produce an area of the combinations of A and B.

8. The Empty Set

Take a moment to calculate the number of fish that speak German. Finished? It didn’t take long, because there are no fish that can speak German. In this sense, it is possible to assert something that does not exist. However, we can say the number of birds able to speak German equals the number of bunny helicopter pilots. Thus, there is something such as an empty set, symbolized by .