Complements and Powers

We have arrived at chapter V and more in Halmos' book: Complements and Powers. Well, complements in an implementable theory of sets are faced with exactly the same problems as complements in common set theory: there is no universal set (i.e. set of everything) available, not in theory and not in practice. Therefore only relative complements can be conceived, as well as implemented.
Let's take a break and take a look at the way kind of set theory has been implemented in my favorite programming language: Delphi Pascal. The complements problem has been solved here in a rather obvious way, which is not quite bad for a start. When seen from the set arrays implementation, all members of an Object Pascal set have an "ordinal value" which is in the range $[0..255]$. This is essentially the same as in the standard implementation of set arrays, as presented in this paper. These set arrays map onto bitmaps which are at most $256$ bits wide, meaning that the compiler should reserve $256$ bits of memory for each set. Because of this limitation, complements of sets are constructed easily: reverse all bits $0..255$. It leaves no doubt that the elementary set operations, like union and intersection, are carried out by bitwise or's respectively and's. It's all very simple and straightforward, once accepted the limitations of a much restricted $0..255$ bits universe.
It is noted that there does not exist a 'typecast' in Object Pascal that maps sets onto integers or vice versa, such as:

  number := Integer(mySet);
  mySet := Set(number);

Not a missed opportunity, I think, but merely a hitherto unknown possibility. Talking about numbers, though, a reference about Two's complement may be intereting. So far so good about complements.

An axiom of Power Set is not necessary within our implementable set theory. Its mere existence can easily be proved within the realm of hereditarily finite sets. Let's see how it works out with our natural number equivalencies. \begin{eqnarray*} & P( \{\} ) = \{\{\}\} = \{0\} = 1 \\ & P( \{0\} ) = \{\{\}\,\{0\}\} = \{0,1\} = 2 \\ & P( \{0,1\} ) = \{\{\}\,\{0\}\,\{1\},\{0,1\}\} = \{0,1,2,3\} = 15 \end{eqnarray*} In general, a power set of a set of $n$ elements contains $2^n$ elements. Consequently: $$ P( \{0,1,2, ... ,n-1\} ) = \{0,1,2, ... ,2^n-1\} = 2^{2^n}-1 $$ In the key article by Alexander Abian [2], the following general result about Power Sets is presented: $$ x = \sum_{i=1}^k 2^{n_i} \quad \mbox{and} \quad y = \prod_{i=1}^k \left(1+2^{2^{n_i}}\right) \quad \Longrightarrow \quad \overline{y} = P(\overline{x}) $$ Together with an example for $\overline{5} = \{\overline{0},\overline{2}\}$: $$ \left( 1+2^{2^0} \right) \left( 1+2^{2^2} \right) = 2^0 + 2^{2^0} + 2^{2^2} + 2^{2^2 + 2^0} = 1 + 2 + 16 + 32 = 51 $$ $$ \quad \Longrightarrow \quad P(\overline{5}) = \overline{51} $$ Where the original overline notation for bitmapped sets is retained and it is assumed - as usual - that any original set is terse, i.e. it contains no duplicate members.
We have promised that the implementable sets can fill up all feasible computer memory, without leaving any room for other things. Let's repeat some easy facts about common computer memory: \begin{eqnarray*} 1 \: \mbox{Byte} = 2^3 \: \mbox{Bit} \\ 1 \: \mbox{KiloByte} = 2^{10} \: \mbox{Byte} = 2^{13} \: \mbox {Bit} \\ 1 \: \mbox{MegaByte} = 2^{10} \: \mbox{KiloByte} = 2^{23} \: \mbox{Bit} \\ 1 \: \mbox{GigaByte} = 2^{10} \: \mbox{MegaByte} = 2^{33} \: \mbox{Bit} \\ 1 \: \mbox{TeraByte} = 2^{10} \: \mbox{GigaByte} = 2^{43} \: \mbox{Bit} \end{eqnarray*} Suppose now that we make the following set. It can be done with Delphi Pascal:

procedure Pascal;
{
  Sets in Object Pascal
}
var
  A : Set of byte;
  k : integer;
begin
  A := [];
  for k := 0 to 42 do
    A := A + [ k ];
end;

Looks rather innocent, and way below the compiler's boundary of $256$ bits wide. But watch out! The power set is somewhat more powerful: $$ P ( \{0,1,2,3, .. ,42\} ) = \{0,1,2,3, .. , 2^{43}-1\} $$ Oops! This is a bit sequence of a .. TeraByte, with all bits up, i.e not a single bit left unused. Thus we we see that our implementable set theory can easily consume up all contemporary and future computer resources. As promised.