Properties satisfied by an order relation

Question

Let $X$ be a finite set and $2^{X}- \{\emptyset\}$ denote its power set excluding the empty set.

Definition 1: A choice correspondence over $X$ is a map $C:2^{X}- \{\emptyset\}\mapsto 2^{X}- \{\emptyset \} $ such that $C(A)\subseteq A$ for all non-empty $A\subseteq X$.

Consider the following order relation ($\succeq$) defined in $2^{X}- \{\emptyset\}$ as follows:

Let $x^*\notin X$ and $C$ a choice correspondence over $X^*=X\cup\lbrace x^*\rbrace$. Let $A, B$ be non-empty subsets of $X$

$$A\succeq B\; \Longleftrightarrow\; C(A\cup x^*) - C(A) \subseteq C(B\cup x^*)- C(B)$$

---

My question is: What properties does the relation $\succeq$ satisfies?

1. It is easy to see it is reflexive and transitive. So it is a pre-order.
2. EDIT: The answer by Jing Zhang proves it is not antisymmetric.
3. Does it satisfies the following 'upper bound' relation?

$$A\succeq B; A\succeq C\;\implies A\succeq B\cup C$$

4. What other 'functional properties' does it satisfy? (Bounty will be offered to the most interesting property and/or the most complete 'characterization')

---

If we add some structure to $C$ how does the answer change?

For example what if $C$ satisfies any (or all, or some) of the following?

1. $C(A)\cap C(B)\subseteq C(A\cup B)$ $\quad$ $\;\forall\;A, B\in 2^{X}- \{\emptyset\}$
2. $A\subseteq B \implies C(B)\cap A\subseteq C(A) $ $\quad$ $\;\forall\;A, B\in 2^{X}- \{\emptyset\}$
3. $C(B)\subseteq A\subseteq B \implies C(A)\subseteq C(B)$ $\quad$ $\;\forall\;A, B\in 2^{X}- \{\emptyset\}$

Any help or hints would be highly appreciated.

Answer 1

Let me rework the definition so that it is a little simpler, then argue that the relation $\succ$ is, at least locally, an arbitrary preorder.

Write $X^{+}$ for $X\cup\{x^*\}$, ${\mathcal P}(Y)$ for the set of subsets of $Y$ (the power set of $Y$), and ${\mathcal P}^{\circ}(Y)$ for the set of nonempty subsets of $Y$.

If $C\colon {\mathcal P}^{\circ}(X^+)\to {\mathcal P}^{\circ}(X^+)$ is a choice correspondence, then define $D\colon {\mathcal P}^{\circ}(X)\to {\mathcal P}(X^+)$ by

$$ D(A) = C(A\cup\{x^*\}) - C(A). $$

Say that $D$ is derived from $C$. Observe that $A\not\subseteq D(A) \subseteq A\cup\{x^*\}$.

Conversely, given any function $D\colon {\mathcal P}^{\circ}(X)\to {\mathcal P}(X^+)$ satisfying $A\not\subseteq D(A) \subseteq A\cup\{x^*\}$, one may define $\overline{C}\colon {\mathcal P}^{\circ}(X^+)\to {\mathcal P}^{\circ}(X^+)$ by the rules $\overline{C}(A) = A-D(A)$ and $\overline{C}(A\cup\{x^*\}) = A\cup D(A)$ when $A$ is a nonempty subset of $X$. Note that $\overline{C}$ is a choice correspondence. Moreover, the function $ \overline{D}(A) = \overline{C}(A\cup\{x^*\}) - \overline{C}(A) $ that is derived from $\overline{C}$ is just $D$, that is $\overline{D}(A)=D(A)$ for every nonempty $A\subseteq X$.

Finally, $A\succ B$ holds (with respect to $C$) iff $D(A)\subseteq D(B)$.

