MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a non-strict total ordering on tuples of real numbers (the ordering includes tuples of differing lengths). Any tuple, t2, generated from another tuple, t1, by increasing one or more values has t2>t1. Is there necessarily a function f from tuples to real numbers which preserves the ordering? Can this be easily further generalised?


  • By non-strict, I mean that different elements may be equivalent
  • This question is actually motivated by investigating Utilitarianism. The tuples are tuples of individual utilities and the aim is to see whether the ability to rank tuples of utilities (with one common sense restriction on the ordering) necessarily means that that a combined utility function can be created
share|cite|improve this question
I'm not sure I understand your question. Is a non-strict total ordering just one in which different elements are allowed to be equivalent? What do you mean by "generated"? Do you mean that if tuple A has tuple B as a subsequence, then A is greater than B, or should "subsequence" be replaced by any of subword, left truncation, right truncation? – Qiaochu Yuan Dec 7 '09 at 5:22
I agree with Qiaochu. As he says, the words "non-strict" and "generated" need clarification. – Tom Leinster Dec 7 '09 at 13:35
Clarified non-strict. Sorry, I don't know how I left out the word increasing from the discussion of generation. – Casebash Dec 10 '09 at 23:40

I'm not sure what the point of taking tuples is, since all you seem to care about is the cardinality of the set of tuples (which is the same as the cardinality of the reals).

If you're asking whether every total ordering on a set with the cardinality of the reals is order-isomorphic to the usual ordering on a subset of the reals, the answer is no. In the reals, there can be at most countably many disjoint intervals, but that's not true in the long line.

If you're asking whether tuples with the lexicographic total order are order-isomorphic to a subset of the reals, the answer is again no, even for 2-tuples, for the same reason: the 2-tuples have uncountably many disjoint intervals of the form (a,b)-(a,c) (with b < c).

As for "I'm not really sure what area of maths this is": order theory.

share|cite|improve this answer
I've clarified the question – Casebash Dec 10 '09 at 23:45
The third paragraph of this answer still answers your question, since one possible utility ordering would be the lexicographic one, and even a quite small subspace of the set of tuples can't be embedded into $\mathbb{R}$. It is possible that <i>some</i> orderings of the tuples do embed into $\mathbb{R}$, but this is in some sense the most natural, and can't work. – Richard Rast Jun 12 '11 at 16:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.