Existence of a utility function on the reals

Suppose I have $\preceq$, a total order on $\mathbb R^n$. I wish to show that there is a utility function $u:\mathbb R^n\to\mathbb R$ such that $x\preceq y \leftrightarrow u(x)\leq u(y)$.

I came up with a constructive proof, which might be best explained with an example:

Suppose we have that $x_1\preceq x_2$. We can assign $x_1$ utility 0 and $x_2$ utility 1. If $x_3$ is smaller than $x_1$ it gets utility -1, if it's bigger than $x_2$ it gets utility 2, and if it's between it gets utility $1/2$. Continue indefinitely.

Is this a valid proof? My concern is that I might be assuming that $\mathbb R^n$ is recursively enumerable.

-
What's an utility function? –  Git Gud Mar 9 '14 at 14:44
@Git: Any function $\mathbb R^n\to\mathbb R$. I don't require computability, continuity, etc... –  Xodarap Mar 9 '14 at 14:51
If you don't require computability, I wonder a little at your choice of tags... –  Ben Millwood Mar 9 '14 at 15:04

This is not a valid proof, because your sequence $x_1, x_2, \dots$ cannot contain all the points of $\mathbb R^n$, because the latter is not countable. (You haven't assumed that it is recursively enumerable, but you have assumed that it is enumerable at all, and it isn't!)

I believe your statement isn't true, even for the $n = 1$ case. If $\preceq$ is a well-ordering, for example, I believe you can show there can be no such $u$. More precisely, if a subset of $\mathbb R$ is well-ordered by the usual ordering relation, it must be countable. Ask me if you want more details on this.

-
You can, however, attempt to use transfinite induction to formalize such "continue indefinitely" proofs. The reason this won't work here, I think, is the "exactly if" in $x \preceq y \leftrightarrow u(x) \leq u(y)$. –  fgp Mar 9 '14 at 14:59
Right. I would have tried transfinite induction next, except that I suspected the statement wasn't true :) and, well, the "exactly if" part is the only reason why a constant function doesn't work, so yes that is the problem :P –  Ben Millwood Mar 9 '14 at 15:06
Hm, true. I wanted to give a plausible reason for why transfinite induction will fail, but I guess that wasn't a particularly good one... –  fgp Mar 9 '14 at 15:08
Once you've already placed infinitely many points, you can no longer be sure there's space to put new points where you need to. E.g. if you had decided to put $x_1$ at 0 and $x_{k+1}$ at $1/2^k$, if you find that $x_\omega$ is supposed to be bigger than $x_1$ but smaller than all the others, there just isn't anywhere you can put it. –  Ben Millwood Mar 9 '14 at 15:11

Your statement is in fact not true. Consider for example the lexicographic ordering ($X \subset \mathbb{R}^2$, and for $x, y \in X$, $x \preceq y \iff x_{1} < y_{1}$ or $x_{1} = y_{1}$ and $x_{2} < y_{2}$. (It is called lexicographic as it reminds one of the dictionary).

This total ordering doesn't allow for a utility function, as can be seen in Mas-Colell, Whiston and Green (p. 46). The proof is the following. Imagine there is such a function $u$. Then for the lexicographic property, it must be true that $u(x_{1}, 2) > u(x_{1}, 1)$, for all $x_{1} \in \mathbb{R}$. But then we can get a rational $r(x_{1})$ such that for all $x_{1}$, $u(x_1, 2) > r(x_{1}) > u(x_1, 1)$, which would be a surjective function from the rationals to the reals, a contradiction with the reals being uncountable.

The problem with your proof is similar, try thinking why your proof wouldn't work for this ordering.

-
I suppose your proof is essentially the observation that $\mathbb R$ cannot contain uncountably many disjoint open intervals? –  Ben Millwood Mar 9 '14 at 15:22
Yes, it is an application of that idea to this particular case. –  Pedro Forquesato Mar 9 '14 at 15:24