# Value representation theorem for countable set

How can we prove the following: if a relation $R$ is a weak order on a set $X$ and $X_\sim$ is finite, then there exist a function $v:X\to \mathbb{N}$, which is a value representation of preference relation $R$.

Here I know the construction of the function $v$ when the range is the set of real numbers (as $X_\sim$ is countable). But,I am confused when the range of $v$ is the set of natural numbers.

• What $X_\sim$ represents ? – Alecos Papadopoulos Mar 29 '17 at 23:27
• Ok. And what is the difference between $X$ and $X_\sim$? – Alecos Papadopoulos Mar 29 '17 at 23:49
• Are you sure that the elements of $X$ are each just one number? Maybe $X \subset \mathbb N^m$? – Alecos Papadopoulos Mar 30 '17 at 0:01

I use the usual notation $(\succeq,\succ,\sim)$ instead of $R$. I assume that $X_{\sim}$ in your question is the set of equivalence classes of $\sim$ on $X$.

Suppose that the cardinality of $X_{\sim}$ is equal to $n \geq 1$. There exist $x_1\cdots,x_n$ such that $x_1 \prec \cdots \prec x_n$. Define $v(x_1)=1,v(x_2)=2,\cdots,v (x_n)=n$.

Since $\sim$ has $n$ equivalence classes, for any $y \notin \{x_1,\cdots,x_n\}$ there exists a unique $x \in \{x_1,\cdots,x_n\}$ such that $y \sim x$. Define $v (y)=v(x)$.

The function $v$ defined on $X$ takes values in $\mathbb{N}$. I leave it to you to check that $v$ is a utility representation of $\succeq$.

The key is that $X_\sim$ is a finite set. That means that there exists an element $x_i \in X$ for which there is no element $x_j \in X$ where $x_j < x_i$. Thus we can safely map $x_i$ (and all other elements that belong to the same equivalence class) to 0. We can then repeat the process with the remaining elements and map then next equivalence class to 1 and so on.

If $X_\sim$ had not been finite there would have been no guarantee of the existence of a smallest value in $X$.

• $X$ is not assumed to be finite in OP's question. This reasoning only requires $X_{\sim}$ to be finite, which is possible even with an infinite $X$. – Oliv Mar 30 '17 at 8:46
• I am unfamiliar with the terminology. What is $X_\sim$? Is it $X$ but with equivalent (mutually uncomparable) elements collapsed into one? – Klas Lindbäck Mar 30 '17 at 9:02
• I think it is the set of equivalence classes of $\sim$, i.e. of subsets of $X$ that are ranked equally by $\sim$. For instance, if $X=\mathbb{R}$ and if $\succeq$ is defined by the utility function $v(x)=1$ if $x \geq 0$ and $v(x)=0$ otherwise, $X_{\sim}$ is simply composed of two subsets: $\mathbb{R}_+$ and its complement. – Oliv Mar 30 '17 at 9:24