Kbyte

Set Theory: A Primer

Developed by Georg Cantor and Richard Dedekind in the 1870s, set theory studies some of the most elementary objects in mathematics – sets.

A set is a collection of objects which are called elements. Elements may be anything from numbers, to people, to even other sets. With these simple constructs mathematicians have managed to build most of our known mathematics and probe some of the most profound questions in the field. Much like numbers, sets can be combined, compared, or even transformed into one another.

You may not be familiar with sets in a mathematical sense but you use them every day. They are really quite simple and I believe are a great introduction to a different type of mathematics than most are used to. Sets are denoted using curly brackets. For instance, we may create a set we will call Names₁ of three elements defined below.

Names₁ = { Mary, Todd, Joseph }

A single set doesn’t really allow us to do much. It simply contains a number of elements. Let us define another slightly larger set called Names₂.

Names₂ = { Mary, Frank, Peter, Tom }

From these two sets, more interesting questions can be asked. For instance, what names are in both sets? The answer is clearly Mary. In set theory this would be defined as the intersection (represented by the ∩ symbol) of the two sets and is shown below. We can also visualize this operation using a venn diagram.

Names₂ ∩ Names₁ = { Mary }

We can also ask what set contains all the elements of both Names₂ and Names₁? Once again, there is a set theory equivalent, the union.

Names₂ ∪ Names₁ = { Mary, Todd, Joseph, Frank, Peter, Tom }

As mentioned – all sets have sizes but there is more to size than meets the eye.

Cardinality: The Size of Sets

Count the elements and you have found the cardinality of a set. For instance, the cardinality of Names₁ is 3 and the cardinality of Names₂ is 4. In set theory this would be denoted via the use of vertical bars around the set name.

|Names₁| = 3
|Names₂| = 4

Now we can tell the size of any set. Or can we? These sets have all been finite, but mathematicians often work with sets that consist of mathematical elements, such as numbers. Consider a set of the counting numbers – also known as the natural numbers.

Using math we can talk about vast sets like the naturals above using much easier to read notation. The natural numbers can be defined as the set N.

N = { 0, 1, 2, 3, 4, 5, … }

What is the size of the set of natural numbers, N? Infinite. That is,

|N| = ∞

With infinite introduced we can reach some conclusions that may seem contradictory at first glance. For instance, which set is larger? N, the infinite set of natural numbers or E, the infinite set of even numbers?

N = { 0, 1, 2, 3, 4, 5, … }
or
E = { 0, 2, 4, 6, 8, … }

Comparing Finite Sets: Which is bigger?

When are set sizes the same? For finite sets you count all the elements of each set and see if the amounts are equal. For instance, the two finite sets below are the same size of 3.

Can we determine if two sets are the same size without counting? Consider another example: In a movie theater we could have a set of seats and set of ticket holders.

If the house is fully packed then we can say without counting that the sets are the same size.

This may seem obvious but often times in mathematics we are just stating the obvious in extremely abstract terms. The reasoning above is similar to finding a one-to-one mapping from the set of people to the set of seats.

A one-to-one mapping is a way to match each element in one set to exactly one element in another set, with no leftovers in either set.

For our theater example above, the mapping was the ticket because each ticket assigned one holder to one seat. When dealing with numbers we can use mathematical functions as a mapping. Consider our previous example of the two finite sets.

Is there a simple function you can think of that takes each element in the first set to a single element in the second set?

The function y=2x maps each element in the first set to a single element in the second set.

The function shows that for every element in the left there is an element in the right. Perhaps you noticed the asymmetry in this statement – unfortunately this single mapping only shows that the set on the left is not larger than the set on the right. For instance there could be an element in the right set which hasn’t been reached. If the right set had an extra element 5 then no element in the left set could reach it via our mapping y=2x.

How do we make sure the right set is the same size? We must also find a mapping from the right set to the left set. In this case, we can use the inverse of the previous function x=y/2.

Now we know each element in the right set has a corresponding element in the left set. We can now say the sets are the same size. But weren’t we talking about infinite sets?

Comparing Infinite Sets: Which is bigger?

Lets look at the previous question. Are the natural numbers and even numbers the same size?

N = { 0, 1, 2, 3, 4, 5, … }
or
E = { 0, 2, 4, 6, 8, 10, … }

All we need to do is find our one-to-one mappings from N to E and E to N. How can we pair off each number in N to E? We can use the exact same mappings from our finite example.

y = 2x and x = y/2

This tells us for each element in E there is one element in N and vice versa. And now we have paired off each element in the sets even though they are infinite! The sets N and E are the same size! In mathematics this infinite is known as countably infinite and is denoted by the symbol aleph-null.

ℵ₀

