previous   overview   next

Hereditary Sets

It has been said in the Abstract : that Implementable Set Theory shall be identified with virtually unlimited Computer Memory. Now everything in material reality is finite. Therefore our hereditary sets must be finite as well. A convenient reference can be found on the Internet: Presented herein is a construction method for the hereditarily finite sets: The hereditarily finite sets are in one-to-one correspondence with the natural numbers, a mapping which is known as the BIT predicate or Ackermann coding, named after its inventor Wilhelm Ackermann. Despite of that BIT predicate, the Ackermann coding is essentially independent of digital computers.

Let's see what the most simple hereditary sets look like.
In the subsection about the empty set, we have shown that the empty set is equivalent with an integer number, namely zero (without the overlines here): $$ \{\} = 0 $$ Applying the recursion rule once, starting with the empty set, we obtain: $$ \{\} = 0 \quad \Longrightarrow \quad \{\{\}\} = \{0\} $$ But the set containing only a zero can be bitmapped upon a sequence of bits where only the bit at position zero is up:

    .. 0000000001
And the numerical (integer) equivalent of this is the number $1$ : $$ \{\} = 0 \quad \Longrightarrow \quad \{\{\}\} = \{0\} = 1 $$ We can proceed in this way: $$ \{ \, \{\{\}\} \, \} = \{ 1 \} = \mbox{?} $$ Bitmap:
    .. 0000000010
Hence: $$ \{ \, \{\{\}\} \, \} = \{ 1 \} = 2 $$ Next example: $$ \{ \, \{\{\}\} , \{\} \, \} = \{ 1,0 \} = 3 $$ Bitmap:
    .. 0000000011
The general pattern is supposed to be clear now. Proceeding in this way, we subsequently have: $$ \begin{array}{l} 0 = 000 = [\; ] = \{\} \\ 1 = 001 = [0] = \{\{\}\} \\ 2 = 010 = [1] = \{\{\{\}\}\} \\ 3 = 011 = [0\; 1] = \{\{\}\{\{\}\}\} \\ 4 = 100 = [2] = \{\{\{\{\}\}\}\} \\ 5 = 101 = [0\; 2] = \{\{\}\{\{\{\}\}\}\} \\ 6 = 110 = [1\; 2] = \{\{\{\}\}\{\{\{\}\}\}\} \\ 7 = 111 = [0\; 1\; 2] = \{\{\}\{\{\}\}\{\{\{\}\}\}\} \\ \cdots \end{array} $$ Where the curly braces in the middle have been replaced by square brackets and where commas and blanks on the right are left out for the purpose of unreadability (:-) Or is it because they might rather disturb automatic processing? Anyway, what we have obtained now, in a very specific sense, is a hitherto missing string of curly braces representation of sets. Herewith, our sequence of set representations (number - bitmap - array - string) is complete.