Relations and Functions

Relations

Binary Relation

A binary relation over sets and is a set of ordered pairs of elements from and :The statement reads ” is -related to ” and is written as .

Homogeneous Relation

A homogeneous relation on a set is a binary relation between and itself, i.e. it is a subset of .

Reflexivity

A homogeneous relation on a set is reflexive if it relates every element of to itself. That is .

Symmetry

A homogeneous relation on a set is symmetric if .

Antisymmetry

A homogeneous relation on a set is antisymmetric if there is no pair of distinct elements of each of which is related by to the other. Formally, is antisymmetric if for all , Equivalently,

Transitivity

A homogeneous relation on a set is transitive if, for all elements in , whenever relates to and to , then also relates to .

Connectedness

A homogeneous relation on a set is connected if for all : It is called strongly connected if or for all no matter if they are equal.

Univalent

For all and with relation , if and implies , we say is univalent.

Serial

We say defined on and is serial or total if for all , there exists some such that .

Equivalence Relation

Equivalence Relation

An equivalence relation is a relation on a set, generally denoted by , that is reflexive, symmetric, and transitive for everything in the set.

• Reflexivity:
• Symmetry:
• Transitivity:

e.g. The relation “is equal to”, denoted , is an equivalence relation on the set .

Equivalence Class

Given an equivalence relation defined on set , the equivalence class of an element is defined by

Proposition

Suppose some equivalence relation is defined on set , then every element is exactly in one of the equivalence classes.

Proof Suppose and . Then we have and , it follows that , hence , yielding that .

Quotient

The set of all equivalence classes in with , is called the quotient of by :

Function and Associated Sets

Function

Let and be two sets. A function is a relation that is univalent and serial defined over and . The sets and are called the domain and codomain of respectively.

Range

For some function , the range is the set

Graph

The following set is called the graph of a function :

Image

Given a subset , its image under is defined by

Preimage

Given a subset , its inverse image or preimage under is defined by

Proposition

Let be a function. For any set and there hold

Proof For any , , thus . For any , for some , thus .

Proposition

Suppose . For any family of sets in there hold

Proof By definition, for all , for some . Thus for some . It follows that . All statements above are reversible, thus we have equality holds: . Consider any , then for some . It follows that for all , hence for all . Thus .

Proposition

Suppose . For any family of sets in there hold

Proof For any , , thus for some . It follows that and hence . All statements above are reversible, thus we have equality holds: . Consider any , then , it follows that for all . Thus for all , hence . Conversely, for any , for all , thus for all , hence . That is .

Composition and Inverse

Composition

Let and be two functions. Then the function defined byis called the composition of and .

Injection, Surjection and Bijection

Let be a function,

• is called injective or one-one if implies .
• is called surjective or onto if , i.e. for every there is such that .
• is called bijective if is both injective and surjective.

Proposition

If a set is finite, then a function is injective if and only if it is surjective.

Proof Suppose is injective. Assume is not surjective, then there exists such that . Because is finite, by the pigeonhole

Invertible Function

A function is invertible if there is a function such thatWe will call the inverse of and denote it as .

Theorem

A function is invertible if and only if it is bijective.

Proof Assume is invertible and denotes its inverse function. If , then which shows that f is injective. Next, for any , we have which means is surjective. Thus is bijective. Conversely, if is bijective, then for any there is one and only one such that . Define by which is well-defined. Moreover and which shows that f is invertible and .