Functions, Relations and Their

Properties

1
 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 class
• A = {Alice, Bob, Claire, Dan}
– Let B be the courses the NIBM 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) }

2
 Representing relations
We can represent We can represent
relations graphically: relations in a table:
CS101 CS201 CS202
Alice
CS101
Alice X
Bob Bob X X
CS201
Claire
Claire
Dan X X
CS202
Dan

Not valid functions!

3
 What is a function?
According to the textbook, “a
function is…a relation in which
every input is paired with
exactly one output”

4
 Is a relation a function?
•Focus on the x-coordinates, when given a relation

If the set of ordered pairs have different x-coordinates,

it IS A function

If the set of ordered pairs have same x-coordinates,

it is NOT a function

•Y-coordinates have no bearing in determining

functions

5
 Example
{(0, −5),(1, −4),(2, −3),(3, −2),(4, −1),(5, 0)}

•Is this a function?

•Hint: Look only at the x-coordinates

YES

6
 Example
{(–1, −7),(1, 0),(2, −3),(0, −8),(0, 5),(–2, −1)}

•Is this a function?

•Hint: Look only at the x-coordinates

NO

7
 Example
Which mapping represents a function?

Choice One Choice Two

3 –1 2 2
1 2 –1 3
0 3 3 –2
0

Choice 1
8
 Example 6
Which mapping represents a function?

A. B.

B
9
 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!

10
 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

11
 Review
• A relation between two variables x and y is a
set of ordered pairs
• An ordered pair consist of a x and y-
coordinate
– A relation may be viewed as ordered pairs,
mapping design, table, equation, or written in
sentences
• x-values are inputs, domain, independent
variable
• y-values are outputs, range, dependent
variable

12
 Example 1

{(0, −5),(1, −4),(2, −3),(3, −2),(4, −1),(5, 0)}

•What is the domain?

{0, 1, 2, 3, 4, 5}
What is the range?
{-5, -4, -3, -2, -1, 0}
5/9/2020 3:39 PM 1-6 Relations and Functions 13
 Example 2

Input 4 –5 0 9 –1

Output –2 7

•What is the domain?

{4, -5, 0, 9, -1}
•What is the range?
{-2, 7}
5/9/2020 3:39 PM 1-6 Relations and Functions 14
 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

15
 Relations on a set
• 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) }

1 1 R 1 2 3 4
1 X X X X
2 2
2 X X
3 3 3 X
4 X
4 4 16
 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 }
• R2 = { (a,b) | a>b } X X X
• R3 = { (a,b) | a=|b| } X X
• R4 = { (a,b) | a=b } X X X
• R5 = { (a,b) | a=b+1 }
X X
• R6 = { (a,b) | a+b≤3 }
X
X X X X

17
 Relation properties
• Six properties of relations we will study:
– Reflexive
– Irreflexive
– Symmetric
– Asymmetric
– Antisymmetric
– Transitive

18
 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:

– <, >

19
 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:

– =, ≤, ≥

20
 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

21
 Symmetry
• A relation is symmetric if, for every (a,b)R, then (b,a)R

• Examples of symmetric relations:

– =, isTwinOf()

• Examples of relations that are not symmetric:

– <, >, ≤, ≥

22
 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(), ≤, ≥
23
 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()
24
 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

25
 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

26
 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

27
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
28