Binary relations examples. The concept of a relationship on a set

Definition. Binary relation R is called a subset of pairs (a,b)∈R the Cartesian product A×B, i.e. R⊆A×B . At the same time, many A is called the domain of definition of the relation R, the set B is called the domain of values.

Notation: aRb (i.e. a and b are in relation to R). /

Comment: if A = B , then R is said to be a relation on the set A .

Ways to specify binary relations

1. List (enumeration of pairs) for which this relationship is satisfied.

2. Matrix. The binary relation R ∈ A × A , where A = (a 1 , a 2 ,..., a n), corresponds to a square matrix of order n , in which the element c ij standing on i-th intersection row and j-th column is equal to 1 if there is a relation R between a i and a j , or 0 if it is absent:

Relationship Properties

Let R be a relation on a set A, R ∈ A×A . Then the relation R:

reflexively if Ɐ a ∈ A: a R a (the main diagonal of the matrix of the reflexive relation contains only ones);

is antireflexive if Ɐ a ∈ A: a R a (the main diagonal of the reflexive relation matrix contains only zeros);

symmetric if Ɐ a , b ∈ A: a R b ⇒ b R a (the matrix of such a relation is symmetric with respect to the main diagonal, i.e. c ij c ji);

antisymmetric if Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (in the matrix of such a relation, there are no ones symmetric with respect to the main diagonal);

transitively if Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c i-th line there is a unit, for example, in the j-th coordinate (column) of the row, i.e. c ij = 1, then all units in the j-th row (let these units correspond to k e coordinates such that, c jk = 1) must correspond to units in the i-th row in the same k-th coordinates, i.e. c ik = 1 (and, maybe, also in other coordinates).

Task 3.1. Determine the properties of the relation R - "to be a divisor", given on the set of natural numbers.

Solution.

ratio R = ((a,b):a divisor b):

reflexive, not antireflexive, since any number divides itself without remainder: a/a = 1 for all a∈N ;

not symmetrical, antisymmetric, for example, 2 is a divisor of 4, but 4 is not a divisor of 2;

transitively, since if b/a ∈ N and c/b ∈ N, then c/a = b/a ⋅ c/b ∈ N, for example, if 6/3 = 2∈N and 18/6 = 3∈N, then 18/3 = 18/6⋅6/3 = 6∈N.

Task 3.2. Determine the properties of the relation R - "to be a brother", given on a set of people.
Solution.

Ratio R = ((a,b):a - brother of b):

non-reflexive, anti-reflexive due to the obvious absence of aRa for all a;

not symmetrical, since in general there is aRb between brother a and sister b, but not bRa ;

not antisymmetric, since if a and b are brothers, then aRb and bRa, but a≠b;

transitively, if we call brothers people who have common parents (father and mother).

Task 3.3. Determine the properties of the relation R - "to be the boss" specified on the set of structure elements

Solution.

Ratio R = ((a,b) : a - boss b):

• non-reflexive, anti-reflexive, if it does not make sense in a particular interpretation;
• not symmetric, antisymmetric, since for all a≠b aRb and bRa are not satisfied simultaneously;
• transitively, since if a is the head of b and b is the head of c , then a is the head of c .

Determine the properties of the relation R i , defined on the set M i by a matrix, if:

