Need Examples to Understand Choice Function and Choice Structure.

Question

Would you please give me a concrete example for the following definitions? Specifically I don't understand why a choice function is defined as $c: B \rightarrow P(X)$.

• For any nonempty set $X$, let $P(X)$ denote the set of all nonempty subsets of X.
• For any nonempty subset $B$ of $P(X)$, a function $c: B \rightarrow P(X)$ is called a choice function iff $c(A) \subset A$ for all $A \in B$. The pair $(B, c)$ is called a choice structure.
• For any binary relation $R$ on $X$, define the function $C_R : P(X) \rightarrow P(X) \cup \{\emptyset\}$ as follows: $$C_R (A) = \{x \in A : ( \forall y \in A ) ( xRy ) \}.$$

This question is in no way a duplicate for the following question: (P(X),CR) may be a choice structure even if R is not a rational relation In this question I am asking people to provide me some examples to understand the definition of Choice function and Choice structure. In the other question, I am asking for an example to show that a relation underlying a choice structure should not necessarily be a rational relation. The only relation between these two questions is the definition included in the latter questions to clarify the question.

Answer 1

Consider for the set $X$ a "simple" example, e.g $X= \{ a, b, d \}$.

Its power-set $\mathcal P(X)$ is the set formed wth the eight subsets of $X$ :

$\mathcal P(X) = \{ \emptyset, \{ a \}, \{ b \}, \{ d \}, \{ a, b \} \ldots , \{ a, b, d \} \}$.

Consider now a nonempty subset $B$ of $\mathcal P(X)$.

What is $B$ ? It is a subset of $\mathcal P(X)$, i.e. a "collection" of subsets of $X$. In the above example $B = \{ \{ a \}, \{ b \}, \{ a, b \} \}$ is such a set.

Now consider a function $c : B → \mathcal P^*(X)$ [here I mean : $\mathcal P^*(X) = \mathcal P(X) \setminus \{ \emptyset \}$]; this function maps elements of $B$ (that are subsets of $X$, see above) into not empty subsets of $X$.

A $c$ of this sort can be a function such that :

$c(\{ a, b \})= \{ a \}$ --- (*).

Now consider all the $A$ such that $A \in B$; in our example, the possible values for $A$ are :

$\{ a \}, \{ b \}, \{ a, b \}$.

In order to be a choice function, we want that :

for all $A \in B$, $c(A) \subset A$.

Our (partial) definition of $c$ in (*) satisfy this condition, because for $A= \{ a, b \}$, $c(A)= \{ a \} \subset A$.

For $A = \{ a \}$, we can define $c(\{ a \})=\{ a \}$, and again the condition is satisfied.

---

Note : the example is very simple and thus it can be misleading. Not every function $f : B → \mathcal P(X)$ is a choice one.

If we define $f(\{ a \})=\{ b \}$, the condition $c(A) \subset A$ is clearly not satisfied.

---

What is a relation $R$ on $X$ ? In our example above, it can be :

$R = \{ (a,a), (a,b), (b,d) \}$.

The function $C_R : \mathcal P(X) → \mathcal P(X)$ is a function that maps subsets of $X$ into subsets of $X$.

We want that it satisfy the condition :

$C_R(A) = \{x∈A : (∀y∈A)(xRy) \}$.

Consider e.g. $A = \{ a, b \}$; $C_R$ maps it into the set $\{ x \in A : (∀y∈A)(xRy) \}$.

The elements of $A$ are $a$ and $b$ and we have $(a,a), (a,b) \in R$, i.e. $aRa, aRb$. Thus, for $a$ it is true that $a \in A$ and $aRy$, for all $y \in A$.

So : $C_R(\{ a, b \})= \{ a \}$.

By definition, the set $\{ x \in A : (∀y∈A)(xRy) \}$ is a subset of $A$ and so : $C_R(A) \subset A$; thus $C_R$ is a choice function.