Go backward to 3.2 TuplesGo up to 3 Sets, Relations, and FunctionsGo forward to 3.4 Functions as Sets |

AnRis a relation betweenS_{0}, ...,S_{n-1}: <=>RsubsetS_{0}x ... xS_{n-1}.

LetRis a relation of arityn(ann-ary relation) : <=>

existsS_0, ...,S_n-1:Ris a relation betweenS_0, ...,S_n-1;Ris ann-ary relation onS: <=>

RsubsetSx ... xS(cartesian product ofninstances ofS).Ris a relation onS: <=>Ris a 2-ary (binary) relation onS.

and read this asR(x_{0}, ...,x_{n-1}) : <=> <x_{0}, ...,x_{n-1}> inR.

A relation is thus the set-theoretic counterpart of a predicate; the notation

with the understanding that this is interpreted in the domain of sets asforallx:existsR: (forally:R(x,y) =>x=y)

whereforallx:existsR: (forally: <x,y> inR=>x=y)

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.

{<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

A graphical representation is that by a

x\y0 1 2 3 4 ... 0 falsetruetruetruetrue1 falsefalsetruetruetrue2 falsefalsefalsetruetrue3 falsefalsefalsefalsetrue4 falsefalsefalsefalsefalse...

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

domain(TheR) := {r_{0}:rinR}.

range(R) := {r_{1}:rinR}.

An equivalent characterization is given by the following law:

( forallx:xin domain(R) <=>existsy: <x,y> inR);( forally:yin range(R) <=>existsx: <x,y> inR).

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.

R^{-1}:= {<b,a>:ainA/\binB/\ <a,b> inR}.

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.

**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.

RoS:= {<a,c>:ain domain(R) /\cin range(S) /\( existsb: <a,b> inR/\ <b,c> inS)}.

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.

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:

( R^{-1})^{-1}=R;Ro (SoT) = (RoS) oT;( RoS)^{-1}=S^{-1}oR^{-1}.

We argue for the correctness of the first law.

(1) (Because of the definition of =, we have to showR^{-1})^{-1}=R.

(2)Take arbitraryforallr:rin (R^{-1})^{-1}<=>rinR.

- We prove
`r`in (`R`^{-1})^{-1}=>`r`in`R`. We assume(3)

and show`r`in (`R`^{-1})^{-1}`r`in`R`.We have

`R`subset`A`x`B`, therefore we know by definition of^{-1}that`R`^{-1}subset`B`x`A`and (`R`^{-1})^{-1}subset`A`x`B`. Thus we can find by (3) some`a`in`A`and`b`in`B`such that`r`= <`a`,`b`>. By definition of^{-1}, we have <`b`,`a`> in`R`^{-1}. Again, by definition of^{-1}, we know that <`a`,`b`> in`R`, therefore`r`in`R`. - The proof that
`r`in`R`=>`r`in (`R`^{-1})^{-1}proceeds in a similar way.

**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