Discrete Structures

CSC 203
Department of Computer Sciences

Akinsola, JET Ph.D.

Relations

2
 Outline
What is a relation
Representing Relations
Mapping
Relation Inverse
Relations Versus Functions
Relation properties
Combining Relations

3
Introduction

How about some definitions?

The domain is the set of 1st
coordinates of the ordered pairs.
The range is the
set of 2nd coordinates of the
ordered pairs.
A relation is a
set of ordered pairs.
4
 What is a relation?
Let A and B be sets. A binary relation R is a subset of
AB
Example
◼ Let A be the students in the CS major

◼ A = {Alice, Bob, Claire, Dan}

◼ Let B be the courses the department offers

◼ B = {CS101, CS201, CS202}

◼ We specify relation R = A  B as the set that lists all students

a  A enrolled in class b  B
◼ R = { (Alice, CS101), (Bob, CS201), (Bob, CS202),
(Dan, CS201), (Dan, CS202) }

5
 Representing relations

We can represent
We can represent relations in a table:
relations graphically:
CS101 CS201 CS202

Alice X
Bob X X
Claire
Dan X X

Not valid functions!

6
 Ways to show relation?
The relation {(2,1), (-1,3), (0,4)} can be shown by
x y
1) a table. 2 1
-1 3
0 4

2) a mapping. 2 1
-1 3
0 4
3) a graph.

7
Examples
Given the relation
{(3,2), (1,6), (-2,0)}, find the domain and range.
Domain = {3, 1, -2}
Range = {2, 6, 0}
What would this be?

{(2,4), (3,-1), (0,-4)}

A bad relationship!! Ha! Ha! 8

 More relation examples
Another relation example:
◼ Let A be the cities in the US
◼ Let B be the states in the US
◼ We define R to mean a is a city in state b
◼ Thus, the following are in our relation:
◼ (C’ville, VA)
◼ (Philadelphia, PA)
◼ (Portland, MA)
◼ (Portland, OR)
◼ etc…
Write a relation of cities and states in Nigeria where:
◼ Let C be the cities
◼ Let D be the states
Most relations we will see deal with ordered pairs of
integers 9
 Example

Given the following table, show the relation,

domain, range, and mapping.
x -1 0 4 7
y 3 6 -1 3

Relation = {(-1,3), (0,6), (4,-1), (7,3)}

Domain = {-1, 0, 4, 7}
Range = {3, 6, -1, 3}

10
 Mapping
x -1 0 4 7
y 3 6 -1 3
-1
3
0
6
4
-1
7
You do not need to write 3 twice in the range!
11
 Class Activity
What is the domain of the relation
{(2,1), (4,2), (3,3), (4,1)}
1. {2, 3, 4, 4} X
2. {1, 2, 3, 1}
3. {2, 3, 4}
4. {1, 2, 3}
5. {1, 2, 3, 4}

Answer Now
12
 Class Activity
What is the range of the relation
{(2,1), (4,2), (3,3), (4,1)}
1. {2, 3, 4, 4}
2. {1, 2, 3, 1}
3. {2, 3, 4}
4. {1, 2, 3}
5. {1, 2, 3, 4}

Answer Now
13
 Relation Inverse
Inverse of a Relation: For every ordered pair
(x,y) there must be a (y,x).
Write the relation and the inverse.

-1 -6
3 -4
4 2
Relation = {(-1,-6), (3,-4), (3,2), (4,2)}
Inverse = {(-6,-1), (-4,3), (2,3), (2,4)} 14
 Class Activity
Write the inverse of the mapping.
4
3
-3
-1
2
1. {(4,-3),(2,-3),(3,-3),(-1,-3)}
2. {(-3,4),(-3,3),(-3,-1),(-3,2)}
3. {-3} Answer Now
4. {-1, 2, 3, 4} 15
Relations vs. functions

Not all relations are functions

But consider the following function:
a 1
b 2
c 3
d 4

All functions are relations!

16
 Relations vs. functions
When to use which?
A function is used when you need to obtain a
SINGLE result for any element in the domain
◼ Example: sin, cos, tan

A relation is when there are multiple

mappings between the domain and the co-
domain
◼ Example: students enrolled in multiple courses

17
 Relations on a set
A relation on the set A is a relation from A to A
◼ In other words, the domain and co-domain are the same set

◼ We will generally be studying relations of this type

Let A be the set { 1, 2, 3, 4 }

Which ordered pairs are in the relation R = { (a,b) | a divides b }
R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4) }

R 1 2 3 4
1 X X X X
2 X X
3 X
4 X
18
 More examples
Consider some relations on the set Z
Are the following ordered pairs in the relation?

(1,1) (1,2) (2,1) (1,-1) (2,2)

R1 = { (a,b) | a≤b } X X X
R2 = { (a,b) | a>b } X X
R3 = { (a,b) | a=|b| } X X X
R4 = { (a,b) | a=b } X X
X
R5 = { (a,b) | a=b+1 }
X X X X
R6 = { (a,b) | a+b≤3 }
19
 Relation properties

Six properties of relations we will study:

◼ Reflexive
◼ Irreflexive

◼ Symmetric

◼ Asymmetric

