Ordered pairs

Ordered pairs - see Halmos [1] chapter VI - are defined in common set theory as Kuratowski ordered pairs: $$ (a,b) := \{\{a\},\{a,b\}\} $$ Elaborate: $$ \{\{a\},\{a,b\}\} = \{2^a,2^a+2^b\} = 2^{2^a} + 2^{2^a+2^b} = 2^{2^a}\left(1+2^{2^b}\right) $$ Examples: \begin{eqnarray*} (0,1) = 2^{2^0}\left(1+2^{2^1}\right) = 2(1+4) = 10 \\ (1,0) = 2^{2^1}\left(1+2^{2^0}\right) = 4(1+2) = 12 \\ (0,2) = 2^{2^0}\left(1+2^{2^2}\right) = 2(1+16) = 34 \\ (2,0) = 2^{2^2}\left(1+2^{2^0}\right) = 16(1+2) = 48 \\ (1,2) = 2^{2^1}\left(1+2^{2^2}\right) = 4(1+16) = 68 \\ (2,1) = 2^{2^2}\left(1+2^{2^1}\right) = 16(1+4) = 80 \end{eqnarray*} It is noted that the second example is employed in Abien's article, where it reads: $$ \{(\overline{1},\overline{0})\} = \{\{\{\overline{1}\},\{\overline{1},\overline{0}\}\}\} = \{\{\overline{2},\overline{3}\}\} = \{\overline{12}\} = \overline{4096} $$ But anyway, it all runs quickly out of hand! For example: $$ (3,4) = 16777472 \quad \mbox{and} \quad (4,3) = 16842752 $$ So an essential difference between standard set theory and an implementable theory of sets may be that the latter is far more "dense". Such an efficient way to store ordered pairs in computer memory is e.g. the one published by Daryl McCullough, in the 'sci.math' thread "Coding of ordered pairs":

Let  = (i+j)*(i+j+1)/2 + i

The inverse function, the one that splits $<\!i,j\!>$ into its components $x$ and $y$, can be found as well, though with somewhat more effort. Here is my Delphi Pascal implementation:

function Daryl(n : integer) : paar;
{
  Natural -> ordered pair
}
var
  f,K : integer;
  p : paar; { (p.i,p.j) }
begin
  f := (Trunc(sqrt(8*n+1)) - 1) div 2;
  K := f*(f+1) div 2;
  p.i := n - K; p.j := f - p.i;
  Daryl := p;
end;

We see that the Kuratowski ordered pairs are sparsely distributed among the integers that represent them. And that far more dense implementations are possible. This turns out to be a common feature with common set theory, when compared with implementable set theory.