3.1 Sets of sets

In Section 2, all the sets and sequences we considered had primitive forms of data as their elements. However, sets and sequences may contain non-primitive forms of data. Let us look first at a situation in which we may find it useful to have a set whose members are themselves sets.
Think again about a shop with just three members of staff, given in the set Staff = {Jo, Jessica, Wesley}. Now let at WorkStaff be the set of staff currently at work. Clearly, at WorkStaff may take a range of values. If just Jo and Wesley are at work, then at WorkStaff is {Jo, Wesley}. If Jessica were to start work and Jo were to leave, then at WorkStaff becomes {Jessica, Wesley}.
Now any combination of staff from the set Staff = {Jo, Jessica, Wesley} might be at work at the same time. Possibilities include all these staff (when at WorkStaff is {Jo, Jessica, Wesley}), and none of them (in which case at WorkStaff is { }). The full list of possibilities (giving the possible values of at WorkStaff ) is given below.
{ }, {Jo}, {Jessica}, {Wesley}, {Jo, Jessica}, {Jo, Wesley}, {Jessica, Wesley}, {Jo, Jessica, Wesley}
Here, we have written out all the sets with members taken from the set Staff = {Jo, Jessica, Wesley}. We can form a set whose members are these sets. We will denote this set by SetOfStaff . So:
SetOfStaff = {{ }, {Jo}, {Jessica}, {Wesley}, {Jo, Jessica}, {Jo, Wesley}, {Jessica, Wesley}, {Jo, Jessica, Wesley}}.
The outer curly brackets here delimit the members of the set SetOfStaff. Each of these members is itself a set, and the inner curly brackets delimit each of these member sets. We will not often need to list the members of a set of sets like this. But it is useful to be aware that we can form a set in this way. We might have a variable atWorkStaff, giving the set of staff currently at work. The set giving all possible states of this variable is then SetOfStaff.
In general, we will use SetOfX to denote the set consisting of all the sets drawn from some given set, X. SetOfX is also known as the power set of X. Various other notations are used for this, including P(X) and 2 ^X . The latter is sometimes used since, if X has cardinality n, then SetOfX has cardinality 2 ⁿ . For example Staff has cardinality 3 and SetOfStaff has cardinality 8, which is 2³.

Activity 10

Suppose that the set of tills in a supermarket is Tills = {T1, T2, T3} and active Tills is a variable giving the set of tills that are staffed at any one time. Write out in full the set of possible states for active Tills.

Discussion

The set of possible states is the set SetOfTills. Written in full, this is:
{{}, {T1}, {T2}, {T3 }, {T1, T2}, {T1, T3}, {T2, T3}, {T1, T2, T3}}.