We're broadcasting live from the Emerald City Bakery.
What muffins are for sale today?
Depending on the day, the bakery offers muffins with a variety of add-ons. The set of all possible add-ons is A:
A = {add-ons} = {chocolate-chip, blueberry, orange, almond, lemon, cherry, walnut}
My favorite is their lemon-almond muffin. We can represent this type using the set {lemon, almond}. They also persist in offering cherry-walnut muffins, despite the fact that they seem to be unpopular. I always seem them for sale at deep discount the next day. We can represent this type as {cherry, walnut}.
There could be muffins with one or three add-ons. (I don't think I've ever seen more than three.) For example, {chocolate-chip} or {orange} or {orange, lemon, blueberry}. We represent the one-element muffins as sets for consistency: each type of muffin is represented by a set of add-ons, i.e. a subset of A.
And naturally they offer plain muffins, which can be represented using the empty set \(\emptyset\).
We can now set up a set M that represents all eight types of muffins for sale today.
M = {\(\emptyset\), {orange}, {lemon}, {chocolate-chip}, {lemon, almond}, {cherry, walnut}, {orange, chocolate-chip}, {orange, lemon, blueberry}}
It would be very bad to flatten out the structure to produce something like this:
(NO NO NO!) M = {orange, lemon, chocolate-chip, almond, cherry, walnut, blueberry}
We need the substructure because each element of M is representing a specific type of muffin.
If A is a set, then the power set of A, shorthand \(\mathbb{P}(A)\), contains all subsets of A. \(\mathbb{P}(A)\) is a bit large to write out completely. Here's is some of it, organized by the size of the subset:
\(\mathbb{P}(A)\) = {\(\emptyset\), {orange}, {lemon}, ...
{orange, lemon}, {orange, blueberry}, ..., {lemon, blueberry}, ....
{orange, lemon, blueberry}, {orange, lemon, walnut}, ...
{orange, lemon, blueberry, walnut}, ...
....
{chocolate-chip, blueberry, orange, almond, lemon, cherry, walnut}}
To create a subset of A, we have 7 independent two-way choices, one for each flavoring in A. Do we include the flavoring or leave it out? So the power set of A contains \(2^7\) different subsets.
Let's compare \(\mathbb{P}(A)\) and M. \(\mathbb{P}(A)\) contains ALL subsets of A. M contains eight subsets of A. M is a subset of \(\mathbb{P}(A)\).
The power set frequently appears in function type signatures, indicating that the input and/or output of the function is a set whose members are chosen from some specific base set.
For example, consider the function C that returns the number of calories in each type of muffin:
C(\(\emptyset\)) = 400
C({lemon,almond}) = 450
C({chocolate-chip}) = 800
Each output value is a natural number. So the co-domain is the set of all natural numbers \(\mathbb{N}\). Similarly, each input value is a subset of A. So the domain of the function is the set of all subsets of A. This is \(\mathbb{P}(A)\). So the type signature is
\(C: \mathbb{P}(A) \rightarrow \mathbb{N}\)
Now suppose that we are taking orders from everyone at a hackathon. Let's say that H contains the set of attendees. We'd like to build a function g that maps each person to their favorite type of muffin.
g(Margaret) = {lemon, almond}
g{Flora} = {orange}
g{Ndumiso} = {}
Each type of muffin is a set of add-ons. So each value produced by g is a subset of A. So the co-domain of g is the set of all subsets of A. So g's type signature is
\(g: H \rightarrow \mathbb{P}(A)\)
So when the domain/co-domain of a function is the power set of A, then an individual input/output is a set of elements of A.