4.1 Basic notions of set theory
In modern mathematics, there is an area called category theory36 which studies the relationships between different areas of mathematics. More precisely, the founders of category theory noticed that essentially the same theorems and proofs could be found in many different mathematical fields — with only the names of the structures involved changed. In this sort of situation, one can make what is known as a categorical argument in which one proves the desired result in the abstract, without reference to the details of any particular field. In effect, this allows one to prove many theorems at once — all you need to convert an abstract categorical proof into a concrete one relevant to a particular area is a sort of key or lexicon to provide the correct names for things.
Category theory probably shouldn’t really be studied until you have a background that includes enough different fields that you can make sense of their categorical correspondences. Also, there are a good many mathematicians who deride category theory as “abstract nonsense.” But, as someone interested in developing a facility with proofs, you should be on the lookout for categorical correspondences. If you ever hear yourself utter something like “well, the proof of that goes just like the proof of the (insert weird technical-sounding name here) theorem,” you are probably noticing a categorical correspondence.
Okay, so category theory won’t be of much use to you until much later in your mathematical career (if at all), and one could argue that it doesn’t really save that much effort. Why not just do two or three different proofs instead of learning a whole new field so we can combine them into one? Nevertheless, category theory is being mentioned here at the beginning of the chapter on sets. Why?
We are about to see our first example of a categorical correspondence. Logic and set theory are different aspects of the same thing. To describe a set, people often quote Kurt Gödel — “A set is a Many that allows itself to be thought of as a One.” (Note how the attempt at defining what is really an elemental, undefinable concept ends up sounding rather mystical.) A more practical approach is to think of a set as the collection of things that make some open sentence true.37
Recall that in logic, the atomic concepts were “true”, “false”, “sentence” and “statement.” In set theory, they are “set”, “element” and “membership.” These concepts (more or less) correspond to one another. In most books, a set is denoted either using the letter \(M\) (which stands for the German word “menge”) or early alphabet capital roman letters — \(A\), \(B\), \(C\), etc. Here, we will often emphasize the connection between sets and open sentences in logic by using a subscript notation. The set that corresponds to the open sentence \(P(x)\) will be denoted \(S_P\). We call \(S_P\) the truth set of \(P(x)\).
\[ S_P = \{ x {\,:\,}P(x) \} \]
On the other hand, when we have a set given in the absence of any open sentence, we’ll be happy to use the early alphabet, capital roman letters convention — or frankly, any other letters we feel like! Whenever we have a set \(A\) given, it is easy to state a logical open sentence that would correspond to it. The membership question: \(M_A(x) = \,\) “Is \(x\) in the set \(A\)?” Or, more succinctly, \(M_A(x) = \,\) “\(x \in A\)”. Thus the atomic concept “true” from logic corresponds to the answer “yes” to the membership question in set theory (and of course “false” corresponds to “no”).
There are many interesting foundational issues which we are going to sidestep in our current development of set theory. For instance, recall that in logic we always worked inside some “universe of discourse.” As a consequence of the approach we are taking now, all of our set theoretic work will be done within some unknown “universal” set. Attempts at specifying (a priori) a universal set for doing mathematics within are doomed to failure. In the early days of the twentieth century, they attempted to at least get set theory itself on a firm footing by defining the universal set to be “the set of all sets” — an innocuous sounding idea that had funny consequences (we’ll investigate this in Section 4.5).
In logic, we had “sentences” and “statements,” the latter were distinguished as having definite truth values. The corresponding thing in set theory is that sets have the property that we can always tell whether a given object is or is not in them. If it ever becomes necessary to talk about “sets” where we’re not really sure what’s in them we’ll use the term collection.
You should think of a set as being an unordered collection of things, thus \(\{ \mbox{popover}, 1, \mbox{froggy} \}\) and \(\{ 1, \mbox{froggy}, \mbox{popover} \}\) are two ways to represent the same set. Also, a set either contains, or doesn’t contain, a given element. It doesn’t make sense to have an element in a set multiple times. By convention, if an element is listed more than once when a set is listed we ignore the repetitions. So, the sets \(\{ 1, 1\}\) and \(\{1\}\) are really the same thing. If the notion of a set containing multiple instances of its elements is needed, there is a concept known as a multiset that is studied in combinatorics. In a multiset, each element is preceded by a so-called repetition number which may be the special symbol \(\infty\) (indicating an unlimited number of repetitions). The multiset concept is useful when studying puzzles like “How many ways can the letters of MISSISSIPPI be rearranged?” because the letters in MISSISSIPPI can be expressed as the multiset \(\{1\cdot M, 4\cdot I, 2\cdot P, 4\cdot S \}\). With the exception of the following exercise, in the remainder of this chapter we will only be concerned with sets, never multisets.
Exercise 4.1 (Not for the timid!) How many ways can the letters of MISSISSIPPI be arranged?
If a computer scientist were seeking a data structure to implement the notion of “set,” he’d want a sorted list where repetitions of an entry were somehow disallowed. We’ve already noted that a set should be thought of as an unordered collection, and yet it’s been asserted that a sorted list would be the right vehicle for representing a set on a computer. Why? One reason is that we’d like to be able to tell (quickly) whether two sets are the same or not. It’s easier if the elements have been presorted.
Consider the difficulty in deciding whether the following two sets are equal.
\[ S_1 = \{ \spadesuit, 1, e, \pi, \diamondsuit, A, \Omega, h, \oplus, \epsilon \} \]
\[ S_2 = \{ A, 1, \epsilon, \pi, e, s, \oplus, \spadesuit, \Omega, \diamondsuit \} \]
If instead we compare them after they’ve been sorted, the job is much easier.
\[ S_1 = \{1, A, \diamondsuit, e, \epsilon, h, \Omega, \oplus, \pi, \spadesuit \} \]
\[ S_2 = \{1, A, \diamondsuit, e, \epsilon, \Omega, \oplus, \pi, s, \spadesuit \} \]
This business about ordered versus unordered comes up fairly often so it’s worth investing a few moments to figure out how it works. If a collection of things that is inherently unordered is handed to us we generally put them in an order that is pleasing to us. Consider receiving five cards from the dealer in a card game, or extracting seven letters from the bag in a game of Scrabble. If, on the other hand, we receive a collection where order is important we certainly may not rearrange them. Imagine someone receiving the telephone number of an attractive other but writing it down with the digits sorted in increasing order!
Exercise 4.2 Consider a universe consisting of just the first 5 natural numbers \(U = \{ 1, 2, 3, 4, 5 \}\). How many different sets having 4 elements are there in this universe? How many different ordered collections of 4 elements are there?
The last exercise suggests an interesting question. If you have a universal set of some fixed (finite) size, how many different sets are there? Obviously you can’t have any more elements in a set than are in your universe. What’s the smallest possible size for a set? Many people would answer 1 — which isn’t unreasonable! — after all a set is supposed to be a collection of things, and is it really possible to have a collection with nothing in it? The standard answer is 0 however, mostly because it makes a certain counting formula work out nicely. A set with one element is known as a singleton set (note the use of the indefinite article). A set with no elements is known as the empty set (note the definite article). There are as many singletons as there are elements in your universe. They aren’t the same though, for example \(1 \neq \{ 1 \}\). There is only one empty set and it is denoted \(\emptyset\) — irrespective of the universe we are working in.
Let’s have a look at a small example. Suppose we have a universal set with three elements, without loss of generality, \(\{1, 2, 3\}\). It’s possible to construct a set, whose elements are all the possible sets in this universe. This set is known as the power set of the universal set. Indeed, we can construct the power set of any set \(A\) and we denote it with the symbol \({\mathcal P}(A)\). Returning to our example, we have
\[\begin{array}{rcl} {\mathcal P}(\{1, 2, 3 \}) = & \left\{ \right. & \emptyset, \\ & & \{ 1 \}, \{ 2 \}, \{ 3 \}, \\ & & \{ 1, 2 \}, \{ 1, 3 \}, \{ 2, 3 \}, \\ & & \left. \{ 1, 2, 3 \} \quad \right\}. \end{array}\]
Exercise 4.3 Find the power sets \({\mathcal P}(\{1, 2 \})\) and
\({\mathcal P}(\{1, 2, 3, 4 \})\).
Conjecture a formula for the number
of elements (these are, of course, sets) in
\({\mathcal P}(\{1, 2, \ldots n \})\).
Hint: If your conjectured formula is correct you should see
why these sets are named as they are.
One last thing before we end this section. The size (a.k.a. cardinality) of a set is just the number of elements in it. We use the very same symbol for cardinality as we do for the absolute value of a numerical entity. There should really never be any confusion. If \(A\) is a set, then \(|A|\) means that we should count how many things are in \(A\). If \(A\) isn’t a set then we are talking about the ordinary absolute value
4.1.1 Exercises
What is the power set of \(\emptyset\)?
Hint: if you got Exercise 4.3, you’d know that this power set has \(2^0 = 1\) element.Try iterating the power set operator. What is \({\mathcal P}({\mathcal P}(\emptyset))\)? What is \({\mathcal P}({\mathcal P}({\mathcal P}(\emptyset)))\)?
Determine the following cardinalities.
\(A = \{ 1, 2, \{3, 4, 5\}\} \quad |A| =\)
\(B = \{ \{1, 2, 3, 4, 5\} \} \quad |B| =\)
What, in logic, corresponds the notion \(\emptyset\) in set theory?
What, in set theory, corresponds to the notion \(t\) (a tautology) in logic?
What is the truth set of the proposition \(P(x) =\) “3 divides \(x\) and 2 divides \(x\)”?
Find a logical open sentence such that \(\{0, 1, 4, 9, \ldots \}\) is its truth set.
How many singleton sets are there in the power set of \(\{a,b,c,d,e\}\)? “Doubleton” sets?
How many 8 element subsets are there in \[ {\mathcal P}(\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p\})? \]
How many singleton sets are there in the power set of \(\{1,2,3, \ldots n\}\)?
The classic text by Saunders Mac Lane (Lane (1998)) is still considered one of the best introductions to category theory.↩
This may sound less metaphysical, but this statement is also faulty because it defines “set” in terms of “collection” — which will of course be defined elsewhere as “the sort of things of which sets are one example.”↩