Lecture 5

Sets
Sets
What is a set?
A set is a group of “objects”
People in a class: {Aisha, Hassan, Leeza }
Classes offered by a department: {MAT129, MAT033, … }
States of matter {solid, liquid, gas}
Sets can contain non-related elements: {3, a, red, Male’ }

Although a set can contain (almost) anything, we will most

often use sets of numbers
All positive numbers less than or equal to 5: {1, 2, 3, 4, 5}
A few selected real numbers: {2.1, π, 0, -6.32, e}
Sets

DEFINITION

A set is an unordered collection of objects, called elements or

members of the set. A set is said to contain its elements. We
write a ∈ A to denote that a is an element of the set A. The
notation a ∉ A denotes that a is not an element of the set A.
Sets

It is common for sets to be denoted using uppercase letters.

Lowercase letters are usually used to denote elements of sets.

There are several ways to describe a set.

One way is to list all the members of a set, when this is
possible. We use a notation where all members of the set are
listed between braces.

For example, the notation {a, b, c, d} represents the set with the
four elements a, b, c, and d. This way of describing a set is
known as the roster method.
Sets
Example
The set V of all vowels in the English alphabet can be written as
V = {a, e, i, o, u}.

Example
The set O of odd positive integers less than 10 can be expressed
by O = {1, 3, 5, 7, 9}.

Some members of the set are listed, and then ellipses (. . .) are
used when the general pattern of the elements is obvious.

Example
The set of positive integers less than 100 can be denoted by
{1, 2, 3, . . . , 99}.
Sets
Another way to describe a set is to use set builder notation. We
characterize all those elements in the set by stating the property or
properties they must have to be members.

Example
the set O of all odd positive integers less than 10 can be written
as
O = {x | x is an odd positive integer less than 10}

O = {x ∈ Z+ | x is odd and x < 10}

Sets
These sets, each denoted using a boldface letter, play an important
role in discrete mathematics:

N = {0,1,2,3,...}, the set of natural numbers

Z = {...,−2,−1,0,1,2,...}, the set of integers
Z+ = {1, 2, 3, . . .}, the set of positive integers
Q = {p/q | p ∈ Z, q ∈ Z, and q ≠ 0}, the set of rational numbers
R, the set of real numbers
R+, the set of positive real numbers
C, the set of complex numbers
Sets
The notation for intervals of real numbers. When a and b are real
numbers with a < b, we write

[a, b] = {x | a ≤ x ≤ b}
[a, b) = {x | a ≤ x < b}
(a, b] = {x | a < x ≤ b}
(a, b) = {x | a < x < b}

Note that [a, b] is called the closed interval from a to b and (a, b)
is called the open interval from a to b.
Sets

DEFINITION

Two sets are equal if and only if they have the same elements.
Therefore, if A and B are sets, then A and B are equal if and
only if ∀ x (x ∈ A ↔ x ∈ B).We write A = B if A and B are
equal sets.
Sets
Example
The sets {1, 3, 5} and {3, 5, 1} are equal, because they have the
same elements.

Note that the order in which the elements of a set are listed does
not matter.

Note also that it does not matter if an element of a set is listed

more than once, so {1,3,3,3,5,5,5,5} is the same as the set
{1, 3, 5} because they have the same elements.
Sets

DEFINITION

Empty set
Æ (“null”, “the empty set”) is the unique set that contains no
elements whatsoever.
Æ = {} = {x | False}
No matter the domain of discourse, we have the axiom
¬$ x : x Î Æ.
Sets

DEFINITION

Subset
The set A is a subset of set B if and only if every element of A
is also an element of B.
We use the notation A ⊆ B to indicate that A is a subset of the
set B.
We see that A ⊆ B if and only if the quantification
∀x (x ∈ A → x ∈ B) is true
A is Not a Subset of B: A ⊄ B, x ∈ A such that x ∉ B.
Sets
Example

The set of all odd positive integers less than 10 is a subset of the
set of all positive integers less than 10.

The set of rational numbers is a subset of the set of real numbers.

The set of all computer science majors at MNU is a subset of the

set of all students at MNU.
Sets

THEOREM

Subset
For every set S

i) Æ⊂S and ii) S ⊆ S

Sets

DEFINITION

Size of a set

Let S be a set. If there are exactly n distinct elements in S where

n is a non-negative integer, we say that S is a finite set and that
n is the cardinality of S.

The cardinality of S is denoted by |S| .

The term cardinality comes from the common usage of the term
cardinal number as the size of a finite set.
Sets
Example

Let A be the set of odd positive integers less than 10.

A = {1, 3, 5, 7, 9}
Then |A| = 5. ?

Let S be the set of letters in the English alphabet.

Then |S| = 26.?

Because the null set has no elements, it follows that |∅| = 0. ?

Sets

DEFINITION

Power sets

Given a set S, the power set of S is the set of all subsets of the
set S.
The power set of S is denoted by ℙ (S)
Sets
Example
What is the power set of the set {0, 1, 2}?
The power set P ({0, 1, 2}) is the set of all subsets of {0, 1, 2}.
Hence, P ({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2},
{0, 1, 2}}.

What is the power set of the empty set? What is the power set of
the set {∅}?

The set {∅} has exactly two subsets, namely, ∅ and the set {∅}
itself. Therefore, P({∅}) = {∅,{∅}}.
Cartesian Product of Sets

DEFINITION

Cartesian Product
Let A and B be sets. The Cartesian product of A and B, denoted
by A × B, is the set of all ordered pairs (a, b), where a ∈ A and
b ∈ B. Hence, A × B = {a, b}|a ∈ A ∧ b ∈ B}
Sets
Example
What is the Cartesian product of A = {1, 2} and B = {a, b, c}
A x B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.

What is cartesian product of A × B × C where A = {0, 1},

B = {1, 2}, C = {0, 1, 2}

A x B x C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2),
(1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1, 2, 2)}.

Note that when A, B, and C are sets, (A × B) × C is not the same as A × B × C

Sets
Example
Suppose that A = {1, 2}. Find the cartesian product of A2 and A3

A2 = {(1, 1), (1, 2), (2, 1), (2, 2)}.

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

 Tutorial
Chapter 2.1 (page 125)
Questions
1, 2, 5, 6, 7, 9, 10, 11, 18, 19, 20, 21,
23, 24, 27, 32 -a, d, 33, 34