Representing Sets of Pure Order

If a man can expect to meet exactly N eligible women in his 
life, what strategy should he use to maximize his chances of
choosing the best one?  This is sometimes called "Bachelor's 
Problem".  The usual answer is that for sufficiently large N 
he should wait until he has seen N/e candidates and then select 
the next candidate that is better than any he's seen previously.
This gives a probability of about 1/e for selecting the best 
candidate.  (However, see the note Optimizing Your Wife for
a critique of this strategy).

More interesting than the problem itself are the assumptions 
on which it's based.  Obviously it's assumed the man can never 
go back and rekindle a romance once it's been terminated, and 
he can't have more than one relationship at a time.  Also, 
it's assumed that he meets the prospective brides in random 
order of suitability.  These assumptions are certainly 
debateable in real life, but they're at least conceivable.

This brings us to the most interesting assumption underlying
the Bachelor's Problem: he can only discern RELATIVE suitability
between two "known quantities"; he has no means whatsoever of 
assessing absolute suitability.  For example, even if he's 
deliriously happy with the first woman, he still has to assume 
she may be the LEAST suitable, because he hasn't met any of the 
others, and for all he knows, EVERY woman may be as nice, or 
nicer, than this first one.

Even after he breaks up with the first woman and has a chance to 
evaluate the second woman, we're asked to assume that he still 
can't deduce anything about the underlying population (so to 
speak).  He can determine which of those two was better, but he
has no idea how these two women stand relative to the women he 
has yet to meet.  The same is true with the third and fourth 
and so on.  At each stage he's only able to determine the 
RELATIVE ORDER of the women he has evaluated so far.

This is a very interesting premise, and it has clearly taxed the
ingenuity of problem-posers as they try to present a situation
in which this assumption would be strictly valid.  For example,
in a recent email message someone presented the problem in 
the form:

  "Suppose you have a bag with N pieces of paper in it.
   On every piece of paper there is a real number.  The 
   numbers are all different and there is no upper or 
   lower bound.  You draw out numbers one at a time until 
   you decide to stop (or you've drawn all the numbers), 
   and the last number you drew is your selection.  What 
   strategy will maximize your chances of selecting the 
   largest number in the bag?"

It's often been observed that this type of formulation is
somewhat ill-posed, because there's no uniform probability
distribution over the set of all numbers.  The very fact 
that the N numbers have somehow been chosen implies that they 
were drawn from some non-uniform distribution, which in turn
suggests that perhaps some information about the absolute 
ordering of the numbers can be inferred from the early samples.
However, since we're not told what that distribution is, we 
can't quantify any such inference.  In it's simplest form
this connundrum is exposed in the notorious "High-Low Number
Problem" (see Choice Without Context?).

People who worry about things like this usually eliminate the
problematical aspect of the question by stating that when a
number is drawn the man is not allowed to actually see it.
Instead, a disinterested third party looks at the number and
tells the man where it falls, in order, relative to the numbers
already drawn.  Thus the man really has access only to the 
relative ordering, and knows nothing about the absolute
ordering.

This is okay, but it makes me wonder if it's the only way in 
which purely relative ordering can be represented.  Why do we 
need to introduce a third party?  Surely it must be possible to 
create N packets of information such that we can unambiguously 
establish the relative order of any packets we've examined, but 
we have zero information about their positions relative to the 
packets we have not examined.

The simplest way I can see to do this is not very simple.  For 
concretness, suppose we have 5 cards on which we want to place 
marks that will allow relative ordering but that will convey zero 
information about absolute order within the set of 5.  Define ten 
symbols, let's say the letters A through J, and put four symbols 
on each card as follows

     Card 1   Card 2   Card 3   Card 4   Card 5
     ------   ------   ------   ------   ------
       A        A        B        C         D
       B        E        F        E         G
       C        F        H        H         I
       D        G        I        J         J

The four letters on each card should be randomly arranged, 
and we should apply a randomly selected permutation to the 10
characters.  Anyway, each card has exactly one character in
common with each other card.  Now to each of the 10 characters
we assign a number randomly selected from the set {0,1,2}.  
This number is placed next to the corresponding character
on the first card where it appears, and the number j+1 (mod 3) 
is placed next to the character on the second card where it
appears.  The result is a set of 5 cards that look like this

    Card 1   Card 2   Card 3   Card 4   Card 5
    ------   ------   ------   ------   ------
     E 0      G 1      D 0      G 2      J 1
     B 0      H 0      C 1      C 2      F 1
     H 2      D 2      E 1      B 1      A 2
     A 1      J 0      F 0      I 2      I 0

Given any two cards, the relative order is determined by comparing
the numbers n,m written next to the common character.  The number
n comes before m if and only if  m-n = 1 (mod 3).  For example, 
given Cards 2 and 5 we would note that the common character is J, 
for which the numbers are 0 and 1 respectively.  This shows that 
Card 2 comes before Card 5.  But nothing on these two cards gives 
us any clue as to their order relative to the remaining three 
cards.

This seems overly complicated, and there's probably a more
economical way of doing it, but the fact that it can be done is
interesting.  In particular, this can be used to define a set of
n purely ordered elements, for any natural number n.  All that's
required is that each element is characterized by n-1 characters
(and associated digits) from an alphabet of n(n-1)/2 characters.
In a sense, we could define these "cards" as "numbers", and they
closely correspond to the set of numbers [1,2,..,n] (i.e., each
element except the first has a unique predecessor, and so on).

What happens if we try to let n go to infinity?  This seems
fairly straightforward for the set [1,..,n].  We just imagine
it extending to infinitely large values of n, and we arrive 
at our notion of the complete infinite set "N" of ALL natural 
numbers.  However, for our purely ordered set of "cards" it 
seems a bit trickier.  Presumably we CANNOT extrapolate this
to a complete infinite set of purely ordered elements, because
that would contradict the fact that there is no uniform
distribution on the natural numbers.

What prevents us from conceiving an infinite set of purely 
ordered elements?  We might think the problem is that we don't 
have a large enough alphabet to cover infinitely many cards, but 
why not just use the natural numbers themselves?  In other words,
A=1, B=2, and so on.  We might begin to construct our infinite
set of purely ordered numbers like this

  Card1  Card2 Card3 Card4 Card5  Card6  Card7  Card8  Card9
  ------ ----- ----- ----- -----  -----  -----  -----  -----
     2      2     4     8    16     32     64    128    256
     4      3     9    27    81    243    729   2187
     8      9     5    25   125    625   3125
    16     27    25     7    49    343
    32     81   625    49    11
    64    243  3125   343        etc.
   128    729 15625
   256   2187
   512

Clearly each card shares exactly one "character" with each 
other card, and we can uniformly select an "order code" from 
the set {0,1,2} for each of these characters.  So now all that
remains is to apply an arbitrary permutation to the labels of 
these characters.  But this is where we run into a problem,
because to perform a truly arbitrary permutation of our infinite
set of charcters we would need a uniform distribution on all
these characters, which we don't have.

Nevertheless, this illustrates an interesting point.  We can
imagine infinitely many orderings of the elements of an infinite 
set, but evidently we can't conceive of ALL POSSIBLE orderings of 
an infinite set, at least not in the symmetrical way that the 
symmetry of the definitions would lead us to expect.  In other 
words, even though no individual element and no particular ordering 
of the elements of the set N (for example) is a_priori preferred 
or distinguished over any other element or ordering, it appears that 
some orderings of the natural numbers are more natural than others.