1. R 1 "have the same remainder when divided by 5"; M 1 is the set of natural numbers.
2. R 2 "be equal"; M 2 is the set of natural numbers.
3. R 3 "live in the same city"; M 3 set of people.
4. R 4 "be familiar"; M 4 many people.
5. R 5 ((a,b):(a-b) - even; M 5 set of numbers (1,2,3,4,5,6,7,8,9).
6. R 6 ((a,b):(a+b) - even; M 6 set of numbers (1,2,3,4,5,6,7,8,9).
7. R 7 ((a,b):(a+1) - divisor (a+b)) ; M 7 - set (1,2,3,4,5,6,7,8,9).
8. R 8 ((a,b):a - divisor (a+b),a≠1); M 8 is the set of natural numbers.
9. R 9 "to be a sister"; M 9 - a lot of people.
10. R 10 "to be a daughter"; M 10 - a lot of people.

Operations on binary relations

Let R 1 , R 1 be relations defined on the set A .

Union R 1 ∪ R 2: R 1 ∪ R 2 = ((a,b) : (a,b) ∈ R 1 or (a,b) ∈ R 2 ) ;

intersection R 1 ∩ R 2: R 1 ∩ R 2 = ((a,b) : (a,b) ∈ R 1 and (a,b) ∈ R 2 ) ;

difference R 1 \ R 2: R 1 \ R 2 = ((a,b) : (a,b) ∈ R 1 and (a,b) ∉ R 2 ) ;

universal relation U: = ((a;b)/a ∈ A & b ∈ A). ;

addition R 1 U \ R 1 , where U = A × A;

identity relation I: = ((a;a) / a ∈ A);

reverse relation R-1 1 :R-1 1 = ((a,b) : (b,a) ∈ R 1 );

composition R 1 º R 2: R 1 º R 2: = ((a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b), where R 1 ⊂ A × C and R 2 ⊂ C×B;

Definition. Degree of relationship R on a set A is its composition with itself.

Designation:

Definition. If R ⊂ A × B, then R º R -1 is called the kernel of the relation R .

Theorem 3.1. Let R ⊂ A × A be a relation defined on a set A .

1. R is reflexive if and only if (hereinafter the sign ⇔ is used) when I ⊂ R.
2. R is symmetrical ⇔ R = R -1 .
3. R is transitive ⇔ R º R ⊂ R
4. R is antisymmetric ⇔ R ⌒ R -1 ⊂ I .
5. R is antireflexive ⇔ R ⌒ I = ∅ .

Task 3.4 . Let R be the relation between the sets (1,2,3) and (1,2,3,4) given by the enumeration of pairs: R = ((1,1), (2,3), (2,4), ( 3.1), (3.4)). In addition, S is a relation between the sets S = ((1,1), (1,2), (2,1), (3,1), (4,2)). Calculate R -1 , S -1 and S º R. Check that (S º R) -1 = R -1 , S -1 .

Solution.
R -1 = ((1.1), (1.3), (3.2), (4.2), (4.3));
S -1 = ((1.1), (1.2), (1.3), (2.1), (2.4));
S º R = ((1,1), (1,2), (2,1), (2,2), (3,1), (3,2));
(S º R) -1 = ((1,1), (1,2), (1,3), (2,1), (2,2), (2,3));
R -1 º S -1 = ((1.1), (1.2), (1.3), (2 .1), (2.2), (2.3)) = (S º R ) -1 .

Task 3.5 . Let R be the relation "...parent..." and S the relation "...brother..." on the set of all people. Give a brief verbal description of the relationship:

R -1 , S -1 , R º S, S -1 º R -1 and R º R.

Solution.

R -1 - relation "... child ...";

S -1 - relation "... brother or sister ...";

R º S - relation "... parent ...";

S -1 º R -1 - relation "... child ..."

R º R - relation "...grandmother or grandfather..."

Tasks for independent solution

1) Let R be the relation "...father...", and S be the relation "...sister..." on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , R º S, S -1 º R -1 , R º R.

2) Let R be the relation "...brother...", and S be the relation "...mother..." on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Let R be the relation "...grandfather...", and S be the relation "...son..." on the set of all people. Give a verbal description of the relationship:

4) Let R be the relation “...daughter...”, and S be the relation “...grandmother...” on the set of all people. Give a verbal description of the relationship:

5) Let R be the relation "...niece...", and S be the relation "...father..." on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Let R be the relation "sister..." and S be the relation "mother..." on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

7) Let R be the relation “...mother...”, and S be the relation “...sister...” on the set of all people. Give a verbal description of the relationship:

R -1 , S1, R º S, S1 º R1, S º S.

8) Let R be the relation “...son...”, and S be the relation “...grandfather...” on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Let R be the relation “...sister...”, and S be the relation “...father...” on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

