previous up next
Go backward to 3.2 Tuples
Go up to 3 Sets, Relations, and Functions
Go forward to 3.4 Functions as Sets
 RISC-Linz logo

3.3 Predicates as Sets

The language of first order predicate logic introduced in Chapter Logic provides variables that represent objects of the considered domain; a variable may not stand for a predicate or a function. Consequently, we cannot state propositions like "for all predicates p" or "there is a function f", which is necessary in a lot of situations. Set theory however provides means to represent predicates and functions as sets, such that we can talk about "higher order objects" (predicates and functions) in a first order framework (using the domain of sets).

Definition 24 (Relation) A  relation (Relation, Beziehung) is a subset of a Cartesian product:
R is a relation between S0, ..., Sn-1 : <=> R subset S0 x ... x Sn-1.
An n-ary relation is a subset of a Cartesian product of n sets:
R is a relation of arity n (an n-ary relation) : <=>
   exists S_0, ..., S_n-1: R  is a relation between  S_0, ..., S_n-1;
R is an n-ary relation on S : <=>
   R subset S x ... x S (cartesian product of n instances of S).
R is a relation on S : <=> R is a 2-ary ( binary) relation on S.
Let R be an n-ary relation. We define the (n+1)-ary predicate
R(x0, ..., xn-1) : <=> <x0, ..., xn-1> in R.
and read this as R  holds on (ist gültig für) x0, ..., xn-1. If R is a binary relation, we may write this as x0 R x1.
A relation is thus the set-theoretic counterpart of a predicate; the notation R(x0, ..., xn-1) is convenient to hide the distinction between relations and predicate constants. We may now quantify over "predicates" as in
forall x: exists R: (forall y: R(x,y) => x=y)
with the understanding that this is interpreted in the domain of sets as
forall x: exists R: (forall y: <x,y> in R => x=y)
where R represents a relation, i.e., a set.

Example  Take the relation R := {<x, y>: x in N /\  y in N /\  x <= y} on the natural numbers N. R is also a relation on the integer numbers Z, because N subset Z.

Take S := {<x, x/2>: x in N}. S is a relation between N and Q (the set of all rational numbers) and it is also a relation on Q; however, it is not a relation on N (because 1/2 not  in N).

The empty set 0 is a relation on every set S.

Logic Evaluator  We define the predicates Relation(R) (R is a relation), isRelation(R, A, B) (R is a relation between A and B) as shown below:

Relations can be represented in various forms.

Example  Take the relation R := {<x, y>: x in N /\  y in N /\  x < y < 5}. It may be represented by enumerating its elements
{<0, 1>, <0, 2>, <0, 3>, <0, 4>, <1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>, <3, 4>}.
Another representation is a truth matrix where an entry true for <x, y> indicates x R y (all entries not shown are false):
x\y 0 1 2 3 4 ...
0 false true true true true
1 false false true true true
2 false false false true true
3 false false false false true
4 false false false false false
...
A graphical representation is that by a directed graph where an arrow x -> y indicates x R y:

We now introduce a notion by which we can denote those values that are affected by a relation.

Definition 25 (Domain, Range) Let R be a binary relation. The   domain (Definitionsbereich) of R is the set of all first components of the tuples in R:
domain(R) := {r0: r in R}.
The  range (Wertebereich) of R is the set of all second components of the tuples in R:
range(R) := {r1: r in R}.

An equivalent characterization is given by the following law:

Proposition 29 (Domain, Range) Let R be a binary relation. Then
(forall x: x in  domain(R) <=> exists y: <x, y> in R);
(forall y: y in  range(R) <=> exists x: <x, y> in R).

Example  Take the relation R := {<0, 0>, <0, 1>, <0, 2>, <1, 2>}. We have domain(R) = {0, 1} and range(R) = {0, 1, 2}.

For the empty relation, we have domain(0) = range(0) = 0.

Logic Evaluator  The functions domain and range are defined as shown in the corresponding mathematical definitions:

The order of elements in a binary relation can be inverted.

Definition 26 (Inverse of a Relation) Let R subset A x B. The  inverse of R is the following relation between B and A:
R-1 := {<b, a>: a in A /\  b in B /\  <a, b> in R}.

Above definition uses the notion R subset A x B to denote that R is a binary relation between A and B (as is common mathematical practice). The clause a in A /\  b in B is only added to make the set quantifier conform to the syntax given here.

Example  Take the relation R := {<0, 0>, <0, 1>, <0, 2>, <1, 2>}. We have R-1 = {<0, 0>, <1, 0>, <2, 0>, <2, 1>}.

Logic Evaluator  We can define the function ^-1(R) (i.e., R-1) as shown below:

Two relations may be combined via an intermediate set to form another relation.

Definition 27 (Composition of Relations) Let R subset A x B and S subset B x C. The  composition (Verknüpfung, Produkt) of R and S is the following relation between A and C:
R o S := {<a, c>: a in domain(R) /\  c in range(S) /\ 
   (exists b: <a, b> in R /\  <b, c> in S)}.

The clause a in A /\  c in C may be omitted in above definition; it is only used to make the set quantifier conform to the syntax given here.

Example  The composition of relations R subset A x B and S subset B x C can be visualized by the composition of arrows:

An arrow between an element of A and an element of C exists only if there exist two arrows that are correspondingly connected via some intermediate point in B.

Logic Evaluator  We can define o(R, S) (i.e, R o S) as follows:

Proposition 30 (Relation Laws) For every A, B, C, D and every R subset A x B, S subset B x C, and T subset C x D, we have:
(R-1)-1 = R;
R o (S o T) = (R o S) o T;
(R o S)-1 = S-1 o R-1.

We argue for the correctness of the first law.

Proof  Take arbitrary A, B and R subset A x B. We prove
(1) (R-1)-1 = R.
Because of the definition of =, we have to show
(2) forall r: r in (R-1)-1 <=> r in R.
Take arbitrary r.

Logic Evaluator  We may test whether our definitions of inversion and composition of relations conform to these laws:

Author: Wolfgang Schreiner
Last Modification: October 4, 1999
previous up next