Monday, September 10, 2012

Introduction to set theory

The midterm has been scheduled for October 24, in class.

1Sets¶

A set is a simple (finite or infinite) collection of elements. Examples of sets:

• $\{0, 1, 2\}$
• $\mathbb{N}$
• $\mathbb{Q}$
• $\mathbb{Z}$

Sets can be described fairly informally (e.g., $\{1, 2, 3, \ldots\}$) or formally (e.g., $\mathbb{N}$, or like $\{n \in \mathbb{N}: n < 4\}$ for $\{0, 1, 2, 3\}$¹). To describe the set of all primes, for example, we can say $\{2, 3, 5, 7, 11 \ldots \}$, but to describe it more rigourously, we could say $\{n \in \mathbb{N}: n = ab \to a = 1 \lor b = 1 \, \, \forall (a, b) \in \mathbb{N}\}$ (the notation is somewhat bastardised but hopefully it makes sense). To describe the rational numbers: $\{a \in \mathbb{Z}, b \in \mathbb{Z} / \{0\}: \frac{a}{b}\}$.

1.1Operations on sets¶

Union ($A \cup B$): $\{x: x \in A \lor x \in B\}$

Intersection ($A \cap B$): $\{x: x \in A \land x \in B\}$

Exclusion ($A \setminus B$): $\{x: x \in A \land x \notin B\}$

Symmetric difference ($A \Delta B$): $\{x: x \in A (A \cup B) \land x \notin (A \land B)\}$ (so the XOR of two sets)

1.2Functions on sets¶

A function, given by the notation $f: A \to B$, is a deterministic mapping that returns an element $b \in B$ (the range, or codomain) for any element $a \in A$ (the domain). Deterministic in this context means that an element $a$ is always mapped to the same element $b$.

1.2.1Properties of functions¶