10) Let R be the relation “...mother...”, and S be the relation “...brother...” on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

Consider the respect relation defined on the set of all people %%M%%. For complete information about who respects whom, we will compose the following set %%R%%. Let's iterate over all pairs %%(a, b)%%, where %%a, b%% run through the set of all people. If %%a%% respects %%b%%, then the pair %%(a,b)%% belongs to the set %%R%%, otherwise not.

This list fully reflects the respect attitude. If we need to find out if the person %%a%% respects the person %%b%%, then we look at the set %%R%%. If the pair %%(a, b) \in R%%, then we conclude that %%a%% respects %%b%%. In the case of %%(a,b) \notin R%% - %%a%% does not respect %%b%%.

Definition

binary relation defined on the set %%M%% is an arbitrary subset %%R%% of the Cartesian product %%M^2%%.

Example

Consider the relation more on the set %%M = \(1, 2\)%%. Then

$$ M^2 = \big\((1, 1), (1,2), (2,1), (2,2)\big\) $$ Select all pairs %%(a,b )%%, where %%a > b%%. We get $$ R = \big\((2,1)\big\) $$

Types of binary relations

Reflexive binary relation

reflective, if for any element %%a%% of %%M%%, the condition %%a~R~a%% is met. $$ \begin(array)(l) \forall a\in M~~a~R~a \text( or)\\ \forall a\in M~~(a,a) \in R. \end( array)$$

Examples

1. Consider the relation more more reflective? If so, then each number is more himself, which is not true. Therefore, the ratio more not reflective.
2. Consider the relation equals on the set of real numbers. It is reflective, since every real number is equal to itself.

Symmetric binary relation

The binary relation %%R%% on the set %%M%% is called symmetrical, if for any two elements %%a, b%% from %%M%%, the condition %%a~R~b%% implies the condition %%b~R~a%%.

$$ \begin(array)(l) \forall a,b\in M~~a~R~b \rightarrow b~R~a \text( or)\\ \forall a,b\in M~~( a,b) \in R \rightarrow (b,a) \in R. \end(array) $$

Examples

1. Consider the relation more on the set of real numbers. Is the attitude more symmetrical? It is not symmetric, because if %%a > b%%, then the condition %%b > a%% is not satisfied. Therefore, the ratio more not symmetrical.
2. Let %%R%% be a relation defined on the set %%M = \(a,b,c\)%%. In this case, %%R = \big\( (a,b), (b,c), (a,a), (b,a), (c,b)\big\)%%. For this relation we have %%\forall x,y \in M ~~ (x,y) \in R \rightarrow (y,x) \in R%%. By definition, %%R%% is symmetrical.

transitive binary relation

The binary relation %%R%% on the set %%M%% is called transitive, if for any elements %%a, b, c%% from %%M%%, from the conditions %%a~R~b%% and %%b~R~c%% the condition %%a~R~ follows c%%.

$$ \begin(array)(l) \forall a,b,c\in M~~a~R~b \land b~R~c \rightarrow a~R~c \text( or)\\ \forall a,b,c\in M~~(a,b) \in R \land (b,c) \in R \rightarrow (a,c) \in R. \end(array) $$

Example

Consider the relation more on the set of real numbers. It is transitive, since for any elements the condition %%\forall a,b,c\in M~~a > b \land b > c \rightarrow a > c%% is satisfied. So, for example, substituting the numbers %%2, 1%% and %%0%% instead of %%a, b%% and %%c%% respectively, we get: if %%2 > 1%% and %%1 > 0%%, then %%2 > 0%% is a true statement (remember the implication, truth follows from truth).

Antisymmetric binary relation

The binary relation %%R%% on the set %%M%% is called antisymmetric, if for any elements %%a, b%% from %%M%%, from the conditions %%a~R~b%% and %%b~R~a%% the condition %%a = b%% follows.

