next up previous contents
Next: Set Theory and the Up: Formal Set Theory Previous: Naive Set versus Axiomatic   Contents

The Power Set

The power set will be a major component of our connection between sets and the laws of thought. While we will carefully avoid getting lost in too much algebra, we'll find it convenient to give them their own symbol and algebra if only to simplify the text itself. We will therefore call the power set $\Pi$ and refer to the power set of a set $S$ as $\Pi(S)$. We will also need to think about the power set of a power set and so on:

\begin{displaymath}\Pi^2(S) = \Pi(\Pi(S)) \end{displaymath}


\begin{displaymath}\Pi^3(S) = \Pi\left(\Pi\left(\Pi(S)\right)\right)\end{displaymath}


\begin{displaymath}...\end{displaymath}

As it is our plan to consider thought only in the context of the real Universe we need a very concrete set to play with to figure out what $\Pi$ is and how it works. Consider, therefore, the set consisting of four cards pulled out of an ordinary deck of playing cards. To make differentiating easy, we'll pull out the four aces and consider each card to be labelled by its suit.

Our toy set is thus:

\begin{displaymath}
S =\left\{\ \framebox{$\clubsuit$}, \framebox{$\spadesuit$}, \framebox{$\heartsuit$}, \framebox{$\diamondsuit$}\ \right\}
\end{displaymath} (3.1)

and the various subsets of this set make up its power set $\Pi(S)$, the existential set Universe for these four set objects.

Here is a listing of $\Pi(S)$ formed from the permutations of the four symbols taken 0 to 4 at a time (where order doesn't matter and each object can only occur once in a set):

$\displaystyle \Pi(S)$ $\textstyle =$ $\displaystyle \{ \left\{ \right\},$  
    $\displaystyle \left\{ \framebox{$\clubsuit$}\right\},$  
    $\displaystyle \left\{ \framebox{$\heartsuit$}\right\},$  
    $\displaystyle \left\{ \framebox{$\diamondsuit$}\right\},$  
    $\displaystyle \left\{ \framebox{$\spadesuit$}\right\},$  
    $\displaystyle \left\{ \framebox{$\clubsuit$}, \framebox{$\diamondsuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\clubsuit$}, \framebox{$\heartsuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\clubsuit$}, \framebox{$\spadesuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\diamondsuit$}, \framebox{$\heartsuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\diamondsuit$}, \framebox{$\spadesuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\heartsuit$}, \framebox{$\spadesuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\clubsuit$}, \framebox{$\diamondsuit$}, \framebox{$\heartsuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\clubsuit$}, \framebox{$\diamondsuit$}, \framebox{$\spadesuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\clubsuit$}, \framebox{$\heartsuit$}, \framebox{$\spadesuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\diamondsuit$}, \framebox{$\heartsuit$}, \framebox{$\spadesuit$}\right\},$  
    $\displaystyle \left\{\framebox{$\clubsuit$}, \framebox{$\diamondsuit$}, \framebox{$\heartsuit$}, \framebox{$\spadesuit$}\right\} \}$ (3.2)

where the first entry is the empty set about which we will have much to say later. In general there are $2^C$ such permutative subsets, where $C$ is the number of elements in the original set $S$, called the cardinality of the set.

There are two general kinds of things we can ``do'' algebraically with $\Pi(S)$ in terms of thought, reason, and language. One is that we can identify particular sets from $\Pi(S)$ by means of a suitable predicate expression. For example, I can ``create a set that has one card that is a black suit and is not a spade'' to uniquely define the set $\left\{
\framebox{$\clubsuit$}\right\}$.

There will often be many ways to create a predicate that specifies a single subset from the power set, but there is one way that always will exist. We can always specify the subset by explicitly specifying the list of its members3.13. We will call this method ``identification'' as it appears to be somehow related to the law of identity. Note that we use identification of the elements of the original set $S$, plus the processes of permutation and union to generate $\Pi(S)$. It seems difficult to imagine - literally - working with a set whose members cannot be identified independent of predicates used to describe them.

The second kind of thing we can do is to identify (in precisely this sense or via predicates) particular sets of subsets drawn from the $\Pi(S)$. If we specify (for example) ``the set of all sets in $\Pi(S)$ that contain a heart'' we end up with:

    $\displaystyle \left\{ \left\{ \framebox{$\heartsuit$}\right\},
\left\{\framebox...
...clubsuit$}, \framebox{$\diamondsuit$}, \framebox{$\heartsuit$}\right\}, \right.$  
    $\displaystyle \quad\quad\quad \left. \left\{\framebox{$\clubsuit$}, \framebox{$...
...diamondsuit$}, \framebox{$\heartsuit$}, \framebox{$\spadesuit$}\right\}\right\}$ (3.3)