An injective function (known colloquially as one-to-one) never maps two elements in the domain to the same element in the range. Mathematically: if $f(a) = f(a')$, then $a = a'$.

A surjective function maps something to every element in $B$. Mathematically: $\forall b \in B$, $\exists a \in A$ such that $f(a) = b$.

A bijective function, also called a bijection, is one that is both injective and surjective.

1.2.2Example functions¶

$f(x) = x^2: \mathbb{R} \to \mathbb{R}$ is neither injective nor surjective. (Both $a$ and $-a$ map to the same number, $a^2$, for $a \neq 0$, and none of the negative numbers are in the range.)

However, $f(x) = x^2: \mathbb{R}^+ \to \mathbb{R}^+$ (so from the positive reals to the positive reals) is both injective and surjective, so it is bijective. This goes to show that the properties of a function depend on the domain and range under consideration.

1.3Cardinality¶

Simply put, the cardinality of a set is the number of elements it contains - its size, or length.

Two sets $A$ and $B$ have the same cardinality if there exists a bijection between $A$ and $B$. For example, the sets $A = \{1, 2, 3\}$ and $B = \{0, 4, 9\}$ have the same cardinality; an example of a bijection between the two sets is one that maps 1 to 0, 2 to 4, and 3 to 9.

1.3.1Infinite sets¶

Let $\mathbb{N} = \{0, 1, 2, \ldots \}$. $\mathbb{N}^+ = \{1, 2, 3, \ldots \}$. Now, is $\mathbb{N}^+$ larger than $\mathbb{N}$? That is, does it have a greater cardinality?

The answer is no. While it may appear that $\mathbb{N}^+$ is larger, there is in fact a bijection between the two: $f: x \to x + 1$, $\mathbb{N} \to \mathbb{N}^+$. This is illustrated in Hilbert's paradox of the Grand Hotel: considering a hotel with an infinite number of occupied rooms (numbered 1, 2, 3 etc), is it possible to make space for one new arrival? Indeed it is, simply by moving the guest in room 1 to room 2, the guest in room 2 to room 3, etc.

Now, consider the sets $\mathbb{Z}$ and $\mathbb{N}$. Do these sets have the same cardinality? Indeed, they do, and we can use the following bijection:

$$f: \mathbb{Z} \to \mathbb{N}, \, x \mapsto \begin{cases} \text{ if } x > 0, & 2x - 1 \\ \text{ if } x \leq 0, & 2| x | \end{cases}$$

What about the the set of all Cartesian pairs involving natural numbers, $\mathbb{N}^2 = \{ (a, b), a, b\in \mathbb{N} \} = \mathbb{N} \times \mathbb{N}$? Again, we can find a bijection between that and $\mathbb{N}$, so they do have the same cardinality. (I'm not exactly sure how, but it has to do with going through $\mathbb{N}^2$ diagonally.)

We now consider $\mathbb{Q}$. Well, this set is actually "smaller" than $\mathbb{N}^2$ (to see why, treat each ordered pair $a, b$ as $\frac{a}{b}$, and you will see that there are some duplicates³). So this set does have the same cardinality as that of the natural numbers.

As we can see, cardinality is not so straightforward when it comes to infinite sets.² Sets that appear to be different in size may still have the same cardinality. However, the above sets were merely examples of countably infinite sets. What happens when we consider sets that are uncountably infinite?

1.3.1.1Uncountably infinite sets¶

First of all, what is an uncountably infinite set? We can answer this with a definition for a countably infinite set: a set whose elements can be described by a finite amount of data. For example, the set of all books is countable, because any individual book is finite - that is, one only needs a finite number of words in order to express the contents of any book. The natural numbers compose a countably infinite set (as does every set that has the same cardinality as the natural numbers) .

In contrast, a real number is not finite, as you need an infinite sequence of digits to describe it. For example, to describe the square root of 4, you really do need an infinite number of zeros after the two to properly define it, You can encode within a real number any sequence of digits of any length. In that vein, you can encode all the data associated with all the books in the world in a single real number.

In a sense, this is a more profound type of infinity than that of the countably infinite sets. Not only is the set itself infinitely large, but each element within the set contains an infinite amount of data. As such, these uncountably infinite sets, of which $\mathbb{R}$ is one example, do not have the same cardinality as the countably infinite sets.

Next, we will look at a slightly more involved example of an uncountably infinite set, and will prove that it is uncountable.

1.3.1.2The set of all functions¶

Let $\mathcal{F}$ be the set of all functions from $\mathbb{N}$ to $\mathbb{N}$. We now endeavour to prove that $\mathcal{F}$ is an uncountably infinite set. We can do this with a proof by contradiction, to prove that it is not a countably infinite set (i.e. there does not exist a bijection between $\mathcal{F}$ and $\mathbb{N}$.

So first, we suppose there is a bijection from $\mathbb{N}$ to $\mathcal{F}$. Recall that $\mathcal{F}$ is the set of all functions from $\mathbb{N} \to \mathbb{N}$. Now, let's see if we can find a function $f: \mathbb{N} \to \mathbb{N}$ not in $\mathcal{F}$. Well, if we let $g_0: \mathbb{N} \to \mathbb{N}$ be the first element $\in \mathcal{F}$, consider the value of $g_0$ at 0. Let's say that $g_0(0) = \alpha$. Well, what if we made a new function $h$, for which $h(0) = \alpha + 1$? Clearly, $h \neq g_0$.

Of course, that's not enough to make a function that is different from every function in $\mathcal{F}$. To do that, we have to define $h$ for every value in the domain, and in the process ensure that it is not the same as any other function in $\mathcal{F}$. Well, what if we just make it differ by one from the value of a function in $\mathcal{F}$ for every value in the domain? Systematically, we could say: $h(1) = g_1(1) + 1$, and $h(2) = g_2(2) + 1$, etc. More generall, for $g_j(j)$, we have that $h(j) = g_j(j) + 1$.

This is enough to make a function that differs from every function in $\mathcal{F}$. Since we've reached a contradiction, it must be that our assumption about the existence of a bijection between $\mathbb{N}$ and $\mathcal{F}$ is incorrect.

This is essentially Cantor's diagonal argument, but applied to functions. Since there is no surjection from $\mathcal{F}$ to $\mathbb{N}$, there is no bijection either, and so the set is not countable.