Preference relations that are order-separable

Question

This question concerns dense order relations and separability of orders.

This question has changed radically since the first version. Hence the first two answers below now look strange because they were answers to the first version of this question.

Let $\preccurlyeq$ be a total preorder on the uncountable set $X$ and let $\prec$ be the associated strict weak order defined as $$x \prec y \iff (x\preccurlyeq y \quad and\quad \neg (y\preccurlyeq x)) $$

Let $x$ and $y$ be two elements in $X$ such that $x\prec y$. If there exists no element $z$ in $X$ such that $x \prec z \prec y$, we call $x$ an immediate predecessor of $y$ and $y$ an immediate successor of $x$.

Now I'm trying to understand a proof that two notions of order separability for the total preorder in question are equivalent. The first notion is the property that $\preccurlyeq$ is order separable in the sense of Debreu. The second notion is the property that $\preccurlyeq$ is order separable in the sense of Jaffray.

The proof appears in Representations of Preference Orderingsby D.S. Bridgesand G.B. Mehta. According to their definitions the total preorder $\preccurlyeq $ is order separable in the sense of Debreu if there is some countable subset $Z$ of $X$ such that for any $x,y$ in $X$ with $x \prec y$ there is some $z$ in $Z$ such that $x \preccurlyeq z \preccurlyeq y$.

And $\preccurlyeq$ is order separable in the sense of Jaffray if there is some countable subset $Z$ of $X$ such that for any $x,y$ in $X$ with $x \prec y$ there are some $z_1,z_2$ in $Z$ such that $x \preccurlyeq z_1 \prec z_2 \preccurlyeq y$.

Now it is easy for my to grasp that a total preorder that is order separable in the sense of Jaffray is also order separable in the sense of Debreu. The problem is with the proof in the other direction, i.e. proving that a total preorder that is order separable in the sense of Debreu is also order separable in the sense of Jaffray.

For the proof assume that $\preccurlyeq$ is order separable in the sense of Debreu. Let $Z= \{z_1, z_2, ...\}$ be such a countable subset of $X$ that fulfils the properties for order separability in the sense of Debreu given above.

The proof involves the definition of new set $Z'$ in the following way: for an arbitrary element $z_k$ in $Z$ let $P(z_k)$ denote the set of immediate predessors of $z_k$ and let $S(z_k)$ denote the set of immediate successors of $z_k$. Let $Z’$ be the set of immediate successors and immediate predecessors of elements in $Z$. Now comes my question: is stated that since $Z$ is countable, $Z’$ must also be countable. I can't understand why $Z’$ has to be countable because of the countability of $Z$. Why is it that the number of immediate successors of a given element must be countable?

Answer 1

It still isn’t true as you’ve stated it, but I think that I’ve figured out what it’s supposed to be. First, here’s a counterexample to the version that you’ve stated:

Let $X=\{\langle n,n\rangle:n\in\Bbb Z\}\cup\{\langle x,-x\rangle:x\in\Bbb R\}$. For $\langle a,b\rangle,\langle c,d\rangle\in X$ set $\langle a,b\rangle\preccurlyeq\langle c,d\rangle$ iff $a+b\le c+d$. Let $Z=\{\langle n,n\rangle:n\in\Bbb Z\}$. If $x,y\in X$ with $x\prec y$, at least one of $x$ and $y$ is in $Z$, and $Z$ is countable, so $X$ is Debreu separable. However,

$$S(\langle -1,-1\rangle)=P(\langle 1,1\rangle)=\{\langle x,-x\rangle:x\in\Bbb R\}$$

is plainly uncountable. However, it’s not hard to check that $X$ is still Jaffray separable. For instance, if $x=\langle -1,-1\rangle$ and $y=\langle 1,-1\rangle$, we can take $z_1=x$ and $z_2=\langle 0,0\rangle$ in the definition of Jaffray separability:

$$\langle -1,-1\rangle\preccurlyeq\langle -1,-1\rangle\prec\langle 0,0\rangle\preccurlyeq\langle 1,-1\rangle\;.$$

What makes this work is that the indifference class $\{\langle x,-x\rangle:x\in\Bbb R\}$ contains a member of $Z$.

Now let $\langle X,\preccurlyeq\rangle$ be Debreu separable with countable Debreu dense subset $Z$. For $x\in X$ let $[x]$ be the indifference class of $x$. The reasoning used to show that the example above is Jaffray separable shows that $X$ will be Jaffray separable provided that

• if $y\in S(x)$, then $Z\cap[x]\ne\varnothing\ne Z\cap[y]$.

That is, we’ll be fine whenever $[x]$ and $[y]$ are adjacent elements in the quotient $X/{\sim}$, $Z$ contains at least one element of each of $[x]$ and $[y]$. This means that we’ll be fine provided that $X/{\sim}$ has only countably many pairs of adjacent elements, since we can then add countably many elements to $Z$ to get a Debreu dense subset of $X$ that also satisfies the bullet point.

Let $P$ be the set of all pairs $\langle [x],[y]\rangle\in(X/{\sim})\times(X/{\sim})$ such that $y\in S(x)$, the set of pairs of adjacent elements in $X/{\sim}$. For each $p=\langle[x],[y]\rangle\in P$ fix $x_p\in[x]$ and $y_p\in[y]$; clearly $x_p\prec y_p$ for each $p\in P$, so there is a $z_p\in Z$ such that $x_p\preccurlyeq z_p\preccurlyeq y_p$. Moreover, $y_p\in S(x_p)$, so $z_p=x_p$ or $z_p=y_p$; let $P_0=\{p\in P:z_p=x_p\}$ and $P_1=\{p\in P:z_p=y_p\}$.

If $p,q\in P$ and $p\ne q$, then $x_p\not\sim x_q$ and $y_p\not\sim y_q$, so the maps

$$P_0\to Z:p\mapsto z_p$$

and

$$P_1\to Z:p\mapsto z_p$$

are injections. Thus, $P_0$ and $P_1$ are countable, as is $P=P_0\cup P_1$. Let

$$Z'=Z\cup\{x_p:p\in P\}\cup\{y_p:p\in P\}\;;$$

then $Z'$ is countable, and whenever $x\prec y$ there are $z_1,z_2\in Z'$ such that $x\preccurlyeq z_1\prec z_1\preccurlyeq y$, so $\langle X,\preccurlyeq\rangle$ is Jaffray separable.

Answer 2

If $\preccurlyeq$ were a total order and not just a total preorder, then every element would have at most one successor, since any two successors would be related by $\prec$ or $\succ$. For preorders this is not true, and there is no bound on the number of successors of an element.

Counterexample: Let $X = \mathbb{Z} \times \mathbb{R}$, and $(a,b) \preccurlyeq (c,d) :\Leftrightarrow a \leq c$.

Every $(z, r)$ now has uncountably many immediate successors, namely all $(z+1, r')$ for $r' \in \mathbb{R}$.

Answer 3

Of course the set of immediate successors of an element can be uncountable.

Let $X=\mathbb R$ and define $$x\preccurlyeq y\iff x\le0\text{ or }y\gt0.$$ Then $S(0)=(0,\infty)$ is uncountable.