Discrete Mathematics

Class 7: Sets


Problem Set 3 is due Friday at 6:29pm.

Notes and Questions

What is a data type? What are the differences between a mathematical data type and a data type in your favorite programming language?


A set is an unordered colection of objects. A set is defined by its membership operation: $x \in S$ is true if $x$ is in the set $S$. When $x$ is not in $S$ we write it as $x \notin S$. A set has only one copy of each element. Namely, there is no repetition in elements of a set. Also, a set $A$ could be a member o another set $B$, denoted by $A \in B$. Note that members of $A$ are not necessarily members of $B$ unless they are explicitly put in $B$ directly.

Set Operations

Subset: $\subseteq$ (note that this does not mean strict subset) $$A \subseteq B \iff \forall x \in A. \fillin \in \fillin.$$

Set Equality: $=$ $$A = B \iff A \fillin B \wedge B \fillin A.$$

Set Union: $\cup$ $$\forall x. x \in A \cup B \iff x \in A \fillin x \in B.$$

Set Intersection: $\cap$ $$\forall x. x \in A \cap B \iff x \in A \fillin x \in B.$$

Set Difference: $-$ $$\forall x. x \in A - B \iff x \in A \wedge x \notin B.$$

Set Complement: $\overline{S}$ $$ \forall x \in D. x \in \overline{A} \iff x \notin A.$$

($D$ is the ``domain of discourse”, the universe of all objects under discussion.)

Russell’s Paradox

$$ S_{R} = \textrm{ the set of all sets that are not members of themselves} $$

Is $S{R} \in S{R}$?

What is the source of this paradox? Note that in this question, we are implicitly assuming that $S{R}$ is a set, but we have never “constructed” this set properly to use it. Namely, here we are implicitly assuming that there is already a “set of all sets” $S{all}$ from which we remove those sets like $T$ for which $T \in T$. By removing all such $T$ from $S_{all}$ we get the set $S_R$.

Using Quantifiers More Carefully

Note that in some of the propositions that we used to define the set operations (such as union, intersection, etc.) above, we wrote quantified $x$ without saying which set it is from. For example $\forall x. [\dots]$. It is much preferred to always say what $x$ is belonging to when we quantify over $x$. The reason is to avoid traps like that of Russell’s paradox! This should not worry us in this class, as we will always work with well-defined universes that include all the elements of the sets that we work with. Therefore, we can always assume implicitly that $x \in U$ (for a well defined set universe $U$) even if not explicitly mentioned.


Set Practice

Here are some practice problems involving sets. We won’t go through these in class, but you should ask questions about any are unclear. (At least a few of these will be on Exam 1.)

  1. Define $A \subset B$ (strict subset).


  1. Prove $A \cup B \equiv B \cup A$.


  1. Prove $A - B = \emptyset \iff A \subseteq B$.


  1. Prove $A = B \iff (\forall a \in A \ldotp a \in B) \wedge (\forall b \in B \ldotp b \in A).$