RELATIONS

INTRODUCTION

Let f be a function of E into F. The function introduces particular relation whose role is to assign a unique element f (x) from set F to the each element x from E.

In everyday life we have a little bit different situation. Let  us take a look at two sets: the set A is the set of the girls and the set B is the set of  the boys. We can say  that there exists relation between them, if the boy from the set B was on a date with a girl from the set A.

The situation can be a little bit complicated in the case when one boy had a date with two or more girls and  contrary. It is less exciting when there is no date between a boy and a girl. We can say that to the each girl a A belongs a subset from B consisted of those elements i.e. boys who had a date with her.

Let A and B be two non empty sets. Each subset r of the Cartesian product A × B is called a relation. A function defined on the Cartesian product A × B of two sets A and B, with the property P(a, b) is called an open sentence and has the characteristic that P(a,b) is true of false for any ordered pair (a, b) A × B. The element x from A is in the relation  with the element y form B if and only if (x,y).

  is called a relation from A to B and is denoted by  = (A, B, P(x, y)). If P(a, b) is true, then we write a  b (“a is related to b"). If P(a, b) is not true, than a is not related to b. Let  = (A, B, P(x, y)) be a relation. The open sentence P(x, y) defines a relation from A to B. If A = B, then we say that P(x, y) defines a relation in A, or that  is a relation in A.

The relation  = (A, B, P(x, y)) has a solution set  *, which is consisted of the elements (a, b) from A × B, for which P(a, b) is true. Then, * = {(a, b) | a A, b B, P(a, b) is true}, * A × B. A graph of the relation  from A to B consists those points on the coordinate diagram of A × B which are a part of  the solution set *.

Inverse relations

Let  be a non-empty subset of A × B. Then its inverse relation is also a subset of A × B.

Every relation  from A to B has an inverse relation ^-1 from B to A which is defined by ^-1 = {(y, x) | (x, y) } .

Reflexive relations

Let  be a binary relation in a set A. Then  is a subset of A × A. We say that  is a reflexive relation if (x, x)   for every x A. In other words,  is reflexive if every element in A is related to itself.

Symmetric relations

We say that relation  A × A is a symmetric relation if  (x, y)   implies (y, x) . In other words, if x is related to y then y is also related to x.

Since (x, y)   implies (y, x) belongs to the inverse relation ^-1, r is a symmetric relation if and only if = ^-1.

Anti-symmetric relations

A relation  A × A, is called an anti-symmetric relation if condition (x, y)   and (y, x)   is never fulfilled or such a condition implies x = y. In other words, if x y then x is possibly related to y or y is possibly related to x, but never both.

Consider the situation when D denotes the diagonal line of A × A, i.e. the set of all ordered pairs (x, x) A × A. Then a relation  in A is anti-symmetric if and only if  ^-1 D. Such a relation is neither reflexive, nor symmetric.

Transitive relations

We say that the relation  in a set A is a transitive relation if (x, y)   and (y, z)   implies (x, z) . In other words, if x is related to y and y is related to x, then x is related to y.

Domain and range of relation

Let  be a relation from A to B, so  A × B. The domain D of the relation  corresponds to the set of all first elements of ordered pairs which belong to , or D = {a | a A, (a, b) }. The range E of the relation  consists of all the second elements of the ordered pairs in , or E = {b | b B, (a, b) }. The domain of a relation from A to B is a subset of A, and its range is a subset of B.

If we take a situation where  is a relation from A to B displayed on the coordinate diagram of A × B, then a A is in the domain of  if, and only if the vertical line through a contains a point of the graph of . On the same way, b B is in the range of  if, and only if, the horizontal line through b contains a point of the graph of .

Relations and functions

We have a situation where f maps set A into B and is defined on some part of the set A, i.e., D(f)  A and (x,y)f.  is the relation from A to B.

Definition: We say that the relation  if functional according to second variable y, if there exists a function f from A into B for which  is its graph. In other words

 = { (g(y),y), | xD(f), D(f)  A}. In the same way, we call the relation  a function according to the first variable x, if there is a function g from A into B, for which  is its graph. In the other words,  = {(g(y), y) | yD(g), D(g)  B}.

Since every subset of A × B is a relation, the function is a special type of relations.

Back to Top

EQUIVALENCE RELATIONS

A relation on A is an equivalence relation if it is reflexive, symmetric and transitive. An example of such a relation is equality on a set.

A relation  in a set A is an equivalence relation if

 is reflexive, that is for every a A, (a, a) ,

 is symmetric, that is, (a, b)   implies (b, a) ,

 is transitive, that is, (a, b)   and (b, c)   implies (a, c)  

Example: Let A be set of triangles in a plane. We can say that two triangles x,y A are equivalent if they are congruent i.e. they can be put one on each other.

Equivalence relations and partitions

Suppose that the set E=A (AF) is the union of sets from the set of sets F. Consider two things: that there is no element AF which is empty and for any two elements A,BF , A=B or AB= is fulfilled. In other words, a set E is distributed on nonempty disjoint sets. Then F is partition of the set E. By the help of partition of the set E, we can define an equivalence relation on the set E. It is enough to put x ~ y, if and only if there exists AF such that x,yA. It is obvious that ~ is  an equvalence relation on E. The elements of the set F can be described with this relation, i. e. for XF exists aX. Now we have X={xE | x~a}. The elements of the set of sets F are called equvalence classes of relation ~.

Lets point out that the elements of the set F are subsets of E, i.e. FP(E), so FP[P(E)]. We have three type of sets here: E, P(E) and P[P(E)].

Now, we shall describe the proces of constructing the partition F of the set E by the help of the equvalence relation on E and the function from E into F.

Fundamental Theorem on Equivalence Relations:

If there exists a relation ~ as an equivalence relation in a set E such that for every aE, exists E_a = {x | x~a}

i.e. the set of elements related to a, then the family of sets F={E_a | aE} is a partition of A.

In an equivalence relation, all elements related to a particular element are related to each other. They form an equivalence class. For the relation "is parallel to", for example, the equivalence class of a particular line a is the set of all lines parallel to a.

An equivalence relation ~ in a set E partitions the set E by putting those elements, which are related to each other in the same equivalence class. The set E_a is called the equivalence class and is determined by a, and the set of equivalence classes F is called the quotient set (F=E/~).

Thus the equivalence classes of a relation are a partition. Each equivalence relation on a set partitions the set into its equivalence classes, but also for each partition of the set there is an equivalence relation whose equivalence classes are the sets in the partition.

Proof:

Lets start from a nonempty set E and the equivalence relation ~ on E.

First step: for aE denote with E_a the set of all elements yE which are equivalent with a, i.e. E_a = {yE | y~a}. With this we have joined all the elements which are equivalent with a and we got a certain element E_aP(E). Let us do the same thing for each aE.

Second step: Let F be the set of all elements from P(E) given on such a way , i.e., F = {E_x | xE}. That way we have joined all sets E_x. We have to prove that F is a partition.

In the frist case, the relation ~ is reflexive, so x ~ x for each x  E. But (x ~ x) (x  E_x); so E = E_{x ,} x  E.

If x, y  E_a, then x ~a  and y ~a. As ~ is a symmetric relation, then y~a a~a. Now, x~a and a~ y and transitivity of the relation ~ imply x ~ y. Therefore, each two elements from E_a are equivalent.

Sets E_a and E_b must be disjoint. Let consider contrary.

If we suppose the existence of at least one element in the intersection of sets E_a and E_b, cE_aE_b, then (c~a and c~b)(a~b).

If xE_a, then x~a. As we already know that a~b, then x~b. On the other hand x~bxE_b. As xE_axE_b, then E_aE_b. From the same reasons E_bE_a. Therefore (E_aE_b)(E_a=E_b). This proves that F is a partition of the set E.

The partition F of the set E produces equivalence relation r on E. As (x,y)r, then x and y are from the same element A of the set F, and that means x~y. Contradiction is also fulfilled, and that implies equality of relations r and ~.

Theorem: Let F be a partition of E and r be the relation in E defined by the open sentence “x is in the same set (of the family F) as y”. Then r is an equivalence relation in E. 

There is a one to one correspondence between all partitions of the set E and all equivalence relations in E.

Back to Top

RELATION OF ORDER IN SETS

We can take an example from every day life. John and Mary are going to school. John has to go through the street in a straight line and pass by the pizzeria before he comes to school and he has to pass by the school if he wants to enter at the schoolyard. Mary is coming from the opposite direction, so first she has to pass by the schoolyard before she arrives to school and she must pass the school if she wants to eat pizza. If we say that John is going from left to the right, then pizzeria is on the left side from the school and the schoolyard is on at right side from the school. If we denote the pizzeria with letter A, the school with letter B and the schoolyard with letter C, we have a straight line with three points on it. Let r be a subset of the set S × S, whose elements are ordered pairs (A, B) for which  A is left from B. According to this is (A, B) r. We have binary relation r on the set S, with a meaning that A is left from B. This relation is not reflexive, (A, A) r, for A S. Then r does not contain not one point from the diagonal of the set S²  = S ´ S which can be imagined in this case as a plane.

Ordered sets are usually surrounded by brackets. Notation could be like this:

<set, order relation>

but these angle brackets look too much like less than and greater than signs, so we can also denote them like this:

[set, order relation]

For the three different points A, B, C S we can say that if A is left from the B and B is left from the C, then A is left from the C. In the other words:

[(A,B) and (B,C)] (A,C).

This shows transitivity of the relation .

Definition: Let S be a non empty set and < the binary relation on S. We say that S is a well ordered (or totally ordered) set regarding relation <, if the following conditions are fulfilled for each par x,yS:

for xy is valid x<y or y<x but not both;    (anti-symmetric)

 if x<y and y<z, then x<z;              (transitive)

x<x is not true for any xS.    (not reflexive)

We have a relation structure on a well-ordered set. We read the relation x<y as “x is less then y”.

The school, from the example above is between the schoolyard and pizzeria.

Definition: Let S be a set ordered by the relation <. We say that the element bS is between elements a,cS if

a<b and b<c.

We say that the element a precedes the element b, or b is dominate to a.

A partial order in a set S is a relation  in S, which is

reflexive, i.e. (x,x)  for every xS,

anti-symmetric, i.e. (x,y)  and (y,x)  implies x=y and

transitive, i.e. (x,y)  and (y,z)  implies (x,z) .

If a relation r in S defines a partial order in S, then (a,b)  is denoted by a b which reads “a precedes b”.

Definition: A set S together with a specific partial order relation  in S is called a partially ordered set.

A partially ordered set consists of the set S and a specific type of relation  in S; for this reason, a partially ordered set is sometimes denoted by the ordered pair (S, ) or (S, ).

Notation:

a<b means ab and ab;     read “a strictly precedes b”.

ba means ab;                  read “b dominates a”.

b>a means a<b;                  read “b strictly dominates a”.

Two elements a and b in a partially ordered set are said to be not comparable if  ab and ba that is, if no element precedes the other element.

If a relation  in the set S is reflexive, anti-symmetric and transitive, then the inverse relation ^-1 is also reflexive, anti-symmetric and transitive. In other words, if  defines a partial order in S then ^-1 also defines a partial order in S which is called the inverse order.

Totally ordered sets

The elements in a partially ordered set do not have to be comparable. The order in set S is called a total order in S, if every two elements in a partially ordered set S are comparable.

Definition:

A total order in a set S is a partial order in S with the additional property

a<b, a=b or a>b

for any two elements a and b belonging to S. A set S together with a specific total order in S is called a totally ordered set.

Definition: Let S be an ordered set. We say that the element mS (if exists) is the minimal element of the set S, if there is no such element xS that is less than m. The element MS (if exists) is called maximal element of the set S, if there is no such element yS, that is greater than M.

Definition: We say that the ordered set S is well ordered, if every non empty subset E  S has a minimal element regarding the relation of the set S.

Theorem: The ordered set has at most one minimal element and at most one maximal element.

Proof: Lets prove this theorem by the use of contradiction.