CMSC 250: Set Theory and Proofs

Justin Wyss-Gallifent

March 13, 2023

1 Sets and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Set Notation Types . . . . . . . . . . . . . . . . . . . . . 2
2 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Subsets and Proper Subsets . . . . . . . . . . . . . . . . . 3
2.2 Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Combining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Intersection and Disjoint Sets . . . . . . . . . . . . . . . . 5
3.3 Complements . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.4 Subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 Venn Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6 Power Sets and Cartesian Products . . . . . . . . . . . . . . . . . 10
6.1 Power Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2 Cartesian Products . . . . . . . . . . . . . . . . . . . . . . 11
7 Cardinality and Countability . . . . . . . . . . . . . . . . . . . . 11
8 Set Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
9 Set Theory Proofs (and Disproofs) . . . . . . . . . . . . . . . . . 15
9.1 What Might We Prove (or Disprove)? . . . . . . . . . . . 15
9.2 Proving or Disproving a Subset . . . . . . . . . . . . . . . 15
9.3 Proving or Disproving Equality . . . . . . . . . . . . . . . 18
9.4 Proving A = ∅ . . . . . . . . . . . . . . . . . . . . . . . . 21
9.5 Proving Conditionals Related to Sets . . . . . . . . . . . . 22

1
1 Sets and Notation
1.1 Basic Definitions
Definition 1.1.1. A set is a collection of (perhaps no) objects, or elements.
What those elements are is entirely irrelevant to the definition. Think of a set
as a box which contains (perhaps no) things.

There is no repetition in a set, meaning each element must be unique. You
could, for example, have variations on an element, such as a regular number 4
and a boldface number 4.
There is no order in a set; in other words order does not matter.

1.2 Set Notation Types

There are several ways to denote the elements in a set. Some sets have specific
notations because they arise so frequently. We have seen Z, R, Q, 2Z and so on.
Definition 1.2.1. We say that x is an element of/in a set A, written x ∈ A,
if it belongs in the set. We write x 6∈ A if not.


Example 1.1. For example 3 ∈ Z and 3.4 6∈ Z.


We can also explicitly list the elements in a set using {} notation.

Example 1.2. Here are a few:

• {1, 2, 3, 4} contains four things, the numbers 1,2,3, and 4.
• {primes} contains all the primes.


Definition 1.2.2. The empty set is denoted by {} or ∅ and contains nothing.
It is an empty box.

Note 1.2.1. Note that {∅} is not the empty set, rater it is a set containing one
thing, that thing is the empty set! Think of it as a box containing an empty
box.

We also have notation for sets which comes from calculus using interval notation.

2
 Example 1.3. The set [1, 2] contains all real number from 1 to 2 inclusive.
Note that this is very different than the set {1, 2} which contains just the
integers 1 and 2.


Lastly we can use set-builder notation to build sets:
Definition 1.2.3. A set is defined using set-builder notation using the notation:

{element(s) | conditions on element(s)}

The vertical bar is usually read as “such that”.



Example 1.4. Here are some examples:

• {x | x ∈ Z ∧ 3 | x} is the set of integers which are multiples of 3.
• {x | x ∈ {people} ∧ x is over 6ft tall} is the set of people over 6 feet
tall.
• {a | a ∈ Z ∧ ((a ≡ 1 mod 10) ∨ (a ≡ 3 mod 10))}


It’s not infrequent that when the elements are taken from a set that this fact is
made clear before the vertical bar:

Example 1.5. For example:

{x | x ∈ Z ∧ 3 | x} = {x ∈ Z | (3 | x)}


Also it’s not infrequent that an expression is used on the left.

Example 1.6. For example the odd numbers can be written as {2k + 1 | k ∈
Z}.

2 Comparison
2.1 Subsets and Proper Subsets
Definition 2.1.1. Given sets A and B we say that A is a subset of B, written
A ⊆ B, if every element in A is also in B. In other words:

A ⊆ B ←→ ∀x, (x ∈ A → x ∈ B)

