Discrete Mathematics

(CSE 101)

Chapter 2
2.1 Sets

1
 Sets
Curly brace notation “{ … }”
Cardinality “| … |”
Element containment ∈
Subset containment ⊆
Empty set { } = ∅
Power set P(S ) = 2S
N-tuples “( … )” and Cartesian product ×

2
 Sets
• Definition1: A set is an unordered collection of
objects.
• Definition2: Objects in a set are called elements, or
members of the set.
– A Set is said to contain its elements.
• Capital letters (e.g. A, B, C, O, N) are ordinarily used
to denote sets and lowercase letters (e.g., a, b, c, p)
are used to denote elements of a sets.
• Elements of a Set may NOT be the same type always!

3
 Sets
• A set is defined only by the elements which it
contains. Thus repeating an element, or
changing the ordering of elements in the
description of the set, does NOT change the
set itself.
• Sets can have other sets as member.

4
 Representation of a Set
▪ Basically there are two ways of representing a set:
1) List/Tabular form: All elements of the set are listed, the
elements being separated by commas(,) and are enclosed by
curly braces “{“ and “}”
Example: B = { a, e, i, o, u}
A = { 2, 4, 6, 8}
2) Rule method, or Set builder form: A set is defined by
specifying a property that elements of the set have in
common.
Example: B = { x| x is a vowel in the English alphabets}
A = { x| x is an even integer between 1 and 8}

5
 Different Types of Sets
• Empty set/ Null set: A set with no member is called empty/null set.
Empty set is denoted by ∅. Empty set is also denoted by { }
Examples: B = { }, A = { x is a multiple of 4 | x is odd }
▪ Note: ∅ ≠ {∅}
• Singleton set: A set with one element is called a singleton set.
Examples: B = {4} , S = {a}
• Finite set : A set with finite number of elements in it, is called a
finite set. Example: A = { 1, 3, 4,77}
• Infinite set : An infinite set is a set which contains infinite number
of elements.
Examples: N = { 0, 1, 2, 3, ……….}
B = { 1, 1/3, 1/9, 1/27, ………..}

6
 Some Examples of Sets
• {1, 2, 3} is the set containing elements “1” and “2” and “3.”
• {1, 1, 2, 3, 3} = {1, 2, 3} since repetition is irrelevant.
• {1, 2, 3} = {3, 2, 1} since sets are unordered (order of elements
does NOT matter)
• {0,1, 2, 3, …} is a way we denote an infinite set (in this case,
the natural numbers).
• ∅ = {} is the empty set, or the set containing no elements.
• A = { a, 2, Fred, New York } ==> Although elements are usually
same type, but they may be of different types

7
 Sets: More examples
• Example 1 : The set V of all vowels in the English
alphabet cab be written as V = { a, e, i, o, u }

• Example 2: The set O of odd positive integers less

than 10 can be denoted by { 1, 3, 5, 7, 9 }

• Example 4 : The set of positive integers less than 100

can be denoted by { 1, 2, 3, ………..,99 }

8
 Standard Numerical Sets
N = {0, 1, 2, 3, …}, natural numbers
Z = {…,-2, -1, 0, 1, 2, …}, integers
Z+ = {1, 2, 3, …}, positive integers
Q = {p/q|p∈Z, q∈Z, and q≠0}, rational numbers
1.5,-3.8
Q+ = {x∈R|x=p/q, for positive integers p and q}
1.5,2.5
R = real numbers
• The real numbers: R ==> contains any decimal number of arbitrary
precision
• The rational numbers: Q ==> these are decimal numbers whose decimal
expansion repeats
9
 ∈-Notation
▪ The Greek letter “∈” (epsilon) is used to denote that an object is an
element of a set. When crossed out “∉” denotes that the object is not
an element.”
Example: 3 ∈ S reads: “3 is an element of the set S ”.
3 ∉ S reads: “3 is an not element of the set S ”.
Q: Which of the following are true:
1. 3∈R
2. -3 ∈ N
3. -3 ∈ R
4. 0 ∉ Z+
5. ∃ x, x∈R ∧ x2 = - 5

10
 ∈-Notation
Answers:
1. 3 ∈ R. True: 3 is a real number.
2. −3 ∈ N. False: natural numbers don’t contain
negatives.
3. −3 ∈ R. True: −3 is a real number.
4. 0 ∉ Z+. True: 0 is NOT a positive integer.
5. ∃x x∈R ∧ x2 = −5 . False: square of a real
number is non-negative, so can’t be −5.

