Summary Modelling Computing Systems Hoofdstuk 7 Faron Moller & Georg Struth

Hoofdstuk 7:

The truth set associated with a predicate P is the set: {x : P(x) holds}. We can also consider the truth
set associated with predicates that take more than one argument: {(x, y, z) : R(x, y, z) holds}. For
example:

R(x, y, z) might hold if and only if the customer with ID x ordered product y on the date z. The
corresponding truth set then defines a subset of the set CustomerID × ProductID × Date.

A relation R on A and B is a subset of a cartesian product A × B. We write R(a,b) or aRb if (a,b) ∈ R;
that is, a and b are related by R. Examples of relations:

- The less-than-or equals relation on numbers, x ⩽ 4
- The equality relation, x = y
- The ‘is-an-ancestor-of’ or the parenthood relation between humans.
- The ‘equivalent’ relation between programs, describing when two programs behave the
same.
- The propositionally equivalent relation between propositions.

Functions and relations are similar, but there are some important differences:

- Given a function f : A → B, we can construct the relation {(x, f(x) : x ∈ A}, sometimes referred
to as the graph of the function f.
- But not all relations are functions. For example, the ‘is-an-ancestor-of’ relation between me
and my ancestors is not a function. Each person has many different ancestors.
- A function f : A → B associates a value in B with each a ∈ A; in a relation each a ∈ A may be
associated with zero, one or many elements of B.
- Given a relation on A × B such that each a ∈ A is related to exactly one b ∈ B - this
determines a function f : A → B

A relation between two sets A and B is called a binary relation. Many familiar binary relations use an
infix operator: ⊆, =, ⇔, ⩽, … Given a relation R ⊆ A × B we sometimes refer to A as the source and B
as the target of R. When a relation R is a subset of A × A we sometimes call R a homogeneous
relation; When a relation R is a subset of A × B (for two different sets A and B) we call R a
heterogeneous relation.

On the right is a example of a relation. U can see this is not a function
because B doesn’t have a single number associated with it, and D has
multiple number associated with it. That’s why this is a relation and
not a function.

A × B is also a relation – every pair of elements (a,b) where a ∈ A and b
∈ B, is related. The empty set ∅ is also a subset of A × B – no two
elements are related. The equality relation on a set A is defined by {
(a,a) : a ∈ A}. For any relation R on A × B, we can define the inverse relation on B × A as follows: R −1
= {(b, a) : (a, b) ∈ R} For example, given the relation < ⊆ N × N, we can define the inverse relation on
B × A as follows: R −1 = {(b, a) : (a, b) ∈ R}.

, We can use familiar operations for manipulating sets to manipulate relations:

- a ⩽ b = (a < b) ∪ (a = b)
- Parent = Father ∪ Mother
- Son = Child ∩ Male

Given a relation R ⊆ A × B, we sometimes refer to the:

- the source of R is given by {a ∈ A : ∃b ∈ B (a, b) ∈ R}
- the target of R is given by {b ∈ B : ∃a ∈ A (a, b) ∈ R}

Properties of relations:

A relation is reflexive if R(x,x) for all x. Examples: 1. equality & 2. propositionally equivalent
formulas;
Non-examples: 1. x < y (where x and y are numbers); 2. The strict-subset relation on sets. 3. Is-a-
parent-of relation between people(no one is a parent of hisself).
If a relation R is ‘never reflexive’, that is, ∀x ¬(xRx) we call R irreflexive.

A relation is symmetric if R(x,y) implies R(y,x). Examples: 1. Equality, 2: propositionally equivalent
formulas, 3. The “is a sibling of relation(X is a brother of y, than y is a brother of x)”; Non-
examples: 1. x ⩽ y (where x and y are numbers); 2. The subset relation on sets. 3. The graph of the
sort function.

A relation is asymmetric if R(x,y) implies ¬R(y,x). Examples: 1. The < relation on numbers; 2. The
‘is-a-strict-prefix-of’ relation on strings. Example: when 4 < 5 then 5 ¬< 4.

A relation is antisymmetric if R(x,y) and R(y,x) implies x = y. Examples: 1. Equality; 2. ⩽ on natural
numbers; 3. ⊆ on sets. Non-examples: 1. Equivalence of propositional formulas. 2. The < relation
on numbers;

A relation is transitive if R(x,y) and R(y,z) implies R(x,z). Examples: 1. Subsets, equality,
comparison of numbers, prefixes of strings. If hell is a prefix of hello, and he is a prefix of hell.


We can compose relations. Given a relation R on A × B and a relation S on B × C, we can form the
composed relation R ◦ S on A × C as follows: R ◦ S = {(a, c) : there is some b ∈ B such that aRb ∧ bSc}.

If R is a relation on A × A:

- R is reflexive when it contains the equality relation, = ⊆ R
- R is symmetric when R −1 ⊆ R (or equivalently, when R ⊆ R −1 )
- R is transitive when R ◦ R ⊆ R

An equivalence relation is a relation that is:

- reflexive – R(x,x) for all x.
- symmetric – R(x,y) implies R (y,x)
- transitive – R(x,y) and R(y,z) implies R(x,z)

The canonical example of such a relation is equality.