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

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, 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 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$$.

• Are you familiar with mathematical induction? Setting $U(x_1)=1/2$ is the base case, and assigning value to $U(x_n)$, as described in your first quote, is the inductive step. Nov 15, 2022 at 17:52
1. If we know where $$x_n$$ stands with respect to the previous points, we need to give $$U(x_n)$$ a value that is higher than the corresponding values to its less preferred points until now, and a lower value than the corresponding values to its more preferred points until now. It has to be this way because utility functions are increasing with respect to preferences (monotone).
2. $$U(x_1)$$ doesn’t need to be $$\frac{1}{2}$$. We just need to set it somewhere in the interval as the base case of the inductive process.