Lecture 5

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

Lecture 5

Uploaded by

Copyright:

Available Formats

Lecture 5

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 5

Uploaded by

Copyright:

Available Formats

Lecture 5

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

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

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

There are several ways to describe a set.

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

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

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

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

i) Æ⊂S and ii) S ⊆ S

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

The cardinality of S is denoted by |S| .

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

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

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

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

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

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)}

You might also like