1

In Grimmet and Strizaker's Probability and Random Processes it states section 1.2

The power set of $\Omega$, which is written $\{0,1\}^{\Omega}$ and contains all subsets of $\Omega$....

It goes on to use this in an example as follows:

A die is thrown once. We can take $\Omega$ = $\{1,2,3,4,5,6\}$, $F = \{0,1\}^{\Omega}$

Here $F$ is the set of all subsets of the sample space $\Omega$ which are of interest. I don't understand this notation to specify that set. How does it generate/enumerate all the subsets of interest?

Asaf Karagila
  • 393,674
  • 4
    The notation $A^B$ with $A$ and $B$ sets denotes the set of all functions from $B$ to $A$; that is, $A^B = {f\colon B\to A\mid f\text{ is a function.}}$. So ${0,1}^{\Omega}$ is the set of all functions from $\Omega$ to ${0,1}$. Now identify a subset $M$ with its characteristic function $\chi_M\colon \Omega\to{0,1}$, where $\chi_M(x)=0$ if $x\notin M$ and $\chi_M(x)=1$ if $x\in M$. – Arturo Magidin Mar 12 '21 at 22:02
  • 1
    To add to @ArturoMagidin's comment, a good motivation for the notation $A^B$ to denote the set of maps $B \to A$ comes from when both sets are finite. If you count the number of such functions, you end up independently choosing one of $|A|$ possible outputs for each of $|B|$ inputs, hence $\bigl\lvert A^B \bigr\rvert = |A|^{|B|}$. – Sammy Black Mar 12 '21 at 22:05
  • @ArturoMagidin got it :+1 –  Mar 12 '21 at 22:11
  • In Set Theory $A^B$ also has other meanings so sometimes $^BA$ (in LaTex ^BA) is used to denote the set of all $f:B\to A$. – DanielWainfleet Mar 13 '21 at 02:56

2 Answers2

2

This is actually quite a profound aspect of set theory.

The powerset of $A$, or $\mathcal{P}(A)$, is defined to be $\{x : x \subseteq A\}$.

What is a subset of $A$? I suggest that, in some sense, a subset of $A$ is really just a function from $A$ to $\{0, 1\}$, where $0$ represents False and 1 represents True.

A function $f : A \to \{0, 1\}$ determines a subset of $A$ by $\{x \in A : f(x) = 1\}$.

Conversely, a subset $X \subseteq A$ determines a function $f : A \to \{0, 1\}$ by defining $f(a) = 1$ if $a \in X$, and $f(a) = 0$ otherwise.

Thus, with 0 representing False and 1 representing True, $f(a)$ tells us whether the statement $a \in X$ is true or false.

So strictly speaking, elements of $\mathcal{P}(A)$ are not functions $f : A \to \{0, 1\}$. But there is a bijective correspondence. Thus, we often write $\mathcal{P}(A) = \{0, 1\}^A$.

Mark Saving
  • 31,855
1

The Cartesian product

$$\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}$$ denotes the set of all $6$-tuples made of zeroes and ones. There are $2^6$ of them. You could write this as

$$\{0,1\}^6.$$

Now if you interpret a $0$ as "leave" and a $1$ as "take", every tuple corresponds to a subset. E.g.$(1,1,0,1,0,0)\equiv\{1, 2, 4\}$. In this context, the notation

$$\{0,1\}^\Omega$$ makes sense, though it is purely conventional. Another common notation is

$$2^\Omega.$$