previous   overview   next

Pairing and Union

Let's proceed with chapter III in Halmos [1], the Axiom of pairing: for each two arbitrary sets, there exists a set that contains them both as a member.
Now we are going to do some real set theoretical stuff. With the empty set alone, we can form the following set, with help of pairing. But the axiom of Extension says that it is equal to a set with only the empty set as an element. And the resulting set is not empty: $$ \{\emptyset,\emptyset\} = \{\emptyset\} = \{\{\}\} \neq \{\} $$ Empty boxes inside empty boxes. It's only until recently that I am beginning to feel a bit comfortable with the mere idea.
Maybe it is possible to implement this as array sets, with help of a decent computer language. But as far as I know, it's cumbersome with Delphi Pascal.
Anyway, with the axiom of pairing, we can make singletons, i.e. sets with only one element in them. But, of course, we can make pairs as well, once a few singletons are created. For example: $$ \{\{\}\} \quad \wedge \quad \{\} \quad \Longrightarrow \quad \{\,\{\{\}\} \, ,\,\{\}\,\} $$ A philosophical note is in place, when we are saying that we "make with an axiom" and denote this as an implication $A \Longrightarrow B$. In common mathematics, the implication $\Longrightarrow$ just means what is defined by a truth table in propositional logic. But there is another form of mathematics, called constructivism. Within constructivist mathematics, an implication has a more "operational" meaning, like: given $A$, we can construct $B$ from $A$. So if we say "make with an axiom", then it is expressed herewith that we adhere to the constructivist meaning of an implication.
The axiom of pairing allows us to create singletons and pairs. But it doesn't allow us to create sets with more than two elements. In other to accommodate with the latter possibility, there is another axiom in common set theory, which is called the Axiom of Union, as presented in Halmos [1] chapter IV:

For any set $x$ there is a set $y$ whose elements are precisely the elements of the elements of $x$.

Sounds more complicated than it actually is. A simple example. Union says that, if there is a set $\{\{1,2\},\{3\}\}$, then there is also another set, namely $\{1,2,3\}$. It is seen that the former set is a pair and the latter set contains more than just two elements. We can proceed in this way, forming the pair and the union $\{\{1,2,3\},\{4\}\} \Longrightarrow \{1,2,3,4\}$, and so on and so forth. It is noted once more that we will not dwell upon the well known set theoretic properties of union and intersection. For the obvious reason that it can all be found in many books about common set theory (e.g. Halmos' book).

More systematically now. Starting with the empty set. $$ \{\} = 0 $$ With the empty set alone, we can make - employing Pairing and Extension - the singleton that contains it. It is associated with the next natural number: $$ \{\;\{\}\;\} = \{0\} = 1 $$ With the sets numbered as $0$ and $1$, we can proceed and create the following sets - employing Pairing and Extension (and substitution): $$ 2 = \{1\} = \{\{0\}\} = \{\{\{\}\}\} $$ $$ 3 = \{0,1\} = \{\{\},\{\{\}\}\} $$ Next we do: \begin{eqnarray*} 4 = \{2\} = \{ \{\{\{\}\}\} \}\\ 5 = \{0,2\} = \{ \{\} , \{\{\{\}\}\} \}\\ 6 = \{1,2\} = \{ \{\{\}\} , \{\{\{\}\}\} \} \end{eqnarray*} But here we are stuck, because the axiom of Pairing forbids us to do something like this: $$ 7 = \{0,1,2\} $$ So we need the axiom of Union for the first time: $$ \{3,\{2\}\} = \{\{0,1\},\{2\}\} \quad \Longrightarrow \quad \{0,1,2\} = 7 = \{ \{\} \{\{\}\} \{\{\{\}\}\} \} $$ Where it is noticed that it would become more and more difficult to decide if a set has "equal members" eventually. Especially if we leave out the commas, which may be essential for readability, but not for definiability. It is thus argued, once more, that the axiom of Extension might be not so trivial as it looks like.
Things we have found so far can also be written as follows, while skipping the first four results: \begin{eqnarray*} 4 = \{2\}\\ 5 = 1 \cup 4\\ 6 = 2 \cup 4\\ 7 = 3 \cup 4 \end{eqnarray*} Where it is noted that actually elements of a Pair (e.g. $\{1,4\}$ ) are taken for making a Union with $\cup$ . Continuing this story, we find: \begin{eqnarray*} 8 = \{3\} \\ 9 = 1 \cup 8 \\ 10 = 2 \cup 8 \\ 11 = 3 \cup 8 \\ 12 = 4 \cup 8 \\ 13 = 5 \cup 8 \\ 14 = 6 \cup 8 \\ 15 = 7 \cup 8 \end{eqnarray*} General pattern: $$ 2^n = \{n\} $$ $$ 2^n + k = k \cup 2^n \qquad \mbox{where} \quad 1 \le k \le 2^n-1 $$ This is a recursive pattern. There are precisely enough numbers $k$ already defined with every jump from $2^n$ to the next power of $2$.
So, for the moment being, we end up with only four out of the nine axioms of Zermelo Fraenkel (and axiom of Choice, eventually: ZFC) set theory:

  1. axiom of Extension
  2. axiom of Empty Set
  3. axiom of Pairing
  4. axiom of Union
These four axioms are constructively equivalent with the Base case and Recursion rule that define together all of the heredarily finite sets.