Set

• Definition: A set is a (unordered) collection of objects. These

objects are sometimes called elements or members of the set.
(Cantor's naive definition)

• Examples:
– Vowels in the English alphabet
V = { a, e, i, o, u }
– First seven prime numbers.
X = { 2, 3, 5, 7, 11, 13, 17 }

Representing sets
Representing a set by:
1) Listing (enumerating) the members of the set.
2) Definition by property, using the set builder notation
{x| x has property P}.
Example:
• Even integers between 50 and 63.
1) E = {50, 52, 54, 56, 58, 60, 62}
2) E = {x| 50 <= x < 63, x is an even integer}

If enumeration of the members is hard we often use ellipses.

Example: a set of integers between 1 and 100
• A= {1,2,3 …, 100}

1
 Important sets in discrete math
• Natural numbers:
– N = {0,1,2,3, …}

• Integers
– Z = {…, -2,-1,0,1,2, …}

• Positive integers
– Z+ = {1,2, 3.…}

• Rational numbers
– Q = {p/q | p  Z, q  Z, q  0}

• Real numbers
– R

Equality
Definition: Two sets are equal if and only if they have the same
elements.

Example:
• {1,2,3} = {3,1,2} = {1,2,1,3,2}

Note: Duplicates don't contribute anything new to a set, so remove

them. The order of the elements in a set doesn't contribute
anything new.

Example: Are {1,2,3,4} and {1,2,2,4} equal?

No!

2
 Special sets
• Special sets:
– The universal set is denoted by U: the set of all objects
under the consideration.
– The empty set is denoted as  or { }.

Venn diagrams
• A set can be visualized using Venn Diagrams:
– V={ A, B, C }

A
B

3
 A Subset
• Definition: A set A is said to be a subset of B if and only if
every element of A is also an element of B. We use A  B to
indicate A is a subset of B.

U
B

• Alternate way to define A is a subset of B:

x (x  A)  (x  B)

Empty set/Subset properties

Theorem   S
• Empty set is a subset of any set.

Proof:
• Recall the definition of a subset: all elements of a set A must be
also elements of B: x (x  A  x  B).
• We must show the following implication holds for any S
x (x    x  S)
• Since the empty set does not contain any element, x   is
always False
• Then the implication is always True.
End of proof

4
 Subset properties
Theorem: S  S
• Any set S is a subset of itself

Proof:
• the definition of a subset says: all elements of a set A must be
also elements of B: x (x  A  x  B).
• Applying this to S we get:
• x (x  S  x  S) which is trivially True
• End of proof

Note on equivalence:
• Two sets are equal if each is a subset of the other set.

Cardinality
Definition: Let S be a set. If there are exactly n distinct elements
in S, where n is a nonnegative integer, we say S is a finite set
and that n is the cardinality of S. The cardinality of S is
denoted by | S |.

Examples:
• V={1 2 3 4 5}
|V|=5

• A={1,2,3,4, …, 20}
|A| =20

• ||=0

5
 Infinite set
Definition: A set is infinite if it is not finite.

Examples:
• The set of natural numbers is an infinite set.
• N = {1, 2, 3, ... }

• The set of reals is an infinite set.

Power set
Definition: Given a set S, the power set of S is the set of all subsets
of S. The power set is denoted by P(S).

Examples:
• Assume an empty set 
• What is the power set of  ? P() = {  }
• What is the cardinality of P() ? | P() | = 1.

• Assume set {1}

• P( {1} ) = { , {1} }
• |P({1})| = 2

6
 Power set
• Assume {1,2}
• P( {1,2} ) = { ∅, {1}, {2}, {1,2} }
• |P({1,2} )| =4

• Assume {1,2,3}
• P({1,2,3}) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
• |P({1,2,3} | = 8

• If S is a set with |S| = n then | P(S) | = 2n

Set operations
Definition: Let A and B be sets. The union of A and B, denoted
by A  B, is the set that contains those elements that are either in
A or in B, or in both.
• Alternate: A  B = { x | x  A  x  B }.
U B
A

• Example:
• A = {1,2,3,6} B = { 2,4,6,9}
• A  B = { 1,2,3,4,6,9 }

7


Set operations
Definition: Let A and B be sets. The intersection of A and B,
denoted by A  B, is the set that contains those elements that are
in both A and B.
• Alternate: A  B = { x | x  A  x  B }.
U B
A

Example:
• A = {1,2,3,6} B = { 2, 4, 6, 9}
• A  B = { 2, 6 }

Disjoint sets
Definition: Two sets are called disjoint if their intersection is
empty.
• Alternate: A and B are disjoint if and only if A B = .
U B A

Example:
• A={1,2,3,6} B={4,7,8} Are these disjoint?
• Yes.
• AB=

8
 Set difference
Definition: Let A and B be sets. The difference of A and B,
denoted by A - B, is the set containing those elements that are in
A but not in B. The difference of A and B is also called the
complement of B with respect to A.
• Alternate: A - B = { x | x  A  x  B }.
U B
A

Example: A= {1,2,3,5,7} B = {1,5,6,8}

• A - B ={2,3,7}

Complement of a set
Definition: Let U be the universal set: the set of all objects under
the consideration.
Definition: The complement of the set A, denoted by A, is the
complement of A with respect to U.
• Alternate: A = { x | x  A }
U
A

Example: U={1,2,3,4,5,6,7,8} A ={1,3,5,7}

• A = {2,4,6,8}

9
 Cartesian product
Definition: Let S and T be sets. The Cartesian product of S and
T, denoted by S x T, is the set of all ordered pairs (s,t), where s
 S and t  T. Hence,
• S x T = { (s,t) | s  S  t  T}.

Examples:
• S = {1,2} and T = {a,b,c}
• S x T = { (1,a), (1,b), (1,c), (2,a), (2,b), (2,c) }
• T x S = { (a,1), (a, 2), (b,1), (b,2), (c,1), (c,2) }
• Note: S x T  T x S !!!!

Cardinality of the Cartesian product

• |S x T| = |S| * |T|.

Example:
• A= {John, Peter, Mike}
• B ={Jane, Ann, Laura}
• A x B= {(John, Jane),(John, Ann) , (John, Laura), (Peter, Jane),
(Peter, Ann) , (Peter, Laura) , (Mike, Jane) , (Mike, Ann) ,
(Mike, Laura)}
• |A x B| = 9
• |A|=3, |B|=3  |A| |B|= 9

Definition: A subset of the Cartesian product A x B is called a

relation from the set A to the set B.

10