Discrete Mathematics
Relations
Cartesian Product & Ordered
Pairs
An ordered pair of elements is written in the form
(a, b) which is distinct from (b, a) unless a = b
Definition(Cartesian Product) :
For sets A, B U , the Cartesian product, or
cross product, of A and B is denoted by A B
and A B {( a, b) | a A, b B}.
Example:
Let A {x, y} and B {a, b, c} then
A B {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}
& B A {(a, x), (a, y), (b, x), (b, y), (c, x), (c, y)}
A A {(x, x), (x, y), (y, x), (y, y)}
Certainly A B B A ( in general)
Example
X = { 1, 2}
Y = { a, b}
X x Y = {(1,a),(1,b),(2,a), (2,b)}
Y x X = { (a, 1), (a,2), (b,1), (b,2)}
Note:
XxYYxX
| X x Y | = |X| .|Y|
Determine:
XxX=
YxY =
Ordered lists
The ordered list does not have to be
restricted to two elements, such as in an
ordered pair.
An n-tuple, written (a1, a2, a3… an) takes order
into account.
Cartesian product of sets X1, X2, X3… Xn is
defined to be the set of all n-tuples (x1, x2, x3…
xn) where xi Xi for i = 1,2,..n
X 1 x X 2 x X 3 x… X n
Relation : Definition
Definition (Relation) : For sets A, B U , any subset of A B is called
a relation from A to B. Any subset of A A is called a binary
relation on A.
If R is a relation from a set A to another set B, then R A B
Remarks:
• In general, for finite sets A,B with |A|=m and |B|=n, there
are 2mn relations from A to B, including the empty relation
as well as the relation A × B itself.
• The domain of a relation R is the set of all first elements of the
ordered pairs which belong to R, and the range of R is the set of
second elements.
Example:
• Let R = { (1,a),(2,b),(1,c)} then dom R = { 1,2 } and
range R = {a,b,c}
• Let A=Z+ and a binary relation R on A be {(x,y) |x<y}
(1,2), (7, 11) is in R, but (2,2), (3,2) are not in R
we can also 1R2, 7R11 (infix notation)
Let X = {2, 3, 4} and Y = { 3, 4, 5,6, 7}
•
If we define a relation R from X to Y by
(x,y) R if x divides y ( with zero remainder)
R = { (2,4), (2,6), (3,3), (3,6), (4,4)}
Domain of R is {2, 3, 4};Range of R is {3, 4 6}
Another Example:
Let R be the relation on X = {1,2,3,4} defined
by (x,y) R if x y, x, y X.
R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,3),
(2,4), (3,3), (3,4),(4,4)}
The domain and Range of R are both equal
to X
Representing Relations using
a Digraph
Digraph – directed graph
Components –
Vertices or Nodes, drawn as dots
Edges - Directed edges i.e. lines between
vertices with arrows showing a direction
between the vertices)
Vertices represent elements of X
Directed Edge represent the members
of the relation R
Example
Let R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3),
(2,4), (3,3), (3,4),} be a relation on
A={1,2,3,4} 1 2
A Loop
4 3
Exercise:
The Relation R on X = {a, b, c, d} is
R = {(a,a), (b,c), (c,b), (d,d)}
What would the digraph to represent this relation
look like?
Representing Relations
Using Matrix
Let A = { 1 , a 2 ,..., a m } and B={b1 , b2 ,..., bn }
a
Let R be relation from A to B. Then R is represented by
a matrix M R [ mij ]mn where
1
if ( ai , b j ) R
mij
0
if (ai , b j ) R
The matrix M R is called the matrix of R.
Example : Let A {1,2,3,4} and B {x, y, z}
Let R {(1, y ), (2, z ), (3, x), (3, y ), (4, x), (4, z )} be a relation from A to B.
Then M R is given by 0 1 0
x y z 0 0 1
10
M R .
1 0 1 1 0
20 0 1
1 0 1
31 1 0
41 0 1
Types of Relations:
Reflexive and Irreflexive
Symmetric
Antisymmetric
Transitive
Reflexive and Irreflexive
A relation R on a set A is called reflexive
if (a, a) R for every a A
e.g. Let A = {1,2,3,4}, then
R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4),(4,4)}
is Reflexive, while
R*={(1,1),(1,2),(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)}
is not a reflexive relation on A.
A relation R on a set A is called irreflexive if
(a,a) does not belong to R for any a A.
R’={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} is irreflexive relation on A.
Symmetric and Anti-
symmetric
A relation R on a set A, is called symmetric if
whenever (a,b) R, then (b,a) R
Example:
R2 = {(a,a), (b,c), (c,b), (d,d)} is symmetric.
Is R2 also Reflexive?
A relation R on a set A is called anitsymmetric if
whenever (a, b) and (b, a) R then a=b.
Example:
R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4), (3,3), (3,4),
(4,4)}
is Antisymmetric as (2,1) , (3,1) and (4,2) are not in
the relation R.
Note that this relation is not symmetric but it is
antisymmetric.
Antisymmetric (continued)
Is R2 = {(a, a), (b, c), (c, b), (d, d)} is
antisymmetric?
No. Both (b,c) and (c,b) are in R.
If a relation R on X has no members of the
form (x, y) with xy, then R is antisymmetric.
WHY?
Let R = {(a,a), (b,b), (c,c)}
then R is antisymmetric
Is R also Symmetric? Yes.
NB. “Antisymmetric” is not the same as
Transitivity
A relation R on set A is called transitive if
whenever (a, b) R and (b, c) R, then
(a, c) R
Example:
Let R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,3),
(2,4), (3,3), (3,4),(4,4)} is transitive but
R = {(a, a), (b, c), (c, b), (d, d)} is not transitive.
WHY?
Inverse of a relation
Let R be a relation from A to B. The inverse
of R, denoted R-1, is the relation from B to A
defined by
R-1 ={(y, x )|(x, y) R}
X = {2,3,4} and Y ={3,4,5,6,7}, a relation R is
defined by
(x, y) R if x divides y (with zero remainder)
R = {(2,4), (2,6), (3,3),(3,6), (4,4)}
Then R-1 = {(4,2), (6,2), (3,3), (6,3), (4,4)}
The composition of two
relations
Let R be a relation from A to B and S be a relation
from B to C. The composition of R and S, denoted by
SoR , is the relation from A to C defined by
SoR = {(a, c) | (a, b) R
and (b, c) S for some b B}
Example: Let R is the relation from {1,2,3} to
{1,2,3,4} with R ={(1,1),(1,4),(2,3),(3,1),(3,4)}
and S is the relation from {1,2,3,4} to {0,1,2}
with S={(1,0),(2,0),(3,1),(3,2),(4,1)}.Find SoR.
Solution: SoR = {(1,0),(1,1),(2,1),(2,2),(3,0),(3,1)}.
Equivalence relations
A relation on a set A is called an equivalence relation if it
is reflexive, symmetric, and transitive
Example 1:
Consider relation R = { (a,b) | len(a) = len(b) }
on set of strings of English letters
Where len(a) means the length of string a
It is reflexive: len(a) = len(a)
It is symmetric: if len(a) = len(b), then len(b) = len(a)
It is transitive: if len(a) = len(b) and len(b) = len(c), then len(a) =
len(c)
Thus, R is a equivalence relation
Example 2: Let R be the relation on the set of real
numbers such that a R b iff a-b is an integer. Is R an
equivalence relation? (Ex!)
Equivalence relation example
Consider the relation R = { (a,b) | a ≡ b (mod m) }
Remember that this means that m | a-b
Called “congruence modulo m”
Is it reflexive: (a,a) R means that m | a-a
a-a = 0, which is divisible by m
Is it symmetric: if (a,b) R then (b,a) R
(a,b) means that m | a-b
Or that km = a-b. Negating that, we get b-a = -km
Thus, m | b-a, so (b,a) R
Is it transitive: if (a,b) R and (b,c) R then (a,c) R
(a,b) means that m | a-b, or that km = a-b
(b,c) means that m | b-c, or that lm = b-c
Adding these two, we get km+lm = (a-b) + (b-c)
Or (k+l)m = a-c or nm = a-c.
Thus, m divides a-c, where n = k+l
Thus, congruence modulo m is an equivalence relation
Examples:
Which of these relations on {0, 1, 2, 3} are equivalence relations?
Determine the properties of an equivalence relation that the others
lack
a) { (0,0), (1,1), (2,2), (3,3) }
Has all the properties, thus, is an equivalence relation
b) { (0,0), (0,2), (2,0), (2,2), (2,3), (3,2), (3,3) }
Not reflexive: (1,1) is missing
Not transitive: (0,2) and (2,3) are in the relation, but not (0,3)
c) { (0,0), (1,1), (1,2), (2,1), (2,2), (3,3) }
Has all the properties, thus, is an equivalence relation
d) { (0,0), (1,1), (1,3), (2,2), (2,3), (3,1), (3,2) (3,3) }
Not transitive: (1,3) and (3,2) are in the relation, but not (1,2)
e) { (0,0), (0,1) (0,2), (1,0), (1,1), (1,2), (2,0), (2,2), (3,3) }
Not symmetric: (1,2) is present, but not (2,1)
Not transitive: (2,0) and (0,1) are in the relation, but not (2,1)
Equivalence classes
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, the
subscript is often deleted, and [a] is used to denote
the equivalence class
Note that these classes are disjoint!
As the equivalence relation is symmetric
More on equivalence classes
Consider the relation R = { (a,b) | a mod a b mod 2 }
Thus, all the even numbers are related to each other
As are the odd numbers
The even numbers form an equivalence class
As do the odd numbers
The equivalence class for the even numbers is
denoted by [2] (or [4], or [784], etc.)
[2] = { …, -4, -2, 0, 2, 4, … }
2 is a representative of its equivalence class
There are only 2 equivalence classes formed by this
equivalence relation
More on equivalence classes
Consider the relation R = { (a,b) | a = b or
a = -b }
Thus, every number is related to additive inverse
The equivalence class for an integer a:
[7] = { 7, -7 }
[0] = { 0 }
[a] = { a, -a }
There are an infinite number of equivalence
classes formed by this equivalence relation
Partitions
Consider the relation R = { (a,b) | a b mod 2 }
This splits the integers into two equivalence classes: even
numbers and odd numbers
Those two sets of equivalence classes [0] and [1] together
form a partition of the integers
Formally, a partition of a set S is a collection of non-empty
disjoint subsets of S whose union is S
In this example, the partition is { [0], [1] }
Or { {…, -3, -1, 1, 3, …}, {…, -4, -2, 0, 2, 4, …} }
Exercise (Imp): What are the sets in the partition of the
integers arising from congruence modulo 4?
Other remarks and
Observations:
Which of the following are partitions of the set of integers?
a) The set of even integers and the set of odd integers
Yes, it’s a valid partition
b) The set of positive integers and the set of negative integers
No: 0 is in neither set
c) The set of integers divisible by 3, the set of integers leaving a
remainder of 1 when divided by 3, and the set of integers leaving a
remainder of 2 when divided by 3
Yes, it’s a valid partition
d) The set of integers less than -100, the set of integers with absolute
value not exceeding 100, and the set of integers greater than 100
Yes, it’s a valid partition
e) The set of integers not divisible by 3, the set of even integers, and the
set of integers that leave a remainder of 3 when divided by 6
The first two sets are not disjoint (2 is in both), so it’s not a valid partition
Partial Order relation:
Introduction
An equivalence relation is a relation that is reflexive,
symmetric, and transitive
A partial ordering (or partial order) is a relation that is
reflexive, antisymmetric, and transitive
Recall that antisymmetric means that if (a,b) and (b,a) R,
then b = a
Thus, (a,a) is allowed to be in R
But since it’s reflexive, all possible (a,a) must be in R
A set S with a partial ordering R is called a partially ordered
set, or poset
Denoted by (S,R) or (P,
)
Partial ordering examples
Show that ≥ is a partial order on the set of integers
It is reflexive: a ≥ a for all a Z
It is antisymmetric: if a ≥ b and b ≥ a then
b=a
It is transitive: if a ≥ b and b ≥ c, then a ≥ c
Note that ≥ is the partial ordering on the set of integers
(Z, ≥) is the partially ordered set, or poset.
Show that the inclusion relation is a partial
ordering relation on the power set of a set S.
(Exercise!) i.e. (P(S), ) is a poset.
Symbol usage
The symbol is used to represent any
partial order relation.
Not just the less than or equals to relation
Can represent ≤, ≥,, etc
Thus, a b denotes that (a,b) R
The poset is (S,)
The symbol is used to denote a b but a ≠
b
If represents ≥, then represents >
Comparability
The elements a and b of a poset (S,) are called
comparable if either a b or b a.
Meaning if (a,b) R or (b,a) R
It can’t be both because is antisymmetric
Unless a = b, of course
If neither a b nor b a, then a and b are
incomparable
Meaning they are not related to each other
If all elements in S are comparable, the relation
is a total ordering
Comparability examples
Let be the “divides” operator |
In the poset (Z+,|), are the integers 3 and 9
comparable?
Yes, as 3 | 9
Are 7 and 5 comparable?
No, as 7 | 5 and 5 | 7
Thus, as there are pairs of elements in Z+ that
are not comparable, the poset (Z+,|) is a
partial order, but not total ordered
Comparability examples
Let be the less than or equals operator ≤
In the poset (Z+,≤), are the integers 3 and 9
comparable?
Yes, as 3 ≤ 9
Are 7 and 5 comparable?
Yes, as 5 ≤ 7
As all pairs of elements in Z+ are comparable,
the poset (Z+,≤) is a total order
Also called as totally ordered poset, linearly ordered
set, chain, etc.
Well-ordered sets
(S,) is a well-ordered set if:
(S,) is a totally ordered poset
Every non-empty subset of S has a first element
Example: (Z,≤)
Is a total ordered poset (every element is comparable to
every other element)
It has no least element
Thus, it is not a well-ordered set
Example: (S,≤) where S = { 1, 2, 3, 4, 5 }
Is a total ordered poset (every element is comparable to
every other element)
Has a least element (1)
Thus, it is a well-ordered set
Lexicographic ordering
Consider two linearly ordered posets S and
T. Then the following order relation can be
defined on SxT :
(a,b) (a’,b’) if a<a’ or if a=a’ and b<b’.
This order can be extended to S1xS2x……Sn
as follows:
(a1,a2,……..an) (a’1,a’2,……a’n) if ai=a’i for
i= 1,2,…….k-1 and ak<a’k.
This order relation is called Lexicographic
ordering
Let R be a total ordering relation
on a set XX and 2 n
let P=
X ........ X (n 1,2.3,.......
Thenu1 , u2 ,.......u p S v1 , v2 ,......vq if any one of
the following holds:
1. u1, u2 ,.......u p v1, v2 ,......v p
2. u1 v1 andu1Rv1inX
3 i i and
u v
u v , i 1 , 2,......, k ( k P ),
k 1 k 1
and u
k 1 v
k 1
If none of these is satisfied, then
u1 , u2 ,.......uq S v1 , v2 ,......v p
Lexicographic ordering
A special case of lexicographic ordering is
used in English Dictionary
Let X={a,b,c,……z} and let R be a simple
ordering on X denoted by ≤ where
a ≤b ≤………. ≤z and P= XUX2UX3. Thus P
consists of all words or strings of 3 or fewer
than 3 letters from X. Let S be the
lexicographic ordering on P. Then we have
me S met by condition 1, bet S met by
Con.2 and beg S bet by Con.3.
How ‘go’ and ‘get’ are related?
Hasse Diagram
In the partial ordered (P,≤) an element
yєP is said to cover an element xєP if there
does not exist an element z єP such that
x ≤ z ≤ y i.e.
y covers x(x<y and (x≤z≤y=>x=z or z=y
A partial order relation ≤ on a set P can be
represented by means of a diagram known
as a Hasse diagram or partially ordered set
diagram of (P, ≤).
In such a diagram , each element is
represented by a small circle or a dot.
The circle for xєP is drawn below the circle for
y є P if x<y and a line is drawn if
y covers x. If x<y & x<z, but y is not related to
z, then y & z are connected with x by St.
lines. If x<y but y does not cover x, then x
and y are not connected directly by a single
line. However, they are connected through
one or more elements of P. It is possible to
obtain the set of ordered pairs in ≤ form a
diagram
Hasse Diagram
Example. Let P={1,2,3,4} and ≤be the relation
Consider the set P = {{ }, {a}, {a, b}, {a, b, c}} and the
relation ‘ ‘ on P
2
1
Hasse Diagram
For the poset ({1,2,3,4,6,8,12}, |)
Hasse Diagram
[Link] X={2, 3, 6, 12, 24, 36} and the relation
≤ be such that x ≤ y if x divides y. Draw Hasse
diagram of ( P, ≤).
[Link] A be a given finite set and
P(A) its power set. Let ‘contained in’ be partial
ordering relation on P(A). Draw Hasse diagram of
(P(A), ) when (i) A={a} {ii} A={a, b}
(iii) A ={a, b, c} (iv) A = {a, b, c, d }.
End of chapter 2.