COMP30026 Models of Computation – Binary Relations, and Functions
COMP30026 Models of Computation
Binary Relations, and Functions
Bach Le / Anna Kalenkova
Lecture Week 6 Part 2
Semester 2, 2021
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 1 / 19
This Lecture is Being Recorded
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 2 / 19
Binary Relations
A binary relation is a set of pairs, or 2-tuples.
“Being unifiable”, “<”, “⊆”, “divides” are all binary relations.
For small relations we can tabulate:
Beats Paper Scissors Rock
Paper 0 0 1
Scissors 1 0 0
Rock 0 1 0
We can express membership of a relation in many ways:
(x , y ) ∈ Beats, Beats(x , y ), or x Beats y .
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 3 / 19
Domain and Range of a Relation
The domain of R is dom(R) = {x | ∃y R(x , y )}.
The range of R is ran(R) = {y | ∃x R(x , y )}.
We say that R is a relation from A to B if dom(R) ⊆ A and
ran(R) ⊆ B . Or, R is a relation between A and B .
A relation from A to A is a relation on A.
“Being unifiable” is a relation on Term.
“<” is a relation on integers.
“⊆” is a relation on P(A).
“Acted in” is a relation between actors and films.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 4 / 19
Identity and Inverse
A× B is a relation—the full relation from A to B .
∅ is a relation.
∆A = {(x , x) | x ∈ A} is a relation on A—the identity relation.
If R is a relation from A to B then R−1 = {(b, a) | (a, b) ∈ R} is a
relation from B to A, called the inverse of R .
Clearly (R−1)−1 = R .
Since relations are sets, all the set operations, such as ∩ and ∪, are
applicable to relations.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 5 / 19
Properties of Relations
Let A be a non-empty set and let R be a relation on A.
R is reflexive iff R(x , x) for all x in A.
R is irreflexive iff R(x , x) holds for no x in A.
R is symmetric iff R(x , y )⇒ R(y , x) for all x , y in A.
R is asymmetric iff R(x , y )⇒¬R(y , x) for all x , y in A.
R is antisymmetric iff R(x , y ) ∧ R(y , x)⇒ x = y for all x , y in A.
R is transitive iff R(x , y ) ∧ R(y , z)⇒ R(x , z) for all x , y , z in A.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 6 / 19
Reflexive, Symmetric, Transitive Closures
Note that
1 The full relation is transitive.
2 Transitive relations are closed under intersection, that is, if R1
and R2 are transitive then so is R1 ∩ R2.
Together, these two properties tell us that for any binary relation R ,
there is a unique smallest transitive relation R+ which includes R .
We call R+ the transitive closure of R .
Similarly we have the (unique) reflexive closure and the (unique)
symmetric closure of R .
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 7 / 19
Closures Quiz
What is the reflexive, transitive closure of R = {(n, n + 1) | n ∈ N}?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 8 / 19
Closures Quiz
What is the reflexive, transitive closure of R = {(n, n + 1) | n ∈ N}?
What is the symmetric closure of < on Z?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 8 / 19
Composing Relations
Let R1 and R2 be relations on A. The composition R1 ◦ R2 is the
relation on A defined by
(x , z) ∈ (R1 ◦ R2) iff ∃y (R1(x , y ) ∧ R2(y , z))
The n-fold composition Rn is defined by
R1 = R
Rn+1 = Rn ◦ R
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 9 / 19
Composition Quiz
If R is {(0, 2), (0, 3), (1, 0), (1, 3), (2, 0), (2, 3)}, what is R2?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 10 / 19
Composition Quiz
If R is {(0, 2), (0, 3), (1, 0), (1, 3), (2, 0), (2, 3)}, what is R2?
What is R3?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 10 / 19
Composition Quiz
If R is {(0, 2), (0, 3), (1, 0), (1, 3), (2, 0), (2, 3)}, what is R2?
What is R3?
If R is < on N, what is R2?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 10 / 19
Transitive Closure Again
The transitive closure of R can be defined in terms of union and
composition:
R
+ =
⋃
n≥1
R
n
R
+ = R ∪ R2 ∪ R3 . . .
(x , y ), (y , z) ∈ R , and hence (x , y ), (y , z) ∈ R+, but since R+ is
transitive, (x , z) ∈ R+ (R2 gives us all such pairs)
(x , z) ∈ R2, (z ,w) ∈ R , and hence (x , z), (z ,w) ∈ R+, but since R+
is transitive, (x ,w) ∈ R+ (R3 gives us all such pairs)
The reflexive, transitive closure is
R
∗ = R+ ∪∆A
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 11 / 19
Equivalence Relations
A binary relation which is reflexive, symmetric and transitive is an
equivalence relation.
The identity relation ∆A is the smallest equivalence relation on a set
A. The full relation A2 is the largest equivalence relation on A.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 12 / 19
Quiz: Equivalence Relations?
Which of these binary relations are equivalence relations?
≤ on Z?
≡m on Z, where a ≡m b iff a mod m = b mod m?
“are unifiable” on the set of terms (over some alphabet)?
{(a, b) | |a − b| ≤ 3}?
“are compatriots” on the set of all people?
“are logically equivalent” on the set of propositional formulas?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 13 / 19
Partial Orders
R is a pre-order iff R is transitive and reflexive.
R is a strict partial order iff R is transitive and irreflexive.
R is a partial order iff R is an antisymmetric preorder.
R is linear iff R(x , y ) ∨ R(y , x) ∨ x = y for all x , y in A.
A linear partial order is also called a total order.
In a total order, every two elements from A are comparable.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 14 / 19
Quiz: Partial Orders?
Which of these binary relations are partial orders?
The relation ≤ on N?
The relation ⊆ on P(N)?
The relation “divides” on N?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 15 / 19
Functions
A function f is a relation with the property that
(x , y ) ∈ f ∧ (x , z) ∈ f ⇒ y = z . That is, for x ∈ dom(f ), there is
exactly one y ∈ ran(f ) such that (x , y ) ∈ f . We write this: f (x) = y .
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 16 / 19
Domains and Co-Domains
We say that the function f is from X to Y , or
f : X → Y
if dom(f ) = X (total function) and ran(f ) ⊆ Y . We call Y the
co-domain of f .
Example: The range of the factorial function is {1, 2, 6, 24, 120, . . .},
but we normally define it as having co-domain N.
The domain/co-domain specification is integral to the function
definition, as we define functions f : X → Y and f ′ : X ′ → Y ′ to be
equal iff X = X ′, Y = Y ′, and for all x ∈ X , f (x) = f ′(x).
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 17 / 19
Injections, Surjections and Bijections
A function f : X → Y is
surjective (or onto) iff ran(f ) equals the co-domain of f .
injective (or one-to-one) iff f (x) = f (y )⇒ x = y .
bijective iff it is both surjective and injective.
X Y
×
×
×
×
×
×
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 18 / 19
Examples
f : Z → Z defined by f (n) = n2 is neither surjective nor injective.
g : Z → N defined by g(n) = |n| is surjective but not injective.
s : N → N defined by s(n) = n + 1 is injective but not surjective.
d : Z → N defined by
d(n) =
{
2n − 1 if n > 0
−2n if n ≤ 0
is bijective. It establishes a one-to-one mapping between Z and N.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 19 / 19
Function Composition
The composition of f : X → Y and g : Y → Z is the function
g ◦ f : X → Z defined by
(g ◦ f )(x) = g(f (x))
We assume that g ’s domain coincides with f ’s co-domain, although
the composition makes sense as long as ran(f ) ⊆ dom(g).
Note the unfortunate inconsistency with the use of ◦ for composing
relations. For functions, g ◦ f is best read as “g after f .”
◦ is associative, and for f : X → Y , f ◦ 1X = 1Y ◦ f = f , where
1X : X → X is the identity function on X .
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 20 / 19