11
 Venn diagram
• Sets can be represented graphically using Venn diagrams.
• In Venn diagrams, the universal set U, which contains all the
objects under consideration, is represented by a rectangle.
Note: the universal set varies depending on which objects are
of interest
• Inside the rectangle,
– Circles or other geometrical figures are used to represent sets.
– Sometimes points are used to represent the particular elements of the
set.
• Venn diagrams are often used to indicate the relationships
between sets.

12
FIGURE 1 Venn Diagram for the Set of Vowels

13
 Equal Set
• Definition 3: Two sets are equal if and only if they
have the same elements.
A = B iff ∀ x(x ∈ A ↔ x ∈ B)
• Two sets A and B are said to be equal if and only if
every element of A is an element of B and
consequently every element of B is an element of A;
that is A ⊆ B and B ⊆ A and it is written as A = B
Example 6 (p.113) : The sets { 1, 3, 5} & { 3, 5, 1 } are
equal because they have the same elements.

14
 Subset
• Definition 4: The set A is a subset of 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.
• A ⊆ B if and only if the quantification
∀x(x ∈ A → x ∈ B) is true
• Note: Every non-empty set S is guaranteed to have at
least two subsets, the empty set and the set S itself,
that is ∅ ⊆ S and S ⊆ S

15
 Subset
▪ Theorem 1: For every non-empty set S,
(1) ∅ ⊆ S, and
(2) S ⊆ S

• Note: If A⊆B and B⊆A, then A=B

• Sets may have other sets as members
A = {∅, {a}, {b}, { a, b} }
B = { x | x is a subset of the set {a ,b } }
• Note: These two sets are equal, that is, A = B
• Note : In the above example, {a} ∈ A but a ∉ A

16
 Proper Subset
• Proper subset: Any subset A is said to be proper subset of
another set B if A is a subset of B, but there is at least one
element of B which does not belong to A, i.e.,
if A⊆B but A ≠ B
∀ x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x ∉ A)
• A ⊂ B means “A is a proper subset of B.”

• Example: A = { 1, 5 }, B = { 1, 5, 6}
Here, A is a proper subset of B, i.e., A ⊂ B

17
FIGURE 2 Venn Diagram Showing that A is a Subset of B

18
 Cardinality of a Set
• Definition: If there are exactly n distinct members in
the set S (n is a nonnegative integer), we say that S
is a finite set and that n is the cardinality of S.
• The cardinality of a set is the number of distinct
elements in the set.
• |S | denotes the cardinality of set S.
• Examples:
|S|= n
|∅|=0
| { 1, 5, 7, 8}|= 4

19
 Cardinality of a Set
Question: Compute cardinality of each of the sets.
1. {1, -13, 4, -13, 1}
2. {3, {1,2,3,4}, ∅}
3. {}
4. { {}, {{}}, {{{}}} }

• Hint: After eliminating the repeatations/redundancies just

look at the number of top level commas and add 1 (except for
the empty set).

20
 Cardinality of a Set
Answer:
1. |{1, -13, 4, -13, 1}| = |{1, -13, 4}| = 3
2. |{3, {1,2,3,4}, ∅}| = 3
3. |{}| = |∅| = 0
4. |{ {}, {{}}, {{{}}} }| = |{ ∅, {∅}, {{∅}}| = 3

21
 Cardinality of a Set: More examples
• Example 9 : Let A be the set of odd positive integers less than
10. Then |A| = 5

• Example 10 : Let A be the set of letters in the English

alphabet. Then |A| = 26

• Example 11 : Because null set has no elements, it follows that,

|∅| = 0
• Example : The cardinality of the set {∅} is 1, i.e., | {∅} | = 1

22
 Cardinality of a Set: More examples

• If S = {1,2,3}, |S| = 3

• If S = {3,3,3,3,3}, |S| = 1

• If S = { ∅, {∅}, {∅,{∅}} }, |S| = 3.

• If S = {0,1,2,3,…}, |S| is infinite.

23
 Super Set
• If A is a subset of B, then B is called the super set of A
and written as B ⊇ A which is read as “B is a super
set of A”.

• A ⊇ V means “A is a superset of V.”

• Example: { 1, 4, 7, 8} is a superset of the set { 4, 7 }

24
 Quiz
Quick examples:
• {1,2,3} ⊆ {1,2,3,4,5} Yes/No?
• {1,2,3} ⊂ {1,2,3,4,5} Yes/No?

• Is ∅ ⊆ {1,2,3}? Yes!
• Is ∅ ∈ {1,2,3}? No!
• Is ∅ ⊆ {∅,1,2,3}? Yes!
• Is ∅ ∈ {∅,1,2,3}?Yes!

25
 Quiz
• Is {x} ⊆ {x}? Yes

• Is {x} ∈ {x,{x}}? Yes

• Is {x} ⊆ {x,{x}}? Yes

26
 Power Set
• Definition : The power set of S is the set of all
subsets of the set S.
• We say, “P(S) is the set of all subsets of S”
• The power set of S is denoted by P(S)

• Note: If a set has n elements, then its power set has

2n elements.

27
 Power Set: Examples
▪ Example 13: What is the power set of the set {0,1,2 } ?
• Solution: 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}}

