UI logo
CS 173
Spring 2021

Collections of Sets 1

Day at the Bakery

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.

The Power Set

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 in function type signatures

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.