# MUN Computer Science 1002 - Lab 5 Sets

### Materials:

Please bring scratch paper and pens/pencils.
During the quiz, you can use only the paper notes you made solving the lab, as well as the text of the lab itself.

### Review:

• Lectures 10, 14, 16-17.

### Vocabulary

• Modular arithmetic, quotient-remainder theorem, congruence modulo a number
• Set, subset, disjoint sets, empty set, universe
• Union, intersection, complement, difference
• Cardinality of a set, rule of inclusion-exclusion
• Power set, cartesian product

## Individual work

Solve each of the following exercises.

1. Recall the quotient-remainder theorem from lecture 14 that for every integer $n$ and natural number $d$ there exist integers q and r, where $0 \leq r \leq d-1$ such that $n = qd+r$. Now, for each of the following pairs of d and n, find $q$ and $r$.
• $d=3$, $n= 1, 9, 10, -4$.
• $d=5$, $n= 1, 9, 10, -4$
2. For d=3 and d=4, list all the numbers congruent to 0 mod d that are between -5 and 10. Now, repeat the exercise with the same two values of d and numbers congruent to 1 mod d (so you should have 4 lists of numbers in this exercise).
3. For each of the following, list all elements in the resulting set.
• $A = \{ x \in \mathbb{N} | 10 \leq x \leq 20\}$.
• $B= \{ x \in \mathbb{N} | 1 \leq x \leq 20$ and x is prime $\}$.
• $C = \{ x \in \{a,b,c,d,e,f,g,h,i\} | x$ is a vowel $\}$
4. For each of the following, write a list of elements of the Cartesian product.
• $A=\{0,1\}, B=\{1,2,3,4\}$. $A \times B = \{$
• $A = \{1,2\}, B = \{2,3\}, C=\{3,4\}. A \times B \times C = \{$
5. Give cardinalities of all sets you described in the previous two questions.

## Group exercises

For each of the questions below, create a representation of a set by putting corresponding figures in a plastic bag. For most of the exercises, copies of the same element count as one element, so avoid duplicates.

#### Exercise 1: Set operations

Use pieces in a bag labeled 1 for this exercise. First, create a representation of a set containing an orange star, a green star and a green circle by picking the corresponding pieces and putting them in a plastic bag. Now, each of the three members of the group should create their own set with 4 elements, by picking 4 pieces each and putting them in their own plastic bags. So together with the original one you have 4 sets. Pick two out of three sets you and your friends made which have at least one element in common. Let's call these sets A and B, and the remaining 4-element set C. Let's call your first set {orangestar, greenstar, greencircle} D.
• Make a set corresponding to the complement of set C, that is, set $\overline{C}$. Here, the universe is the set of 10 elements of 5 different colours and 2 different shapes. Keep the set $\overline{C}$ you just made for the 3rd part of this exercise.
• Take elements of the A and B, and use them to make their union $A \cup B$ and intersection $A \cap B$. Now, make an intersection and union of all three 4-element sets. That is, make sets corresponding to $A \cap B \cap C$ and $A \cup B \cup C$. Hint: you can represent the empty set by an empty bag, if you need an empty set.
• Draw a Venn diagram showing the relationships between A, B and C. Make sure to show on your diagram if any of your sets are disjoint.
• Make a set corresponding to the difference of the complement of C with the set D, that is, $\overline{C}-D$. Then make a set corresponding to $D-\overline{C}$. Finally, use two sets you just made to make a set for symmetric difference of $\overline{C}$ and D, $\overline{C} \triangle D$.
• Finally, suppose you start with a set of 5 elements and a set of 3 elements. What are the minimal and maximal possible number of elements in their intersection? In their union? In their difference? What are the relationships between the sets when minimums and maximums are achieved?

#### Exercise 2: Subsets and powersets

Use a bag number 2 for this exercise.
• Make a set of 3 elements. Now, make a set containing its subset with 2 elements. How many such 2-element subsets can you make?
• Make a set corresponding to a powerset of {heart, $\emptyset$}. Hint: You can put bags inside a bag. And empty bag represents empty set. How many elements are in the resulting set (that is, what is the cardinality of the powerset of {heart, $\emptyset$})?
• Make a set corresponding to a powerset of { {star, heart}, star, cross}. Use the large bag to represent your powerset. What is the number of elements (cardinality) in the set corresponding to your large bag?

#### Exercise 3: The law of inclusion/exclusion

Take the bag marked "3". For this exercise, you will treat each piece in this bag individually (so the bag has 9 pieces, rather than 4 types).
• Draw a Venn diagram representing a set of red pieces and a set of stars, and fill in the numbers of elements in each part of the diagram. Now, use the law of inclusion-exclusion to calculate how many pieces you chose are either red or a star; check that you indeed have that many.
• Now, note that some pieces are small and some large. Draw a Venn diagram with three sets: red pieces, stars and large pieces. Now, use the law of inclusion-exclusion for three sets to calculate (with information given in the previous subquestion) how many pieces are either red or stars or large. Check your answer by counting your pieces.
• At the start of group exercise, your group had to make 3 sets of 4 elements each, using elements of 5 colours and 2 shapes, for 10 types total. What is the smallest number of types of pieces you could use to make 3 different sets of 4? Could you select 3 sets of 4 out of this universe in such a way that all of them are disjoint? Such that no two of these sets have intersection containing more than 1 piece?

## Review after the group activity

Let $A = \{0,2, 5\}$ and $B = \{ 5, \{\emptyset\}\}$.

1. List elements in $A \cup B$, $A \cap B$, $A-B$ and $A \triangle B$. Draw a Venn diagram for each.
2. Let the universe be $\{0,1,2,3,4,5,\{\emptyset\} \}$. List elements in $\overline{A}$ and in $\overline{B}$.
3. What are the powerset of A and of the powerset of B? Describe the set as $\{ .... \}$ with the list of elements. Note that the last element in B is a set containing an empty set, not just an empty set (think empty bag inside an empty bag).
4. Let $|C|=20$ and $|D|=15$ for some sets $C$ and $D$. What are the maximal and minimal values of $|C \cup D|$ and $|C \cap D|$? What is the relationship between C and D when the values are minimal/maximal?
5. Solve the following problem using inclusion-exclusion.
Suppose there are 30 people at a party interested in music, 35 interested in mathematics and 40 interested in biology. There are 15 people interested in both math and biology, 20 in math and music and 10 in music and biology; out of them 5 people are interested in all three. How many people are at the party? Draw a Venn diagram, and for each region on it, note how many people are in that region.