Assiut University

‫قومية‬ ‫كلية‬
‫ل معتمدة من الهيئة ال عتماد‬
‫ضمان جودة التعليم واال‬

Course Title: Discrete Structures

Course Code: CS201

Prof. Dr. Khaled F. Hussain

Sets
• A set is an unordered collection of objects, called elements or members of
the set. Sets are denoted by curly braces {}. For example, the set of even
integers between 2 and 6 can be represented as {2, 4, 6}.
• The set V of all vowels in the English alphabet can be written as V = {a, e, i, o,
u}.
• Set Operations:
• Union (∪): The union of two sets A and B contains all elements that are in A or in B or in
both.
• Intersection (∩): The intersection of two sets A and B contains all elements that are in
both A and B.
• Difference ( - ): The difference of set A and set B contains all elements that are in A but
not in B.
• Complement (A'): The complement of set A contains all elements in the universal set
that are not in A.
• Cartesian Product (A × B): The Cartesian product of two sets A and B contains all
ordered pairs (a, b) where a is in A and b is in B.
Sets (Cont.)
• Set Notation:
• Sets are typically denoted by curly braces {}. For example, the set of even
numbers between 2 and 6 can be written as {2, 4, 6}.
• It is common for sets to be denoted using uppercase letters. Lowercase letters
are usually used to denote elements of sets.
• Elements of a set are separated by commas.
• The symbol ∈ is used to indicate that an element belongs to a set. For example,
4 ∈ {2, 4, 6}.

• Example1: The set of natural numbers N are the “whole numbers”: N = {0,
1, 2, 3, . . .}
• Example2: The set of integers Z are the whole numbers and their
negatives: Z = {. . . ,−2,−1, 0, 1, 2, . . .}
Sets (Cont.)
Sets are used to group objects together.
• A set is a collection of objects (members, elements). A = {3, 7, 14}
• A set is completely defined by its elements.
• An element ‘belongs to’ a set (or a set contains its elements).
• If a set is defined by listing its elements, all that matter is which elements included, not the order. {3, 7, 14}
is equal to {7, 3, 14}
• An element can appear more then once: Sets {3, 7, 14} and {3, 3, 14, 7, 7} are equal.
 Typically, sets will be denoted by uppercase letters.
Sets (Cont.)
• Types of Sets:
• Empty set (∅): A set containing no elements.
• Finite set: A set with a countable number of elements.
• Infinite set: A set with an uncountable number of elements.
• Universal set (U): The set containing all elements under consideration in
a particular context.
Sets (Cont.)
There are some other sets we should be familiar with since they come up so often. Here they are:
• Z = {0, 1, -1, 2, -2, ...} (the set of integers)
• N = {0, 1, 2, 3, ...} (the set of non-negative integers)
• Z+ = {1, 2, 3, ...} (the set of positive integers)
• Q = {a/b | a, bZ  b0} “|” such as
• R = the set of real numbers...
Sets (Cont.)
We have two usual methods of denoting the elements in a set:

1) Explicitly list the elements inside of a set of curly braces ({}), as follows: {1, 2, 3, 4}

• a set of vowels in English alphabet

V ={a, e, i, o, u} (finite set)
• a set of odd positive integers less then 10
B ={1, 3, 5, 7, 9} (finite set)
• a set of natural numbers (nonnegative integers)
 = {0, 1, 2, 3, …}(infinite set)
• a set of integers:
Z={…,-2, -1, 0, 1, 2, …}(infinite set)

2) To use “set builder” notation

Sets (Cont.)
• Set builder notation is a concise way to define sets by specifying a property or condition that elements
must satisfy. It involves using curly braces {}, a variable, a colon :, and a condition.
• In order to understand the second method, we must define the various symbols that are used in this notation.
Here is a list of the symbols we will be using:
• | - translates to “such that”
- “is an element of”
- “is a proper subset of”
- “is a subset of”

• General form: { x | condition(x) }

• This notation reads as "the set of all x such that condition(x) is true."

