Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
1  
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 at 14:59
1  
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 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 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 at 15:11
add comment

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.

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

Your Answer

 
discard

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.