T- 5 hours until the Super Bowl. Let’s knock some FOM out first, shall we?

## 2.1: Exploring Sets

Definition 2.1: For a set A, the *power set* *of A*, written “P(A)”, is the set consisting of all the subsets of A.

Definition 2.2: For sets A and B, “A is a *subset* of B” means: if x ∈ A, then x ∈ B.

BUT, what about when one set is the empty set? No worries, because of the way “If, Then” statements work, there is no way the hypothesis could be true (There are no elements in the empty set), so the conclusion will always be vacuously true. Because there are no elements in the empty set, though, that means that the empty set is a subset of any and all sets.

Theorem 2.1: For any set A, ∅⊆ A.

**Get Your Hands Dirty 1**

List the elements of P(X) and find the cardinality |P(X)| for each of the following sets:

A. X = {1}

{ { }, {1} }, |X| = 1

B. X = {1,2}

{ { }, {1}, {2}, {1,2}}, |X| = 2

C. X = {1,2,3,4}

{ { }, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,3,4}, {1,2,4}, {2,3,4}, {1,2,3,4}}, |X| = 4

**Get Your Hands Dirty 2**

Is it possible for something to be both an element and a subset of something?

Yes! We’ve gone over it in class! Take this example.

Take this set: {&, $, ℤ, ∑, Ω, Ψ} ∪ ℤ. (This whole thing is a set. You can union two sets and have that union stand alone as a set).

In this case, ℤ is an element of the set (It’s in the {}!) and since we are union-ing (making new words, YOLO) this new set with ℤ, this set has to be a subset of Z.

Definition 2.3: For sets A and B, the *Cartesian Product* of A and B (written “A x B”) is the set consisting of all ordered pairs (x,y) in which x is an element of A and y is an element of B.

A x B= {(x,y): x ∈ A and y ∈ B}; A and B are called

factorsof A x B, and “x” and “y” are calledcoordinatesof the pair (x,y).

**Get Your Hands Dirty 3**

List the elements and the cardinality of each of the following Cartesian products:

A. {1,2,3} x {2,4,6}

= {(1,2), (1,4), (1,6), (2,2), (2,4), (2,6), (3,2), (3,4), (3,6)}

B. {1,2} x {1,2,3} x {2,3}

= {(1,1,2), (1,1,3), (1,2,2), (1,2,3), (1,3,2), (1,3,3),(2,1,2), (2,1,3), (2,2,2), (2,2,3), (2,3,2), (2,3,3)}

**Get Your Hands Dirty 4**

Give five elements of the truth set for each of the following open sentences:

A. 3x-7y = 12 (universe = ℝ x ℝ: make “x” the first coordinate)

{(1, (-9/7)), (2, (-6/7)), ((19/3),1),(3, (-3/7)), ((26/3),2)}

B. r + 2s + 3y = 17 (universe = ℕ x ℕ x ℕ: make “r” the first coordinate and “s” the second coordinate)

{(1,2,4), (7,2,2), (6,2,3), (8,3,1), (6,4,1)}

C. a ≠ b (universe = {1,2,3,4} x {2,3,4,5}: make “a” the first coordinate)

{(1,2),(1,3),(1,4),(1,5),(2,3)}

**Get Yours Hands Dirty **5

If A is any set (possibly empty), what are A x ∅ and ∅ x A?

If this were to happen, I think you would end up just listing the elements of A, like so:

Say A = {1,2,3,4}

A x ∅ = { (1, ),(2, ),(3, ),(4, )}

And the same would go for if ∅ was the first set. I would not write an element set like: (1, ∅), as that would designate a set of the empty set, not the empty et by itself.

**Get Your Hands Dirty 6**

A. None of the portions are empty.

{1,2,3,4,5,6,7,8}

B. Exactly three of the portions are nonempty.

{1,2,3}

C. Exactly two of the portions are empty.

{1,2,3,4,5,6}

## 2.2 Proofs About Sets

Theorem 2.2**: **For sets A, B, and C,

If A ⊆ B and B ⊆ C, then A ⊆ C.

*Proof:*

- Since this is an “if…then…” statement, we can assume “If A ⊆ B and B ⊆ C” is true, so we have to prove “then A ⊆ C” is true.
- We can break down the conclusion further to another “if…then…” statement to: “If x ∈ A, then x ∈ C”, and for the same reasoning as step 1, we only need to focus on proving that “x ∈ C”
- Combine assumptions! We can combine “A ⊆ B” and “x ∈ A” to get the assumption that “x must be an element of B” as well. So now we can take that new assumption and combine it with B ⊆ C to understand that “x must be an element of C” must be true as well!
- BOOM GOES THE DYNAMITE.