• Example1: The set of even integers can be written as: { x | x is an integer, and x is divisible by 2 }.
• Example2: The set of prime numbers less than 10 can be written as: { x | x is a prime number and x < 10 }
• Example3: O = {x | x is an odd positive integer less than 10} = {x ∈ Z+ | x is odd and x < 10}.
Sets (Cont.)
• set of odd positive integers less then 10:
B={x | x is positive odd integer less then 10}

• set of rational numbers:

Q = {a / b | a, b Z and b 0 }

• set of positive integers:

Z+= {x | x Z  x>0 }

• a set of squares of natural numbers:

S ={ x2 | xN}
Sets (Cont.)
• Set Properties:
• Equality: Two sets A and B are equal if they contain 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.
• Subset: 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. We see that A ⊆ B if and only if the quantification ∀x(x ∈ A → x ∈ B)
• Proper subset: A set A is a proper subset of set B if A is a subset of B and A is
not equal to B.
• A  B ≡ x [xA →x B] x [xB  x  A]
• Note: A  B iff A  B  AB.
• AB→AB
• but A  B does not imply A  B
Sets (Cont.)
• Example: Show that A  B, where
A ={ x| x is a prime number and 42x 51}
B = { y | y = 4k +3 and k  N }

To prove that A  B takes all x  A and show that x B. If x  A, then either x =43 or x=47.
x=43=410+3 and x=47= 411+3. So, in either case x has the form of an element of B, thus x B. Therefore A 
B.
Sets (Cont.)
• 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 (Cont.)
Equality of two sets
Two sets are equal if they contain the same elements. For example:
{1, 3, 5} = {3, 5, 1, 5}
{1, 4, 9, 16} = {x2 | x  Z+  x2 <20}

More rigorously:
Definition. Two sets are equal if and only if each of them is a subset of the other.
A = B  A B  B  A

Example. Show that A=B, where

A = { x | x is a prime number and 12 x 18 }
B = { y | y =4k +1 and k {3, 4} }

First show A B. Take any x A, then either x=13 or x=17. 13=43+1 →13 B, 17 = 44+1 →17 B, therefore A B. Similarly show
that B  A.
Sets (Cont.)
• Cardinality: The cardinality of a set is the number of elements in the
set. It is denoted by |A| for a set A.
• Let A be the set of odd positive integers less than 10. Then |A| = 5.
• Let S be the set of letters in the English alphabet. Then |S| = 26.
• What is the cardinality of each of the following sets?
|{a}| =1
|{{a}}| =1
|{a, {a}}| =2
|{a, {a}, {a, {a}}}| =3

• Cardinality of empty set || = 0

|{}|=1
|{, {}}|=2
|{, {}, {, {}}}|=3
Venn diagrams
• Venn diagrams are a graphical representation of sets and their
relationships.

• Basic Structure
• A Venn diagram typically consists of overlapping circles enclosed within a
rectangle. Each circle represents a set. The overlapping regions between
circles show the elements common to both sets.
Venn diagrams (Cont.)
• Universal Set (U): This is the set containing all elements under consideration
in a given context. The rectangle usually represents the universal set.
• Intersection (A ∩ B): The intersection of sets A and B is the set of elements
that belong to both A and B. It is represented by the overlapping region of the
circles for A and B.
• Union (A ∪ B): The union of sets A and B is the set of elements that belong to
either A or B (or both). It is represented by the entire area covered by both
circles.
• Complement (A'): The complement of set A is the set of elements in the
universal set that are not in A. It is represented by the area outside of circle A
within the rectangle.
• Difference (A - B): The difference of sets A and B is the set of elements that
belong to A but not to B. It is represented by the portion of circle A that does
not overlap with circle B.
Venn diagrams (Cont.)
• Example:
• Let's consider two sets:
• A: Set of even numbers
• B: Set of multiples of 3
• Venn diagram with two overlapping circles, one labeled A for even
numbers and the other labeled B for multiples of 3.
• The overlapping region represents numbers that are both even and
multiples of 3.
• A ∩ B: Numbers that are both even and multiples of 3 (e.g., 6, 12, 18)
• A ∪ B: Numbers that are either even or multiples of 3 (or both)
• A': Odd numbers
• A - B: Even numbers that are not multiples of 3 (e.g., 2, 4, 8)
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 P(S).
• 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}}. Note that the empty set and the set itself are members of this
set of subsets.