▪ Example 14: What is the power set of empty set? What is the
power set of the set {∅} ?
• Solution:
P(∅) = {∅}
P( {∅} ) = { ∅, {∅} }

28
 Ordered n-tuples
• The order of elements in a collection is often
important. Because sets are unordered, a different
structure is needed to represent ordered collections.
This is provided by ordered n-tuples.
• Definition : Ordered n-tuple (a1, a2, …, an) is the
ordered collection that has ai as its ith element for
i=1, 2, …, n.

29
 Ordered n-tuples
• Two ordered n-tuples are equal if and only if each
corresponding pair of their elements is equal.
In other words, (a1, a2 , ….., an) = (b1 , b2 , …….., bn )
if and only if ai = bi for i = 1, 2, ……, n

• 2-tuples are called ordered pairs. The ordered pairs

(a, b) and (c, d) are equal if and only if a = c and b = d
• Note: ( a, b) and ( b, a ) are not equal unless a = b

30
 Ordered n-tuples
• Notationally, n-tuples look like sets except that curly
braces are replaced by parentheses:

▪ ( 11, 12 ) ==> A 2-tuple (aka ordered pair)

▪( , , ) ==> A 3-tuple

▪( , , , 11, Leo ) ==> A 5-tuple

31
 Ordered n-tuples

• As opposed to sets, repetition and ordering

DO MATTER with n-tuples.
(11, 11, 11, 12, 13) ≠ ( 11, 12, 13 )

32
 Cartesian Product of Sets
• Definition : 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.
A × B = {(a, b)| a ∈ A ∧ b ∈ B}

33
 Cartesian Product of Sets: Example
• Example 16: What is the Cartesian product of
A = { 1, 2 } and B = { a, b, c} ?
• Solution:
A X B = { (1,a), (1,b), (1,c), (2,a), (2,b), (2,c) }
Note : A × B and B × A are not equal, unless A=∅ or B=∅ or A=B
Note: Cartesian product of more than two sets can be defined
Note: A subset R of the Cartesian product A X B is called a
Relation from the set A to the set B (Relation will be
covered in the final term)
Practice @ Home: Example 17

34
 Cartesian Product of Sets: Example
• Question: If A = {1,2}, B = {3,4}, C = {5,6,7}
what is A ×B ×C ?
▪ Answer:
A ×B ×C = { (1,3,5), (1,3,6), (1,3,7),(1,4,5), (1,4,6), (1,4,7),
(2,3,5), (2,3,6), (2,3,7), (2,4,5), (2,4,6), (2,4,7) }

• Note: |A ×B ×C | = |A|.|B|.|C| = 2.2.3 = 12

• Practice @ Home: Example 18

35
 Set Operation
Definition: Let A and B be sets. The union of A and B, denoted
by A U B, is the set that contains those elements that are in
both A andB.

• Alternate: A U B = { x | x ϵ A V x ϵ B }.

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

• A U B = { 1,2,3,4,6,9 }
 Set Operation
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 andB.

• Alternate: A ∩ B = { x | x ϵ A ˄ x ϵ B }.

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

•A∩ B={2}
 Disjoin Set
Definition: Two sets are called disjoint if their intersection is
empty.

• Alternate: A and B are disjoint if and only if A ∩ B = Ø.

Example:
• A={1,2,3,6} B={4,7,8} Are these disjoint?
• Yes.
•A∩B=Ø
 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 but not in B. The difference of A and B is also called
the complement of B with respect to A.

• Alternate:

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 Ã, is the
complement of A with respect to U.
• Alternate: Alternate:

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

• Ã={2,4,6,7,8}
 Generalized union
