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
  • 4
    $\begingroup$ 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? $\endgroup$ Dec 7, 2009 at 5:22
  • 1
    $\begingroup$ I agree with Qiaochu. As he says, the words "non-strict" and "generated" need clarification. $\endgroup$ Dec 7, 2009 at 13:35
  • $\begingroup$ Clarified non-strict. Sorry, I don't know how I left out the word increasing from the discussion of generation. $\endgroup$
    – Casebash
    Dec 10, 2009 at 23:40

1 Answer 1


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.

  • $\begingroup$ I've clarified the question $\endgroup$
    – Casebash
    Dec 10, 2009 at 23:45
  • $\begingroup$ 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. $\endgroup$ Jun 12, 2011 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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