Note that there is no way to collapse or reduce this to a member of the original power set. Each of these sets is an object in its own right that satisfies the criterion for selection.

This set of subsets (drawn from $\Pi(S)$) is itself a subset from a set of subsets of the subsets of the original set $S$3.14. Clearly this set is $\Pi^2(S)$. There seems to be no reason we cannot similarly recursively generate $\Pi^n(S)$ for any finite $n$ by iterating the process of making $\Pi^{n+1}(S)$ out of the sets generating by permuting the members of $\Pi^n(S)$ taken from 0 to the cardinality of times3.15 .

Of course, this process scales fairly agressively. We cannot actually draw even $\Pi^2(S)$ because the number of elements in it is $2^{2^4} = 2^{16} = 65536$, and the number of elements in the $\Pi^3(S)$ is $2^{2^{2^4}} = 2^{65536}$ and so on. However, if the cardinality of the original set $S$ is finite, so is the cardinality of the $\Pi^n(S)$ for any finite $n$. It's just large.

This may seem like a rather lot of complexity - in only the third level power set we already have considerably more objects than atoms in the physical Universe, for example, and it was only four cards! However, nothing less will do, as the answer to any set theoretic question we can ask must lie therein. Fortunately for us all, in the physical Universe a great deal of this complexity can be compressed by the human mind into structure.

We have already performed such a simplification - imagine if we specified $S$ in terms of the very large set of molecules that make up the cards, of the even larger set of atoms that make up the molecules, of the larger still set (call it, say, $S_e$) of of elementary particles (electrons and quarks and the various field quanta) that make up the atoms and their nuclei. The first level power set $\Pi(S_e)$ would contain many absurd (non-physical) subsets, but it would also include subsets that contained just three quarks and an electron, which on a good day could take on a new name: a ``hydrogen atom''. Indeed, follow the process of forming power sets forward, we will discover therein sets of sets of elementary particles that aggregate into other atoms, sets of sets of sets that aggregate into molecules, and so on up to cards.

So each of our cards is actually internally organized into structures that can be treated as independently identifiable subsets, themselves aggregated into independently identifiable subsets, all part of a whole hierarchy of $\Pi^n(S_e)$. The card is just one out of a very large number of such subsets, with all sorts of internal symmetries. The count of permutations, and permutations of permutations, etc. scales up extremely rapidly, which is why statistical mechanics works as well as it does in physics. There is no infinity there, but there are plenty of finities that (as I like to tell my students) are really good friends with infinity, their children play together, every now and then they all get together at infinity's house and drink a few beers.

We are therefore fortunate indeed that the human brain more or less automatically makes this sort of hierarchical decomposition when confronted with permutative power set-theoretic information that even at the first or second levels causes our internal number-registers to beep and return ``overflow''. And this is still, recall, just four cards. Imagine dealing with a deck of cards, or a Universe with many decks of cards that are one tiny part of one tiny planet in one small solar system in a single galaxy. Yet when I refer to each of these things, your mind effortlessly erases all the detail and replaces it with a hierarchy drawn from power set upon power set all the way down to whatever the real, existential microscopic elementary set of objects are that make up the Universe (where we might have to include all of the points in space and time some way in our set descriptions.

There are a number of consequences of this hierarchical decomposition. One to keep in mind is that when we reason about anything real (as opposed to mathematics, which might be real, might not - lots of controversy there and I don't want to get into it) we are forced to do so at the level of one of these $\Pi^n(S)$, and maybe a few recursions on either side of it. We cannot extend our reasoning down to the indefinitely microscopic or up to the indefinitely macroscopic. It is absurd to try to understand the rules of poker in terms of the properties and motion of the elementary particles of the Universe even though every particle in the game obeys rules defined at that level at all times. Nor do we compute the effect of folding a hand in the poker game on the motion of the Milky Way galaxy as it meanders around in the gravitational field of all the other galaxies in the Universe. More is different, and so is less.

For this and many other excellent reasons that we'll go into, our actual reasoning process about the actual Universe is almost immediately forced to be probabilistic. This suggests that when we get around to axioms and all that, one of the first things we should work out is the mathematics of induction as the process of building the hierarchies is necessarily inductive as otherwise there is no reason to favor any particular decomposition over any other. We must find a reason, or give up on ``reason'' altogether.

For the moment, though, let's ignore all this appalling complexity and go back to just the some given finite set $S$ and maybe $\Pi(S)$ and $\Pi^2(S)$, just to see what insight we can gain from this formulation into the laws of thought.


next up previous contents
Next: Set Theory and the Up: Formal Set Theory Previous: Naive Set versus Axiomatic   Contents
Robert G. Brown 2007-12-17