MUN Computer Science 1002 - Lab 5

Sets

Review:

• Lectures 10, 15-16.

Vocabulary

• Definition, theorem, proofs
• Set, subset, disjoint sets, empty set, universe
• Union, intersection, complement, difference
• Cardinality of a set, rule of inclusion-exclusion
• Power set, cartesian product
• Proving properties of sets, laws of set theory, boolean algebra

Individual work

Solve each of the following exercises.

1. In a proof, you often see a line following from previous by definition. For example, you might say "n is an even number. Then, n=2k for some integer k". In the following, fill in the blank after "then" by using a corresponding definition.
   1. (Definition: an integer a is odd if there exists an integer b such that a=2b+1).
      Let n and m be two odd integers. Then, ...
   2. (Definition: for $a,b \in \mathbb{Z}$, a divides b if there exists $ c \in \mathbb{Z}$ such that a = bc).
      Let n be an integer divisibe by 5. Then,
   3. (Definition: for $a \in \mathbb{R}$, $|a|=a$ if $a \geq 0$, and $|a|= -a$ if $a <0$).
      Suppose $r \in \mathbb{R}$. Then, case 1 ... |r| is ... case 2 ...
2. For each of the following, describe the union, intersection and symmetric difference of the given sets, their differences and complements (symmetric difference is the union of differences). Draw a Venn diagram, and give an example of an element in every region of the Venn diagram.
   1. $U = $ set of all living creatures. $A =$ set of all mammals. $B = $ set of all pets.
   2. $U = \mathbb{R}$, $A = \{ x \in \mathbb{N}| x$ is prime$\}$, $B = \{x \in \mathbb{Z} | $ last digit of x is 3 $\}$, $C = \mathbb{Q}$.
3. For each of the following, list or describe all elements in the resulting set.
   • $A = \{ x \in \mathbb{N} | 1 \leq x \leq 30\}$. $B= \{ x \in \mathbb{N} | 1 \leq x \leq 20$ and x is prime $\}$. $A \cap B = \{$
   • $A = \{ x \in \mathbb{N} | 1 \leq x \leq 30\}$. $B= \{ x \in \mathbb{N} | 1 \leq x \leq 20$ and x is prime $\}$. $A \cup B = \{$
   • $U = \{a,b,c,d,e,f,g,h,i\}$. $A =\{d,f,g,h,i\}$. $B = \{x | x$ is a vowel $\}$. $\overline{A} \cap B =\{ $
   • $U = \mathbb{N}$ $A = \{x | x$ is prime $\}$. $B= \{ x| 1 < x < 8\}$. $C = \{x | x$ is even $\}$. $(\overline{A} -C)\cap B = \{$
4. Give cardinalities of all finite sets from the previous question.

Group exercises

For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

Topic 1: Power sets

• $A=\{1,2,3\} $
• $B=\{ \emptyset \}$
• $C = \{a, \{a\} \} $

Topic 2: Cartesian product

For each of the following, write a list elements of the Cartesian product.

• $A=\{0,1\}, B=\{1,2,3,4\}$. $A \times B = \{ $
• $A = \{\emptyset, 0 \}, B = \{A, \{0,1\}, 0 \} $ $ A \times B \times A = \{ $

Topic 3: The rule of inclusion/exclusion.

• Suppose that $|A|=20$, $|B|=30$ and $|A \cup B|= 40$. What is the value of $|A \cap B|$? How will your answer change if $|A|=10$? And what are the maximal and minimal values for |A| which do not give a contradiction, provided other numbers are the same?
• 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.

Review after the group activity

Let $A = \{0,6,9\}$ and $B = \{ \emptyset, \{0\}\}$.

1. What are the powerset of A and of the powerset of B? Describe the set as $\{ .... \}$ with the list of elements.
2. What is the Cartesian product of A and B? Describe the set as a list of elements.
3. What is the cardinality of the Cartesian product of the powerset of A and a powerset of B? Do not list the set, just compute the numbers.
4. Let $|C|=20$ and $|D|=15$. What are the maximal and minimal values of $|C \cup D|$ and $|C \cap D|$?