• When a sets cardinality is ℵ₀ then it is countably infinite. A useful feature of being countably infinite is that any countably infinite set can be turned into a numbered list. Why is that? Because a list is mapping from the counting numbers to what elements are being listed.

1. element 1
2. element 2
3. element 3
…

Maybe the fact that two infinites are equal isn’t surprising. As we are about to see, this is not always the case.

Infinites: Beyond ℵ₀

There are other ways to define sets. We may define a set S using a function as follows:

S = { x | f(x) }

This reads as “S is the set of all elements x such that f(x) is true”. To determine if an element is in the set S we see if f(x) is true.

For instance, let’s look at the set of all real numbers between 0 and 1.

We will use a function to define this set which we will call R_(0,1).

R_(0,1) = { x | 0 < x < 1 }

This set is every number inbetween 0 and 1. If you want to know if a number is in this set you just see if it between 0 and 1.

Something to consider is there are an infinite amount of numbers between 0 and 1. Is the infinity the same size as the infinity of the natural numbers?

Multiple Infinites: The Diagonal Argument

How can we determine if R_(0,1) and N are the same size? We will use a proof written by Georg Cantor in 1891 – which is famously known as the diagonal argument.

It begins by assuming that R_(0,1) is the same size as N. Remember if a set is the same size as N then it is countably infinite and can be listed. Suppose our list looks like this…

Perhaps your list doesn’t look like this but it doesn’t matter. As soon as we create a list we can create a new number that is not on the list. Here is how…

We pull the first digit from the first number and change it. We pull the second digit from the second number…and change it. We continue this process for every number on the list. Below is our list with the digits we changed in highlighted. Note how this creates a diagonal pattern in the list hence the name.

In order to create a new number we may just add one to each digit we pulled. If the digit we pulled is 9 then turn it into 0. Using this technique the beginning of our new number would look like…

.74780…

This new number is not in our list. How do we know that? Because we constructed it to make sure it didn’t match any other number on the list exactly. Let’s add this number to the list. Have we listed all the numbers? No, because we can now construct a new number that isn’t on the new list using the same process.

This applies to any list that can be created. We have shown that we can’t map N to R_(0,1) because there is always an element in R_(0,1) that isn’t on the list. This means that R_(0,1) is larger than N. R_(0,1) is infinite but not countably infinite. We have stumbled upon what is called the infinite of the continuum. This list is uncountably infinite.

Is there a way we can compare the sizes of these infinities?

Power Sets

There is another operation that can be performed on sets. You can determine the power set of a given set. This will be denoted using the letter P. For instance the power set of a set A is denoted as follows

P(A)

The power set of a set is the set of all possible subsets of that set. Where a subset is any set that contains only elements from the original set. One set that is always a subset of any set is the empty set or what is known as the null set. This is denoted by the following symbol.

∅

Now let’s find the power set of another set of names.

Names₁ = { Mary, Todd }

Every possible subset of Names₁ is…

P(Names₁)={ ∅ , {Mary}, {Todd}, {Mary, Todd} }

A seemingly not so surprising property of the power set is that it is always larger than the original set. It actually follows a very simple rule. To discover this rule we are going to represent a set within the power set as a binary number. How do we do this? For our names set we consider all two digit binary numbers. The left digit will represent Mary and the right one will represent Todd.

We just found a mapping between the set of all binary digits of length N and the subsets of a set. What does this do for us?

Consider how many binary numbers of length 1 there are. 2.
Consider how many binary numbers of length 2 there are. 4.
Consider how many binary numbers of length 3 there are. 8.

See the pattern? For each binary digit added the total possible numbers doubles. That is…

Binary Digits of Length n = 2ⁿ

So the power set of a set with N elements has 2ⁿ elements.

The Power Set of the Set of Natural Numbers, P(N)

What would the power set of the set of natural numbers look like? It would be huge. Consider creating another table like we did before except this time with the natural numbers. For each binary number we create we will have a subset of the natural numbers.

Clearly, there are a lot of sets in the power set of the natural numbers. There is another thing about this the table. What would happen if we took each row from the table on the left and turned it into a binary number and placed a decimal in front of it?

We would get infinite long binary decimals like .00000000…, .100000000…, .101010111111… , .11111111111…, etc. These are all the numbers between 0 and 1 in binary form.

We just mapped the power set of the natural numbers to the real numbers between 0 and 1. This means these sets are the same size. What is the size of the power set of natural numbers?

|P(N)| = 2^|N| = 2^ℵ₀

And since the real numbers are the same size…

|R_(0,1)| = 2^ℵ₀

So we know that the infinite of the continuum is larger than the countably infinite. That is,

ℵ₀ < 2^ℵ₀

But is there an infinite between these two infinites?