$$ \begin(array)(l) \forall a,b,c\in M~~a~R~b \land b~R~a \rightarrow a = b \text( or)\\ \forall a, b\in M~~(a,b) \in R \land (b,a) \in R \rightarrow a = b. \end(array) $$

Example

Attitude more or equal on the set of real numbers antisymmetric. Indeed, if %%a \geq b%% and %%b \geq a%%, %%a = b%%.

Equivalent binary relation

equivalence if it reflexively, symmetrically And transitively.

It is easy to check that the ratio parallelism on the set of lines in the plane is an equivalence relation.

Partial order relation

The binary relation %%R%% on the set %%M%% is called the relation partial order if it reflexively, antisymmetric And transitively.

Attitude more or equal on the set of real numbers is a partial order relation.

Construction of negations

Let %%R%% be a binary relation on the set %%M%% and %%P%% be one of the following conditions:

• the relation %%R%% is reflexive,
• the ratio %%R%% is symmetrical,
• relation %%R%% is transitive,
• the ratio %%R%% is antisymmetric.

Let us construct for each of them the negation of the fulfillment of the condition %%P%%.

Denial of reflexivity

By definition, %%R%% is reflexive if each element of the set %%M%% is in relation %%R%% to itself, that is, %%\forall a \in M~~a~R~a%%. Then consider the negation of reflexivity as the true proposition %%\overline(\forall a \in M~~a~R~a)%%. Use the equivalence %%\overline(\forall x P(x)) \equiv \exists x \overline (P(x))%%. In our case, we get %%\forall a \in M~~a~R~a \equiv \exists a\in M~~a~\not\text(R )~a%%, which is what we need.

Similarly, we obtain the remaining negations. As a result, we get the following statements:

%%R%% is not reflexive if and only if

$$ \exists a \in M~~a~\not R~a $$

%%R%% is not symmetrical if and only if

$$ \exists a, b \in M~~ a~R~b \land b~\not R~a $$

%%R%% is not transitive if and only if

$$ \exists a, b, c \in M a~R~b \land b~R~c \land a~\not R~c $$

%%R%% is not antisymmetric if and only if

$$ \exists a, b \in M~~ a~R~b \land b~R~a \land a \neq b. $$

A relation defined on a set can have a number of properties, namely:

2. Reflexivity

Definition. Attitude R on the set X is called reflexive if each element X sets X is in relation R With myself.

Using symbols, this relationship can be written as follows:

R reflectively on X Û(" XÎ X) x R x

Example. The relation of equality on the set of segments is reflexive, since each segment is equal to itself.

The reflexive relation graph has loops at all vertices.

2. Antireflexivity

Definition. Attitude R on the set X is called anti-reflexive if no element X sets X not in relation R With myself.

R antireflexively on X Û(" XÎ X)

Example. The relationship "direct X perpendicular to the line at» on the set of lines in the plane is antireflexive, because no straight line of a plane is perpendicular to itself.

The graph of an antireflexive relation does not contain any loops.

Note that there are relations that are neither reflexive nor antireflexive. For example, consider the relation "point X symmetrical to a point at» on the set of points of the plane.

Dot X symmetrical to a point X- true; dot at symmetrical to a point at- is false, therefore, we cannot assert that all points of the plane are symmetrical to themselves, nor can we assert that no point of the plane is symmetrical to itself.

3. Symmetry

Definition. Attitude R on the set X is called symmetric if, from the fact that the element X is in relation R with element at, it follows that the element at is in relation R with element X.

R symmetrical X Û(" X, atÎ X) x R y Þ y R x

Example. The relationship "direct X crosses the line at on the set of straight lines of the plane” is symmetrical, because if straight X crosses the line at, then the straight line at must cross the line X.

Symmetric relation graph along with each arrow from a point X exactly at should contain an arrow connecting the same points, but in the opposite direction.

4. Asymmetry

Definition. Attitude R on the set X is called asymmetric if for no elements X, at from many X it cannot happen that the element X is in relation R with element at and element at is in relation R with element X.

R asymmetric X Û(" X, atÎ X) x R y Þ

Example. Attitude " X < at» asymmetrically, because for any pair of elements X, at cannot be said to be at the same time X < at And at<X.

A graph of an asymmetric relation has no loops, and if two vertices of the graph are connected by an arrow, then this arrow is only one.

5. Antisymmetry

Definition. Attitude R on the set X is called antisymmetric if, from the fact that X is in relationship with at, A at is in relationship with X follows that X = y.

R antisymmetric X Û(" X, atÎ X) x R y Ù y R xÞ x = y

Example. Attitude " X£ at» is antisymmetric, because conditions X£ at And at£ X are executed at the same time only when X = y.

The graph of an antisymmetric relation has loops, and if two vertices of the graph are connected by an arrow, then this arrow is only one.

6. Transitivity

Definition. Attitude R on the set X is called transitive if for any elements X, at, z from many X from what X is in relationship with at, A at is in relationship with z follows that X is in relationship with z.

R transitive X Û(" X, at, zÎ X) x R y Ù at RzÞ x Rz

Example. Attitude " X multiple at» is transitive, because if the first number is a multiple of the second, and the second is a multiple of the third, then the first number is a multiple of the third.

Graph of a transitive relation with each pair of arrows from X To at and from at To z contains an arrow going from X To z.

7. Connectivity

Definition. Attitude R on the set X is called connected if for any elements X, at from many x x is in relationship with at or at is in relationship with X or x = y.

R connected X Û(" X, at, zÎ X) x R y Ú at RzÚ X= at

In other words: relationship R on the set X is called connected if for any distinct elements X, at from many x x is in relationship with at or at is in relationship with X or x = y.

Example. Attitude " X< at» is connected, because no matter what real numbers we take, one of them is sure to be greater than the other or they are equal.

On a relation graph, all vertices are connected by arrows.

Example. Check what properties

attitude " X - divider at» defined on the set

X= {2; 3; 4; 6; 8}.

1) this relation is reflexive, since each number from the given set is a divisor of itself;

2) this relation does not have the property of antireflexivity;

3) the symmetry property is not satisfied, because for example, 2 is a divisor of 4, but 4 is not a divisor of 2;

4) this relation is antisymmetric: two numbers can simultaneously be divisors of each other only if these numbers are equal;

5) the relation is transitive, since if one number is a divisor of the second, and the second is a divisor of the third, then the first number will necessarily be a divisor of the third;

6) the relation does not have the property of connectivity, since for example, the numbers 2 and 3 on the graph are not connected by an arrow, because two distinct numbers 2 and 3 are not divisors of each other.

Thus, this relation has the properties of reflexivity, asymmetry and transitivity.

§ 3. Equivalence relation.
Connection of the equivalence relation with the division of a set into classes

Definition. Attitude R on the set X is called an equivalence relation if it is reflexive, symmetric, and transitive.

Example. Consider the relationship " X classmate at» on a set of students of the pedagogical faculty. It has properties:

1) reflexivity, since each student is a classmate to himself;

2) symmetry, because if student X at, then the student at is a classmate of a student X;

3) transitivity, because if student X- classmate at, and the student at- classmate z, then the student X be a classmate of a student z.

Thus, this relation has the properties of reflexivity, symmetry and transitivity, and therefore is an equivalence relation. At the same time, the set of students of the pedagogical faculty can be divided into subsets consisting of students enrolled in the same course. We get 5 subsets.

The equivalence relation is also, for example, the relation of parallel lines, the relation of equality of figures. Each such relation is connected with the division of the set into classes.

Theorem. If on the set X given an equivalence relation, then it splits this set into pairwise disjoint subsets (equivalence classes).

The converse statement is also true: if any relation defined on the set X, generates a partition of this set into classes, then it is an equivalence relation.

Example. On the set X= (1; 2; 3; 4; 5; 6; 7; 8) the relation "have the same remainder when divided by 3" is given. Is it an equivalence relation?

Let's build a graph of this relationship:

This relation has the properties of reflexivity, symmetry and transitivity, therefore, it is an equivalence relation and splits the set X into equivalence classes. Each equivalence class will have numbers that, when divided by 3, give the same remainder: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

It is believed that the equivalence class is determined by any of its representatives, i.e. arbitrary element of this class. So, the class of equal fractions can be specified by specifying any fraction belonging to this class.

In the initial course of mathematics, equivalence relations also occur, for example, "expressions X And at have the same numerical values", "figure X equal to figure at».

Lecture 3

item 3. Relations on sets. Properties of binary relations.

3.1. binary relations.

When they talk about the relationship of two people, for example, Sergey and Anna, they mean that there is a certain family to which they belong. An ordered couple (Sergei, Anna) differs from other ordered pairs of people in that there is some kind of relationship between Sergei and Anna (cousin, father, etc.).

In mathematics, among all ordered pairs of the direct product of two sets A And B (A´ B) “special” pairs are also distinguished due to the fact that between their components there are some “related” relationships that others do not have. As an example, consider the set S students of some university and many K courses taught there. In direct work S´ K one can single out a large subset of ordered pairs ( s, k) having the property: student s listens to the course k. The constructed subset reflects the relationship "... listens to ...", which naturally arises between sets of students and courses.

For a rigorous mathematical description of any connections between elements of two sets, we introduce the concept of a binary relation.

Definition 3.1. binary (or double )attitude r between sets A And B called an arbitrary subset A´ B, i.e.

In particular, if A=B(i.e. rÍ A 2), then we say that r is a relation on the set A.

Elements a And b called components (or coordinates ) relations r.

Comment. Let's agree that to denote the relationship between the elements of the sets, use the Greek alphabet: r, t, j, s, w, etc.

Definition 3.2. Scope of definition D r=( a| $ b, What a r b) (left side). Value area binary relation r is called the set R r=( b| $ a, What a r b) (right part).

Example 3. 1. Let two sets be given A=(1; 3; 5; 7) and B=(2; 4; 6). We define the relation as follows t=(( x; y)Î A´ B | x+y=9). This ratio will consist of the following pairs (3; 6), (5; 4) and (7; 2), which can be written as t=((3; 6), (5; 4), (7; 2) ). In this example D t=(3; 5; 7) and R t= B={2; 4; 6}.

Example 3. 2. The equality relation on the set of real numbers is the set r=(( x; y) | x And y are real numbers and x equals y). There is a special notation "=" for this relation. The domain of definition coincides with the domain of values ​​and is the set of real numbers, D r= R r.

Example 3. 3. Let A- a lot of goods in the store, and B is the set of real numbers. Then j=(( x; y)Î A´ B | y– price x) is the ratio of sets A And B.

If you pay attention to example 3.1., then you can see that this relation was first set in the form t=(( x; y)Î A´ B | x+y=9), and then written as t=((3; 6), (5;4), (7;2)). This suggests that relations on sets (or one set) can be specified in various ways. Let's consider ways of specifying binary relations.

Ways to set relationships:

1) using a suitable predicate;

2) a set of ordered pairs;

3) in graphical form: let A And B are two finite sets and r is a binary relation between them. The elements of these sets are represented by points on the plane. For each ordered pair, the relations r draw an arrow connecting the points representing the components of the pair. Such an object is called directed graph or digraph, while the points representing the elements of the sets are usually called graph vertices.

4) in the form of a matrix: let A={a 1, a 2, …, an) And B={b 1, b 2, …, bm), r is the ratio on A´ B. Matrix representation r is called a matrix M=[mij] size n´ m, defined by the relations

.

By the way, a matrix representation is a representation of a relation in a computer.

Example 3. 4. Let two sets be given A=(1; 3; 5; 7) and B=(2; 4; 6). The ratio is defined as follows t=(( x; y) | x+y=9). Specify this relation as a set of ordered pairs, digraph, in the form of a matrix.

Solution. 1) t=((3; 6), (5; 4), (7; 2)) - is the assignment of a relation as a set of ordered pairs;

