Proving that Every preference relation can be represented by utility function

Question

Im looking the prove the following:

every preference relation ⪰ over finite/countable set X can be represented as a utility function u such that x1 ⪰ x2 <=> u(x1) ≥ u(x2)

At the first direction: x1 ⪰ x2 => u(x1) ≥ u(x2), i just built a utility function u that is defined to be:
u(xi) = |set of all xj such that xi ⪰ xj |

the function is well defined since set X is countable, and therefore there is a finite number of options (xj) that are less than xi.

Im struggling with proving the other direction... And so i hope that you can help me with that :)

Answer 1

The following is a nice proof from Osborne and Rubinstein's Models in Microeconomic Theory. We want to prove that

Every preference relation on a finite set can be represented by a utility function.

Let $X$ be a finite non-empty set and let $\succeq$ be a preference relation on $X$. Next, let $Y_0 = X$ and let $M_1$ be the set of alternatives minimal with respect to $\succeq$ in $Y_0$, which is non-empty since it can be shown that any finite non-empty set admits at least one maximal and at least one minimal element with respect to a preference relation.

Next, for $k \geq 1$, define $Y_k = Y_{k - 1} \setminus M_k$ as long as $Y_{k - 1}$ is non-empty. As before, $M_k$ is the set of alternatives minimal with respect to $\succeq$ on $Y_{k - 1}$, and is non-empty as long as the latter is also non-empty.

Since by assumption $X$ is finite, there exists $K \in \mathbb{N}$ such that $Y_K$ is empty (while $Y_{K - 1}$ is non-empty). This means that every $x \in X$ is an element of $M_k$ for some $k = 1, 2,\dots, K$. Now define $u : X \to \mathbb{R}$ given by $u(x) = k$ for all $x \in M_k$ for some $k = 1, 2,\dots, K$. We claim that $u$ is a utility function for $\succeq$, i.e. for any alternatives $a$ and $b$ we have $a \succeq b$ if and only if $u(a) \geq u(b)$. To see that, note that $u(a) = u(b)$ if and only if $a$ and $b$ are both minimal with respect to $\succeq$ in $Y_{u(a) - 1}$, i.e. $a \succeq b$ and $b \succeq a$, so $a \sim b$.

Also, we have $u(b) > u(a)$ if and only if $a$ is minimal with respect to $\succeq$ in $Y_{u(a) - 1}$ but $b$ is not, hence $b \succeq a$ but $a \nsucceq b$ and so $b \succ a$. $\square$

Hope this helps.

Answer 2

Let $X=\{x_1,\dots, x_n\}$, we will use induction on size of $X$ to prove that utility representation exists.

Base step $(|X|=1)$:
In the base step $X=\{x_1\}$ and so utility representation exists trivially

Inductive Hypothesis $(|X|=n-1)$:
Suppose there exists a utility representation $u': \{x_1, \dots, x_{n-1} \to \mathbb R\}$

Inductive step:
We need to show that there exists a utility representation for $\succeq$ when $|X|=n$. We do this by exhausting all the possible cases.

1. Case 1: $\exists x_j \in \{x_1, \dots, x_{n-1}\}$ such that $x_n \sim x_j$.
   Then we can define $u: \{x_1, \dots, x_n\} \to \mathbb R$ as: $$\forall x_i \in X, \quad u(x_i)=\begin{cases} u'(x_i) & \text{ if }x_i\neq x_n\\ u'(x_j) & \text{ if }x_i=x_n \end{cases}$$

2. Case 2: $x_n \succ x_j, \forall x_j \in \{x_1, \dots, x_{n-1}\}$. Then we can define $u: \{x_1, \dots, x_n\} \to \mathbb R$ as: $$\forall x_i\in X, \quad u(x_i)=\begin{cases} u'(x_i) & \text{ if }x_i\neq x_n \\ \displaystyle \max_{x_j \in \{x_1, \dots, x_{n-1}\}} u'(x_j)+1 & \text{ if }x_i=x_n \end{cases}$$

3. Case 3: $x_j \succ x_n, \forall x_j \in \{x_1, \dots, x_{n-1}\} $. Then we can define $u: \{x_1, \dots, x_n\} \to \mathbb R$ as: $$\forall x_i \in X, \quad u(x_i)=\begin{cases} u'(x_i) & \text{if }x_i\neq x_n \\ \displaystyle \min_{x_j \in \{x_1, \dots, x_{n-1}\}} u'(x_j)-1 & \text{if }x_i=x_n \end{cases}$$

4. Case 4: $\exists x_j, x_k \in \{x_1, \dots, x_{n-1}\}$ such that $x_j \succ x_n \succ x_k$

   Let $\alpha = \min\{u'(x_i): x_i \succ x_n\}$ and $\beta=\max\{u'(x_i): x_n \succ x_i\}$. Then we can define $u: \{x_1, \dots, x_n\} \to \mathbb R$ as: $$u(x_i)=\begin{cases} u'(x_i) & \text{if }x_i\neq x_n \\ \frac{\alpha+\beta}{2} &\text{if } x_i=x_n \end{cases}$$

We have shown the existence of utility representation in each case. To finish the proof, we need to show that $u: \{x_1, \dots, x_n\} \to \mathbb R$ represents $\succeq$ on $X$, that is, show that for any $x, y \in X, \quad x \succeq y \iff u(x) \geq u(y)$.

The usefulness of this proof lies in the fact that it can be extended to the case where $X$ is countably infinite. Note that I do not take credit for the proof; This proof was shown to me by Professor Arunava Sen.