<p>The following is a nice proof from Osborne and Rubinstein's <em>Models in Microeconomic Theory</em>. We want to prove that</p>
<blockquote>
<p>Every preference relation on a finite set can be represented by a utility function.</p>
</blockquote>
<p>Let <span class="math-container">$X$</span> be a finite non-empty set and let <span class="math-container">$\succeq$</span> be a preference relation on <span class="math-container">$X$</span>. Next, let <span class="math-container">$Y_0 = X$</span> and let <span class="math-container">$M_1$</span> be the set of alternatives minimal with respect to <span class="math-container">$\succeq$</span> in <span class="math-container">$Y_0$</span>, 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.</p>
<p>Next, for <span class="math-container">$k \geq 1$</span>, define <span class="math-container">$Y_k = Y_{k - 1} \setminus M_k$</span> as long as <span class="math-container">$Y_{k - 1}$</span> is non-empty. As before, <span class="math-container">$M_k$</span> is the set of alternatives minimal with respect to <span class="math-container">$\succeq$</span> on <span class="math-container">$Y_{k - 1}$</span>, and is non-empty as long as the latter is also non-empty.</p>
<p>Since by assumption <span class="math-container">$X$</span> is finite, there exists <span class="math-container">$K \in \mathbb{N}$</span> such that <span class="math-container">$Y_K$</span> is empty (while <span class="math-container">$Y_{K - 1}$</span> is non-empty). This means that every <span class="math-container">$x \in X$</span> is an element of <span class="math-container">$M_k$</span> for some <span class="math-container">$k = 1, 2,\dots, K$</span>.
Now define <span class="math-container">$u : X \to \mathbb{R}$</span> given by <span class="math-container">$u(x) = k$</span> for all <span class="math-container">$x \in M_k$</span> for some <span class="math-container">$k = 1, 2,\dots, K$</span>. We claim that <span class="math-container">$u$</span> is a utility function for <span class="math-container">$\succeq$</span>, i.e. for any alternatives <span class="math-container">$a$</span> and <span class="math-container">$b$</span> we have <span class="math-container">$a \succeq b$</span> if and only if <span class="math-container">$u(a) \geq u(b)$</span>. To see that, note that <span class="math-container">$u(a) = u(b)$</span> if and only if <span class="math-container">$a$</span> and <span class="math-container">$b$</span> are both minimal with respect to <span class="math-container">$\succeq$</span> in <span class="math-container">$Y_{u(a) - 1}$</span>, i.e. <span class="math-container">$a \succeq b$</span> and <span class="math-container">$b \succeq a$</span>, so <span class="math-container">$a \sim b$</span>.</p>
<p>Also, we have <span class="math-container">$u(b) &gt; u(a)$</span> if and only if <span class="math-container">$a$</span> is minimal with respect to <span class="math-container">$\succeq$</span> in <span class="math-container">$Y_{u(a) - 1}$</span> but <span class="math-container">$b$</span> is not, hence <span class="math-container">$b \succeq a$</span> but <span class="math-container">$a \nsucceq b$</span> and so <span class="math-container">$b \succ a$</span>. <span class="math-container">$\square$</span></p>
<p>Hope this helps.</p>

CC BY-SA 4.0
2024-06-21T07:54:38.773Z
2024-06-21T07:54:38.773Z
Riccardo Iorio
<p>Let <span class="math-container">$X=\{x_1,\dots, x_n\}$</span>, we will use induction on size of <span class="math-container">$X$</span> to prove that utility representation exists.</p>
<p><em><strong>Base step</strong></em> <span class="math-container">$(|X|=1)$</span>:<br />
In the base step <span class="math-container">$X=\{x_1\}$</span> and so utility representation exists trivially</p>
<p><em><strong>Inductive Hypothesis</strong></em> <span class="math-container">$(|X|=n-1)$</span>:<br />
Suppose there exists a utility representation <span class="math-container">$u': \{x_1, \dots, x_{n-1} \to \mathbb R\}$</span></p>
<p><em><strong>Inductive step:</strong></em><br />
We need to show that there exists a utility representation for <span class="math-container">$\succeq$</span> when <span class="math-container">$|X|=n$</span>. We do this by exhausting all the possible cases.</p>
<ol>
<li><p><strong>Case 1:</strong> <span class="math-container">$\exists x_j \in \{x_1, \dots, x_{n-1}\}$</span> such that <span class="math-container">$x_n \sim x_j$</span>.<br />
Then we can define <span class="math-container">$u: \{x_1, \dots, x_n\} \to \mathbb R$</span> as:
<span class="math-container">$$\forall x_i \in X, \quad u(x_i)=\begin{cases}
         u'(x_i) &amp; \text{ if }x_i\neq x_n\\
         u'(x_j) &amp; \text{ if }x_i=x_n
     \end{cases}$$</span></p>
</li>
<li><p><strong>Case 2:</strong> <span class="math-container">$x_n \succ x_j, \forall x_j \in \{x_1, \dots, x_{n-1}\}$</span>. Then we can define <span class="math-container">$u: \{x_1, \dots, x_n\} \to \mathbb R$</span> as:
<span class="math-container">$$\forall x_i\in X, \quad u(x_i)=\begin{cases}
         u'(x_i) &amp; \text{ if }x_i\neq x_n \\
         \displaystyle \max_{x_j \in \{x_1, \dots, x_{n-1}\}} u'(x_j)+1 &amp; 
 \text{ if }x_i=x_n
     \end{cases}$$</span></p>
