Properties satisfied by an order relation 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?


*

*It is easy to see it is reflexive and transitive.  So it is a pre-order.

*EDIT: The answer by Jing Zhang proves it is not antisymmetric.

*Does it satisfies the following 'upper bound' relation?


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


*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?


*

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

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

*$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.
 A: 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$.
A: 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:


*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$.] 
