Existence of a utility function on the reals

Question

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.

Answer 1

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.

Answer 2

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.