Sets of sets (about one lecture)
================================

(0) Trailer in previous lecture

We've seen sets of atomic objects.   Also sets containing tuples.
Now sets containing sets. [We'll call them "COLLECTIONS."]

Potential for getting lost in the curly brackets.  think of each set
as a box.  Do not flatten structure.

Example of 3-level nesting:   this gets very confusing.   We won't go
there.   Just examples with two levels of set brackets.

Example of CS faculty committees web page.
   f: {committees} --> P({faculty})
   f(x) = y
   x is a commitee, y is a set of faculty




==================================================

(1) Recall basic notation
  
   a set of atomic objects

   a collection of sets.   remember to use script variable letters for these

   power set:  concrete example with 3-element set A.   Notice that it contains
      A and the emptyset

   how many items in power set?  in/out choice for each element in set


(2) Combinations and permutations

  lead in:  sets vs. ordered tuples
      differences:  order?  duplicates?

  recall permutations
   
  57-flavor 4-scoop ice cream cone example.   Two questions to ask yourself:
      does order matter?
      can we have repeats?

  Joke:  for those who have seen Big Bang theory, Sheldon Cooper would *really* 
      care about the order of scoops.

  Give formulas for three of the four cases, recapping earlier in the term
      and readings for today.

(3) Breakout for the combinations with repetition case (and go back
   to fill in table in 2)

   Ex 1: Make constants smaller:  buy 8 bagels of 4 different kinds

   DO THE PICTURE with stars and dividers.  You need to remember how the
   construction works since the formula is hard to memorize but easy to
   re-build if you understand the construction.

   Ex 2: How many natural number solutions to a+b+c = 11?
         
   Ex 3: How many positive integer solutions to a+b+c = 11?


(4) Set-valued functions  

    The power set itself is not hard.    But they have a LOT of trouble groking
    what it means as the domain or co-domain in the type signature of a function.
   
    Example 1:  P = {people}   
              G = {food groups}
              F = {foods}

    Want to define function f that takes a person and a food group and returns the
        set of foods they eat from that group.

    build some input output pairs first
         (Margaret, dairy) --> {milk, cheese, yogurt}
              we need a set because multiple return values
         (Ally, vegetables) --> {peas}
              must be a set to keep output type consistent
         (Margaret, insects) --> emptyset
              sets also allow empty returns

    Need to return a set, not just a single food, so we can allow multiple returns
        or no return.

    Now work up to type signature f:PxG --> P(F)
       * an individual input is a pair of a person and a food group (p,g), 
         so domain is PxG
       * an individual output is a set of foods, so co-domain is P(F)
    
    Example 2: Domain can also be a power set, e.g.
      f:P(F) --> N
         f(X) = |X|
      I think this class of example may be easier for them.


(5) A larger example, segue into partitions

    Show the former exam question from the lecture handout last spring
         WTF?  What is this question even asking?

        A = {2,3,4,5,10,12}

        F:A --> P(A) such that F(x) = {y in A | y is a factor of x}

        Work out the values of F(12) and F(5)
  
        S = {F(x) | x in A}
   
        List the members of S.

        What's a partition?

(6) Partition idea

    Each element of X is in exactly one subset
          * no empty set
          * no overlap
          * covers all of X

    Example:   divide students into sets based on color of shirt
    
       >>> need a less lame example

    Is this true for S above?   (No)


(7) Another near-miss non-example

    Small graph with nodes X
    D: N --> P(X) 
       D(n) = {nodes with degree n}

    S = {D(n) | n in N} = {D(0), D(1), D(2), ...}

    Satisfies two properties ok.   But contains the empty set.   

    Could patch definition of S to make it a partition, e.g.

    S = {D(n) | n in N and D(n) not empty} 


(8) Formal definition

    (A lecture) didn't have time for both versions.  So just did the
        fully general ones and skipped the index finite set one.
    (B lecture) did both