Module 1.

The Set Theory

In this module, you are expected to attain the following learning outcomes:
1. Discuss the concept of set.
2. Indicate sets by the description method, roster method, and by using set
builder notation.
3. Properly use notation for element, subset, and proper subset.
4. Determine if sets are equal, equivalent, or neither.
5. Discuss the algebra of sets, special sets and ordered pairs
6. Discuss Cartesian products, relations, functions and partitions.

It is common practice in mathematics today to categorize the various entities we

encounter such as numbers, functions, matrices, vectors etc. into groupings known as
sets. So what exactly is a set? How do we determine set membership? Can we form new
sets from old ones?

In this first module, you will get to understand operations between, relations
among, and statements about sets. This study of Set theory is important mainly because
it serves as a foundation for the rest of mathematics--it provides the axioms from which
the rest of mathematics is built up.

A. Sets, Functions and Relations

The Concept of Set

A set is a collection of objects or symbols. The objects in a set is called elements

of the set. Sets are usually described using "{ }" and inside these curly brackets a list of
the elements or a description of the elements of the set.

Example.

{1, 2, 3, 4, 5 } - set of counting numbers 1, 2, 3, 4 and 5. (finite set)

{ 𝑥 | 𝑥 is a real number } - (infinite set)

If 𝒂 is an element of a set A, we use the notation 𝒂 ∈ 𝐀 and say "a in A" or “a an

element of A". The notation 𝒂 ∉ 𝐀 indicates that “a is not an element of A” and is often
read "a is not in A".
 Some Basic Notations and Definition in Sets

∈ Belongs to
∉ Does not belongs to
: or | Such that
∅ Null set or empty set
n(A) Cardinal number of the set A
∪ Union of two sets
∩ Intersection of two sets
N Set of natural numbers = {1, 2, 3, ……}
W Set of whole numbers = {0, 1, 2, 3, ………}
I or Z Set of integers = {………, -2, -1, 0, 1, 2, ………}
Z+ Set of all positive integers
Q Set of all rational numbers
Q+ Set of all positive rational numbers
R Set of all real numbers
R+ Set of all positive real numbers
C Set of all complex numbers

These are the different notations in sets generally required while solving various
types of problems on sets.

Note:

a. The pair of curly braces { } denotes a set. The elements of set are written inside
a pair of curly braces separated by commas.

b. The set is always represented by a capital letter such as; A, B, C, …….. .

c. If the elements of the sets are alphabets then these elements are written in small
letters.

d. The elements of a set may be written in any order.

e. The elements of a set must not be repeated.

f. The Greek letter Epsilon ‘∈’ is used for the words ‘belongs to’, ‘is an element of’,
etc.

g. The symbol ‘∉’ stands for ‘does not belongs to’ also for ‘is not an element of’.
B. Subsets, Equality of Sets, Power Set and Empty Set
C. Algebra of Sets

Set Operations
The fundamental laws of set algebra

The binary operations of set union and intersection satisfy many identities. Three
pairs of laws are stated in the following proposition.

PROPOSITION 1: For any sets A, B, and C, the following identities hold:

Commutative laws:
 A∪B = B∪A
 A∩B = B∩A

Associative laws:
 (A ∪ B ) ∪ C = A ∪ (B ∪ C )
 (A ∩ B ) ∩ C = A ∩ (B ∩ C )

Distributive laws:
 A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C )
 A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
PROPOSITION 2: For any subset A of universal set U, the following identities hold:

Identity laws:
 A∪∅ = A
 A∩U = A

Complement laws:
 A ∪ A′ = U
 A ∩ A′ = ∅

PROPOSITION 3: For any subsets A and B of a universal set U, the following identities
hold:
Idempotent laws:
 A∪A = A
 A∩A = A

Domination laws:
 A∪U = U
 A∩∅ = ∅

Absorption laws:
 A ∪ (A ∩ B ) = A
 A ∩ (A ∪ B ) = A

PROPOSITION 4: Let A and B be subsets of a universe U, then:

De Morgan's laws:
 (A ∪ B )′ = A′ ∩ B′
 (A ∩ B )′ = A′ ∪ B′

Double complement or Involution law:

 A′′ = A

Complement laws for the universal set and the empty set:
 ∅′ = U
 U′ = ∅

PROPOSITION 5: Let A and B be subsets of a universe U, then, uniqueness of

complements:
 If A ∪ B = U, and A ∩ B = ∅ then B = A′.

PROPOSITION 6: If A, B and C are sets then the following hold:

Reflexivity:
 A⊆A
Antisymmetry:
 A ⊆ B and B ⊆ A if and only if A = B
Transitivity:
 If A ⊆ B and B ⊆ C then A ⊆ C
PROPOSITION 7: If A, B and C are subsets of a set S then the following hold:

Existence of a least element and a greatest element:

 ∅⊆A⊆S

