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).$