# MATH 360 Review of Set Theory

5. **Theorem:** Suppose A, B and C are sets. Prove that
A∪ (B ∩ C) = (A ∪B) ∩

(A ∪ C).

**Proof:** We need the definitions of set equality and of subsets. We need to
prove

two things:

A ∪ (B ∩ C) (A ∪ B) ∩
(A ∪ C)

A ∪ (B ∩ C) (A ∪ B) ∩ (A ∪ C)

: Let x ∈ A ∪ (B ∩ C).
Then x ∈ A or x ∈ B ∩ C.

• If x ∈ A, then x ∈ A ∪ B and x ∈ A ∪ C by definition of union. Thus

x ∈ (A ∪ B) ∩ (A ∪ C) by definition of intersection.

• If x ∈ B ∩ C, then x ∈ B and x ∈ C. Thus x ∈ A ∪ B and x ∈ A ∪ C by

definition of union. Thus x ∈ (A∪B)∩(A∪C) by definition of intersection.

Either way, x ∈ (A ∪ B) ∩ (A ∪ C). Thus we have proved A ∪ (B ∩ C)

(A ∪ B) ∩ (A ∪ C)

: Let x ∈ (A ∪ B) ∩ (A ∪ C). Then x ∈ A ∪ B
and x ∈ A ∪ C. Now there are

two choices: either x ∈ A or x A.

• If x ∈ A, then x ∈ A ∪ (B ∩ C) by definition of union.

• If x A, then x ∈ B and x ∈ C by definition
of unions. Thus x ∈ B ∩ C

by definition of intersections. Thus x ∈ A ∪ (B ∩ C).

Either way, x ∈ A∪(B∩C). Thus we have proved A∪(B∩C)
(A∪B)∩(A∪C),

which, together with the first part, proves A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

6**. Theorem: DeMorgan's Laws: **X − (A ∪ B) = (X − A) ∩ (X − B)

**Proof:** Again, we need two parts to the proof:
and .

Let x ∈ X − (A ∪ B).

x ∈ X but x A ∪ B

x ∈ X but x A** and** x
B

x ∈ X − A and x ∈ X − B

x ∈ (X − A) ∩ (X − B).

Note: This time, rather than being forced to prove this in two separate parts

like the previous proof (i.e. first proving
then ) we were able to combine

both parts of the proof at once. But** be careful:** you must make sure that
the

proof reads correctly both from the top down **and from the bottom up!** (We

could not have done this with the previous proof: two different methods were

used.)

Second Note: If x A ∪
B, what does that mean? Well, for x ∈ A ∪ B means

x ∈ A or x ∈ B. Thus if x A ∪ B it must be
the case that
**both** x A **and**

x B.

**Definition: **Let A_{1},A_{2}, ..,A_{n} be a
collection of n sets. The** union** of A_{1},A_{2}, ...,A_{n}

is the set A_{1} ∪A_{2} ∪...∪A_{n} = {x : x ∈ A_{i}
for some i ∈ {1, 2, ...n}}. The
**intersection**

of A_{1},A_{2}, ...,A_{n} is the set A_{1} ∩ A_{2}
∩ ... ∩ A_{n} = {x : x ∈ A_{i}
for every i ∈ {1, 2, ...n}}.

The union is sometimes denoted and the
intersection is sometimes denoted

. Note: This should have all been covered in
your discrete math class (espe-

cially if you took that with me! ) If this is new to you, please come to see me
and

we will go over it.

**Example:** Let A_{1} = [0, 4),A_{2} = (−1, 6),A_{3}
= [3, 5],A_{4} = [2,∞). Then A_{1} ∪ A_{2} ∪

A_{3}
∪ A_{4} = (−1,∞) and A_{1} ∩ A_{2} ∩ A_{3} ∩ A_{4}
= [3, 4).

**Definition:** Let A_{1},A_{2}, ..,A_{n} be a
collection of n sets. The
**product **of A_{1},A_{2}, ...,A_{n}

is the set for every i ∈ {1, 2, ...n}}. The