Existence of joins:
 A ⊆ A∪B
 If A ⊆ C and B ⊆ C then A∪B ⊆ C

Existence of meets:
 A∩B ⊆ A
 If C ⊆ A and C ⊆ B then C ⊆ A∩B

PROPOSITION 8: For any two sets A and B, the following are equivalent:
 A⊆B
 A∩B = A
 A∪B = B
 A−B = ∅
 B′ ⊆ A′
PROPOSITION 9: For any universe U and subsets A, B, and C of U, the following
identities hold:
 C − (A ∩ B ) = (C − A ) ∪ (C − B )
 C − (A ∪ B ) = (C − A ) ∩ (C − B )
 C − (B − A ) = (A ∩ C ) ∪ (C − B )
 (B − A ) ∩ C = (B ∩ C ) − A = B ∩ (C − A )
 (B − A ) ∪ C = (B ∪ C ) − (A − C )
 A−A = ∅
 ∅−A = ∅
 A−∅ = A
 B − A = A' ∩ B
 (B − A )' = A ∪ B′
 U − A = A′
 A−U = ∅

D. Ordered Pairs and Relations

An ordered pair (a; b) is a mathematical object comprised of two objects a and b

belonging to sets A and B respectively. The order in which the element is written is crucial
and we define equality on ordered pairs as follows:
Properties of Cartesian Products

NOTATION: At this point, it is worthwhile to introduce new notation. The symbols below
will be used informally in arguments as a way of simplifying notation and making our
proofs and definitions neater. At some point, we will introduce more formal logic and
certain symbols will have a more precise meaning at that time.

 The universal quantifier: ∀ = "for all".

 The existential quantifier: ∃ = "there is" or "exists".

Operations and Properties of Relations

Definition. (Composite Relations). Let R be a relation from A to B and let S be a
relation from B to C. The composite of R and S is

Definition. (Inverse relation) Given a relation R from A to B we define the inverse

relation R−1 to be the relation from B to A defined by

Equivalence Relations and Partitions

Definition. (Equivalence Relation) Let A be a set and let R be a relation on A. We

say that R is an equivalence relation if R is
E. Functions
 Viewing the function this way, it becomes very clear that a function is given by
THREE pieces of information: The domain, the range, and the assignment between the
two.

Examples:
 Problem Set 1
Problem Set 1

1. Write each of the following sets by listing its elements explicitly.

2. Assume U=Z , and let

A={…,−6,−4,−2,0,2,4,6,…}= 2Z,
B={…,−9,−6,−3,0,3,6,9,…}= 3Z,
C={…,−12,−8,−4,0,4,8,12,…}= 4Z.

Describe the following sets by listing their elements explicitly.

3. An insurance company classifies its set U of policy holders by the following sets:
A = {x ∣x drives a subcompact car},
B = {x ∣x drives a car older than 5 years},
C = {x ∣x is married},
D = {x ∣x is over 21 years old},
E = {x ∣x is a male}.

Describe each of the following subsets of U in terms of A, B, C, D, and E.

(a) Male policy holders over 21 years old.

(b) Policy holders who are either female or drive cars more than 5 years old.
(c) Female policy holders over 21 years old who drive subcompact cars.
(d) Male policy holders who are either married or over 21 years old and do not drive
subcompact cars.

3. Let A, B, and C be any three sets. Prove that if A ⊆ C and B ⊆ C, then A ∪ B ⊆ C.

4. Let A, B, and C be any three sets. Prove that

(a) A – B = A ∩ B’
(b) A = (A − B) ∪ (A ∩ B)
(c) A − (B − C) = A ∩ (B’ ∪ C)
(d) (A − B) – C = A − (B ∪ C)

5. Let A={x ∈ R | x2 < 4} and let B={ x ∈ R | x < 2}

(a) Is A ⊆ B ? Justify your conclusion with a proof or a counterexample.

(b) Is B ⊆ A ? Justify your conclusion with a proof or a counterexample.
 Problem Set 2

1. Let A = {1, 2}, B = {a, b, c, d}, and C = {1, a, b}. Use the roster method to list all of
the elements of each of the following sets:
(a) A × B
(b) B × A
(c) A × C
(d) A2
(e) A × (B ∩ C)
(f) (A × B) ∩ (A × C)
(g) A × ∅
(h) B × {2}

2. Let A= {1}, B= {2}, and C= {3}.

(a) Explain why A × B ≠ B × A
(b) Explain why (A×B) × C ≠ A × (B × C)

3. Let A and B be nonempty sets. Prove that A × B = B × A if and only if A = B.

4.

5. Show that if F : X → Y is a bijection, then F-1 : Y → X is a bijection.

References

McMillan, Jack F. (2007). Lecture Notes on Set Theory and Point-Set Topology. Hawaii
Pacific University, College of Natural and Computational Sciences

[Link]

[Link]
/[Link]

[Link]

[Link]