CHAPTER 1
SETS
What is a Set?
A set is a well-defined collection of
distinct objects.
The objects in a set are called the
elements or members of the set.
Capital letters A,B,C,… usually
denote sets.
Lowercase letters a,b,c,… denote
the elements of a set.
Examples
The collection of the vowels in the word
“probability”.
The collection of real numbers that
satisfy the equation x 2 9 0.
The collection of two-digit positive
integers divisible by 5.
The collection of great football players in
the National Football League.
The collection of intelligent members of
the United States Congress.
The Empty Set
The set with no elements.
Also called the null set.
Denoted by the symbol f.
Example: The set of real numbers x
that satisfy the equation
x2 1 0
Finite and Infinite Sets
A finite set is one which can be
counted.
Example: The set of two-digit
positive integers has 90 elements.
An infinite set is one which cannot
be counted.
Example: The set of integer
multiples of the number 5.
The Cardinality of a Set
Notation: n(A)
For finite sets A, n(A) is the number
of elements of A.
For infinite sets A, write n(A)=∞.
Specifying a Set
List the elements explicitly, e.g.,
C a, o, i
List the elements implicitly, e.g.,
K 10,15,20,25,....,95
Use set builder notation, e.g.,
Q x x p / q where p and q are integers and q 0
The Universal Set
A set U that includes all of the
elements under consideration in a
particular discussion.
Depends on the context.
Examples: The set of Latin letters,
the set of natural numbers, the set
of points on a line.
The Membership Relation
Let A be a set and let x be some
object.
Notation: x A
Meaning: x is a member of A, or x
is an element of A, or x belongs to
A.
Negated by writing x A
Example: V a, e, i, o, u . e V , b V .
Equality of Sets
Two sets A and B are equal, denoted
A=B, if they have the same elements.
Otherwise, A≠B.
Example: The set A of odd positive
integers is not equal to the set B of prime
numbers.
Example: The set of odd integers between
4 and 8 is equal to the set of prime
numbers between 4 and 8.
Subsets
A is a subset of B if every element of A is
an element of B.
Notation: A B
For each set A, A A
For each set B, Ø B
A is proper subset of B if A B and A B
Unions
The union of two sets A and B is
A B x x A or x B
The word “or” is inclusive.
Intersections
The intersection of A and B is
A B x x A and x B
Example: Let A be the set of even
positive integers and B the set of prime
positive integers. Then
A B {2}
Definition: A and B are disjoint if
A B Ø
Complements
o If A is a subset of the universal set U,
then the complement of A is the set
Ac x U x A
c
o Note: A Ac ; A A U
Venn Diagrams
Set A represented as a disk inside a
rectangular region representing U.
Possible Venn Diagrams
for Two Sets
U U
A B
A B
A B
The Complement of a Set
Ac
A
The shaded region represents the
complement of the set A
The Union of Two Sets
A B
The Intersection of Two Sets
A B
Sets Formed by Two Sets
o R1 A Bc
R2 A B
U
A B
R1
R2
R3 R3 Ac B
R4
R4 Ac Bc
Two Basic Counting Rules
If A and B are finite sets,
1. n( A B ) n( A) n( B ) n( A B)
2. n( A B c ) n( A) n( A B)
See the preceding Venn diagram.
Operations on Sets
Operations on Sets: Union (∪)
Definition: The union of two sets A and B,
denoted A∪B, is the set containing all elements
that are in A, or in B, or in both.
Set-Builder Notation: A∪B={x∣x∈A or x∈B}
Venn Diagram: (Insert a simple Venn Diagram
showing A∪B shaded)
Example:
A={1,2,3}
B={3,4,5}
A∪B={1,2,3,4,5}
Operations on Sets
Operations on Sets: Intersection (∩)
Definition: The intersection of two sets A and B,
denoted A∩B, is the set containing all elements
that are common to both A and B.
Set-Builder Notation: A∩B={x∣x∈A and x∈B}
Venn Diagram: (Insert a simple Venn Diagram
showing A∩B shaded)
Example:
A={1,2,3}
B={3,4,5}
A∩B={3}
Disjoint Sets: If A∩B=∅.
Operations on Sets
Operations on Sets: Difference (− or ∖)
Definition: The difference of set A and set B,
denoted A−B or A∖B, is the set of all elements that
are in A but not in B.
Set-Builder Notation: A−B={x∣x∈A and x∈/B}
Venn Diagram: (Insert a simple Venn Diagram
showing A−B shaded)
Example:
A={1,2,3,4}
B={3,4,5,6}
A−B={1,2}
B−A={5,6} (Note: Difference is not commutative)
Operations on Sets
Operations on Sets: Complement (Ac or A′)
Definition: The complement of a set A, denoted Ac
or A′, relative to a universal set U, is the set of all
elements in U that are not in A.
Set-Builder Notation: Ac={x∣x∈U and x∉A}
Venn Diagram: (Insert a simple Venn Diagram
showing Ac shaded, with U clearly defined)
Example:
U={1,2,3,4,5}
A={1,2,3}
Ac={4,5}
Laws of Set Theory (Set Identities)
Importance: Used to simplify and prove
set expressions, analogous to algebraic
laws.
Commutative Laws:
A∪B=B∪A
A∩B=B∩A
Associative Laws:
(A∪B)∪C=A∪(B∪C)
(A∩B)∩C=A∩(B∩C)
Laws of Set Theory (Cont.)
Distributive Laws:
A∪(B∩C)=(A∪B)∩(A∪C)
A∩(B∪C)=(A∩B)∪(A∩C)
Identity Laws:
A∪∅=A
A∩U=A
Complement Laws:
A∪Ac=U
A∩Ac=∅
Laws of Set Theory (Cont.)
Idempotent Laws:
A∪A=A
A∩A=A
De Morgan's Laws: (Crucial for
negation in logic and computer
science)
(A∪B)c=Ac∩Bc
(A∩B)c=Ac∪Bc
Double Complement Law: (Ac) c=A
Power Sets
Power Sets (P(A) or 2A)
Definition: The power set of a set A is the set
of all possible subsets of A. This includes the
empty set and the set A itself.
Cardinality: If ∣A∣=n, then ∣P(A)∣=2n.
Example 1:
A=∅
P(A)={∅} (size = 20=1)
Example 2:
A={a}
P(A)={∅,{a}} (size = 21=2)
Power Sets
Example 3:
A={1,2}
P(A)={∅,{1},{2},{1,2}} (size = 22=4)
Example 4:
A={a,b,c}
P(A)={∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c
}} (size = 23=8)
Think: Why are power sets important? (Hint:
Combinations, logical possibilities)
Cartesian Products
Cartesian Products (A×B)
Definition: The Cartesian product of two sets A
and B, denoted A×B, is the set of all possible
ordered pairs (a,b) where a∈A and b∈B.
Set-Builder Notation:
A×B={(a,b)∣a∈A and b∈B}
Cardinality: If ∣A∣=m and ∣B∣=n, then
∣A×B∣=m×n.
Example 1:
A={1,2}
B={a,b}
A×B={(1,a),(1,b),(2,a),(2,b)}
Cartesian Products (Cont.)
Example 2: (Order matters!)
B×A={(a,1),(a,2),(b,1),(b,2)}
Note: A×B≠B×A unless A=B or one is empty.
Cartesian Product of Multiple Sets:
A×B×C={(a,b,c)∣a∈A,b∈B,c∈C}
Applications: Coordinates in geometry,
relations, databases.
Partitions of Sets
Definition: A partition of a non-empty set A is
a collection of non-empty subsets of A (called
blocks or cells) such that:
1. Disjointness: The blocks are pairwise disjoint
(Ai∩Aj=∅ for i ≠ j).
2. Completeness: The union of all blocks is the
entire set A (⋃Ai=A).
Intuition: Dividing a set into non-overlapping,
exhaustive sub-groups.
Partitions of Sets (Cont.)
Example 1:
A={1,2,3,4,5}
Partition: {{1,2},{3},{4,5}}
(Verify disjointness and union)
Example 2:
Set of all integers Z
Partition: {Even Integers, Odd Integers}
Connection to Equivalence Relations: Every
equivalence relation on a set induces a partition
of the set, and vice versa.
The Principle of Inclusion and
Exclusion (PIE)
Purpose: A powerful counting technique to find
the size of the union of multiple sets, especially
when there are overlaps.
Why not just add? Simple addition overcounts
elements that belong to more than one set.
Basic Idea: Add the sizes of individual sets,
then subtract the sizes of pairwise intersections
(to correct for overcounting), then add back the
sizes of triple intersections (because they were
subtracted too many times), and so on.
PIE for Two Sets
Formula: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
Venn Diagram: (Illustrate how A∩B is counted
twice in ∣A∣+∣B∣, so it needs to be subtracted
once.)
Example:
In a class, 20 students play Cricket (C) and 15
play Football (F). 8 students play both. How
many students play at least one sport?
∣C∪F∣=∣C∣+∣F∣−∣C∩F∣
∣C∪F∣=20+15−8=27 students.
PIE for Three Sets
PIE for Three Sets
Formula: ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣
−(∣A∩B∣+∣A∩C∣+∣B∩C∣) +∣A∩B∩C∣
Explanation:
Add singles: ∣A∣+∣B∣+∣C∣ (elements in multiple
intersections are overcounted).
Subtract doubles: Corrects for elements
counted two or three times.
Add triples: Corrects for elements in all three
sets that were subtracted three times.
PIE for Three Sets(Example)
Problem: Out of 100 students:
40 study Math (M)
30 study Physics (P)
25 study Chemistry (C)
10 study Math and Physics (M∩P)
8 study Math and Chemistry (M∩C)
7 study Physics and Chemistry (P∩C)
5 study all three (M∩P∩C)
How many students study at least one subject?
Solution: ∣M∪P∪C∣=40+30+25−(10+8+7)+5
=95−25+5=75 students.