2) the corresponding directed graph is shown in the figure.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

Example 3. 5 . As an example, consider the proposed J. von Neumann(1903 - 1957) a block diagram of a sequential computer, which consists of many devices M:

,

Where a- input device, b- arithmetic unit (processor), c- control device, d- Memory device, e- output device.

Consider the information exchange between devices mi And mj, which are in relation to r, if from the device mi information enters the device mj.

This binary relation can be defined by listing all of its 14 ordered pairs of elements:

The corresponding digraph defining this binary relation is shown in the figure:

The matrix representation of this binary relation is:

. ,

For binary relations, set-theoretic operations are defined in the usual way: union, intersection, etc.

Let us introduce a generalized concept of relation.

Definition 3.3. n-local (n-arnoe ) the relation r is a subset of the direct product n sets, that is, the set of ordered sets ( tuples )

rÍ A 1 An={(a 1, …, an)| a 1О A 1Ù … Ù anÎ An}

Many-place relations are conveniently defined using relational tables . Such a task corresponds to the enumeration of the set n-k relation r. Relational tables are widely used in computer practice in relational databases. Note that relational tables have been used in everyday practice. All sorts of production, financial, scientific and other reports often take the form of relational tables.

Word " relational" comes from the Latin word relation, which in translation into Russian means "relationship". Therefore, in the literature, the letter is used to indicate the relationship R(Latin) or r (Greek).

Definition 3.4. Let rÍ A´ B there is a relation to A´ b. Then the relation r-1 is called reverse attitude to a given ratio r by A´ B, which is defined as follows:

r-1=(( b, a) | (a, b)нr).

Definition 3.5. Let r Н A´ B there is a relation to A´ b, a s Н B´ C- relation to B´ C. Composition relations s and r is the relation t Н A´ C, which is defined as follows:

t=s◦r= (( a, c)| $bÎ B what (a, b)Оr And (b, c)Оs).

Example 3. 6 . Let , and C=(, !, d, a). And let the ratio r on A´ B and the relation s on B´ C given in the form:

r=((1, x), (1, y), (3, x)};

s=(( x,), (x, !), (y, d), ( y, à)}.

Find r-1 and s◦r, r◦s.

Solution. 1) By definition, r-1=(( x, 1), (y, 1), (x, 3)};

2) Using the definition of the composition of two relations, we obtain

s◦r=((1,), (1, !), (1, d), (1, a), (3,), (3, !),

since from (1, x)нr and ( x,)нs follows (1,)нs◦r;

from (1, x)нr and ( x, !)Îs follows (1, !)Îs◦r;

from (1, y)нr and ( y, d)нs follows (1, d)нs◦r;

from (3, x)нr and ( x, !)Îs follows (3, !)Îs◦r.

Theorem 3.1. The following properties hold for any binary relations:

2) ;

3) - Associativity composition.

Proof. Property 1 is obvious.

We prove property 2. To prove the second property, we show that the sets written on the left and right sides of the equality consist of the same elements. Let ( a; b) н (s◦r)-1 ы ( b; a) н s◦r ы $ c such that ( b; c) О r and ( c; a) О s у $ c such that ( c; b) О r-1 and ( a; c) н s-1 ь ( a; b) О r -1◦s -1.

Prove property 3 yourself.

3.2. Properties of Binary Relations.

Consider special properties of binary relations on the set A.

Properties of binary relations.

1. The ratio of r to A´ A called reflective , If ( a,a) belongs to r for all a from A.

2. The relation r is called anti-reflexive , if from ( a,b)нr follows a¹ b.

3. Ratio symmetrically , if for a And b belonging to A, from ( a,b)нr it follows that ( b,a)Оr.

4. The relation r is called antisymmetric , if for a And b from A, from membership ( a,b) And ( b,a) the relation r implies that a=b.

5. Ratio transitively , if for a, b And c from A from what ( a,b)нr and ( b,c)нr, it follows that ( a,c)Оr.

