$\newcommand{\nc}{\newcommand}$ $\nc{\Nn}{\mathbb{N}}$ $\nc{\Qq}{\mathbb{Q}}$ $\nc{\Zz}{\mathbb{Z}}$ $\nc{\Rr}{\mathbb{R}}$ $\nc{\ol}{\overline}$

Operations on Sets

Power Set

The power set of a set $X$, denoted by $P(X)$, is the set of all subsets of $X$.

That is, $P(X) = \{Y \colon Y \subseteq X\}.$

Since $\emptyset$ is always a subset of any set $X$,

so a power set is never empty (always contains the empty set as an element).

Ex: Write out $P(\emptyset)$.

Ex: Write out $P(\{0,1,2\})$. See this section of ADS for a computation of power set using SAGE.

If $Y \subseteq X$, then clearly $P(Y) \subseteq P(X)$. Is the converse true? Why?

The converse is also true. To see why, take any $a \in Y$, then $\{a\}$ is an element of $P(Y)$. Since $P(Y)$ is a subset of $P(X)$, $\{a\} \in P(X)$. But that just means $\{a\} \subseteq X$ and so $a \in X$. Since $a \in Y$, is arbitrary, we conclude that $Y \subseteq X$.

Complement

The complement of $Y$ in $X$ is the set

$$ X \setminus Y = \{a \in X \colon a \notin Y\}. $$

For instance, let $X = \{m,a,t,h,e\}$ and $Y = \{m,a,t,i,c,s\}$.

Q: What is $X \setminus Y$ and what is $Y \setminus X$?

In our mathematics discourse, often there is a set contains all sets of interest. We call it the universe and often denote it by $U$.

There is nothing universal about the universe. For number theory the universe maybe $\Zz$. For computer science the universe maybe the set of all binary strings.

If the universe $U$ is understood, we simply write $\ol{X}$ for, $U\setminus X$, the complement of $X$ in $U$.

Other common notations for $\ol{X}$ are $X^{c}, \neg X, \sim X$.

For example, if $U = \Zz$, then $\ol{\Nn}$ is the set of negative integers.

Q: What is $\ol{X}$ where $X = \{m,a,t,h,e\}$ ?

Two properties of set complementation.

1. $\ol{\ol{X}} = X$
2. $Y \subseteq X \iff \ol{X} \subseteq \ol{Y}$

Union and Intersection

Let $X,Y$ be sets.

The union of $X$ and $Y$ is the set $$ X \cup Y = \{a \colon a \in X \text{ or } a \in Y\}. $$ The intersection of $X$ and $Y$ is the set $$ X \cap Y = \{a \colon a \in X \text{ and } a \in Y\}.$$

$X$ and $Y$ are disjoint if $X \cap Y = \emptyset$.

It is clear from the definitions of union and intersection that

Let $X = \{m,a,t,h,e\}$ and $Y = \{m,a,t,i,c,s\}$.

Q: What is $X \cup Y$? What is $X \cap Y$?

A: $X \cap Y = \{m,a,t\}$, $X \cup Y = \{m,a,t,h,e,i,c,s\}$

There is a cool characterization of $\cup$ and $\cap$ by $\subseteq$:

$X \cup Y$ is the smallest set (in terms of set inclusion) that contains both $X$ and $Y$.

That is, $X,Y \subseteq X \cup Y$ and if $X,Y \subseteq Z$, then $X \cup Y \subseteq Z$.

Similarly, $X \cap Y$ is the largest common subset (in terms of inclusion) of $X$ and $Y$.

That is, $X \cap Y \subseteq X,Y$ and if $Z \subseteq X,Y$ then $Z \subseteq X \cap Y$.

Question. Given $|X|=5$ and $|Y|=6$, what is the smallest possible size of $X\cup Y$? What is the largest possible size of $X \cup Y$?

Give concrete examples that realize those bounds.

In general,

$$ |X \cup Y| = |X|+|Y|-|X \cap Y|.$$

This is the simpliest incidence of the principle of inclusion exclusion. We will see a visual proof using Venn diagram. More on this in when we study the principle in general.

Properties of Set Operations

