College Math Teaching

January 16, 2015

Power sets, Function spaces and puzzling notation

I’ll probably be posting point-set topology stuff due to my being excited about teaching the course…finally.

Power sets and exponent notation
If $A$ is a set, then the power set of $A$, often denoted by $2^A$, is a set that consists of all subsets of $A$.

For example, if $A = \{1, 2, 3 \}$, then $2^A = \{ \emptyset , \{1 \}, \{ 2 \}, \{3 \}, \{1, 2 \}, \{1,3 \}, \{2, 3 \}, \{1, 2, 3 \} \}$. Now is is no surprise that if the set $A$ is finite and has $n$ elements, then $2^A$ has $2^n$ elements.

However, there is another helpful way of listing $2^A$. A subset of $A$ can be defined by which elements of $A$ that it has. So, if we order the elements of $A$ as $1, 2, 3$ then the power set of $A$ can be identified as follows: $\emptyset = (0, 0, 0), \{1 \} = (1, 0, 0), \{ 2 \} = (0,1,0), \{ 3 \} = (0, 0, 1), \{1,2 \} = (1, 1, 0), \{1,3 \} = (1, 0, 1), \{2,3 \} = (0, 1, 1), \{1, 2, 3 \} = (1, 1, 1)$

So there is a natural correspondence between the elements of a power set and a sequence of binary digits. Of course, this makes the counting much easier.

The binary notation might seem like an unnecessary complication at first, but now consider the power set of the natural numbers: $2^N$. Of course, listing the power sets would be, at least, cumbersome if not impossible! But there the binary notation really shows its value. Remember that the binary notation is a sequence of 0’s and 1’s where a 0 in the i’th slot means that element isn’t an element in a subset and a 1 means that it is.

Since a subset of the natural numbers is defined by its list of elements, every subset has an infinite binary sequence associated with it. We can order the sequence in the usual order 1, 2, 3, 4, ….
and the sequence 1, 0, 0, 0…… corresponds to the set with just 1 in it, the sequence 1, 0, 1, 0, 1, 0, 1, 0,… corresponds to the set consisting of all odd integers, etc.

Then, of course, one can use Cantor’s Diagonal Argument to show that $2^N$ is uncountable; in fact, if one uses the fact that every non-negative real number has a binary expansion (possibly infinite), one then shows that $2^N$ has the same cardinality as the real numbers.

Power notation
We can expand on this power notation. Remember that $2^A$ can be thought of setting up a “slot” or an “index” for each element of $A$ and then assigning a $1$ or $0$ for every element of $A$. One can then think of this in an alternate way: $2^A$ can be thought of as the set of ALL functions from the elements of $A$ to the set $\{ 0, 1 \}$. This coincides with the “power set” concept as set membership is determined by being either “in” or “not in”. So, the set in the exponent can be thought of either as the indexing set and the base as the value each indexed value can take on (sequences, in the case that the exponent set is either finite or countably finite), OR this can be thought of as the set of all functions where the exponent set is the domain and the base set is the range.

Remember, we are talking about ALL possible functions and not all “continuous” functions, or all “morphisms”, etc.

So, $N^N$ can be thought of as either set set of all possible sequences of positive integers, or, equivalently, the set of all functions of $N$ to $N$.

Then $R^N$ is the set of all real number sequences (i. e. the types of sequences we study in calculus), or, equivalently, the set of all real valued functions of the positive integers.

Now it is awkward to try to assign an ordering to the reals, so when we consider $R^R$ it is best to think of this as the set of all functions $f: R \rightarrow R$, or equivalently, the set of all strings which are indexed by the real numbers and have real values.

Note that sequences don’t really seem to capture $R^R$ in the way that they capture, say, $R^N$. But there is another concept that does, and that concept is the concept of the net, which I will talk about in a subsequent post.