◼ Antisymmetric

◼ Transitive

20
 Reflexivity

A relation is reflexive if every element is

related to itself
◼ Or, (a,a)R

Examples of reflexive relations:

◼ =, ≤, ≥

Examples of relations that are not reflexive:

◼ <, >
21
 Irreflexivity
A relation is irreflexive if every element is not related
to itself
◼ Or, (a,a)R
◼ Irreflexivity is the opposite of reflexivity

Examples of irreflexive relations:

◼ <, >

Examples of relations that are not irreflexive:

◼ =, ≤, ≥

22
 Reflexivity vs. Irreflexivity
A relation can be neither reflexive nor
irreflexive
◼ Some elements are related to themselves, others
are not
We will see an example of this later on

23
 Symmetry
A relation is symmetric if, for every (a,b)R,
then (b,a)R A= {(2,3), (4.5), (3,2)}
B= {(5,6),(2,3)
Examples of symmetric relations:
◼ =, isTwinOf()

Examples of relations that are not symmetric:

◼ <, >, ≤, ≥

24
 Asymmetry
A relation is asymmetric if, for every (a,b)R,
then (b,a)R
◼ Asymmetry is the opposite of symmetry

Examples of asymmetric relations:

◼ <, >

Examples of relations that are not asymmetric:

◼ =, isTwinOf(), ≤, ≥
25
 Antisymmetry
A relation is antisymmetric if, for every (a,b)R,
then (b,a)R is true only when a=b
◼ Antisymmetry is not the opposite of symmetry

Examples of antisymmetric relations:

◼ =, ≤, ≥

Examples of relations that are not antisymmetric:

◼ <, >, isTwinOf()

26
 Notes on *symmetric relations

A relation can be neither symmetric or

asymmetric
◼ R = { (a,b) | a=|b| }
◼ This is not symmetric
◼ -4 is not related to itself
◼ This is not asymmetric
◼ 4 is related to itself
◼ Note that it is antisymmetric

27
 Transitivity
A relation is transitive if, for every (a,b)R
and (b,c)R, then (a,c)R

If a < b and b < c, then a < c

◼ Thus, < is transitive

If a = b and b = c, then a = c
◼ Thus, = is transitive

28
 Transitivity examples
Consider isAncestorOf()
◼ Let Alice be Bob’s parent, and Bob be Claire’s parent
◼ Thus, Alice is an ancestor of Bob, and Bob is an ancestor of
Claire
◼ Thus, Alice is an ancestor of Claire
◼ Thus, isAncestorOf() is a transitive relation

Consider isParentOf()
◼ Let Alice be Bob’s parent, and Bob be Claire’s parent
◼ Thus, Alice is a parent of Bob, and Bob is a parent of Claire
◼ However, Alice is not a parent of Claire
◼ Thus, isParentOf() is not a transitive relation

29
 Relations of relations summary

= < > ≤ ≥

Reflexive X X X

Irreflexive X X

Symmetric X

Asymmetric X X

Antisymmetric X X X

Transitive X X X X X
30
 Combining relations

There are two ways to combine relations R1

and R2
◼ Via Boolean operators
◼ Via relation “composition”

31
 Combining relations via Boolean operators
Consider two relations R≥ and R≤
We can combine them as follows:
◼ R≥ U R≤ = all numbers ≥ OR ≤
◼ That’s all the numbers
◼ R≥ ∩ R≤ = all numbers ≥ AND ≤
◼ That’s all numbers equal to
◼ R≥  R≤ = all numbers ≥ or ≤, but not both
◼ That’s all numbers not equal to
◼ R≥ - R≤ = all numbers ≥ that are not also ≤
◼ That’s all numbers strictly greater than
◼ R≤ - R≥ = all numbers ≤ that are not also ≥
◼ That’s all numbers strictly less than
Note that it’s possible the result is the empty set
32
 Combining relations via relational composition

Let R be a relation from A to B, and S be a

relation from B to C
◼ Let a  A, b  B, and c  C
◼ Let (a,b)  R, and (b,c)  S

◼ Then the composite of R and S consists of the

ordered pairs (a,c)
◼ We denote the relation by S ◦ R
◼ Note that S comes first when writing the composition!

33
 Combining relations via relational composition
Let M be the relation “is mother of”
Let F be the relation “is father of”
What is M ◦ F?
◼ If (a,b)  F, then a is the father of b
◼ If (b,c)  M, then b is the mother of c
◼ Thus, M ◦ F denotes the relation “maternal grandfather”
What is F ◦ M?
◼ If (a,b)  M, then a is the mother of b
◼ If (b,c)  F, then b is the father of c
◼ Thus, F ◦ M denotes the relation “paternal grandmother”
What is M ◦ M?
◼ If (a,b)  M, then a is the mother of b
◼ If (b,c)  M, then b is the mother of c
◼ Thus, M ◦ M denotes the relation “maternal grandmother”
Note that M and F are not transitive relations!!!
34
 Combining relations via relational composition

Given relation R
◼ R ◦ R can be denoted by R2
◼ R2 ◦ R = (R ◦ R) ◦ R = R3

◼ Example: M3 is your mother’s mother’s mother

35