Definition 1. Binary relation on set A is a set R  A × A.
* R is reflexive  for all a  A holds (a, a)  R
* R is symmetric  for all a, b  A holds: if (a, b)  R, then (b, a)  R
* R is transitive  for all a, b, c  A holds: if (a, b), (b, c)  R, then (a, c)  R
* R is an equivalence relation  R is reflexive, symmetric and transitive
Exercise 1
Give an example of a set A and a binary relation R on A such that
1. R is reflexive and symmetric, but not transitive.
2. R is reflexive and transitive, but not symmetric.
3. R is symmetric and transitive, but not reflexive.
Exercise 2
Let R, S  A × A be equivalences on A. Prove or disprove the following statements:
1. R  S is equivalence relation.
2. R  S is equivalence relation.
3. R \ S is equivalence relation.
Exercise 3
Prove or disprove the following statement: If R, S  A × A are equivalence relations on A, then R  S
is equivalence.
Exercise 4
How many equivalence relations on  exist?
Definition 2. Function from the set A to the set B is a relation f  A × B satisfying the following. For
all a  A there is exactly one b  B cush that (a, b)  f.
We write f : A  B and we also use f(a) = b instead of (a, b)  f.
1. f : A  B is injective  for all a, b  A such that a = b we have f(a) = f(b).
2. f : A  B is surjective  for all b  B there is a  A such that f(a) = b.
3. f : A  B is bijective  f is both injective and surjective.
Exercise 5
Let f : A  B be a function. Prove that f is injective iff there is g : B  A such that g  f = idA
(idA(a) = a for all a  A).
Definition 3. Let R  A × A be a relation on A.
* R is antisymmetric  for all a, b  A the following holds: if (a, b), (b, a)  R, then a = b
* R is an ordering  R is reflexive, transitive and antisymmetric.
We write aRb instead of (a, b)  R.
Definition 4. Ordered set is a tuple (A, ) where A is a set and  A × A is an ordering on A.
1
Two ordered sets (A, ) and (B, ) are isomorphic iff there is a bijection f : A  B such that for all
a, b  A we have a b  f(a) f(b).
Exercise 6
Find two ordering and on N0 = {0, 1, . . .} such that (N0, ) and (N0, ) are not isomorphic.
Exercise 7
Find infinitely many orderings 0, 1, . . . on N0 such that for all i = j the ordered sets (N0, i) and
(N0, j) are not isomorphic.
Exercise 8
Let U be an uncountable set. Find an ordering s on N0 for each s  U such that for any s1, s2  U
satisfying s1 = s2 the ordered sets (N0, s1
) and (N0, s2
) are not isomorphic.
Exercise 9
Find two linear orderings and on N0 such that (N0, ) and (N0, ) are not isomorphic.
Exercise 10
Find infinitely many linear orderings 0, 1, . . . on N0 such that for all i = j the ordered sets (N0, i)
and (N0, j) are not isomorphic.
Exercise 11
Let U be an uncountable set. Find a linear ordering s on N0 for each s  U such that for any
s1, s2  U satisfying s1 = s2 the ordered sets (N0, s1 ) and (N0, s2 ) are not isomorphic.
Exercise 12
Let (A, ) be a finite ordered set. Prove that there is a linear ordering on A such that  .
2