Lecture 3.
p. 3. Relations on sets. Properties of binary relations.
3.1. Binary relationship.
When they talk about the kinship of two people, for example, Sergei and Anna, they mean that there is a certain family, to whose members they belong. An ordered couple (Sergei, Anna) differs from other ordered pairs of people in that there is a kind of relationship between Sergei and Anna (cousin, father, etc.).
In mathematics, among all ordered pairs of direct product of two sets A and B (A´ B) also stand out "special" pairs due to the fact that between their components there are some "kinship" relationships that others do not have. As an example, consider the set S university students and many K courses read there. In direct work S´ K a large subset of ordered pairs ( s, k) with the property: student s listens to the course k... The constructed subset reflects the attitude "... listens ..." that 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 is called an arbitrary subset A´ B, i.e.
In particular, if A =B(i.e. rÍ A 2), then r is said to be a relation on the set A.
The elements a and b are called components (or coordinates ) relations r.
Comment. Let's agree that the Greek alphabet should be used to denote the relations between the elements of the sets: r, t, j, s, w, etc.
Definition 3.2. The scope of D r = ( a| $ b, what a r b) (left side). Range of values of a binary relation r is called the set R r = ( b| $ a, what a r b) (right part).
Example 3. 1. Let there be given two sets 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- real numbers and x equals y). There is a special notation "=" for this relationship. The range of definition coincides with the range of values and is a set of real numbers, D r = R r.
Example 3. 3. Let A- a lot of products in the store, and B- a set of real numbers. Then j = (( x; y)Î A´ B | y- price x) Is the relation of sets A and B.
If we pay attention to Example 3.1., Then we can notice that this relation was first specified in the form t = (( x; y)Î A´ B | x +y= 9), and then written in the form 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 to define binary relations.
Ways of defining 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 of relations r, an arrow is drawn connecting the points representing the components of the pair. Such an object is called directed graph or digraph, the points representing the elements of the sets are usually called the vertices of the graph.
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 the matrix M=[mij] size n´ m defined by the relations
.
By the way, matrix representation is a representation of a relationship in a computer.
Example 3. 4. Let there be given two sets 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, by digraph, in the form of a matrix.
Solution. 1) t = ((3; 6), (5; 4), (7; 2)) - there is a specification of the 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 . Another example is the proposed J. von Neumann(1903 - 1957) block diagram of a sequential computer that consists of many devices M:
,
where a- input device, b- arithmetic unit (processor), c- control device, d- Memory device, e- output device.
Consider information exchange between devices mi and mj that are in relation r if from device mi information enters the device mj.
This binary relation can be specified 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 a relation.
Definition 3.3. n-bed (n-arno ) the relation r is a subset of the direct product n sets, that is, the set of ordered sets ( tuples )
rÍ A one An={(a 1, …, an)| a 1Î A 1Ù… Ù anÎ An}
It is convenient to define multiplace relations using relational tables ... Such a task corresponds to enumeration of the set n-k relationship r. Relational tables are widely used in computer practice in relational databases. Note that relational tables are used in everyday practice. All kinds of production, financial, scientific and other reports are often in the form of relational tables.
Word " relational"Comes from the Latin word relation, which in translation into Russian means "attitude". Therefore, in the literature, the letter is used to denote a relationship R(Latin) or r (Greek).
Definition 3.4. Let rÍ A´ B there is a relation to A´ B. Then the ratio r-1 is called inverse attitude to a given relation 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, and s Í B´ C - attitude on B´ C. Composition relationship s and r is the ratio t Í A´ C which is defined as follows:
t = s◦r = (( a, c)| $bÎ B that (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 ratio s to 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 it follows (1,) Îs◦r;
from (1, x) Îr and ( x,!) Îs follows (1,!) Îs◦r;
from (1, y) Îr and ( y, d) Îs implies (1, d) Îs◦r;
from (3, x) Îr and ( x,!) Îs follows (3,!) Îs◦r.
Theorem 3.1. For any binary relationship, the following properties are fulfilled:
2) 
;
3) 
- the associativity of the composition.
Proof. Property 1 is obvious.
Let us 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 independently.
3.2. Properties of Binary Relations.
Consider the 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 ratio r is called anti-reflective if from ( a,b) Îr implies a¹ b.
3. The ratio r symmetrically if for a and b belonging to A, from ( a,b) Îr it follows that ( b,a) Îr.
4. The ratio r is called antisymmetric if for a and b from A, from belonging ( a,b) and ( b,a) the relation r implies that a=b.
5. Ratio r transitively if for a, b and c from A from the fact that ( 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 has the form: 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 relation have?
Solution. 1) This attitude is reflexive, since for everyone aÎ A, (a; a) Îr.
2) The attitude is not anti-reflective, since the condition of this property is not met. For example, (2, 2) Îr, but this does not mean that 2¹2.
3) Consider all possible cases, showing that the ratio 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 this does not mean 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 properties of a binary relation
1. Reflexivity: all ones are on the main diagonal, zeros or ones are denoted by asterisks.
.
2. Anti-reflectiveness: all zeros on the main diagonal.
3. Symmetry: if .
4. Antisymmetry: all elements outside the main diagonal are zero; there can be zeros on the main diagonal too.
.
The "*" operation is performed according to the following rule: 
, where , .
5. Transitivity: if . The operation "◦" is performed according to the usual rule of multiplication, while taking into account:.
3.3 Equivalence relation. Partial order relation.
The 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 reflexively, symmetrically and transitively. Equivalence relation a r b often indicated: a~ b.
Example 3. 8 . An equality relation on the set of integers is an equivalence relation.
Example 3. 9 . The ratio 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 call two numbers x and y from ¢ comparable in modulusm(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 absolute value m integers "is an equivalence relation on the set of integers ¢. Indeed:
this attitude is reflexive, because for " xÎ ¢ we have x-x= 0, and therefore it is divisible by m;
this relation is symmetric, since if ( x-y) divided by m, then ( y-x) is also divisible by m;
this relation is transitive, since 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 = ">, hence 
, 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 °.
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 on the set of real numbers there is a partial order relation. ,
Example 3. 1 2 . In the set of subsets of some universal set U attitude AÍ B there is a partial order relation.
Example 3. 1 3 . The organization chart of subordination in an institution is a partial order relationship in a variety of positions.
The prototype of the partial order relation is the intuitive concept of the preference relation (precedence). The preference relation defines a class of tasks that can be combined as choice problem the best object .
Problem statement: let there be a collection of objects A and it is required to compare them in terms of preference, that is, to set the preference relation on the set A and identify 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 no worse than itself, and if the object a not worse b and b not worse a, then they are the same in preference). It is natural to assume that the attitude P transitively (although in the case when, for example, preferences are discussed by a group of people with opposite interests, this property can be violated), i.e. P- a partial order relation.
One of the possible ways to solve the problem of comparing objects by preference is ranging , that is, the ordering of objects in accordance with the decreasing of their preference or equivalence. As a result of ranking, we single out the "best" or "worst" objects in terms of the preference relationship.
Areas of use problems about the problem of choosing the best object: decision theory, applied mathematics, technology, economics, sociology, psychology.
Let R- some binary relation on the set X, and x, y, z are any of its elements. If the element x is in relation to R with the element y, then they write xRy.
1. A relation R on a set X is called reflexive if each element of the set is in this relation with itself.
R -reflexive on X<=>xRx for any x € X
If the relation R is reflexive, then there is a loop at each vertex of the graph. For example, the relationship of equality and parallelism for line segments is reflexive, and the relationship of perpendicularity and "longer" is not reflective. This is reflected in the graphs in Figure 42.
2. A relation R on a set X is called symmetric if from the fact that an element x is in a given relation with an element y it follows that an element y is in the same relation with an element x.
R - symmetric on (xYy => y Rx)
A symmetric relationship graph contains paired arrows pointing in opposite directions. The relations of parallelism, perpendicularity and equality for line segments are symmetrical, and the ratio "longer" is not symmetric (Fig. 42).
3. A relation R on a set X is called antisymmetric if, for different elements x and y from a set X, the fact that an element x is in a given relation with an element y implies that an element y is not found in this relation with an element x.
R - antisymmetric on X «(xRy and xy ≠ yRx)
Note: the bar above denotes the negation of the statement.
On an antisymmetric relation graph, only one arrow can connect two points. An example of such a relationship is the “longer” relationship for line segments (Figure 42). The relationships of parallelism, perpendicularity, and equality are not antisymmetric. There are relationships that are neither symmetric nor antisymmetric, such as the relationship “being a brother” (Figure 40).
4. A relation R on a set X is called transitive if from the fact that an element x is in a given relation with an element y and an element y is in this relation with an element z, it follows that an element x is in a given relation with an element Z
R - transitively on A ≠ (xRy and yRz => xRz)
On the graphs of relations "longer", parallelism and equality in Figure 42, you can see that if the arrow goes from the first element to the second and from the second to the third, then there is necessarily an arrow going from the first element to the third. These relationships are transitive. Perpendicularity of line segments does not have the property of transitivity.
There are other properties of relations between elements of one set, which we do not consider.
The same relationship can have several properties. So, for example, on a set of segments the relation “equals” is reflexive, symmetric, transitive; the relation “more” is antisymmetric and transitive.
If a relation on a set X is reflexive, symmetric and transitive, then it is an equivalence relation on this set. Such a relationship breaks the set X into classes.
These relationships are manifested, for example, when performing tasks: "Pick up strips of equal length and arrange them into groups", "Arrange the balls so that there are balls of the same color in each box." Equivalence relations ("to be equal in length", "to be of the same color") determine in this case the division of the sets of stripes and balls into classes.
If a relation on a set 1 is transitive and antisymmetric, then it is called an order relation on this set.
A set with an ordering relation given on it is called an ordered set.
For example, completing the tasks: "Compare strips in width and expand them from narrowest to widest", "Compare numbers and arrange number cards in order", children arrange the elements of sets of stripes and number cards using order relations; To be wider, to follow.
In general, the relations of equivalence and order play an important role in the formation of correct ideas about the classification and ordering of sets in children. In addition, there are many other relationships that are neither equivalence nor ordering.
6. What is the characteristic property of a set?
7. What relationships can there be in sets? Explain each case and depict it using Euler circles.
8. Give the definition of a subset. Give an example of sets, one of which is a subset of the other. Write down their relationship using symbols.
9. Give the definition of equal sets. Give examples of two equal sets. Write down their relationship using symbols.
10. Give a definition of the intersection of two sets and depict it using Euler circles for each particular case.
11. Give a definition of the union of two sets and depict it using Euler circles for each particular case.
12. Give a definition of the difference of two sets and depict it using Euler circles for each particular case.
13. Define the complement and depict it using Euler circles.
14. What is called splitting a set into classes? What are the conditions for the correct classification.
15. What is called a correspondence between two sets? What are the ways of setting correspondences?
16. Which correspondence is called one-to-one?
17. What sets are called equal?
18. What sets are called equal?
19. What are the ways of defining relationships on the set.
20. What relation on the set is called reflexive?
21. What relation on the set is called symmetric?
22. What relation on a set is called antisymmetric?
23. What relation on a set is called transitive?
24. Give the definition of an equivalence relation.
25. Give the definition of the relationship of order.
26. Which set is called ordered?
Definition. The binary relation R called a subset of pairs (a, b) ∈R Cartesian product A × B, that is, R⊆A × B. Moreover, the set 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.
Methods for Specifying Binary Relations
1. A list (enumeration of pairs) for which this relation is fulfilled.
2. Matrix. A binary relation R ∈ A × A, where A = (a 1, a 2, ..., an), corresponds to a square matrix of order n, in which the element c ij at the intersection of the i-th row and j-th column, is equal to 1 if there is a relation R between ai and aj, or 0 if it is absent:
Relationship properties
Let R be a relation on a set A, R ∈ A × A. Then the ratio R:
reflexive if Ɐ a ∈ A: a R a (the main diagonal of the reflexive relation matrix contains only ones);
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, that is, c ij c ji);
antisymmetric if Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (the matrix of such a relation does not contain units that are symmetric with respect to the main diagonal);
transitively, if Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c lines, i.e., with ij = 1, then all units in the j-th row (let these units correspond to kth 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, perhaps, also in other coordinates).
Task 3.1. Determine the properties of the relation R - "to be a divisor", defined on the set of natural numbers.
Solution.
ratio R = ((a, b): a divisor b):
reflexive, not anti-reflective, since any number divides itself without remainder: a / a = 1 for all a∈N;
not symmetric, 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 relationship R - "to be a brother", given on a set of people.
Solution.
Ratio R = ((a, b): a - brother b):
non-reflective, anti-reflective due to the obvious absence of aRa for all a;
not symmetric, since in the general case between brother a and sister b there is aRb, but not bRa;
not antisymmetric, since if a and b are brothers, then aRb and bRa, but a ≠ b;
transitively, if we call people who have common parents (father and mother) brothers.
Task 3.3. Determine the properties of the relationship R - "to be the boss", given on the set of structure elements
Solution.
Ratio R = ((a, b): a - boss b):
- not reflective, anti-reflective, if it does not make sense in a specific interpretation;
- not symmetric, antisymmetric, since for all a ≠ b, aRb and bRa do not hold simultaneously;
- transitively, since if a is the boss of b and b is the boss of c, then a is the boss of c.
Determine the properties of the relation R i defined on the set M i by the matrix if:
- R 1 "have the same remainder when divided by 5"; M 1 is the set of natural numbers.
- R 2 "be equal"; M 2 is the set of natural numbers.
- R 3 “live in one city”; M 3 a lot of people.
- R 4 "to be familiar"; M 4 a lot of people.
- R 5 ((a, b) :( a-b) - even; M 5 is a set of numbers (1,2,3,4,5,6,7,8,9).
- R 6 ((a, b) :( a + b) - even; M 6 is a set of numbers (1,2,3,4,5,6,7,8,9).
- R 7 ((a, b): (a + 1) - divisor (a + b)); M 7 - set (1,2,3,4,5,6,7,8,9).
- R 8 ((a, b): a - divisor (a + b), a ≠ 1); M 8 is the set of natural numbers.
- R 9 “to be a sister”; M 9 is a lot of people.
- 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.
an association R 1 ∪ R 2: R 1 ∪ R 2 = ((a, b): (a, b) ∈ R 1 or (a, b) ∈ R 2);
crossing 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 attitude U: = ((a; b) / a ∈ A & b ∈ A). ;
addition R 1 U \ R 1, where U = A × A;
identity relation I: = ((a; a) / a ∈ A);
inverse 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. The degree of relationship R on a set A is called 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 the set A.
- R is reflexive if and only if (in what follows, the sign ⇔ is used) when I ⊂ R.
- R is symmetric ⇔ R = R -1.
- R transitively ⇔ R º R ⊂ R
- R is antisymmetric ⇔ R ⌒ R -1 ⊂ I.
- 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 enumerating pairs: R = ((1,1), (2,3), (2,4), ( 3.1), (3.4)). In addition, S is the 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 ) -one .
Task 3.5 ... Let R be the relation "... parent ...", and S the relation "... brother ..." on the set of all people. Give a short verbal description of the relationship:
R -1, S -1, R º S, S -1 º R -1 and R º R.
Solution.
R -1 - attitude "... child ...";
S -1 - attitude "... brother or sister ...";
R º S - relation "... parent ...";
S -1 º R -1 - attitude "... child ..."
R º R - attitude "... grandmother or grandfather ..."
Tasks for independent solution
1) Let R be the relation "... father ...", and S - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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.
A relation defined on a set can have a number of properties, namely:
2. Reflexivity
Definition. Attitude R many X is called reflexive if each element X multitudes 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. Anti-reflectiveness
Definition. Attitude R many X is called antireflexive if no element X multitudes X not in relation R With myself.
R anti-reflective on X Û(" XÎ X)
Example. The relationship "straight line X perpendicular to a straight line at»On the set of straight lines in the plane is antireflexive, since no straight line of the plane is perpendicular to itself.
The antireflexive relation graph does not contain any loops.
Note that there are relationships that are neither reflexive nor anti-reflective. For example, consider the relation “point X symmetrical to point at»On the set of points of the plane.
Dot X symmetrical to point X- true; dot at symmetrical to point at- false, therefore, we cannot assert that all points of the plane are symmetrical to themselves, and we also cannot assert that not a single point of the plane is symmetric to itself.
3. Symmetry
Definition... Attitude R many 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 "straight line X crosses the straight line at on the set of straight lines in the plane "is symmetric, since if straight X crosses the straight line at, then a straight line at will definitely cross the straight line X.
Symmetric relationship 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 many X is called asymmetric if for no elements X, at of the multitude 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 asymmetrical X Û(" X, atÎ X) x R y Þ
Example. Attitude " X < at»Asymmetrically, because for no pair of elements X, at it cannot be said that at the same time X < at and at<X.
An asymmetric relation graph has no loops, and if two vertices of the graph are connected by an arrow, then there is only one arrow.
5. Antisymmetry
Definition... Attitude R many X is called antisymmetric if from the fact that X is in relation with at, a at is in relation with X follows that X = at.
R antisymmetric X Û(" X, atÎ X) x R y Ù y R xÞ x = y
Example. Attitude " X£ at»Antisymmetric, because conditions X£ at and at£ X are simultaneously executed only when X = at.
The antisymmetric relation graph has loops and if two vertices of the graph are connected by an arrow, then there is only one arrow.
6. Transitivity
Definition... Attitude R many X is called transitive if for any elements X, at, z of the multitude X from what X is in relation with at, a at is in relation with z follows that X is in relation with z.
R transitively X Û(" X, at, zÎ X) x R y Ù y R zÞ x R z
Example. Attitude " X multiples at»Transitively, since if the first number is a multiple of the second, and the second is a multiple of the third, then the first number will be a multiple of the third.
Transitive relation graph with each pair of arrows from X To at and from at To z contains an arrow from X To z.
7. Connectivity
Definition... Attitude R many X is called connected if for any elements X, at of the multitude X x is in relation with at or at is in relation with X or x = y.
R connected X Û(" X, at, zÎ X) x R y Ú y R zÚ X= at
In other words: attitude R many X is called connected if for any different elements X, at of the multitude X x is in relation with at or at is in relation with X or x = y.
Example. Attitude " X< at»Is connected, since whatever real numbers we take, one of them is sure to be greater than the other, or they are equal.
On the graph of a connected relation, all vertices are connected to each other by arrows.
Example. Check what properties
attitude " X - divider at»Defined on the set
X= {2; 3; 4; 6; 8}.
1) this attitude is reflexive, because each number from a given set is a divisor of itself;
2) this attitude does not possess the property of antireflexivity;
3) the property of symmetry is not fulfilled, since for example, 2 is a divisor of 4, but 4 is not a divisor of 2;
4) this ratio is antisymmetric: two numbers can be simultaneously 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 possess the connectivity property, since For example, the numbers 2 and 3 on the graph are not connected by an arrow, because two different numbers 2 and 3 are not divisors of each other.
Thus, this relation has the properties of reflexivity, asymmetry and transitivity.
§ 3. Equivalence relation.
Relationship between an equivalence relation and partitioning 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 relation “ X fellow student at"On a lot of pedagogical students. It has properties:
1) reflexivity, because each student is his own classmate;
2) symmetry, because if student X at, then the student at is a fellow student X;
3) transitivity, since if student X- classmate at and student at- classmate z then student X will be a fellow student z.
Thus, this relation possesses the properties of reflexivity, symmetry and transitivity, which means it is an equivalence relation. Moreover, the set of pedagogical students can be divided into subsets consisting of students enrolled in the same course. We get 5 subsets.
Equivalence relations are also, for example, the relation of parallelism of straight lines, the relation of equality of figures. Each such relationship is associated with dividing the set into classes.
Theorem. If on the set X an equivalence relation is given, then it splits this set into pairwise disjoint subsets (equivalence classes).
The converse 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 specified. Is it an equivalence relation?
Let's construct a graph of this relation:
This relation possesses 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 contain 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. an arbitrary element of this class. So, a class of equal fractions can be specified by specifying any fraction belonging to this class.
In the elementary course of mathematics, there are also equivalence relations, for example, “expressions X and at have the same numerical values "," the figure X equal to the figure at».
Binary ratio T (M) on the set M called a subset M 2 = M X M, T (M) With M 2. The formal notation of a binary relation looks like shkT (M) =((X, y) / (x, y) e T With M X M). Please note: further we will consider only non-empty sets Mi assigned non-empty binary relations T (M)
A binary relation is a more general concept than a function. Every function is a binary relation, but not every binary relation is a function.
For example, many pairs R = {(a, b), (a, c), (a, b)) is a binary relation on the set (a, b, c, (1), but it is not a function. Conversely, the function P = {(a, b), (b, c), (c1, a)) is a binary relation defined on the set (a, b, c, c. !}
We have already encountered the concept of a relationship when considering c (inclusion) and = (equality) between sets. Also, you have repeatedly used the relationship =, F, given on the set of numbers - both natural and integer, rational, real, etc.
Let us define several concepts regarding a binary relation defined on the set M [ 2, 11].
Reverse attitude
I - "= ((x, y) / (y, x) € I). (1.14)
Complementary relation
Л = ((*, Y) / (X, y) d /?). (1.15)
Identity relation
and =((X, x) / XEM). (1.16)
Universal attitude
I = ((x, y) / xeM, yeM). (1.17)
Let's consider several tasks.
Task 1.8
On the set M = (a, b, With, c1, f) a binary ratio T (M) = = ((a, a), (a, B), (B, s), (s,? /), (^ /, b), (b, f)). Build relationships: inverse to T, complementary to T, identical binary relation and and universal binary relation /.
Solution.
To solve these problems, we only need definitions.
By definition, on the set M = (a, B, With, b, f) inverse to DL /) binary relation must contain all inverse pairs identical binary relation T ~ = {(a, a), (/ ?, i), (s, 6), (b, c), (^ /,? /), (c, b)).
By definition, on the set M = (a, b, c, b, f) additional to T (M) the binary relation must contain all pairs from the Cartesian product M 2, which do not belong T (M), those. (( a, With), (a, A), (a, e), (b, a), (b, b), (b, b), (b, e),(With, a),(With, B), (c, s), (s, f), (b, a), (b, b), (b, c), (f, a), (f, b), (f, With), (f, b), (f, f)).
By definition, on the set M = (a, b, With, b, e) identical binary relation and = ((a, a), (B, /?), (c, c), (^ /, ^ /), (her)).
By definition, on the set M = {a, 6, s, b, f) the universal binary relation contains all pairs from the Cartesian product M 2, those. / = ((a, a), (a, A), (o, s), (a,), (i, f), (b, a), (b, b), (b, With), (B, b), (b, f),(With, a),(s, L), (s, s), (s, dO, (s, f), (b, a), (b, A), (, c), (,), (^,
Task 1.9
On the set M of natural numbers from 1 before 5 build a binary relation R = {(a, d) / mod (? r, Z>) = 0), where mod - remainder after dividing a by b.
Solution.
In accordance with the task on the set of natural numbers M we construct such pairs ( a, B), where a divided by b without a remainder, i.e. mod (?, B) = = 0. We get R = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3, 1), (4, 1), (5, 1), (4, 2)}.
There are several main ways to define binary relations: enumeration, graphical representation, matrix representation.
Binary relationship R can be specified as an enumeration, like any set of pairs.
In graphical representation, each element x and y multitudes M is represented by a vertex, and the pair (x, y) appears as an arc of x in u.
In a matrix way, binary relations are specified using an adjacency matrix. This method is most convenient when solving problems using a computer.
Adjacency matrix S is a square matrix tx / d, where T - cardinality M, and each of its elements 5 (x, y) is equal to one if the pair (x, y) belongs to T (M), and is equal to zero otherwise.
In fig. 1.3 presents a graphical and matrix representation for T (M) = {(a, a), (a, b), (b, c), (c, d), (d, d), (d, e)).
When defining the properties of binary relations, one usually distinguishes reflexivity, symmetry and transitivity.
Binary relation T (M) called reflective if and only if for each element x e M pair (x, x) belongs to this binary relation T (M), those. Vx e M, 3 (x, x) e T (M).
Rice. 1.3. Graphic (a) and matrix (b) representation of the set
The classical definition of this property is the following statement: from the fact that the element x belongs to the set M, it follows that the pair (x, x) belongs to the binary relation T (M), given on this set, i.e. / xєM-) (x, x) є T (M).
The opposite property of binary relations is called irreflexivity. Binary relation T (M) called irreflexive if and only if for each element x from the set M the pair (x, x) does not belong to this binary relation, i.e. / x є M-> (x, x) e T (M).
If the binary relation T (M) has neither the property of reflexivity, nor the property of irreflexivity, then it is non-reflective.
For example, for the set M - (a, b, c, ^/, e) binary relation T X (M) = {(a, a), (a, b), (b, b), (b, s), (s, s), (s, cі), (cі, cі), (si, With), (her)) is reflexive, T 2 (M) = {(a, B), (B, s), (s, cі), (cі, c), (cі, e)) is irreflexive, and T 3 (M) = {(a, a), (a, b), (B, s), (s, cі), (si,? /), (? /, s)) is non-reflective.
If in the set M contains at least one element x, then the correct classification is not difficult. Please note: for an unambiguous solution to the classification problem, the reflexivity property should be determined only for non-empty sets!
Accordingly, a binary relation on an empty set is non-reflexive, just as an empty binary relation will be non-reflexive.
Binary relation T (M) called symmetrical if and only if for each pair of different elements (x, y) belonging to the binary relation T (M), the inverse pair (y, x) also belongs to this binary relation, i.e. /(X, y) є T (M), 3 (y, x) є T (M). We define the symmetry property only for sets containing at least two different elements and non-empty binary relations.
The classical definition of the property of symmetry is the following statement: from the fact that the pair (x, y) belongs T (M), it follows that the inverse pair (y, x) also belongs to T (M), those. / (x, y) є T (M)-> (y, x) є T (M). In this case, if x = y, then the property of symmetry smoothly turns into reflexivity.
The opposite property of binary relations is called antisymmetry. Binary relation T (M) called antisymmetric if and only if for each pair of different elements x and y the pair (y, x) does not belong to this binary relation, i.e. / (x, y) є T (M),(y, x) i T (M).
The following can be considered the classical definition of antisymmetry. From the fact that in an antisymmetric binary relation T (M) for any pair (x, y) reverse pair (y, X) also belongs to T (M), follows that x = y, those. ((X, y)e T (M), (at, x) e T (M)) -> -> x = at.
If the binary relation T (M) has neither the property of symmetry nor the property of antisymmetry, then it is asymmetric.
When Miles T (M) empty or M contains a single element x, our binary relation is both symmetric and antisymmetric at the same time. For an unambiguous solution to the classification problem, the set M must contain at least two different elements x and y. Then binary relations on an empty set, as well as on sets with one element, are asymmetric.
M - (a, b, c, ^/, e). Binary relation Г, = (( a, a), (a, b), (B, a), (With, c1), (With/, s), (e, s), (s, f)) is symmetrical, T 2 = ((a, a), (a, b),(With, c1), (e, s), (s, B), (B, e)) is antisymmetric, T 3 = ((a, a), (a, B), (6, i), (s, c1), (e, s), (s, i)) - asymmetric. Please note: the loop ( a, i) does not in any way affect the symmetry and antisymmetry.
The transitivity property is defined on three different elements x, at and I multitudes M. Binary relation T (M) called transitive if and only if for every two pairs of different elements (x, y) and (y, O belonging to a binary relation T (M), pair (x, ?) also belongs to this binary relation, i.e. (/ (x, y) e T (M),/ (y, I) e T (M)), 3 (x, I) e T (M). Thus, between the elements x and ^ there is a transitive closure ("transit"), which "straightens" a path of length two (x, y) and (y, z)?
The classical definition of the transitivity property is formulated as follows: from the fact that in a transitive binary relation T (M) there is a pair (x, y) and a pair (y, I), it follows that the pair (x, I) also belongs to this binary relation, i.e. ((x, y) e T (M), (y, I) e T (M))-e (x, I) e T (M).
Binary relation T (M) called intransitive if and only if for every two pairs of elements (x, y) and (y,?) belonging to the binary relation T (M), pair (x, does not belong to this binary relation, i.e. (f (x, y) e T (M),/ (y, I) e T (M)),(X, I) ? T (M). Thus, in an intransitive binary relation, no existing path of length two has a transitive closure!
The classical definition of the intransitivity property is formulated as follows: from the fact that in a transitive binary relation T (M) there is a couple (X, y) and a pair (y, I), it follows that the pair (x, i) does not belong to this binary relation, i.e. ((*, y) e T (M),(y, I) e T (M))-e (x, I)? T (M).
If the binary relation T (M) possesses neither the property of transitivity, nor the property of intransitivity, then it is nontransitive.
For example, consider the set M - (a, B, With, b, f). Binary relation T x = {(a, a), (a, B), (a, With), ( B, With), (With, With), ( e, c)) is transitive, T 2= ((i, i), (i, 6), (6, s), (s, 1), (?, 0) is intransitive, T 3 = {(a, i), (i, 6), (6, c), (^ /, c), (i, c), ( e,? /)) - non-transitive.
Task 1.10
On the set M x - (a, b, c, b, e) construct a binary relation R with the given properties: non-reflexivity, antisymmetry and nontransitivity.
Solution.
There are a lot of correct solutions to this problem! Let's build one of them. In our binary relation, some vertices, but not all, must have loops; there should not be a single back arc; there must be at least two paths of length 2, of which at least one does not have a transitive closure. Thus, we get I = ((a, a), (B, B), (a, B), (B, c), (c, b), (b, f), (a, c), (c, f)).
Task 1.11
Determine the properties of the binary relation T, given on the set M 2 = (a, b, c, b, f), shown earlier in Fig. 1.3.
Solution.
In a given binary relation, there are loops on two vertices, and there are no three loops, therefore, the binary relation is non-reflective. There is no backward arc, therefore, the binary relation is antisymmetric. A binary relation has several paths of length two, but none of them has a transitive closure - T intransitively.