Definition: The union of a collection of sets is the set that
contains those elements that are members of at least one set
in the collection.

Example:
A1 = {1}
• Let Ai= {1,2,...,i} i =1,2,...,n
A2= {1,2}
A3= {1,2,3}
…………..
…………..
An {1,2,3,4,...,n}
 Generalized intersection
Definition: The intersection of a collection of sets is the set
that contains those elements that are members of all sets in
the collection.

Example:
• Let Ai= {1,2,...,i} i =1,2,...,n
A1 = {1}
A2= {1,2}
A3= {1,2,3}
…………..
…………..
An {1,2,3,4,...,n}
 Computer representation of
set
How to represent sets in the computer?
• One solution: Data structures like a list

• A better solution: Assign a bit in a bit string to each element

in the universal set and set the bit to 1 if the element is
present otherwise use 0

Example:
All possible elements: U={1 2 3 4 5}
• Assume A={2,5}
– Computer representation: A = 01001

• Assume B={1,5}
– Computer representation: B = 10001
 Computer representation of
set
Example:
• A = 01001
• B = 10001

• The union is modeled with a bitwise or

• A U B = 11001

• The intersection is modeled with a bitwise and

• A ∩ B = 00001

• The complement is modeled with a bitwise negation

• Ã =10110
 Quiz Problem
4. Let A = {a, b, c}, B = {x, y} and C= {0, 1}. Find C × B × A.

C×B {{0,x}{0,y},{1,x}{1,y}}
C×B×A {{0,x,a}, {0,x,b}, {0,x,c},{0,y,a}, {0,y,b},
{0,y,c},{1,x,a}, {1,x,b}, {1,x,c},{1,y,a}, {1,y,b},
{1,y,c}}
 Operators
The symmetric difference, A ⊕ B, is: like
“exclusive or”
A ⊕ B = { x : (x ∈ A ∧ x ∉ B) v (x ∈ B ∧ x
∉ A)}

= (A - B) U (B - A)

U
A
B
 Operators

Proof: { x : (x ∈ A ∧ x ∉ B) v (x ∈ B ∧ x ∉ A)}
= (A - B) U (B - A)

A ⊕ B = { x : (x ∈ A ∧ x ∉ B) v (x ∈ B ∧ x ∉ A)}
= { x : (x ∈ A - B) v (x ∈ B - A)}
= { x : x ∈ ((A - B) U (B - A))}
= (A - B) U (B - A)
 Famous Identities
• Identity
A∩U=A
AU∅=A

• Domination A U U = U
A∩∅=∅

• Idempotent AUA=A
A∩A=A
 Famous Identities
• Excluded Middle
AUA=U

• Uniqueness A∩A=∅

A=A
• Double complement
 Famous Identities
• Commutativity AUB= BUA
A∩B= B∩A

(A U B) U C = A U (B U C)
• Associativity
(A ∩ B) ∩ C = A ∩ (B ∩ C)

A U (B ∩ C) = (A U B) ∩ (A U C)
• Distributivity
A ∩ (B U C) = (A ∩ B) U (A ∩ C)
 Famous Identities
• DeMorgan’s I
(A U B) = A ∩ B

• DeMorgan’s II (A ∩ B) = A U B
 Inclusion/Exclusion
Example:
How many people are wearing a watch?
How many people are wearing
sneakers?
How many people are wearing
a watch OR sneakers?

What’s wrong?
|A ∪ B| = |A| + |B| 7
B A
|A ∪ B| = |A| + |B| - |A ∩ B| 6
 Inclusion/Exclusion
Example:
There are 217 cs majors.125
157 are taking cs125. 173
145 are taking cs173.
98 are taking both.

How many are taking neither?

217 - (157 + 145 - 98) = 13
 Generalized Inclusion/Exclusion
Suppose we have: A = {0, 2, 4, 6, 8},
B B = {0, 1, 2, 3, 4},
A
C = {0, 3, 6, 9}.

And I want to know |A U B U C|

|A U B U C| = |A| + |B| + |C|

- |A ∩ B| - |A ∩ C| - |B ∩ C|
+ |A ∩ B ∩ C|
|A ∪ B ∪ C| = 5+5+4-3-2-2+1 ≡ 8 ≡{0, 1, 2, 3, 4, 6, 8, 9}.
 Practice @ Home
• Relevant odd-numbered Exercises from your
book
• Exercises: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23,
27, 29, 33, 35

55