</li>
<li><p><strong>Case 3:</strong> <span class="math-container">$x_j \succ x_n, \forall x_j \in \{x_1, \dots, x_{n-1}\} $</span>. Then we
can define <span class="math-container">$u: \{x_1, \dots, x_n\} \to \mathbb R$</span> as:
<span class="math-container">$$\forall x_i \in X, \quad u(x_i)=\begin{cases}
         u'(x_i) &amp; \text{if }x_i\neq x_n \\
         \displaystyle \min_{x_j \in \{x_1, \dots, x_{n-1}\}} u'(x_j)-1 &amp; 
 \text{if }x_i=x_n
     \end{cases}$$</span></p>
</li>
<li><p><strong>Case 4:</strong> <span class="math-container">$\exists x_j, x_k \in \{x_1, \dots, x_{n-1}\}$</span> such that <span class="math-container">$x_j \succ x_n 
 \succ x_k$</span></p>
<p>Let <span class="math-container">$\alpha = \min\{u'(x_i): x_i \succ x_n\}$</span> and <span class="math-container">$\beta=\max\{u'(x_i): 
 x_n \succ x_i\}$</span>. Then we can define <span class="math-container">$u: \{x_1, \dots, x_n\} \to \mathbb R$</span> as:
<span class="math-container">$$u(x_i)=\begin{cases}
         u'(x_i) &amp; \text{if }x_i\neq x_n \\
         \frac{\alpha+\beta}{2} &amp;\text{if } x_i=x_n
     \end{cases}$$</span></p>
</li>
</ol>
<p>We have shown the existence of utility representation in each case. To finish the proof, we need to show that <span class="math-container">$u: \{x_1, \dots, x_n\} \to \mathbb R$</span> represents <span class="math-container">$\succeq$</span> on <span class="math-container">$X$</span>, that is, show that for any <span class="math-container">$x, y \in X, \quad x \succeq y \iff u(x) \geq u(y)$</span>.</p>
<p>The usefulness of this proof lies in the fact that it can be extended to the case where <span class="math-container">$X$</span> is countably infinite. Note that I do not take credit for the proof; This proof was shown to me by Professor Arunava Sen.</p>

CC BY-SA 4.0
2024-06-23T17:58:37.230Z
2024-06-23T17:58:37.230Z
mynameparv
<p>Im looking the prove the following:</p>
<p>every preference relation ⪰ over finite/countable set X can be represented as a utility function u such that <code>x1 ⪰ x2 &lt;=&gt; u(x1) ≥ u(x2)</code></p>
<p>At the first direction: <code>x1 ⪰ x2 =&gt; u(x1) ≥ u(x2)</code>, i just built a utility function <code>u</code> that is defined to be:<br />
<code>u(xi) = |set of all xj such that xi ⪰ xj |</code></p>
<p>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.</p>
<p>Im struggling with proving the other direction...
And so i hope that you can help me with that :)</p>

CC BY-SA 4.0
2022-03-07T17:31:11.777Z
Hi! What exactly do you mean by "*the other direction*"? Seems like you have to prove that a $u$ representing $\succeq$ exists. You constructed a function $u$. Does it represent $\succeq$ or not?
Giskard
CC BY-SA 4.0
2022-03-07T17:55:03.573Z
Well Im pretty much confused because i searched a lot on the web and yet everything I found is a prove to what you just wrote. Im trying to figure out if its the same as what Im trying to prove. Also, by "the other direction" - i mean to prove that from a function "u" i can create a preference relation i guess? im not quite certain, as im very confused by what is meant to be proven here...
StrugglingResearcher
CC BY-SA 4.0
2022-03-07T18:14:53.273Z
The set in your definition of the utility function need not be finite, it can be countably infinite.
Michael Greinecker
CC BY-SA 4.0
2022-03-07T18:17:12.250Z
I didnt quite understand, if the set would be countably infinite, then the function might never return a value
StrugglingResearcher
CC BY-SA 4.0
2022-03-07T22:07:00.610Z
@StrugglingResearcher Exactly, or a value of $\infty$, which is not a real number. The usual trick is to use a weighted sum like $u(x_i)=\sum_{j:x_j\preceq x_i} 1/2^i$.
Michael Greinecker
CC BY-SA 4.0
2022-03-08T01:47:49.680Z
I was told to prove it for a finite set, I guess it makes it a bit easier.   so is the first part of my prove is currect? and how should the second part be handled?
StrugglingResearcher
<mathematical-economics><preferences>
Proving that Every preference relation can be represented by utility function
StrugglingResearcher
# Proving that Every preference relation can be represented by utility function

(Asked by: username_0 on 2022-03-07)

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 :)

**Tags:** mathematical-economics, preferences
> **Comments:**
> **username_1**: Hi! What exactly do you mean by "*the other direction*"? Seems like you have to prove that a $u$ representing $\succeq$ exists. You constructed a function $u$. Does it represent $\succeq$ or not?  
> **username_0**: Well Im pretty much confused because i searched a lot on the web and yet everything I found is a prove to what you just wrote. Im trying to figure out if its the same as what Im trying to prove. Also, by "the other direction" - i mean to prove that from a function "u" i can create a preference relation i guess? im not quite certain, as im very confused by what is meant to be proven here...  
> **username_2**: The set in your definition of the utility function need not be finite, it can be countably infinite.  
> **username_0**: I didnt quite understand, if the set would be countably infinite, then the function might never return a value  
> **username_2**: @StrugglingResearcher Exactly, or a value of $\infty$, which is not a real number. The usual trick is to use a weighted sum like $u(x_i)=\sum_{j:x_j\preceq x_i} 1/2^i$.  
> **username_0**: I was told to prove it for a finite set, I guess it makes it a bit easier.   so is the first part of my prove is currect? and how should the second part be handled?  

---

## 2 answers

### Answer by username_3 on 2024-06-21. Score: 3

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 by username_4 on 2024-06-23. Score: 1

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.


---