• Theorem:The cardinality of the power set of S (S with cardinality |S|=n) is 2n, |Power(S)|=2|S|.
Cartesian Products
• 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}.

• Example: What is the Cartesian product of A = {1, 2} and B = {a, b, c}?

• Solution: The Cartesian product A × B is
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
• Note that the Cartesian products A×B and B × A are not equal,
Cartesian Products (Cont.)
• What is the Cartesian product A × B × C, where A = {0, 1}, B = {1, 2}, and C = {0, 1, 2} ?
• Solution: The Cartesian productA × B × C consists of all ordered triples (a, b, c), where a ∈ A,
b ∈ B, and c ∈ C. Hence,
A × B × 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)}.
Set Operations
• Let A and B be sets. The union of the sets 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. A ∪ B = {x | x ∈ A ∨ x ∈ B}.
• Note that |A ∪ B| = |A| + |B| − |A ∩ B|.

• Let A and B be sets. The intersection of the sets A and B, denoted by A ∩ B, is the set containing those
elements in both A and B. A ∩ B = {x | x ∈ A ∧ x ∈ B}.
Set Operations (Cont.)
• Two sets are called disjoint if their intersection is the empty set.
• Let A = {1, 3, 5, 7, 9} and B = {2, 4, 6, 8, 10}. Because A ∩ B = ∅, A and B are disjoint.
• 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. A − B = {x | x
∈ A ∧ x ∉ B}.
• The difference of sets A and B is sometimes denoted by A\B.
• The difference of {1, 3, 5} and {1, 2, 3} is the set {5}; that is, {1, 3, 5} − {1, 2, 3} = {5}.
• Let U be the universal set. The complement of the set A, denoted by 𝐴,ҧ is the complement of A with respect to
U. Therefore, the complement of the set A is U − A. 𝐴ҧ = {x ∈ U | x ∉ A}.
Set Operations (Cont.)
• Example
If U = {1,2,3 … 9,10} A ={1,2,3,4,5} B={3,4,5,6,7}
• A  B ={1,2,3,4,5,6,7}
• A  B ={3,4,5}
• A ={6,7,8,9,10}
• B – A={6,7}
• A  B={1,2,6,7}

• Definition:
• S, T  U. The sets S and T are called disjoint or mutually disjoint,
when S  T = 
Set Operations (Cont.)
Do not confuse  and  (or ) signs!
Let A ={a, , {b}}.
• aA (T)
• {a} A (F)
• a A (F)
• {a}  A (T)
• {a}  A (T)
• {b}  A (F)
• {b}  A (T)
• {a, {b}}  A (T)
• {a, {b}}  A (T)
• A (T)
•  A (T)
Set Identities
Set Identities (Cont.)
• AB = B A
Proof
AB = { x | xA  xB }, by definition of union
= { x | xB  xA }, by commutative property of 
= B A, by definition of union

• A  (B  C) = (A  B)  C
Proof
A (BC)
={x | (x  A)  (x BC)]}, by definition of 
={x | (x  A)  [(x B) (x C)]}, by definition of 
= {x |[(x  A)  (x B)] (x C)}, by associative property of 
= {x |(x  A  B) (x C)}, by definition of 
= (A B) C, by definition of 
Set Identities (Cont.)
• A  (B  C) = (A  B)  (A  C)
Proof
A B C BC A (BC) A B A C (A  B)  (A  C)
1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1
0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0
Set Identities (Cont.)
• A   = A, A  U = A Identity Laws
Proof
A  = {x | x A  x}, by definition of a set union
= {x | x A  F}, since x [x] , x=F
= {x | x A}, by identity law p  F  p
=A
In the proof of A U = A you can consider x  U =T and use another identity law p  T ≡ p
Set Identities (Cont.)
prove that A = (A – B)  (A  B), for all sets A and B.
Proof

(A – B)  (A  B) = (A  B)  (A  B), definition of –