Theorem 2.3: If U ⊆ W, then P(U) ⊆ P(W)

*Proof:*

- Just like before, we can assume that “U ⊆ W” is true, as well as x ∈ P(U). We just need to prove that x ∈ P(W).
- The definition of a “power set” proves that x ⊆ U.
- Since we just did the previous proof of: “If A ⊆ B and B ⊆ C, then A ⊆ C. ” we can use it here! Since x ⊆ U and U⊆ W, x ⊆ W.
- Since x is a subset of W, that means that T is an element of P(W)
- BOOM GOES THE DYNAMITE.

**Get Your Hands Dirty 1**

Prove that: If A ⊆ B and C ⊆ D, then A ∩ B ⊆ B ∩ D.

Theorem 2.4: For any sets A and B:

i. (A ∪ B)’ = A’ ∩ B’

ii. (A ∩ B)’ = A’ ∪ B’

*Proof (i):*

- We need to show that (A ∪ B)’ ⊆ A’ ∩ B’ and A’ ∩ B’ ⊆ (A ∪ B)’.
- First of all we need to assume that x ∈ (A ∪ B)’. Because of the definition of union, x is not an element of A or B. And x is not an element of A ∪ B. SO, (A ∪ B)’ ⊆ A’ ∩ B’.
- Assume x ∈ A’ ∩ B’. This means that x is not an element of A’, or an element of B’. But because of this statement, x is also an element of (A ∩ B)’. SO, A’ ∩ B’ ⊆ (A ∪ B)’.

**Get Your Hands Dirty 2**

Convince yourself of the following facts.

For any sets A and B:

A. (A’)’ = A.

A’ means that you are speaking of all the elements not in A. If you were to talk about the elements that are not the elements that are not in A, you would be talking about the elements in A, due to double negation.

B. A ∪ B = B ∪ A

This still gives the same exact information..nothing is added or taken away when A and B are switched.

C. A ∩ B = B ∩ A

See B.

Theorem 2.5:** **If A ⊆ B and C ⊆ D, then A x C ⊆ B x D.

**Get Your Hands Dirty 3**

Choose specific sets for A, B, C and D which fit the hypothesis and look at the theorem with these sets incorporated.

A = {2,4}

B = {1,2,3,4}

C = {1,3}

D = {1,2,3}

If {2,4} ⊆ {1,2,3,4} and {1,3} ⊆ {1,2,3}, then {(2,1),(2,3), (4,1), (4,3)} ⊆ {(1,1),(1,2),(1,3),**(2,1)**,(2,2),**(2,3),**(3,1),(3,2),(3,3),**(4,1)**,(4,2),**(4,3)**}. TRUE!

*Proof:*

- Need to focus on A x C ⊆ B x D.
- w ∈ A x C; w = (x.y) for some x ∈ A and y ∈ C.
- x ∈ A and A ⊆ B, so x ∈ B.
- y ∈ C and C ⊆ D, so y ∈ D.
- SO, (x,y) ∈ B x D.
- BOOM GOES THE DYNAMITE.

Theorem 2.6: If A x B ⊆ A x C and A ≠∅, then B ⊆ C.

*Proof:*

- Assume that A x B ⊆ A x C and A ≠∅. Focus on showing that B ⊆ C is true.
- Assume that x ∈ B, then x ∈ C.
- Since A cannot equal the empty set, it has to have some sort of element in it: t.
- (t, x) ∈ A x B, and since A x B ⊆ A x C AND (t,x) ∈ A x C, and x ∈ C, so we’re all good!
- BOOM GOES THE DYNAMITE.

Theorem 2.8: Suppose X, Y, and Z are sets such that:

i. X ∩ Y = X ∩ Z and

ii. X’ ∩ Y = X’ ∩ Z

*Proof:*

- Assume that X, Y, and Z are sets satisfying i and ii.
- To prove that Y = Z, we need to prove that Y ⊆ Z and Z ⊆ Y.
- Supposed c ∈ Y. we need to show that c ∈ Z. Two things can happen:
- Case 1: c ∈ X. c ∈ X ∩ Y. by i, c ∈ X ∩ Z, SO c ∈ Z.
- Case 2: c ∉ X, which means that c ∈ X’, so c is in X’ ∩ Y. by ii, c ∈ X’ ∩ Z, so c ∈ Z.
- Either way, c ∈ Z!
- BOOM GOES THE DYNAMITE.

**Get Yours Hands Dirty 5 **

Prove the following:

For any sets A, B, and C:

A. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)