**Table of Contents**

In this appendix we give a brief account of the most important notions and definitions used in the course material. We take the notion of a set as granted. We define set containment with the help of :

Two
sets are equal if they mutually contain each other. If is a set, a property of the elements of is
a subset of . If , then *P* also defines a property:
this is the set of elements such that . We denote
this property by . We define set theoretic operations as usual. That is,

and

Moreover, , where , and

We can define intersection and union in a more general setting. Let , that is, assume, for every , . Then

and

Let
*X*, *Y * and *Z* be sets. Then any set is called a binary
relation over . If , we say that *R* is a relation over *X*. If
and implies , then *R* is called a
function from *X* into *Y *, and is denoted by

We may write or instead of . The most widespread operations on relations are forming the inverse relation and the composition of relations. Let , and and . We define

and

We understand the composition of functions as relation composition. Observe that the composition of functions is again a function. In contrast to the usual notation for relation composition, we introduce a different notation for the compound relation.

That is, we read the relations taking part in a composition in an order differing from the conventional
one. In the rest of the section, if otherwise stated, we assume that *R* is a relation over a fixed set *X*. We
say that a relation

A partial order is a reflexive, transitive, antisymmetric relation. An equivalence is a reflexive, symmetric,
transitive relation. Let *R* be a relation. Let , and
for . Then the reflexive, transitive
closure of *R*, which is denoted by , is defined as

It is easy to check that *R* is reflexive, transitive and contains *R*. Moreover, *R* is the least such relation
which will be demonstrated in the next section together with the relation

where is the identity function on *X*.

Let , assume and . Then

and

are
the image of *A*, and the inverse image of *B* with respect to *R*, respectively. In a similar manner we can
talk about images and inverse images with respect to a function .
Moreover, a function is injective, if and
implies for every *x*, *y*, . *f * is surjective, if
. An injective and surjective function is a bijection. Let .
Then we apply the notation .