Commutative

• $X \cup Y = Y \cup X$, $X \cap Y = Y \cap X$

Associative

• $X \cup (Y \cup Z) = (X \cup Y) \cup Z$, $X \cap (Y \cap Z) = (X \cap Y) \cap Z$

Distributive

• $X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)$
• $X \cup (Y \cap Z) = (X \cup Y) \cap (X \cup Z)$

De Morgan's Laws

• $\ol{X \cup Y} = \ol{X} \cap \ol{Y}$
• $\ol{X \cap Y} = \ol{X} \cup \ol{Y}$

An example: Say $A$ for Asians and $B$ for Boys.

Then what is $\ol{A \cap B}$? What is $\ol{A} \cup \ol{B}$?

Venn Diagram

Venn diagram is a tool that helps us to visual various boolean operations (union, intersection, complement) on sets.

Read this discussion of them in DM.

Cartesian Product

The Cartesian Product of $X$ and $Y$ is the set

$$ X \times Y = \{(x,y) \colon x \in X, y \in Y\}.$$

Example. $X = \{0,1,2\}$, $Y = \{a,b\}$. Then $$X \times Y = \{(0,a),(0,b),(1,a),(1,b),(2,a),(2,b)\}.$$

Question. What is $Y \times X$ then? What is $|X\times Y|$? $X \times Y = Y \times X$?

N.B. For order pairs, $(x,y) = (x',y')$ if and only if $x=x'$ and $y=y'$.

Read this section of ADS for more information on Cartesian Product.

Algebra of Sets

The set operations that we have talked about can be viewed as algebraic operations.

And that often make things easier to understand.

The key is to identify the subsets of a fix set $U$ with functions from $U$ to $2 = \{0,1\}$ as follows:

Associate to each $X \subseteq U$, the function indicator function of $X$ (in $U$):

\begin{align*} 1_X(a) = \begin{cases} 1 & \text{if}\ a \in X \\ 0 & \text{if}\ a \notin X \end{cases} \end{align*}

Example. $U=\{a,b,c,d\}$ $X=\{b,c\}$.

Then $1_X$ is the function $\begin{pmatrix} a & b & c & d \\ 0 & 1 & 1& 0\end{pmatrix}$

Exercise. Consider the function $f \colon U \to \{0,1\}$ given by

$$ \begin{pmatrix} a & b & c & d \\ 1 & 1 & 0& 1\end{pmatrix} $$

Find the subset corresponding to the function, i.e. find the subset $X$ of $U$ so that $1_X = f$.

Exercise Which subset of $U$ corresponds to the constant $1$ function? Which function correspond to the emptyset?

Here are some easy properties:

1. If $X$ is finite, $|X| = \sum_{a \in U} 1_X(a)$.
2. $Y \subseteq X$ if and only if $1_Y \le 1_X$ (i.e. $1_Y(a) \le 1_X(a)$ for all $a$).
3. $1_{\ol{X}} = 1-1_X$.
4. $1_{X\cup Y} = \max\{1_X, 1_Y\}$
5. $1_{X\cap Y} = 1_X1_Y$

Some applications

It is straight-forward to check (by cases) that

$$ \max\{1_X, 1_Y\} = 1_X + 1_Y - 1_X1_Y $$

From the stated properties, it follows that

$$ 1_{X \cup Y} = 1_X + 1_Y -1_{X \cap Y} $$

If $X$ and $Y$ are finite then summing over the elements of $U$, we get back

$$ |X\cup Y| = |X|+|Y|-|X \cap Y|$$

We can also deduce De Morgan's Law using algebra

\begin{align*} 1_{\ol{X} \cap \ol{Y}} &= 1_{\ol{X}}1_{\ol{Y}} = (1-1_X)(1-1_Y) \\ &= 1 - 1_X - 1_Y + 1_X1_Y \\ &= 1- (1_X + 1_Y - 1_{X \cap Y}) \\ & =1 - 1_{X \cup Y} = 1_{\ol{X\cup Y}} \end{align*}

That is $$ \ol{X \cup Y} = \ol{X} \cap \ol{Y}.$$