An Enumerator for any set of data, mathematical set, or other collection
of things whether finite or infinite is, in programming terminology, an object
with the following two methods:

    next()  always delivers a data item that it has never delivered before,
            if there are any left

    more()  returns true if there remain any data items that have not yet
            been delivered, false if the collection has run out.

An enumerator for an infinite collection will have a more() method defined
simply as { return true; }

Essential Rules.
    For an object to be an enumerator, these are absolute requirements:

    If only you could wait long enough, every possible data item would
    eventually be delivered by successive calls to next()

    Next() never produces the same data item twice.

An enumerator does not need to produce its values in any particular order.
An enumerator for the letters of the alphabet could quite reasonably produce
   Q, W, E, R, T, Y, U, I, O, P, A, S, D, F, G, H, J, K, L, Z, X, C, V, B, N, M
or P, T, Q, L, G, A, M, Z, O, Y, W, K, H, S, N, C, X, I, R, E, U, D, J, V, F, B
or A, B, C, D, E, F, G, H, I, J, K, L, M, N, Q, P, O, R, S, T, U, V, W, X, Y, Z.

As reminders, four simple enumerators
______________________________________________
struct Enumerate_Natural_Numbers
{ string current;

  Enumerate_Natural_Numbers()
  { current="0"; }

  bool more()
  { return true; }

  string next()
  { string answer=current;
    for (int i=current.length()-1; i>=0; i-=1)
    { if (current[i]=='9')
        current[i]='0';
      else
      { current[i]+=1;
        return answer; } }
    current=string("1")+current;
    return current; } };
______________________________________________
struct Enumerate_Wives_of_Henry_VIII
{ int current;

  Enumerate_Wives_of_Henry_VIII()
  { current=0; }

  bool more()
  { if (current<6)
      return true;
    else
      return false; }

  string next()
  { current+=1;
    if (current==1) return "Catherine of Aragon";
    if (current==1) return "Anne Boleyn";
    if (current==1) return "Jane Seymour";
    if (current==1) return "Anne of Cleves";
    if (current==1) return "Catherine Howard";
    if (current==1) return "Catherine Parr";
    return "xxxxx"; } };
______________________________________________
struct Enumerate_Integers
{ bool positive, clean;
  Enumerate_Natural_Numbers nats;
  string lastone;

  Enumerate_Integers()
  { clean=true;
    positive=true; }

  bool more()
  { return true; }

  string next()
  { if (clean)
    { clean=false;
      return nats.next(); }
    else if (positive)
    { positive=false;
      lastone = nats.next();
      return lastone; }
    else
    { positive=true;
      return string("-")+lastone; } } };
______________________________________________
struct Enumerate_Positive_Even_Numbers
{ Enumerate_Natural_Numbers nats;

  Enumerate_Positive_Even_Numbers()
  { }

  bool more()
  { return true; }

  string next()
  { string answer = nats.next();
    nats.next();
    return answer; } };
______________________________________________

If you have enumerators for two different collections, you can make the
items of those collections pair up two-by-two:

{ Enumerate_Integers en_int;
  Enumerate_Positive_Even_Numbers en_posev;
  while (true)
  { if (!en_int.more() && !en_posev.more())
    { cout << "Both sets are finite and the same size\n";
      break; }
    if (en_int.more() && !en_posev.more())
    { cout << "More ints than positive evens, and positive evens is finite\n";
      break; }
    if (!en_int.more() && en_posev.more())
    { cout << "More positive evens than ints, and ints is finite\n";
      break; }
    cout << en_int.next() << " : " << en_posev.next() << "\n"; } }

If the items in two collections can be made to pair up, two-by-two, with no
repeats and nobody left over, then the two sets must be the same size. The
pairing up doesn't have to be physically performed. Knowing that it can be
done is enough. 

Being able to define an enumerator for a set, and knowing that the set
is infinite, is enough to prove that the items of the set can be paired up
two-by-two with the natural numbers, with no repeats and nobody left out
on either side.

A set or data structure or whatever, is called Enumerable if it is possible
to write an enumerator for it.

Every Infinite Enumerable set has exactly the same size as the set of all natural
numbers.

Any Finite set is obviously smaller.

So the question of "Are all infinite sets the same size?" or "Is there just
one infinity?" is answered by the question !"Are there any non-enumerable
sets?".