3
 

Example 2.1. For example {1, 2, 3, 4} ⊆ Z and Z ⊆ R.


Definition 2.1.2. Given sets A and B we say that A is a proper subset of B,
written A ⊂ B or A ( B, if every element in A is also in B but B has more. In
other words:
A ( B ←→ (∀x, (x ∈ A → x ∈ B) ∧ (∃y ∈ B, y 6∈ A))

Example 2.2. For example {1, 2, 3, 4} ( Z and Z ( R.


Note 2.1.1. Observe that:
A = B ←→ (A ⊆ B ∧ B ⊆ A)

2.2 Equality
Definition 2.2.1. We say that two sets A and B are equal and write A = B
if they have exactly the same elements. More specifically A = B iff A ⊆ B and
B ⊆ A.


Example 2.3. For example {x ∈ Z | (3|x)} = 3Z.

3 Combining
3.1 Union
Definition 3.1.1. Given sets A and B we define the union of A and B, denoted
A ∪ B to be the set of elements with are in A or in B or in both. In other words:

A ∪ B = {x | x ∈ A ∨ x ∈ B}

Thus:

x ∈ A ∪ B ←→ x ∈ A ∨ x ∈ B

4
 

Example 3.1. If A = {1, 2, 3, 4, 5} and B = {4, 5, 6, 7, 8} then A ∪ B =

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

3.2 Intersection and Disjoint Sets

Definition 3.2.1. Given sets A and B we define the intersection of A and B,
denoted A ∩ B to be the set of elements with are in both A and B. In other
words:

A ∩ B = {x | x ∈ A ∧ x ∈ B}

Thus:

x ∈ A ∩ B ←→ x ∈ A ∧ x ∈ B

Example 3.2. If A = {1, 2, 3, 4, 5} and B = {4, 5, 6, 7, 8} then A ∩ B =

{4, 5}.


Definition 3.2.2. We say sets are disjoint if A ∩ B = ∅. This means they have
nothing in common!


Example 3.3. The sets A = {1, 2, 3, 4, 5} and B = {4, 5, 6, 7, 8} are not

disjoint but the sets A = {1, 2, 3} and B = {4, 5, 6} are.

3.3 Complements
In order to define the notion of things “not in” a set we have to have a sense of
a universal set.
Definition 3.3.1. In a given problem or situation the universal set, denoted U ,
generally denotes a large set for which everything else is taken to be a subset.


5
 Example 3.4. When working with sets of integers we would take U = Z
whereas when working with sets of reals we would take U = R.


Definition 3.3.2. Suppose A ⊆ U . Then we define the complement of A,
denoted Ac or A0 , to be the set of things in U but not in A. That is:

Ac = A0 = {x ∈ U | x 6∈ A}

Thus:

x ∈ Ac ←→ x 6∈ A

Example 3.5. If U = Z and A = 2Z then Ac = {2k + 1 | k ∈ Z}.

3.4 Subtraction
Lastly we define set subtraction.
Definition 3.4.1. If A and B are sets then we define the set A − B to be the
set of things in A but not in B. Note that B doesn’t need to be a subset of A
for this to make sense. That is:

A − B = {x | (x ∈ A) ∧ (x 6∈ B)}

The notation A \ B is also used but is going out of fashion.

Thus:

x ∈ A − B ←→ (x ∈ A) ∧ (x 6∈ B)

Example 3.6. If A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7} then A − B =

{1, 2} and B − A = {6, 7}.


c 0
Note 3.4.1. Note that A = A = U − A.


6
4 Venn Diagrams
Useful for visualizing all of the above and for a good intuitive understanding of
when things are true and not true. In a Venn diagram we start with a rectangle
that indicates the universal set and typically another two sets A and B:

A B

Then we can shade various regions:

Example 4.1. Here is A shaded:

A B

Example 4.2. Here is A ∩ B shaded:

A B

Example 4.3. Here is A ∪ B shaded:

7
 A B

Example 4.4. Here is Ac shaded:

A B

Example 4.5. Here is A − B shaded:

A B


And lastly:

Example 4.6. Here is Ac ∩ B c = (A ∪ B)c shaded:

8
 A B


We can do the same with three sets.

Example 4.7. Here is A − B − C shaded:

A B

5 Partitions
Definition 5.0.1. A partition of a set A is a choice of dividing the elements
of A into pairwise disjoint nonempty subsets whose union is A. This sounds
complicated but it just means we’re dividing up the elements of A in some way.
Technically speaking a partition is a set of subsets.


Example 5.1. Suppose A = {1, 2, 3, 4, 5}. Here are some partitions of A:

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

9
 The following are not partitions of A:
• {{1, 2}, {3, 5}}
• {{1, 2, 3, 4, 5}, ∅}
• {{1, 2, 3}, {3, 4, 5}}
• {1, 2, 3, 4, 5}

6 Power Sets and Cartesian Products

These are useful ways of building new sets out of old sets.

6.1 Power Sets

Definition 6.1.1. For a set A, the power set of A, denoted P(A), is the set of
all subsets of A.


Example 6.1. If A = {1, 2} then P(A) = {∅, {1}, {2}, {1, 2}}


Power sets can get pretty big.

Example 6.2. If A = {1, 2, 3, 4} then P(A) contains 16 elements. Do you

see why?


n
Theorem 6.1.1. If A has n elements then P(A) has 2 elements.
—

Proof. When constructing a subset of A we can choose whether or not to put

each element of A in that subset. We then make a binary choice n times for 2n
total possibilities. If this doesn’t make complete sense right now it will make
more sense when we get to combinatorics. QED


Power sets can be pretty confusing.

Example 6.3. We have:

• P(∅) = {∅}

10
 • P({∅}) = {∅, {∅}}


Fun fact - power sets of the empty sets are one way that the nonnegative integers
can be constructed from scratch!

P(A) = {S | S ⊆ A}

6.2 Cartesian Products

Definition 6.2.1. If A and B are sets then we define the cartesian product
A × B as:
A × B = {(a, b) | a ∈ A ∧ b ∈ B}

Example 6.4. If A = {1, 2} and B = {α, β} then:

A × B = {(1, α), (1, β), (2, α), (2, β)}

Example 6.5. Note that in mathematics we have the cartesian plane which
is just the set of points (x, y). Formally this is R × R and is usually denoted
R2 .

7 Cardinality and Countability

When studying sets it’s useful to ask about how many things are in the set.
Definition 7.0.1. The cardinality of a set A, denoted |A|, loosely speaking, is
the number of elements in a set.

There is lots of formal structure to the study of cardinality but we will broadly
break the cardinality of sets down first into two types and then one of those
types will be broken down further.
The first division will be whether a set has finitely or infinitely many elements.
If it is finite we can just give the number of elements.

Example 7.1. We have:

• |{1, 3, 5, 7}| = 4

11
 • We have |Z| infinite
• We have |R| infinite.

However the term “infinite” is vague and we will break it down further. We’ll
start by looking at two sets: Z+ and R.
Observe that the set Z+ of positive integers may be listed one-by-one:

1, 2, 3, 4, 5, ...

It’s not clear how we would do this with the set R:

0.1, π, −45, 56.58, ...?????

It turns out that these two sets have different sizes in a meaningful way. In
order to formalize this we have the following definition:
Definition 7.0.2. We say that a set A is countable if we can match the element
in 1-1 correspondance with Z+ . Essentially this means we can choose a starting
element and list all elements in a manner which does not miss any.

Definition 7.0.3. We say that a set A is uncountable if it is not countable.


Example 7.2. The set of positive even integers is countable. Here they are:

2, 4, 6, 8, ...

Formally the 1-1 matching is:

Z+ Positive Evens
1 ↔ 2
2 ↔ 4
3 ↔ 6
4 ↔ 8
.. .. ..
. . .

Example 7.3. The set of all integers is countable. Here they are:

0, 1, −1, 2, −2, 3, −3, 4, −4, ...

Formally the 1-1 matching is:

12
 Z+ Z
1 ↔ 0
2 ↔ 1
3 ↔ -1
4 ↔ 2
5 ↔ -2
6 ↔ 3
.. .. ..
. . .


It is not clear right now whether we can or cannot do this with R but before we
try, let’s look at Q+ , the set of positive rational numbers.
Theorem 7.0.1. The positive rationals are countable.

Proof. Observe that we can put all the positive rational numbers in an infinite
table with the numerators n running across the top and the denominators d
down the left edge:

n/d 1 2 3 4 ...
1 1/1 2/1 3/1 4/1 ...
2 1/2 2/2 3/2 4/2 ...
3 1/3 2/3 3/3 4/3 ...
4 1/4 2/4 3/4 4/4 ...
5 1/5 2/5 3/5 4/5 ...
.. .. .. .. .. ..
. . . . . .

Note that there are repeats, for example 1/1 shows up as 2/2 and 1/2 shows up
as 2/4 and so on.
Here’s the fun part. We can use this table to generate a list of all of these
numbers. There are various ways to do this but here is one:
Let’s create a path through the table:
(i) Start in the top left: 1/1
(ii) Go down one: 1/1, 1/2
(iii) Go along the diagonal going up and right: 1/1, 1/2, 2/1
(iv) Go right one: 1/1, 1/2, 2/1, 3/1
(v) Go along the diagonal going down and left: 1/1, 1/2, 2/1, 3/1, 2/2, 1/3
(vi) Repeat from (ii).
This path hits everything in the table:

1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, 5/1, 4/2, 3/3, 2/4, 1/5, ...

13
Now then, following this path, simply skip rationals that have previously been
hit. This creates a list of all the positive rationals!

1/1, 1/2, 2/1, 3/1, 1/3, 1/4, 2/3, 3/2, 4/1, 5/1, 1/5, ...
QED


Okay, now let’s go back to R. We won’t even look at all of them, let’s just look
at the reals in the interval [0, 1].
Theorem 7.0.2. The set [0, 1] is uncountable.

Proof. We proceed by induction. Assume we have a correspondance with Z+ .

Since each real number is a 0 followed by a string of decimal digits we can
write our correspondance as follows. Let’s assume we never run out of alphabet
letters!

Z+ Z
1 ↔ 0.a1 a2 a3 a4 a5 . . .
2 ↔ 0.b1 b2 b3 b4 b5 . . .
3 ↔ 0.c1 c2 c3 c4 c5 . . .
4 ↔ 0.d1 d2 d3 d4 d5 . . .
5 ↔ 0.e1 e2 e3 e4 e5 . . .
.. .. ..
. . .

Remember, we are assuming that every real number in [0, 1] is in this list!
Consider the new real number built as follows:
0.α1 α2 α3 α4 α5 . . .
where we insist that:
• α1 6= a1 , so this new number is not the first number in the list.
• α2 6= b2 , so this new number is not the second number in the list.
• α3 6= b3 , so this new number is not the third number in the list.
• α4 6= b4 , so this new number is not the fourth number in the list.
• α5 6= b5 , so this new number is not the fifth number in the list.
• ...etc...
Clearly this real number should be in the list by assumption, since the list is
assumed to contain all of [0, 1].
But this real number differs by the k th number at the k th digit, so it is not one
of the numbers in the list.
This is a contradiction and we are done. QED

14
 

8 Set Identities
Much like the logical equivalences there are set identities which arise frequently
and can be proved using the definitions. We have the following set identities.
Some of them look similar to logical equivalences!

Commutative A ∪ B = B∪ and A ∩ B = B ∩ A
Associative A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C
Distributive A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Identity A ∪ ∅ = A and A ∩ U = A
Complement A ∪ Ac = U and A ∩ Ac = ∅
Double Complement (Ac )c = A
Idempotent A ∪ A = A and A ∩ A = A
Universal Bound A ∪ U = U and A ∩ ∅ = ∅
DeMorgan’s (A ∩ B)c = Ac ∪ B c and (A ∪ B)c = Ac ∩ B c
Absorption A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A
Complement of ∅ and U U c = ∅ and ∅c = U
Set Difference A − B = A ∩ Bc
Later on we will discuss proving things with sets and we will be able to revisit
these and prove them.

9 Set Theory Proofs (and Disproofs)

9.1 What Might We Prove (or Disprove)?
First of all we should note that our set-related proofs will fall into one of two
categories:
(a) Proving: For all sets A, B, ... some fact is true. Since this is a proof of a
universal we will start with unknown sets A, B, ... and go from there.
(b) Disproving: For all sets A, B, ... some fact is true. This disproof of a uni-
versal becomes a proof of the negation which then involves finding explicit
sets A, B, ... for which the statement is false.

9.2 Proving or Disproving a Subset

Consider this example:

Example 9.1. Let’s prove half of the set difference law A − B = A ∩ B c .

Specifically let’s prove that:
For all sets A and B we have A − B ⊆ A ∩ B c .

15
 
Before proceeding note that we want to prove ⊆ so recall the definition. Here
I’ve abstracted using S1 and S2 for the two sets:
S1 ⊆ S2 means ∀x, x ∈ S1 → x ∈ S2
We therefore start with some arbitrary x ∈ S1 and show it is in S2 . Back to our
example:

Example 9.2. We want to prove that:

For all sets A and B we have A − B ⊆ A ∩ B c .
Proof:
We start with some arbitrary x ∈ A − B.
We wish to prove that x ∈ A ∩ B c .
Since x ∈ A − B we know that x ∈ A and x 6∈ B by the definition of A − B.
Since x 6∈ B we know x ∈ B c .
Then since x ∈ A and x ∈ B c we know x ∈ a ∩ B c .


When disproving the subset property we look for a counterexample. A Venn
diagram can help us but an explicit example is the final goal.

Example 9.3. Let’s disprove:

For all sets A and B we have A ∪ B ⊆ Ac ∪ B.
Let’s draw Venn Diagrams of the left and right sides. Here is A ∪ B:

A B

Here is Ac ∪ B:

16
 A B

Clearly we see:

A B A B

6⊆

But we should give an explicit example. We can draw another Venn Diagram
and put some numbers in the various areas:

A B

1 3 2

So here is our actual (dis)proof:

(Dis)proof:
We assign:
U = {1, 2, 3, 4}
A = {1, 3}
B = {2, 3}
Then we have
A ∪ B = {1, 2, 3}
Ac ∪ B = {2, 3, 4}
And then A ∪ B 6⊆ Ac ∪ B.

17
9.3 Proving or Disproving Equality
When proving set equality we use the fact that:

S1 = S2 ←→ (S1 ⊆ S2 ) ∧ (S2 ⊆ S1 )

So we simply prove both of these. Specifically we prove:

∀x, x ∈ S1 → x ∈ S2
and
∀x, x ∈ S2 → x ∈ S1

Example 9.4. Let’s prove the absorption law. Specifically let’s prove that:
For all sets A and B, we have A ∪ (A ∩ B) = A.
Proof:
• First we prove that A ∪ (A ∩ B) ⊆ A.
To do this, start with some x ∈ A ∪ (A ∩ B).
We wish to prove that x ∈ A.
We know that either x ∈ A or x ∈ A ∩ B.
If x ∈ A then we are done.
If x ∈ A ∩ B then x ∈ A and we are done.
• Second we prove that A ⊆ A ∪ (A ∩ B).
To do this, start with some x ∈ A.
We wish to prove that x ∈ A ∪ (A ∩ B), however this is immediate
since x ∈ A.


Note 9.3.1. Note that we’re using cases in the first bullet point. Remember
cases:
p∨q
p→r
q→r
∴ r
Do you see how? Cases emerge when our hypothesis breaks into two (or more)
possibilities and we show that each of those leads to exactly the same conclusion.
Look at it this way. We proved that:
(x ∈ A) ∨ (x ∈ A ∩ B)
(x ∈ A) → (x ∈ A)
(x ∈ A ∩ B) → (x ∈ A)
∴ (x ∈ A)

18
 

Example 9.5. Let’s prove one of the DeMorgan’s Laws. Specifically let’s
prove that:
For all sets A and B we have (A ∩ B)c = Ac ∪ B c .
Proof:
• First we prove that (A ∩ B)c ⊆ Ac ∪ B c .
To do this, start with some x ∈ (A ∩ B)c .
We wish to prove that A ∈ Ac ∪ B c .
Since x ∈ (A ∩ B)c this means x 6∈ A ∩ B which then means either
x 6∈ A or x 6∈ B (or both).
If x 6∈ A then x ∈ Ac and then x ∈ Ac ∪ B c .
if x 6∈ B then x ∈ B c and then x ∈ Ac ∪ B c .
• Second we prove that Ac ∪ B c ⊆ (A ∩ B)c . To do this, start with some
x ∈ Ac ∪ B c .
We wish to prove that x ∈ (A ∩ B)c .
Since x ∈ Ac ∪ B c we know either x ∈ Ac or x ∈ B c (or both).
If x ∈ Ac then x 6∈ A and then x 6∈ A ∩ B and then A ∈ (A ∩ B)c .
If x ∈ B c then x 6∈ B and then x 6∈ A ∩ B and then A ∈ (A ∩ B)c .


When disproving set equality we look for a counterexample. That counterex-
ample only needs to violate one of the two subset statements! A Venn diagram
can help us but an explicit example is the final goal.

Example 9.6. Let’s disprove:

For all sets A, B, and C we have A ∪ (C − B) = (A ∪ C) − B.
Let’s draw Venn Diagrams of the left and right sides. Here is A ∪ (C − B):

19
 A B

Here is (A ∪ C) − B:

A B

Clearly we see:

A B A B

6=

C C

Specifically A ∪ (C − B) 6⊆ (A ∪ C) − B.
But we should give an explicit example. We can draw another Venn Diagram
and put some numbers in the various areas:

20
 A B

4
1 2
7
5 6

C
8

So here is our actual (dis)proof:

(Dis)proof:
We assign:
U = {1, 2, 3, 4, 5, 6, 7, 8}
A = {1, 4, 5, 7}
B = {2, 4, 6, 7}
C = {3, 5, 6, 7}
Then we have
A ∪ (C − B) = {1, 3, 4, 5, 7}
(A ∪ C) − B = {1, 3, 5}
And then A ∪ (C − B) 6= (A ∪ C) − B.

9.4 Proving A = ∅
When proving A = ∅ we proceed differently because the logic above doesn’t
apply.
Instead, we prove this by contradiction - we assume that there is something in
A and find a contradiction.

Example 9.7. Let’s prove that:

For any set A that A ∩ ∅ = ∅.
Suppose not, so that there is some x ∈ A ∩ ∅. Then we know x ∈ A and
x ∈ ∅. But the second of these is impossible and we have our contradiction.

21
9.5 Proving Conditionals Related to Sets
When we are proving conditionals related to sets we have to start pulling several
things together.

Example 9.8. Let’s prove that:

For all sets A, B, and C, if A ⊆ B and B ⊆ C c , then A ∩ C = ∅.
Proof:
This is a for all statement so we start with unknown sets A, B, and C and
we assume the hypotheses, that A ⊆ B and B ⊆ C c .
We then claim that A ∩ C = ∅.
To prove A ∩ C = ∅ we proceed by contradiction and assume x ∈ A ∩ C.
Since x ∈ A ∩ C we know that x ∈ A and x ∈ C.
Since x ∈ A and A ⊆ B and B ⊆ C c we know x ∈ C c .
However then x ∈ C and x ∈ C c and this is a contradiction.

22