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 ,
,
,
and
, i.e. union and intersection are associative.
and
(i.e. union and intersection are commutative).
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
.