Appendix A. Mathematical background

Table of Contents

Sets and relations
Complete partial orders and fixpoint theorems

Sets and relations

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,


Moreover, , where , and

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


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


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.

Notation 135. Let and . Then

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


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 .