Summary: The relation $\succ$ is the inverse image of the subset relation $\subseteq$ under the $D$-function. The only restrction on $D$ is that $A\not\subseteq D(A) \subseteq A\cup\{x^*\}$.

---

Without the restriction $A\not\subseteq D(A) \subseteq A\cup\{x^*\}$ one could realize any preorder on the set ${\mathcal P}^{\circ}(X)$ whose associated partial order is embeddable in $\langle {\mathcal P}(X^+); \subseteq\rangle$ as the preorder $\succ = D^{-1}(\subseteq)$ for an appropriately chosen $D$. But with the restriction you cannot realize some preorders. For example, $D(\{a\}) = \emptyset$ or $\{x^*\}$, so there are only two $(\succ\cap\prec)$-equivalence classes of singletons. This shows that you cannot realize some preorders.

Nevertheless, the following is true:

If $\langle Y; \leq\rangle$ is any preorder, then there is a superset $X= Y\cup Z$ and a function $D\colon {\mathcal P}^{\circ}(X)\to {\mathcal P}(X^+)$ such that the restriction of $\succ = D^{-1}(\subseteq)$ to the set of elements of the form $\{y\}\cup Z$ recovers $\leq$. (This means: $\{y\}\cup Z\succ \{y'\}\cup Z$ iff $y\leq y'$.)

Here is a construction for this. Let $Z$ be the set of order ideals of $\langle Y;\leq\rangle$, ordered by inclusion. Let $X = Y\cup Z$. For an element $y\in Y$, define $D(\{y\}\cup Z)$ to be the set of order ideals of $\langle Y;\leq\rangle$ contained in the order ideal generated by $y$. (So $D(\{y\}\cup Z)$ is a subset of $Z$.) It doesn't matter how $D$ is defined elsewhere, except that it must satisfy $A\not\subseteq D(A) \subseteq A\cup\{x^*\}$, so let $D(A) = \{x^*\}$ for any other subset $A\subseteq X$. This function satisfies $A\not\subseteq D(A) \subseteq A\cup\{x^*\}$.

On can check that if $\succ$ is defined to be $D^{-1}(\subseteq)$, then $\{y\}\cup Z\succ \{y'\}\cup Z$ iff $y\leq y'$ in $\langle Y; \leq\rangle$. Thus, the restriction of $\succ$ to the set of elements of the form $\{y\}\cup Z$ recovers the relation $\leq$.

In particular, the construction just given can be used to answer the following question negatively:

3. Does it satisfies the following 'upper bound' relation?

$$A\succ B; A\succ C\Longrightarrow A\succ B\cup C.$$

[Just apply the construction to the preorder $\langle \{A, B,C\};\leq\rangle$ where $A\leq B; A\leq C$. You will get $\{A\}\cup Z\succ\{B\}\cup Z; \{A\}\cup Z\succ\{C\}\cup Z$, but $\{A\}\cup Z\not\succ\{B\}\cup \{C\}\cup Z$.]

Answer 2

First of all it is not antisymmetric. Think about X as a finite set, along with $x^*$, let $<$ be a well-order put on $X\cup \{x^*\}$ such that $x^*$ is the third element under $<$ (say there are 5 elements to be concrete, so $x_0<x_1<x^*<x_2<x_3<x_4$.) Then $C$ picks the $<$-least element each time (to be precise, it picks the singleton that contains the $<$-least element). Then $\{x_0\}\preceq \{x_1\}, \{x_1\}\preceq \{x_0\}$ but they are not equal.

Now slightly change $C$ such that it still picks as before except that if the input contains $x_0,x_1$ simultaneously, then it returns the largest element. Now $A=\{x_0\}$ and $B=\{x_0\}, C=\{x_1\}$, we know $B,C\prec A$, but $B\cup C\not \prec A$ as $C(B\cup C \cup \{x^*\})-C(B\cup C)=\{x^*\}, C(A\cup \{x^*\})-C(A)=\emptyset$.