previous   overview   next

Von Neumann successors

Let's skim quickly through the remaining chapters of Halmos' book, until we arrive at chapter XI: Numbers. And pause there for a moment, at last.
An essential difference between standard set theory and our implementable set theory is that heredetarily finite sets already have an order of their own, as has been repeatedly illustrated, e.g. in Pairing and Union : $$ 0 = \{\} \quad ; \quad 1 = \{\{\}\} \quad ; \quad 2 = \{\{\{\}\}\} \quad ; \quad 3 = \{\{\{\}\}\,\{\}\} \\ 4 = \{\{\{\{\}\}\}\} \quad ; \quad 5 = \{\{\{\{\}\}\}\,\{\}\} \quad ; \quad 6 = \{\{\{\{\}\}\}\,\{\{\}\}\} \quad ; \quad 7 = \{\{\{\{\}\}\}\,\{\{\}\}\,\{\}\} $$ Definition. The Binary successor of a set $x$ is defined by the above pattern. If any set is mapped upon the binary number $x$, then the binary successor of that set is the one which is mapped upon the next binary number $x+1$. Hence the name: binary successor. This is all due to the fact that sets and natural numbers share exactly the same bitmaps.
Another aspect of our implementable set theory is that features of the latter are far more "dense". We have seen this before with ordered pairs. Let's see how it is working with the so-called von Neumann ordinals. They are created in Halmos' book by: $$ x^+ = x \cup \{ x \} $$ where $^+$ is the so-called successor function. In order to avoid confusion with our own successor function, which is the corresponding binary number $+1$ , we shall denote $x \cup \{ x \}$ as the von Neumann successor. Start with the empty set. \begin{eqnarray*} \{\} = 0 \\ \{\} \cup \{0\} = \{0\} = 0 + 2^0 = 1 \\ \{0\} \cup \{1\} = \{0,1\} = 1 + 2^1 = 3 \\ \{0,1\} \cup \{3\} = \{0,1,3\} = 3 + 2^3 = 11 \\ \{0,1,3\} \cup \{11\} = \{0,1,3,11\} = 11 + 2^{11} = 2059 \end{eqnarray*} But: $$ \{0,1,3,11\} \cup \{2059\} = \{0,1,3,11,2059\} = 2059 + 2^{2059} = \mbox{??} $$ And it's already "impossible" to find the next von Neumann ordinal, that is: within the scope of common 32 bits integer (Delphi Pascal) numbers. Meaning that these "ordinals" are quite sparsely distributed among the integers that represent implementable sets, even more sparsely than ordered pairs. But isn't that just the big trick? In standard set theory, the ordinals are defined as an extremely sparse "subset" of "all" sets. It feeds the suggestion that set theory is thus far more general than number theory and that set theory therefore can serve as a foundation for number theory.

Quite another picture is emerging with implementable set theory. Each of our implementable (that is: hereditarily finite) sets uniquely corresponds with a natural number (and $\{\} = 0$). And each natural number uniquely corresponds with an implementable set. Thus our theory of sets does not contain more sets than it contains numbers. Therefore it's not suggested that our implementable set theory can serve as a foundation for the whole of mathematics. It's rather suggested that sets are based upon numbers. And that a good old statement still holds: 'Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk' (Leopold Kronecker - 1886). It's the whole numbers that are foundational for Mathematics, not sets.

The theory of finite ordinals could be labeled as von Neumann's left hand. The common von Neumann computer architecture could be labeled as his right hand. Clearly von Neumann's left hand didn't know what his right hand was doing. Any serious implementation of the former into the latter would be so tremendously inefficient that all computation with naturals would become impossible.

The mapping of sets upon numbers may be denoted by an overline, as in $\overline{x}$ . In one of our key references, the paper by Abian [2], that overline notation has been employed all over the place. According to standard mathematics, indeed, a bijection, say the 'Ackermann / Alexander Abian' function $A$, which maps sets onto integers, should be defined in the first place. After doing so, we could proceed with, for example: $$ A \left(\;\{ \{\} \{\{\}\} \{\{\{\}\}\} \}\;\right) = A(\overline{7}) = 7 \quad \mbox{and} \quad A^{-1}(7) = \{ \{\} \{\{\}\} \{\{\{\}\}\} \} = \overline{7} $$ But instead of all that jazz with bijections and overlines, we have followed an even more simple minded approach and simply declare sets and numbers equal. This is motivated by the fact that sets and naturals share exactly the same bitmaps, when implemented in a computer's memory.
The mapping of numbers onto sets is also useful from another point of view. I don't claim it will ever become a method with beats others from a viewpoint of effiency, but representing numbers as sets in array implementations certainly is an alternative way of doing calculations with very large numbers. A rapid prototyping package has been made available as [6] , for demonstration purposes only. Here are some core routines:

It all works by means of the standard array implementation of sets. Calling sequence of (main) addition and multiplication routines defined by: 
function plus(a,b : integers) : integers; { a + b }
function maal(a,b : integers) : integers; { a * b }
An example: 
program demo;
Uses Rekenen;
begin
  Writeln(faculteit(53));
end.

53! = 4274883284060025564298013753389399649690343788366813724672000000000000