Mathematicians tend to prove results about sets as they need them, rather than memorizing and using a large collection of rules. There are a lot of rules involving sets; you'll probably become familiar with the most important ones simply by using them a lot.
Usually you can check informally (for instance, by using a Venn diagram) whether a rule is correct; if necessary, you should be able to write a proof. In most cases, you can give a proof by going back to the definitions of set contructions in terms of elements.
Once you've compiled a collection of known facts about sets, you can use those facts to prove other facts.
There are also various styles for these proofs. You can write a proof formally, as a series of implications or double implications.
Alternatively, you can give a proof that relies more on words.
Example. ( Distributivity) Let A, B, and C be sets. Prove that
If X and Y are sets, if and only if for all x,
if and only if
.
First, I'll give a formal proof, written as a series of double implications:
I've shown that
By definition of set equality, this proves that .
The idea of the proof was to reduce everything to statements about elements. Then I used logical rules to manipulate the element statements.
Here's an alternative proof written with more words. I'll prove by showing that each
set is contained in the other.
First, I'll show that . Let
. By definition of
intersection, this means that
and
.
Now means, by definition of union,
or
. Combining this with the fact
that
, this means that either
and
, or
and
.
By definition of intersection (twice), this means that either or
. And by the definition of
union, this means that
.
I've shown that if , then
. By definition of subset,
.
Next, I'll show that . Let
. By
definition of union,
or
.
In the first case, . By definition of
intersection, this means
and
. Now by
constructing a disjunction,
gives
or
, and by definition of union, I
get
.
Since I know , the definition of intersection gives
.
In the second case, . By definition of
intersection, this means
and
. Now by
constructing a disjunction,
gives
or
, and by definition of union, I
get
.
Since I know , the definition of intersection gives
.
Since in both cases I have , I have shown
that if
, then
. By definition of subset, this means that
.
Finally, since I've shown that and
are each contained in the other, they must
be equal:
.
You can see that the first proof is shorter, but sometimes shorter proofs require more thinking to understand: The proof is shorter because the reasoning is compressed. The second proof is much longer, but maybe the words make more sense to you.
Note: It's also true that
Example. ( DeMorgan's Law) Let A and B be sets. Prove that
I'll just prove the first statement; the second is similar. This proof will illustrate how you can work with complements. I'll use the logical version of DeMorgan's law to do the proof.
Let x be an arbitrary element of the universe.
Therefore,
.
Example. Let A and B be sets. Prove that .
This example will show how you prove a subset relationship.
By definition, if X and Y are sets, if and only if
for all x, if
, then
.
Take an arbitrary element x. Suppose
(conditional proof). I want to show that
.
means that
and
, by definition of intersection. But
and
implies
(decomposing a conjunction), and this is what I
wanted to show. Therefore,
.
By the way, you usually don't write the logic out in such gory detail. The proof above could be shortened to the following.
means that
and
, so in particular
. Therefore,
.
The "in particular" substitutes for decomposing the
conjunction.
The procedure I've followed is so common that it's worth pointing it
out: To prove a subset relationship (an
inclusion) , take an arbitrary
element of X and prove that it must be in Y.
In the next example, I'll need the following facts from logic. First,
is a tautology:
Also, :
In effect, this means that I can drop tautologies from "and" statements. I'll just call this "Dropping tautologies" in the proof below.
Example. Prove that .
Therefore, .
Example. Let A be a set. Prove that
This example will show how you can deal with the empty set.
To prove , let x be an arbitrary element of
the universe. First, by definition of
,
I'll show that
. To prove
, I must prove
and
.
First, if , then
(constructing a disjunction).
Next, suppose . The second
statement
is false for all x, by definition
of
. But the
-statement is true by assumption,
so
must be true by disjunctive syllogism. This proves
that if
, then
.
This completes my proof that . So
Therefore, .
To prove that , I must prove that
for all x,
if and only if
.
As usual, x be an arbitrary element of the universe. To prove if and only if
, I must prove that the following implications:
I'll do this by showing that, in each case, the antecedent (i.e. the
"if" part of the statement) is false --- since by
basic logic, if P is false, then is true.
For the first implication, consider the statement . By definition of intersection,
Now is false, by definition of the
empty set. Therefore, the conjunction
is also false. Hence,
is
false.
It follows that the implication is true, because the "if" part is false.
Likewise, the second implication is true because
is false, by definition of the empty set.
Since both implications are true, if
and only if
. And this in turn proves that
.
Copyright 2019 by Bruce Ikenaga