By devising enumerators, we have shown that all of these sets of things:

      Positive whole numbers
      whole numbers
      even numbers,
      strings,
      data files,
      C++ programs,
      Things that can be said in Norwegian

are exactly the same size.

_______________________________________________________________________

Here's a useful lemma. An enumerator produces its values in some arbitrary
but fixed order. If you have an enumerator, it is always possible to go backwards
in that same ordering. That is, you can always have a previous() method to
go with your next() if you want it:

   string previous(string Q)
   { string last="ERROR!!!";   // you can't go back beyond the beginning
     Enumerate_Something enum;
     while (true)
     { string current = enum.next();
       if (current==Q)
         return last;
       last=current; } }

This may be a very inefficient way to go backwards through an enumeration, but
it does show that it is always possible to do so.

Additionally, any enumerator can easily be given a reset() method which sets
it back to the beginning again. reset() just needs to repeat whatever the
constructor did at the beginning. The reset for natural numbers would simply
say 
   { current="0"; }
The one for integers would say 
   { clean=true;
     positive=true;
     nats.reset(); }
etc.

And with that, we can create Cantor's Enumeration, which adds another dimension
to our colection of infinite sets.

How can we have an enumeration for all possible pairs of natural numbers, such
as [0,0] [3,7] [98,1153] [3,0] [0,1] [2,1] [75,34] ....?
Cantor's enumeration works by first producing all pairs where the sum of the
parts is zero ([0,0]) then producing all pairs where the sum of the parts is
1 ([0,1] [1,0]) then all pairs with a sum of 2 ([0,2] [1,1] [2,0]) then the
threes ([0,3] [1,2] [2,1] [3,0]) and so on and so on. Any possible cair you
care to mention will obviously eventually be reached (the sum of its parts
gives you an idea of how long it will take), and clearly no pair can be produced
twice. It works like this

   struct Enumerate_Pairs
   { Enumerate_Natural_Numbers enum_sum;
     Enumerate_Natural_Numbers enum_first;
     string sum, first, second, zero;

     Enumerate_Pairs()
     { sum = enum_sum.next();
       zero = sum;
       first = enum_first.next();
       second = sum; }

     more()
     { return true; }

     next()
     { string answer = "[";
       answer = answer + first + "," + second + "]";
       if (second == zero)
       { sum = enum_sum.next();
         enum_first.reset();
         first = enum_first.next();
         second = sum; }
       else
       { first = enum_first.next();
         second = Enumerate_Natural_Numbers::previous(second); }
       return answer; } };

Notice that the two internal enumerators for natural numbers could be replaced
by any other enumerators and it would still work in the same way. That's why the
slightly mystifying variable "zero" is used - it captures the first thing ever
to come out of an enumerator, so it can serve as the equivalent of "0" for any
set. We can enumerate all possible pairings of C++ programs with data files,
we could even make pairs out of pairs of things, giving lists of any length.

Sticking with the enumerator of pairs of natural numbers for a while longer,
suppose the form of the output were changed, replacing the first two lines
of next() with
    string answer = first + "/" + second;
It might seem that we would have an enumerator for all fractions, or rational
numbers. But we wouldn't. It would not be a proper enumerator. The sequence
would be 0/0, 0/1, 1/0, 0/2, 1/1, 2/0, 0/3, 1/2, 2/1, 3/0, 0/4, 1/3, 2/2, ....
It contains bot things that are not rational numbers (0/0, 1/0, etc) and
repeated values (1/2 and 2/4 are the same thing).

This is easily solved. The next() function becomes a loop that keeps on running
until it produces an acceptable result. Any time the divisor is zero, reject
it and go round the loop again. Repeats are prevented by calculating the
greatest common divisor of the two numbers. If the gcd is not 1, then the two
numbers have a common factor (e.g. gcd(9,6)=3, 9/6 isn't a good fraction,
dividing its parts by 3 gives 2/3, the fraction that it is the same as).
Dividing numbers by a gcd>1 always makes them smaller, and the enumeration
produces fractions with smaller numbers before the larger ones, so the
simple rule is that if gcd(first,second)!=1 then the fraction is a repeat,
go round the loop again.

Of course, when numbers are represented as strings, calculating their
gcd takes some programming effort, but nobody should be afraid of that.

So even adding more dimensions doesn't give us a bigger infinity. The
set of all rational numbers is also exactly the same size as the set of
all natural numbers.