How to prove that any preference relation on (countable) X has a utility representation with a range (0,1)?

Question

Theorem: If $X$ is countable, then any preference on $X$ has a utility representation with a range $(0,1)$.

The stated proof in Rubinstein's lecture notes:

Proof: Let $\{x_n\}$ be an enumeration of all elements in $X$. We will construct the utility function inductively. Set $U(x_1) =1/2$. Assume that you have completed the definition of the values $U(x_1), . . ., U(x_{n-1})$ so that $x_k \succeq x_l$ iff $U(x_k) \geq U(x_l)$. If $x_n$ is indifferent to $x_k$ for some $k<n$, then assign $U(x_n)=U(x_k)$. If not, choose $U(x_n)$ to be between the two nonempty sets $\{U(x_k) | x_k \prec x_n \} \cup \{0\}$ and $\{U(x_k) | x_n \prec x_k \} \cup \{1\}$. This is possible since by transitivity all numbers in the first set are below all numbers in the second set. Thus, for any $k<n$ we have $x_n \succeq x_k$ iff $U(x_n) \geq U(x_k)$ and the function $U$ extended to $\{x_1, ..., x_n\}$ represents the preferences on those elements. To complete the proof that $U$ represents $\succeq$, take any two elements, $x$ and $y\in X$. For some $k$ and $l$ we have $x=x_k$ and $y=y_l$. The above applied to $n=\max\{k,l\}$ yields $x_k \succeq x_l$ iff $U(x_k) \geq U(x_l)$.

I highlighted below the step in the proof I couldn't figure out. I tried to draw a number line or break the parts of the statement, yet couldn't understand.

If not, choose $U(x_n)$ to be between the two nonempty sets $\{U(x_k) > | x_k \prec x_n \} \cup \{0\}$ and $\{U(x_k) | x_n \prec x_k \} \cup > \{1\}$. This is possible since by transitivity all numbers in the first set are below all numbers in the second set.

Furthermore, why have we done this step? Is it necessary to complete the proof?

Set $U(x_1) =1/2$.

Thanks for your help.

Answer 1

If not, choose $U(x_n)$ to be between the two nonempty sets $\{U(x_k) > | x_k \prec x_n \} \cup \{0\}$ and $\{U(x_k) | x_n \prec x_k \} \cup > \{1\}$. This is possible since by transitivity all numbers in the first set are below all numbers in the second set.

Since $x_k$ is not indifferent to any of $x_1,\ldots,x_{n-1}$, we need to pick a value for $U(x_n)$ so that for all $k\in\{1,\ldots,n-1\}$:

• $U(x_n)>x_k$ when $x_n\succ x_k$
• $U(x_n)<x_k$ when $x_n\prec x_k$

The quoted text is just saying we can do this because the values of $U(x_k)$ for elements $x_k$ such that $x_k\prec x_n$ are all strictly less than the values of $U(x_j)$ for elements $x_j$ such that $x_j\succ x_n$. This is because transitivity means that if $x_j\succ x_n$ and $x_n\succ x_k$ then $x_j\succ x_k$ and we know that $U(x_j)>U(x_k)$ (as we have already completed the definition of $U$ for those elements of $X$ and it cannot be that $U(x_j)=U(x_k)$ because then it would have to be that $x_j$ and $x_k$ are indifferent.)

Set $U(x_1)=1/2$

This just deals with the base case of the inductive proof (when $n=1$). If we set $U(x_1)=1/2$, then clearly we have satisfied the requirement that $U(x_1)\geq U(x_1)$ iff $x_1\succeq x_1$. (We don't have to choose $1/2$, we could set $U(x_1)$ to any number in $(0,1)$.)