2
$\begingroup$

My question is about the following notation:

I have noticed in several places (for example here (page 15) and here (page 1)) that different authors use different notations for choice correspondences. Given a set $X$ of objects that might be chosen and a collection of non-empty subsets $\mathcal{A}$ of the power set of $X$, some use

  1. $c:\mathcal{A} \rightarrow 2^{X}\backslash \emptyset$ (as in the second link)
  2. $c:\mathcal{A} \rightarrow 2^{X}\backslash \{ \emptyset\}$ (as in the first link)

They both want to express that the co-domain of the choice correspondence must include all the non-empty subsets of the power set of X, i.e from any menu of options, you must choose something.

My question is, which one is the correct way to define it? Clearly, since $\emptyset \neq \{\emptyset\}$, both definitions cannot be equivalent.

My intuition would tell me that from the list above, (1) is the correct one. For example, if $X=\{\text{pasta (p)}, \text{chicken (c)}, \text{sushi (s)}\}$, then the power set of $X$ is:

$$ 2^{X}=\Bigg\{\emptyset, \{p \}, \ \{c \}, \{s \}, \{p,c \}, \{p,s \} , \{c,s \}, \{ p,c, s\} \Bigg\} $$

Since I want to “take out” the empty set from $2^{X}$ so that the choice from any non-empty subset of $X$ is itself non-empty, and since $\{\emptyset\} \notin 2^{X}$, it should be

$$ c:\mathcal{A} \rightarrow 2^{X}\backslash \emptyset $$

Thank you for any answers!

$\endgroup$
3
$\begingroup$

"1." is wrong and "2." is correct, because (see e.g. Wolfram):

$$A \setminus B = \{x: x \in A \text{ and } x \notin B\}$$

Say for example we have $S = \{a, b, c\}$ and $T = \{b,c\}$.

Then we'd write $S \setminus \{a\} = T$. We do NOT write $S \setminus a = T$.

And so in general, for any set $S$, $S\setminus \emptyset =S$.

We write $2^{X}\backslash \{\emptyset\}$ because $\emptyset \in 2^X$. In contrast, we have $2^{X}\backslash \emptyset = 2^{X}$.

Example. The set $S$ contains four elements: the empty set, an element called $a$, the set containing the empty set, and the set containing $a$.

$$ S=\Bigg\{\emptyset,a,\{\emptyset \},\{a \}\Bigg\}. $$

Then we have:

$$ \begin{align} S \setminus \emptyset & = S \\ S\setminus\{\emptyset\}& = \Bigg\{a,\{\emptyset \},\{a \}\Bigg\}, \\ S\setminus\{\{\emptyset\}\}& = \Bigg\{\emptyset,a,\{a \}\Bigg\}, \\ S\setminus\{a\}& = \Bigg\{\emptyset,\{\emptyset \},\{a \}\Bigg\}, \\ S\setminus\{a,\{\emptyset\}\}& = \Bigg\{\emptyset,\{a \}\Bigg\}, \\ S\setminus\{\{a,\emptyset\}\}& = S. \end{align} $$

The last equation is true because $S$ does not contain the set $\{a,\emptyset\}$.

See Enderton, in particular p.3, top paragraph -- it's well worth spending a little time if only on the first chapter.

$\endgroup$

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.