Andrew Cooper

Just like we defined logical formulae by giving truth tables, we can define set formulae by giving a criterion for membership.

Definition. Given sets $A$, $B$, we define

•  the complement of $A$, $A^c$, by the rule $x\in A^c$ iff $x\notin A$.
•  the intersection} of $A$ and $B$, $A\cap B$, by the rule $x\in A\cap B$ iff $x\in A$ and $x\in B$.
•  the union of $A$ and $B$, $A\cup B$, by the rule $x\in A\cup B$ iff $x\in A$ or $x\in B$.
•  the difference of $A$ and $B$, $A\setminus B$, by the rule $x\in A\setminus B$ iff $x\in A$ and $x\notin B$.

The set operations ${}^c, \cap, \cup, \setminus$ take in sets and produce sets. So we can ask, just as we asked for the logical operations, whether these operations commute, distribute, associate, etc. We’d like to prove the following theorem:

Theorem. For sets $A$, $B$, $C$,

1. $\left(A\cup B\right)\cup C=A\cup\left(B\cup C\right)$ and $\left(A\cap B\right)\cap C=A\cap\left(B\cap C\right)$, i.e. union and intersection are associative.
2. $A\cup B=B\cup A$ and $A\cap B=B\cap A$ (i.e. union and intersection are commutative).
3. $A\cup\left(B\cap C\right)=\left(A\cup B\right)\cap \left(A\cup C\right)$ and $A\cap\left(B\cup C\right)=\left(A\cap B\right)\cup \left(A\cap C\right)$ (i.e. union and intersection each distributes over the other)

Exercise. Write a formula (in terms of ${}^c,\cup,\cap,\setminus$) which corresponds to exclusive {\em or}. That is, give an expression for $S$ so that $x\in S$ iff $x\in A$ exclusive or $x\in B$.

To prove a theorem like the one above, we need to understand what it means for two sets to equal each other. Since sets are defined by their elements, two sets should be equal if they have the same elements. That is,

Definition. $A=B$ means $x\in A$ iff $x\in B$.

The fact that $P\Leftrightarrow Q$ is equivalent to $\left(P\Rightarrow Q\right)\wedge\left(Q\Rightarrow P\right)$ means we could just as well say that

Definition. $A=B$ means $x\in A$ guarantees $x\in B$ and $x\in B$ guarantees $x\in A$.

We’ll prove the commutativity of $\cup$ as an example.

Proof that $A\cup B=B\cup A$. We need to show that $x\in \left(A\cup B\right)$ guarantees $x\in \left(B\cup A\right)$. So let $x\in\left(A\cup B\right)$. By definition of union, this means $(x\in A)\vee (x\in B)$, which is equivalent to $(x\in B)\vee (x\in A)$. By definition of union, this means $x\in \left(B\cup A\right)$.

We also need to show that $x\in \left(B\cup A\right)$ guarantees $x\in \left(A\cup B\right)$. So let $x\in\left(B\cup A\right)$. By definition of union, this means $(x\in B)\vee (x\in A)$, which  is equivalent to $(x\in A)\vee (x\in B)$. By definition of union, this means $x\in \left(A\cup B\right)$. $\Box$.

Definition. We write $A\subseteq B$ (read “$A$ is a subset of $B$”) if $x\in A\Rightarrow x\in B$.

So we finally have our most useful equivalent definition of set equality:

Definition. $A=B$ iff $A\subseteq B$ and $B\subseteq A$.

Theorem. Set inclusion is transitive. That is, if $A$, $B$, and $C$ are sets with $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

Proof. Let $A$ and $B$ and $C$ be sets with $A\subseteq B$ and $B\subseteq C$. To see that $A\subseteq C$, let $x\in A$. Since $A\subseteq B$, and $x\in A$, $x\in B$. Since $B\subseteq C$ and $x\in B$, $x\in C$.

Thus we’ve shown that every $x\in A$ is guaranteed to have $x\in C$, so $A\subseteq C$. $\Box$

Theorem. If $A$, $B$, and $C$ are sets with $A\subseteq B$, $B\subseteq C$, and $C\subseteq A$, then $A=B$ and $B=C$.

Proof.Let $A$, $B$, and $C$ be such sets. We’ll first show $A=B$. $A\subseteq B$ by assumption. We’ll show $B\subseteq C$ by applying the previous theorem to $B$, $C$, and $A$.

Now since $A=B$, we have by assumption that $B\subseteq C$ and also by assumption $C=A\subseteq B$. So $B=C$. $\Box$

The Empty Set and Other Subsets

An important set for us will be the {\em empty set}. It is the set-theoretic equivalent of a contradiction.

Definition. The empty set is $\varnothing = \{ x\vert x\neq x\}$, the set of all things which are not themselves.

Lemma. The empty set has no elements.

Proof. Suppose, for the purpose of obtaining a contradiction, that there were some $x\in\varnothing$. Then $x\neq x$. But this is absurd. So there can be no such $x$. $\Box$.

Theorem. For any set $A$, $\varnothing\subseteq A$.

Proof. To show $\varnothing \subseteq A$, we need to show that $x\in \varnothing \Rightarrow x\in A$.

So let $x\in \varnothing$. By definition of $\varnothing$, $x\neq x$. But there are no such $x$, so the statement $x\in\varnothing$ is false. Thus the conditional $x\in\varnothing\Rightarrow x\in A$ must be true. $\Box$

Theorem. The empty set is the unique set with no elements.

That is, not only does $\varnothing$ have no elements, but it’s also the case that {\em any} set with no elements must be $\varnothing$.

Proof. Let $A$ be a set with no elements. We’ll show that $\varnothing\subseteq A$ and $A\subseteq \varnothing$. The first was established by the previous theorem.

To see that $A\subseteq\varnothing$, we’ll show that $x\in A \Rightarrow x\in\varnothing$. But there are no $x\in A$, so this is a conditional with a false antecedent, hence automatically true.$\Box$

This is somewhat surprising, because it means, in particular, that the set of natural numbers with no successor and the set of married bachelors and the set of dogs with twelve million legs are all the same set (notwithstanding that one of them is a “set of numbers”, one is a “set of people”, and one is a “set of dogs”).

The Powerset

There’s one more axiom of sets we need, besides the empty set being a set. That’s

Axiom of Infinity. For any set $A$, the collection of all subsets of $A$ is its powerset, $2^A$.

That is, $z\in 2^A$ means $z\subseteq A$.

E.g. Let $A=\{1,2\}$. The powerset of $A$ is $\{\varnothing, \{1\}, \{2\},\{1,2\}\}$.

Exercise. What is $2^\varnothing$? What is $2^{2^\varnothing}$?

Exercise. Can a powerset ever be empty?

Why the notation $2^A$?

Theorem. If $A$ is a finite set with $N$ elements, then $2^A$ is finite and has $2^N$ elements.

This proof is a counting proof–we need to know how many of something there are, so we just make sure we count everything once. More on this later!

Proof. Each element of $2^A$ is a subset of $A$. So we really need to count the number of subsets of $A$.

Given a subset $S$, for any element $x$ $A$, we can ask “Is $x$ in $S$?”. There are $N$ times we need to ask this question, and 2 possible answers, so we have $2^N$ possibilities (each of which corresponds to a subset of $A$). Thus there are $2^N$ subsets of $A$, hence $2^N$ elements of $2^A$. $\Box$