= A  (B  B), distributive law
= A  U, Inverse law
= A, Identity law

membership table method

A B A-B AB (A – B)  (A  B)
1 1 0 1 1
1 0 1 0 1
0 1 0 0 0
0 0 0 0 0
Set Identities (Cont.)
ҧ 𝐵.
• Use set builder notation and logical equivalences to establish the first De Morgan law 𝐴 ∩ 𝐵 = 𝐴𝑈 ത
• Solution:We can prove this identity with the following steps.
𝐴 ∩ 𝐵 = {x | x ∉ A ∩ B} by definition of complement
= {x | ￢(x ∈ (A ∩ B))} by definition of does not belong symbol
= {x | ￢(x ∈ A ∧ x ∈ B)} by definition of intersection
= {x | ￢(x ∈ A)∨￢(x ∈ B)} by the first De Morgan law for logical equivalences
= {x | x ∉ A ∨x ∉ B} by definition of does not belong symbol
= {x | x ∈ 𝐴ҧ ∨ x ∈ 𝐵}
ത by definition of complement
= {x | x ∈ 𝐴ҧ ∪ 𝐵}
ത by definition of union
= 𝐴ҧ ∪ 𝐵ത by meaning of set builder notation
Set Identities (Cont.)
• Use a membership table to show that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Functions
• Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each
element of A. We write f (a) = b if b is the unique element of B assigned by the function f to the element a of A.
If f is a function from A to B, we write f : A → B.
• Functions are sometimes also called mappings or transformations.
• If f is a function from A to B, we say that A is the domain of f and B is the codomain of f.
• If f (a) = b, we say that b is the image of a and a is a preimage of b.
• The range, or image, of f is the set of all images of elements of A.
• If f is a function from A to B, we say that f maps A to B.
Functions (Cont.)
• Example: Let f : Z → Z assign the square of an integer to this integer. Then, f (x) =
x2, where the domain of f is the set of all integers, the codomain of f is the set of all
integers, and the range of f is the set of all integers that are perfect squares,
namely, {0, 1, 4, 9, . . . }.
One-to-one (injunction)
• Afunction f is said to be one-to-one, or an injunction, if and only if f (a) = f (b) implies that a = b for all a and
b in the domain of f.
• A function is said to be injective if it is one-to-one.
• Example: Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5} with f (a) = 4, f (b) = 5, f (c) = 1,
and f (d) = 3 is one-to-one.
• The function f is one-to-one because f takes on different values at the four elements of its domain.
One-to-one (injunction) (Cont.)
• Example: Determine whether the function f (x) = x2 from the set of integers to the
set of integers is one-to-one.
• Solution: The function f (x) = x2 is not one-to-one because, for instance, f (1) = f (−1) = 1, but 1 = −1.
One-to-one (injunction) (Cont.)
• Example: Determine whether the function f (x) = x + 1 from the set of
real numbers to itself is one-to-one.
• Solution: The function f (x) = x + 1 is a one-to-one function. To demonstrate this, note that x + 1
≠ y + 1 when x ≠ y.
Onto (surjection)
• A function f from A to B is called onto, or a surjection, if and only if
for every element b ∈ B there is an element a ∈ A with f (a) = b.
• A function f is called surjective if it is onto.
• Example Let f be the function from {a, b, c, d} to {1, 2, 3} defined by
f (a) = 3, f (b) = 2, f (c) = 1, and f (d) = 3. Is f an onto function?
• Solution: Because all three elements of the codomain are images of
elements in the domain, we see that f is onto.
• Note that if the codomain were {1, 2, 3, 4}, then f would not be onto.
Onto (surjection) (Cont.)
• Example: Is the function f (x) = x2 from the set of integers to the set of integers
onto?
• Solution: The function f is not onto because there is no integer x with x2 = −1, for instance.

