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 / 28
This Lecture is Being Recorded
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 2 / 28
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 / 28
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 / 28
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 / 28
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 / 28
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 / 28
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 / 28
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 / 28
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 / 28
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 / 28
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 / 28
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 / 28
Transitive Closure Again
The transitive closure of R can be defined in terms of union and
composition:
R
+ =
⋃
n≥1
R
n
The reflexive, transitive closure is
R
∗ =
⋃
n≥0
R
n = R+ ∪∆A
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 11 / 28
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 / 28
Quiz: Equivalence Relations?
Which of these binary relations are equivalence relations?
≤ on Z?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 13 / 28
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?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 13 / 28
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)?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 13 / 28
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}?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 13 / 28
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?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 13 / 28
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 / 28
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 / 28
Quiz: Partial Orders?
Which of these binary relations are partial orders?
The relation ≤ on N?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 15 / 28
Quiz: Partial Orders?
Which of these binary relations are partial orders?
The relation ≤ on N?
The relation ⊆ on P(N)?
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 15 / 28
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 / 28
Functions
Mathematically: 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 .
Computationally: A prescription (an algorithm) for how to
calculate output values from input values.
Note that a function-as-a-relation may be infinite, but we assume
that an “algorithm” is finite.
The question of how to define “algorithm” is central to computability
theory—we won’t venture into that territory just yet.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 16 / 28
The Two Views Contrasted
The three Haskell functions defined by
f0 n = n^2 + n
f1 n = n * (n+1)
f2 n = if n == 0 then 0 else 2*n + f2 (n-1)
all prescribe calculations of the (mathematical) function
{(0, 0), (1, 2), (2, 6), (3, 12), . . .} = {(n, n2 + n) | n ∈ N}
But note that there is no Haskell type corresponding to N, and the
functions do not behave identically if applied to a negative integer.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 17 / 28
Domains and Co-Domains
We say that the function f is from X to Y , or
f : X → Y
if dom(f ) = X 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 18 / 28
Recurrences versus Closed Forms
The definition of f2 above is given as a recurrence formula—to
define f2, we refer back to f2 itself!
The definition of (the equivalent) f1 does not depend (directly or
indirectly) on f1 itself. We say that the definition is in closed form.
Computationally, and also for readability, a closed form definition is
usually preferable—though not always possible to find.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 19 / 28
Images and Co-Images
Let A ⊆ X , B ⊆ Y , and consider f : X → Y .
f [A] = {f (x) | x ∈ A} is the image of A under f .
f −1[B] = {x ∈ X | f (x) ∈ B} is the co-image of B under f .
Consider the relation f = {(1, 2), (2, 3), (3, 5), (4, 3), (5, 2)}.
f is a function with domain D = {1, 2, 3, 4, 5} and range {2, 3, 5}.
We could take N to be the co-domain and write f : D → N.
Let A = {2, 5}. We have:
f [A] = {2, 3}
f −1[A] = {1, 3, 5}
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 20 / 28
Injections, Surjections and Bijections
A function f : X → Y is
surjective (or onto) iff f [X ] = Y .
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 21 / 28
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 22 / 28
Examples
h : N2 → N defined by
h(m, n) =
(m + n)2 + 3m + n
2
is bijective. It establishes a one-to-one mapping between N2 and N.
The last two examples are interesting, because they show that, in a
precise sense, there are no more integers than there are natural
numbers, and similarly there are no more pairs of natural numbers
than there are natural numbers.
Bijections will play a central role when we get to computability theory.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 23 / 28
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 24 / 28
Function Composition
Let f : X → Y and g : Y → Z . It is easy to show that
g ◦ f injective ⇒ f injective;
g ◦ f surjective ⇒ g surjective;
g , f injective ⇒ g ◦ f injective;
g , f surjective ⇒ g ◦ f surjective.
Models of Computation (Sem 2, 2021) Binary Relations © University of Melbourne 25 / 28