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₁,A₂, ..,A_n be a collection of n sets. The union of A₁,A₂, ...,A_n
is the set A₁ ∪A₂ ∪...∪A_n = {x : x ∈ A_i for some i ∈ {1, 2, ...n}}. The intersection
of A₁,A₂, ...,A_n is the set A₁ ∩ A₂ ∩ ... ∩ 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₁ = [0, 4),A₂ = (−1, 6),A₃ = [3, 5],A₄ = [2,∞). Then A₁ ∪ A₂ ∪
A₃ ∪ A₄ = (−1,∞) and A₁ ∩ A₂ ∩ A₃ ∩ A₄ = [3, 4).

Definition: Let A₁,A₂, ..,A_n be a collection of n sets. The product of A₁,A₂, ...,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, 2},A₂ = {2, 3},A₃ = {4}. Then

A₁ × A₂ × A₃ = {(1, 2, 4), (1, 3, 4), (2, 2, 4), (2, 3, 4)}.

Example: Note that R³= 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, 2),A₀ = [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.