• Example: Is the function f (x) = x + 1 from the set of integers to the set of integers
onto?
• Solution: This function is onto, because for every integer y there is an integer x such that f (x) = y. To see
this, note that f (x) = y if and only if x + 1 = y, which holds if and only if x = y − 1.
Examples of Different Types of
Correspondences
One-to-one correspondence (bijection)
• The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say
that such a function is bijective.
• Example: Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f (a) = 4, f (b) = 2, f (c) = 1, and f (d) = 3. Is f
a bijection?
• Solution: The function f is one-to-one and onto. It is one-to-one because no two values in the domain are assigned the
same function value. It is onto because all four elements of the codomain are images of elements in the domain.
Hence, f is a bijection.
Inverse Functions
• Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is the function that
assigns to an element b belonging to B the unique element a in A such that f (a) = b. The inverse function of f
is denoted by f −1. Hence, f−1(b) = a when f (a) = b.
Inverse Functions (Cont.)
• Example: Let f be the function from {a, b, c} to {1, 2, 3} such that f (a) = 2, f (b) = 3,
and f (c) = 1. Is f invertible, and if it is, what is its inverse?
• Solution: The function f is invertible because it is a one-to-one correspondence. The inverse function f−1
reverses the correspondence given by f , so f−1(1) = c, f−1(2) = a, and f−1(3) = b.

• Example: Let f : Z → Z be such that f (x) = x + 1. Is f invertible, and if it is, what is