Example 3. 7. Let A=(1; 2; 3; 4; 5; 6). On this set, the relation rÍ A 2, which looks like: r=((1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2) , (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)). What properties does this relationship have?

Solution. 1) This relation is reflexive, since for each aÎ A, (a; a)Оr.

2) The relation is not anti-reflexive, since the condition of this property is not satisfied. For example, (2, 2)нr, but it does not follow from this that 2¹2.

3) Consider all possible cases, showing that the relation r is symmetric:

	(a, b)Оr	(b, a)	(b, a)Оr?

4) This relation is not antisymmetric, since (1, 2)нr and (2,1)нr, but it does not follow from this that 1=2.

5) It can be shown that the relation r is transitive using the brute force method.

	(a, b)Оr	(b, c)Оr	(a, c)	(a, c)Оr?

As per view matrix

define the properties of a binary relation

1. Reflexivity: all ones are on the main diagonal, zeros or ones are marked with asterisks.

.

2. Antireflexivity: all zeros on the main diagonal.

3. Symmetry: If .

4. Antisymmetry: all elements outside the main diagonal are zero; zeros can also be on the main diagonal.

.

The "*" operation is performed by next rule: , Where , .

5. Transitivity: If . The operation "◦" is performed according to the usual multiplication rule, while taking into account: .

3.3 Equivalence relation. Partial order relation.

An equivalence relation is a formalization of such a situation when one speaks of the similarity (identity) of two elements of a set.

Definition 3.6. The ratio of r to A There is equivalence relation, if it reflexive, symmetric and transitive. Equivalence relation a r b often denoted: a~ b.

Example 3. 8 . The relation of equality on the set of integers is an equivalence relation.

Example 3. 9 . The relation of "one height" is an equivalence relation on a set of people X.

Example 3. 1 0 . Let ¢ be the set of integers. Let's name two numbers x And y from ¢ comparable in modulom(mн¥) and write if the remainders of these numbers are equal after dividing them by m, i.e. the difference ( x-y) divided by m.

The ratio of "comparable in modulus m integers” is an equivalence relation on the set of integers ¢. Indeed:

this relation is reflexive, since for " xн¢ we have x-x=0, and hence it is divisible by m;

this relation is symmetrical, because if ( x-y) divided by m, then ( y-x) is also divisible by m;

this relation is transitive, because if ( x-y) divided by m, then for some integer t 1 we have https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, from here , i.e. ( x-z) divided by m.

Definition 3.7. The ratio of r to A There is partial order relation, if it reflexive, antisymmetric and transitive and is denoted by the symbol °.

Partial order is important in situations where we want to somehow characterize seniority. In other words, decide under what conditions to consider that one element of the set is superior to another.

Example 3. 11 . Attitude x£ y there is a partial order relation on the set of real numbers. ,

Example 3. 1 2 . In the set of subsets of some universal set U attitude AÍ B is a partial order relation.

Example 3. 1 3 . The scheme of organization of subordination in an institution is a relation of partial order on a set of positions.

The prototype of a partial order relation is the intuitive notion of a preference (precedence) relation. The preference relation distinguishes a class of tasks that can be combined as problem of choice the best object .

Task Formulation: let there be a collection of objects A and it is required to compare them in terms of preference, i.e., to set a preference relation on the set A and determine the best objects.

preference relation P, which can be defined as " aPb, a, bÎ AÛ object a no less preferable than object b» is reflexive and antisymmetric in meaning (each object is not worse than itself, and if the object a no worse b And b no worse a, then they are equally preferred). It is natural to assume that the relation P transitively (although in the case when, for example, preferences are discussed by a group of people with opposite interests, this property may be violated), i.e. P is a partial order relation.

One of the possible ways to solve the problem of comparing objects by preference is − ranging , i.e., the ordering of objects in accordance with decreasing their preference or equivalence. As a result of the ranking, we select the “best” or “worst” objects in terms of the preference relation.

Areas of use tasks about the problem of choosing the best object: decision theory, applied mathematics, technology, economics, sociology, psychology.