element is called an ordered n-tuple. This
is sometimes denoted
.

**Example:** A_{1} = {1, 2},A_{2} = {2, 3},A_{3} =
{4}. Then

A_{1} × A_{2} × A_{3} = {(1, 2, 4), (1, 3, 4), (2, 2,
4), (2, 3, 4)}.

**Example:** Note that R^{3}= R × R × R.

Now we generalize to any union of any collection of sets and to any intersection
of

any collection of sets. Let = {1, 2, ..., n}. We could rewrite the union above
as

. But we can also understand
to be any set, not
just a finite set:

Let be a nonempty
set. If for each α ∈
there is a set A_{α} , the collection

is called an** indexed collection of
sets.
**

**Example:**Let = R and for each α ∈ let A

_{α}= [ α, α + 1). Then {A

_{α}: α ∈ } is

an indexed collection of sets. Note that A

_{1}= [1, 2),A

_{0}= [0, 1),A

_{π}= [ π, π+ 1) etc.

**Definition:**Now we can define {A

_{α}: α ∈ } = {x : x ∈ A

_{α}for some α ∈ } and

{A

_{α}: α∈ } = {x : x ∈A

_{α}for every α ∈ }.

**Examples:**

1. Let = and for each α ∈ let A

_{α}= [0, 1 +α ). Then {A

_{α}} = [0, 1]

and {A

_{α}} = [0,∞).

2. Let = and for each
α ∈ let B_{α}
= (−α , α). Then {B_{α}
} = (−1, 1)

and {B_{α} }
= R.

3. Let = Z and for each α ∈
let D_{α} = [ α, α+ 1]. Then
{D_{α} } = and

{D_{α} } = R.

**Theorem (DeMorgan’s Law for Indexed Sets):** Let {A_{α} : α ∈
} be an indexed

collection of subsets of a set X. Then .

**Proof: **Let x ∈ X.

Then x ∈ X −
{A_{α} }

x
{A_{α} }

x A_{α} for each and every α ∈

x ∈ X − A_{α} for every α ∈

x ∈ {X − A_{α}
}. QED.

Note: How can x not be in a union? If it is not in each and every one of the
sets!

That is how we proceed from the second to the third line in the proof above.

Second Note: To show that these two sets **are** equal we are actually using
the defi-

nition of set equality, showing that each set is a subset of the other, by
showing that

every element in one set is also an element of the other. (Go back and see how
we are

using the definitions if this is not clear to you. Or, come and see me! Sense a
theme

yet? )

**Theorem (DeMorgan's Law for Indexed Sets): **Let {A_{α} : α ∈
} be an indexed

collection of subsets of a set X. Then .

**Proof: **This proof is similar to the proof of DeMorgan's other law, given
above. Make

sure that you understand the reasoning behind it!

**Theorem:** Let {A_{α} : α ∈
} be an indexed collection of sets and let B be a set.

Then B ∩ {A_{α}
} =
{B ∩ A_{α} }.

**Proof: **Remember, to show that two sets are equal, we have to show that
each is a

subset of the other. This time, we cannot do this using a string of s,
as the logic

doesn’t quite work both ways.

: Assume x ∈ B ∩
. Then x ∈ B and x ∈
. Therefore there

exists β ∈
such that x ∈ A_{β} . Hence x ∈ B∩A_{β} . It follows that
.

Thus we have B ∩ {B ∩ A_{α} }.

: Homework.

**Theorem:** Let {A_{α} : α ∈
} be an indexed collection of sets and let B be a set.

Then B ∪ {B ∪ A_{α} }

**Proof:**

: Assume x ∈
{B ∪A_{α} }. Then x ∈ B ∪A_{α} for every α ∈
. Now either x ∈ B

or x B.

• If x ∈ B, then obviously x ∈ B ∪.

• If x B, then since x ∈ B∪A for every
α ∈ , it follows that
x ∈ A_{α} for every

α ∈ . Therefore x ∈
{A_{α} } which implies that x ∈B∩
.

In either case we have x ∈ B ∪
. This proves that

B ∪

: Homework.