its inverse?
• Solution: The function f has an inverse because it is a one-to-one correspondence. To reverse the
correspondence, suppose that y is the image of x, so that y = x + 1. Then x = y − 1. This means that y − 1 is
the unique element of Z that is sent to y by f . Consequently, f−1 (y) = y − 1.
Inverse Functions (Cont.)
• Example: Let f be the function from R to R with f (x) = x2. Is f invertible?
• Solution: Because f (−2) = f (2) = 4, f is not one-to-one. If an inverse function were defined, it would have
to assign two elements to 4. Hence, f is not invertible.
• Note we can also show that f is not invertible because it is not onto.
Composition of the functions
• Let g be a function from the set A to the set B and let f be a function from the set B
to the set C. The composition of the functions f and g, denoted for all a ∈ A by f ◦ g,
is defined by (f ◦ g)(a) = f (g(a)).
Composition of the functions (Cont.)
• Example: Let f and g be the functions from the set of integers to the set
of integers defined by f (x) = 2x + 3 and g(x) = 3x + 2. What is the
composition of f and g? What is the composition of g and f ?
• Solution: Both the compositions f ◦ g and g ◦ f are defined.
• (f ◦ g)(x) = f (g(x)) = f (3x + 2) = 2(3x + 2) + 3 = 6x + 7
• (g ◦ f )(x) = g(f (x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11.
• f ◦ g and g ◦ f are not equal. In other words, the commutative law does not hold for the
composition of functions.
Floor and ceiling functions
• The floor function assigns to the real number x the largest integer that is less than or equal to x. The value of
the floor function at x is denoted by 𝑥 .
• The ceiling function assigns to the real number x the smallest integer that is greater than or equal to x. The
value of the ceiling function at x is denoted by 𝑥 .
Relations
• Let A and B be sets. A binary relation from A to B is a subset of A × B.
• Example: Let A = {0, 1, 2} and B = {a, b}. Then {(0, a), (0, b), (1, a), (2, b)} is a relation from A to B. This means,
for instance, that 0 R a. Relations can be represented graphically
Relations (Cont.)
• Recall that a function f from a set A to a set B assigns exactly one element of B to each element of A.
• Relations are a generalization of functions; they can be used to express a much wider class of relationships
between sets.
Relations (Cont.)
• A relation on a set A is a relation from A to A.
• In other words, a relation on a set A is a subset of A × A.

• EXAMPLE: Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R = {(a, b) | a
divides b}?
• Solution: Because (a, b) is in R if and only if a and b are positive integers not exceeding 4 such
that a divides b, we see that R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.
Relations (Cont.)
• EXAMPLE: How many relations are there on a set with n elements?
• Solution: A relation on a set A is a subset of A × A. Because A × A has n2 elements when A has
2
n elements, and a set with m elements has 2m subsets, there are 2𝑛 subsets of A × A. Thus,
2 2
there are 2𝑛 relations on a set with n elements. For example, there are 23 = 29 = 512 relations
on the set {a, b, c}.
Relations (Cont.)
More examples of relations:
• “parent-of”
• “child-of”
• “likes”
• “meet one another today”
• “less then” = {(a, b) | a, b A and a<b} where A={1, 2, …5}
“less then” = { (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}
Relations (Cont.)
Properties of Relations:
• Reflexive: A relation R on set A is reflexive if (a, a) ∈ R for all a ∈ A.
• EXAMPLE: Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.
Which of these relations are reflexive?
Solution: The relations R3 and R5 are reflexive because they both contain all pairs of the form (a, a). R1, R2, R4,
and R6 are not reflexive because (3, 3) is not in any of these relations.
Relations (Cont.)
• Example: Is the “divides” relation on the set of positive integers reflexive?
Solution: Because a | a whenever a is a positive integer, the “divides” relation is reflexive.
(Note that if we replace the set of positive integers with the set of all integers the relation is not
reflexive because 0 does not divide 0.)
Relations (Cont.)
• Symmetric: A relation R on set A is symmetric if (a, b) ∈ R implies (b, a) ∈ R for all a, b ∈ A.
• The relation R on the set A is symmetric if ∀a∀b((a, b) ∈ R → (b, a) ∈ R).
• Antisymmetric: A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R,
then a = b is called antisymmetric.
• The relation R on the set A is antisymmetric if ∀a∀b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b)).
• EXAMPLE: Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.
Which of the relations are symmetric and which are antisymmetric?
• Solution: The relations R2 and R3 are symmetric, because in each case (b, a) belongs to the relation whenever (a, b) does.
• None of the other relations is symmetric. This is done by finding a pair (a, b) such that it is in the relation but (b, a) is not.
• R4, R5, and R6 are all antisymmetric. For each of these relations there is no pair of elements a and b with a ≠ b such that both (a, b)
and (b, a) belong to the relation.
Relations (Cont.)
• Example: Is the “divides” relation on the set of positive integers symmetric? Is it
antisymmetric?
• Solution: This relation is not symmetric because 1| 2, but 2 does not divide 1.
It is antisymmetric, for if a and b are positive integers with a |b and b |a, then
a = b.
Relations (Cont.)
• Transitive: A relation R on set A is transitive if (a, b) ∈ R and (b, c) ∈ R
implies (a, c) ∈ R for all a, b, c ∈ A.
• The relation R on a set A is transitive if we have ∀a∀b∀c(((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R).
• EXAMPLE: Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.
Which of the relations are transitive?

Solution: R4, R5, and R6 are transitive.

R1 is not transitive because (3, 4) and (4, 1) belong to R1, but (3, 1) does not.
R2 is not transitive because (2, 1) and (1, 2) belong to R2, but (2, 2) does not.
R3 is not transitive because (4, 1) and (1, 2) belong to R3, but (4, 2) does not.
Relations (Cont.)
• Example: Is the “divides” relation on the set of positive integers
transitive?
• Solution: Suppose that a divides b and b divides c. Then there are
positive integers k and l such that b = ak and c = bl. Hence, c = a(kl),
so a divides c. It follows that this relation is transitive.
Relations (Cont.)
• Equivalence Relation: A relation R on set A is an equivalence
relation if it is reflexive, symmetric, and transitive.

• EXAMPLE: Let R be the relation on the set of real numbers such that aRb if and
only if a − b is an integer. Is R an equivalence relation?
• Solution: Because a −a = 0 is an integer for all real numbers a, aRa for all real
numbers a. Hence, R is reflexive.
• Now suppose that aRb. Then a −b is an integer, so b−a is also an integer.
Hence, bRa. It follows that R is symmetric.
• If aRb and bRc, then a −b and b−c are integers. Therefore, a −c = (a −b) + (b−c)
is also an integer. Hence, aRc. Thus, R is transitive.
• Consequently, R is an equivalence relation.
Relations (Cont.)
• EXAMPLE: Suppose that R is the relation on the set of strings of English letters
such that aRb if and only if l(a) = l(b), where l(x) is the length of the string x. Is R
an equivalence relation?
• Solution: Because l(a) = l(a), it follows that aRa whenever a is a string, so that
R is reflexive.
• Next, suppose that aRb, so that l(a) = l(b). Then bRa, because l(b) = l(a). Hence,
R is symmetric.
• Finally, suppose that aRb and bRc. Then l(a) = l(b) and l(b) = l(c). Hence, l(a) =
l(c), so aRc. Consequently, R is transitive.
• Because R is reflexive, symmetric, and transitive, it is an equivalence relation.
Relations (Cont.)
Example: Is the following relation reflexive, irreflexive, symmetric, antisymmetric, or transitive? R =
{(a,b) | a,bZ+  a, 2a, and b are side lengths of a triangle} Note: For all triangles, the sum of the lengths
of any two sides must exceed the length of the third side.
• Reflexive? No – because (a,a)R, this is because a triangle can not have side lengths, a, a and 2a.
• Irreflexive? Yes – the previous argument holds for all positive integers a.
• Symmetric? No – (a, 2a)R, since we can have a triangle with side lengths a, 2a and 2a. However, (2a,
a)R because we can not have a triangle with side lengths 2a, 4a and a.
• Antisymmetric? Yes – If we have a  b, then we have (a,b)R. To prove this, consider a forming a
triangle with side lengths a, 2a, and b. We know that we must have a+b > 2a for a triangle to be formed.
BUT, a+b  a+a = 2a, which means that a+b is NOT greater than 2a. Thus, in this situation, we have
(a,b)R. Thus, for any element (a,b)R, we must have a < b. For each of these elements, we can
guarantee that (b,a)R since b > a.
• Transitive? No – (a, 2a)R as shown above, and we also know that (2a, 4a)R, by a similar analysis.
But we can show that (a,4a)R because a triangle can not have side lengths a, 2a and 4a.
Relations (Cont.)
• Give an example of a relation on A ={a, b, c} that is
a) reflexive but not symmetric
R={(a, a), (b, b), (c, c), (a, b)}

• b) symmetric but not reflexive and not transitive

• R={(a, b), (b, a), (b, b), (b, c), (c, b)}
Relations(Cont.)
• Functions:
• A function is a special type of relation where each element in the first set
(domain) is associated with exactly one element in the second set
(codomain).

• Properties of Functions:
• Injective (one-to-one): A function is injective if no two different elements
in the domain map to the same element in the codomain.
• Surjective (onto): A function is surjective if every element in the codomain
has at least one element in the domain that maps to it.
• Bijective (one-to-one correspondence): A function is bijective if it is both
injective and surjective.
Relations(Cont.)
• Equivalence Classes:
• An equivalence relation partitions a set into disjoint subsets called
equivalence classes. Elements within the same equivalence class are
considered equivalent under the relation.
• Let R be an equivalence relation on a set A. The set of all elements that
are related to an element a of A is called the equivalence class of a. The
equivalence class of a with respect to R is denoted by [a]R. When only one
relation is under consideration, we can delete the subscript R and write
[a] for this equivalence class.
• [a]R = {s | (a, s) ∈ R}.
Relations(Cont.)
• Example: Let R be the relation on the set of integers such that aRb if and only if a
= b or a = −b. What is the equivalence class of an integer for the equivalence
relation R.
• Solution: Because an integer is equivalent to itself and its negative in this
equivalence relation, it follows that [a] = {−a, a}. This set contains two distinct
integers unless a = 0. For instance, [7] = {−7, 7}, [−5] = {−5, 5}, and [0] = {0}.
Relations(Cont.)
• Example: What are the sets in the partition of the integers arising from congruence modulo 4?
• Solution: There are four congruence classes, corresponding to [0]4, [1] 4, [2] 4, and [3] 4. They are
the sets:
[0] 4 = {. . . ,−8,−4, 0, 4, 8, . . . },
[1] 4 = {. . . ,−7,−3, 1, 5, 9, . . . },
[2] 4 = {. . . ,−6,−2, 2, 6, 10, . . . },
[3] 4 = {. . . ,−5,−1, 3, 7, 11, . . . }.
These congruence classes are disjoint, and every integer is in exactly one of them.