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.

  • $\begingroup$ @Asaf Karagila, The only problem was that I mistakenly copied my other question's title to this one. If you check the content of the questions and answers, they are not duplicate at all. By the way, I modified the title and I'll appreciate it if you remove the duplicate tag. $\endgroup$ – user2521204 Sep 20 '15 at 15:11
  • 2
    $\begingroup$ I agree that whatever question this is, it is not a duplicate of the other. However I'm not exactly clear what you are asking. Are you asking for a "concrete example", or are you asking for help understanding the definition. If the latter, then the third bullet point doesn't appear to be necessary at all, and you should perhaps explain what you don't understand about that part of the definition (noting that you are leaving out the most important part of the definition). $\endgroup$ – user642796 Sep 20 '15 at 18:22
  • $\begingroup$ This question asks for an example (in its first sentence). The other question asks for an example (in its first sentence). So every answer to the other question is an answer to this one, so this one is a duplicate of that one. @Arthur Fischer $\endgroup$ – Carl Mummert Sep 20 '15 at 20:06

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.

  • $\begingroup$ Thank you so much for your complete answer. There is a small issue that is in the definition, I have mentioned that both B and P(X) are nonempty. Also I did not understand what you mean by c({a})=∅ --- (*). $\endgroup$ – user2521204 Sep 20 '15 at 15:18
  • $\begingroup$ I wish I had enough reputation to vote your answer up! $\endgroup$ – user2521204 Sep 20 '15 at 15:22
  • $\begingroup$ I know what you are sayin, but the definition says: let P(X) denote the set of all "nonempty" subsets of X and also for any "nonempty" subset B of P(X). I do not mean X is empty. $\endgroup$ – user2521204 Sep 20 '15 at 17:10
  • 1
    $\begingroup$ I appreciate your time and concern, but would you please tell me how do you interpret this statement in the definition: "let P(X) denote the set of all "nonempty" subsets of X." I think it means $\emptyset \notin P(X)$. $\endgroup$ – user2521204 Sep 20 '15 at 17:27
  • 1
    $\begingroup$ @user2521204 - make the extra-effort of changing title : the title must try to adress the issue, and not be too generic. In addition, try to proceed step-by-step, with a clear question at time, without stuffing too many issues in only ine question. :) $\endgroup$ – Mauro ALLEGRANZA Sep 20 '15 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.