# Set Operations and Subsets

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

Definition. Given sets , , we define

•  the complement of , , by the rule iff .
•  the intersection} of and , , by the rule iff and .
•  the union of and , , by the rule iff or .
•  the difference of and , , by the rule iff and .

The set operations 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 , , ,

1. and , i.e. union and intersection are associative.
2. and (i.e. union and intersection are commutative).
3. and (i.e. union and intersection each distributes over the other)

Exercise. Write a formula (in terms of ) which corresponds to exclusive {\em or}. That is, give an expression for so that iff exclusive or .

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. means iff .

The fact that is equivalent to means we could just as well say that

Definition. means guarantees and guarantees .

We'll prove the commutativity of as an example.

Proof that . We need to show that guarantees . So let . By definition of union, this means , which is equivalent to . By definition of union, this means .

We also need to show that guarantees . So let . By definition of union, this means , which  is equivalent to . By definition of union, this means . .

Definition. We write (read  is a subset of ") if .

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

Definition. iff and .

Theorem. Set inclusion is transitive. That is, if , , and are sets with and , then .

Proof. Let and and be sets with and . To see that , let . Since , and , . Since and , .

Thus we've shown that every is guaranteed to have , so .

Theorem. If , , and are sets with , , and , then and .

Proof.Let , , and be such sets. We'll first show . by assumption. We'll show by applying the previous theorem to , , and .

Now since , we have by assumption that and also by assumption . So .

### 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 , 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 . Then . But this is absurd. So there can be no such . .

Theorem. For any set , .

Proof. To show , we need to show that .

So let . By definition of , . But there are no such , so the statement is false. Thus the conditional must be true.

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

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

Proof. Let be a set with no elements. We'll show that and . The first was established by the previous theorem.

To see that , we'll show that . But there are no , so this is a conditional with a false antecedent, hence automatically true.

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 , the collection of all subsets of is its powerset, .

That is, means .

E.g. Let . The powerset of is .

Exercise. What is ? What is ?

Exercise. Can a powerset ever be empty?

Why the notation ?

Theorem. If is a finite set with elements, then is finite and has 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 is a subset of . So we really need to count the number of subsets of .

Given a subset , for any element , we can ask Is in ?". There are times we need to ask this question, and 2 possible answers, so we have possibilities (each of which corresponds to a subset of ). Thus there are subsets of , hence elements of .

Published in sets.