Let r be a relation on a set. Binary Relations - MT1102: Linear Algebra (Introduction to Mathematics) - Business Informatics
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, but 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 terms 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, but 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: relation 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».
The concept of a relation, along with the concept of a set, "penetrates" all of mathematics. Intuitively, a relationship is understood as a connection of objects. Our task is to, using the constructions of set theory formulated above, determine in mathematical language what is meant in mathematics by the term "relationship".
Binary relations on a set
Let there be a set BUT. Relationship of elements henna sets BUT modeled by a pair (du>). If element X associated with y, hence, we have a pair (n:, y) as an element of some set; if d; not associated with at, so the pair (n: ^) is not an object of a set. So we have the following definition.
Binary relation on the set A is an arbitrary set of pairs of elements from BUT.
In other words, the binary relation on the set BUT- subset of the direct product AHA=A 2 . In particular, the very set A 2 of all pairs is a binary relation.
By analogy with a binary (or two-place) relation, one can consider n-local relation on the set as a subset of the direct product BUT". We will mainly consider binary relations, but for the sake of brevity, we simply say: “a relation on a set BUT".
Denote an arbitrary binary relation by the Greek letter p.
If (l", y )e p, then we say that l" is in relation p with y, and write
If (dy)? P> then we have the negation of the corresponding statement. In this case, along with the notation ~|(xpy) (or xpy), they write dr, crossing out the relation sign.
Example 8.1.1. Consider the set BUT= (1,2,3,4,5). Plenty of couples
determines on BUT the ratio "less than", denoted by the sign<.>
11on the same set, one can consider another set of pairs
it defines the relation of equality.
Example 8.1.2. Consider the set (N, Z, Q, I, R) of basic numerical sets and the set of pairs
We have the relation defined by us in Section 2.2 as the relation of strict inclusion of sets. Note that, for example, the pair (Q. I) does not lie in the specified set, since Qczl; moreover, these sets do not intersect.
Example 8.1.3. Given a set of words L = (current, cat, shock, stake, varnish). Consider this relation:
p = ((current, shock), (shock, current), (shock, count), (count, shock),
(col, varnish), (lacquer, coll), (cat, coll), (col, cat)).
This relation can be expressed as follows: the words of the set BUT are in relation p if and only if they have exactly two identical letters.
Note that any set of pairs is a relation, whether or not there is a good verbal description for that relation.
Since the relation is a set, it can be specified by a characteristic property, then the network is a predicate R(xy): p = ((.*,>>) eL 2 R(xy)). The notation is also used:
They read: “g is in relation to at if and only if true R(hu)".
Example 8.1.4. We define on the set /! = (1,2,3,4,5) ratio:
Here R(xy)= (l+2=y). Let's define this relation by enumeration of pairs:
Example 8.1.5. Set on the set Z(or on a set N) relation with the help of the sentence: "There is an integer /? such that x=n y. Symbolically, we can write:
We have the divisibility relation already defined earlier, denoted by the sign:. This relation includes such pairs as (6.2), (6.3), (4.4), (111, -37) and others. Unlike the previous examples, this set of pairs is infinite, and it will not be possible to enumerate all the pairs.
Let us consider the most important properties that binary relations on a set can have.
The relation p on the set BUT called reflective if any element X from BUT is in relation p with itself, that is, for all q; from BUT lrt is running:
Example 8.1.6. Consider the divisibility relation on the set Z. Take an arbitrary integer X. Because x=x 9 then x': x. So every integer is divisible by itself: V.veZ (l:l). Therefore, the divisibility relation is reflexive.
Since any set is a subset of itself, the set inclusion relation is reflexive (on any collection of sets).
The relation p on the set BUT called antireflective if no element of the set BUT is not in relation p with itself:
Example 8.1.7. R is antireflexive, since no number is less than itself.
Let us construct the negation of the sentence "The relation p is reflexive":
Thus, the relation p is not reflexive if and only if there is an element hea, which is not in relation to p with itself. A relation that is not reflexive need not be antireflexive.
Example 8.1.8. Consider the relation on the set R, given by the sentence "Number X opposite number at". Number X called the opposite number y, if the amount x+y equals 0.
This relationship is not reflexive. Counterexample: x=1. Since 1 + 1*0, 1 is not the opposite of 1.
This relation is not antireflexive. Counterexample: ,v=0. Since 0+0=0, then 0 is the opposite of 0.
The relation p on the set BUT called symmetrical if from what X is in relation to r y, follows that at is in relation to r
Example 8.1.9. From identity x+y=y+.x the statement follows: for any real numbers X And at if X opposite to v, then at opposite X. So this relationship is symmetrical. It is often said simply: "Numbers X And at are opposite."
The ratio "Number X less than number at" on the set R is not symmetrical: 3 is less than 4, but 4 is not less than 3.
The relation p on the set BUT called antisymmetric, if for no different elements x and y from A, such that xru, not fulfilled
urh:
Example 8.1.10. The relation "less than" on the set R antisymmetric.
The definition of an antisymmetric relation can be formulated in other ways. Let us introduce the notation:
Using the truth table, we can prove that formula 1 R l M- is equivalent to the formula M l K -> P, which, in turn, according to the rule of contraposition is equivalent to 1 R->~|(L/L TO). Based on this, we can say that the relation p is antisymmetric if and only if one of the equivalent conditions is satisfied:
A) Because xru And urh, should x=y:
B) No different elements can be in relation p with each other at the same time.
Example 8.1.11. Consider the inclusion relation on an arbitrary family of sets. Since Lsul Y^X=>X=Y, then the inclusion e is an antisymmetric relation.
Example 8.1.12. Divisibility relation on a set Z is neither symmetric nor antisymmetric. Since 4:2 but 2?4, the ratio is not symmetrical. Since 2:(-2) and (-2):2 but (-2)^2, the relation is not antisymmetric.
However, on the set N of natural numbers we have an antisymmetric relation: Vjt^eN (x:y lu:x -> x=y). Check this statement using the definition of divisibility.
The relation p on the set BUT called transitive if from what X is in relation to r y, but at is in relation to p with z, it follows that V is in relation to p with z:
Example 8.1.13. The divisibility relation is transitive (both on the set Z and on the set N): x:y l y: z => x:z. Let's show it. Let be x:y And y:z. Then x=ny And y=kz for some integers P And to. Then x = n(kz) = (nk)z = mz, where T is an integer. That's why xz.
The set inclusion relation is also transitive: Xcy l YcZ => XezZ. Prove it.
The relation "Numbers X And at opposite" is not transitive. Counterexample: x=2, y=-2, 2=2. Then the numbers 2 and (-2) are opposite, and also (-2) and 2 are opposite. But the numbers x=2 and z=2 ns are opposite.
Example 8.1.14. Consider some examples of relationships from the previous paragraph.
The relation from Example 8.1.3 is anti-reflexive and symmetrical. The relation from Example 8.1.4 is antireflexive and antisymmetric. None of these relations is transitive. Prove this by considering appropriate counterexamples.
Some relations that simultaneously have a number of properties are given common names. From the examples considered above, the inclusion relation c and the divisibility relation on the set N simultaneously have the properties of reflexivity, antisymmegricity, and transitivity. Also, these three properties are possessed by the relation "X less than or equal at", defined on the set R (or on any of its subsets):
The reflexive, antisymmetric and transitive relation is called relation of order.
Lots of BUT, on which the order relation p is given, is called ordered set. Write (BUT, R).
At present, the theory of ordered sets is a large branch of mathematics, to which entire books are devoted. We note only a number of features of the concept of "ordered set".
Intuitively, the words "ordered set" are often understood in a narrower sense. Consider an ordered l-ku, composed of pairwise distinct elements. For example, the five letters (III, K, O, L, A) define the word SCHOOL. In this case, the words "the elements are written in a certain order" are understood in the sense that we numbered them with natural numbers 1, 2, 3, 4, 5 and arranged them in ascending order of numbers. Let's generalize this example.
Let an "-element set BUT. Having somehow numbered the elements with it a, a 2 > a „, we actually get an ordered set by defining the order relation as follows:
The ratio is understood as follows: what an element X associated with another element y, means that X written in the tuple to the left y.
Example 8.1.15. The set /4=(a,b.c,d) is given. The ordered quadruple of its different elements (b, c, a, d) will give the following order relation:
((b,b), (b,c), (b,a), (b,d), (c,c), (c,a), (c,d), (a,a), ( a, d), (d, d)).
Note that the order need not have the so-called linearity property.
Example 8.1.16. Consider on the set A =(2,4,6,8) divisibility ratio:. Specify this relation by a set of pairs. Since in BUT lie only natural numbers, then: order relation. We have an ordered set A, :).
Such an order cannot be represented as an ordered four consecutive elements. You can give a graphic illustration of the relationship using dots and arrows: from a point X exactly at arrow leads if and only if x:y.
Consider the numbers 6 and 4. Neither of them is divisible by the other. They say that these are incomparable elements.
Let on the set BUT the ratio of order p is given. Elements * and at called comparable, if at least one of the two relations is satisfied xru or urkh.
The order of p on the set BUT called linear if any two elements of the set BUT comparable. A set on which a linear order is defined is called linearly ordered(or chain).
Example 8.1.17. The relation R is a linear order, since Vx^yeR (x Therefore (R,
ordered set.
The ratio of divisibility of natural numbers in the general case is not a linear order. A counterexample is given in Example 8.1.16."
Note that any linear order on a finite set is given by the enumeration of its elements. To emphasize that the order may not be linear, an ordered set is generally sometimes called a partially ordered set.
To define the general concept of a binary relation on a set, we proceed in the same way as in the case of correspondences,
those. Let's look at a specific example first. Let the relation "less than" be given on the set X = (2, 4, 6, 8). This means that for any two numbers from the set X, you can say which of them is less: 2< 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения X х X, поэтому об отношении «меньше», заданном на множестве X, можно сказать, что оно является подмножеством множества X х X.
In general, binary relations on a set X are defined in the following way:
Definition. A binary relation on a set X is any subset of the Cartesian product X x X.
Since in the future we will consider only binary relations, the word "binary", as a rule, will be omitted.
Let us agree to denote relations by the letters R, S, T, P, etc.
If R are relations on the set X, then, according to the definition, R X x X. On the other hand, if some subset of the set X x X is given, then it defines some relation R on the set X.
The statement that the elements x and y are in relation R can be written as: (x, y) R or x R y. The last entry reads: "Element x is in relation R with element y."
Relationships are defined in the same way as correspondences. A relation can be specified by listing the pairs of elements of the set X that are in this relation. The forms of representation of such pairs can be different - they are similar to the forms of assignment of correspondences. The differences relate to setting relationships using a graph.
Let's build, for example, a graph of relations "less than" given on the set X= (2, 4, 6, 8). To do this, we depict the elements of the set X as points (they are called the vertices of the graph), and the “less than” relation is represented by an arrow (Fig. 1).
On the same set X, another relation can be considered - "multiply". The graph of this relation will have a loop at each vertex (an arrow whose beginning and end coincide), since each number is a multiple of itself (Fig. 2).
A relation can be specified using a two-variable clause. So, for example, the relations “less than” and “multiple” considered above are given, and the short form of the sentences “the number x is less than the number y” and “the number x is a multiple of the number y” is used. Some of these sentences can be written using symbols. For example, the relations “less than” and “multiply” could be specified in the following form: “x<у», «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х – у = 3).
For the relation R, given on the set X, one can always set the relation R -1 , its inverse - it is defined in the same way as the correspondence inverse to the given one. For example, if R is the relation "x is less than y", then the relation "y is greater than x" will be its inverse.
The concept of a relation inverse to a given one is often used in the initial teaching of mathematics. For example, in order to prevent an error in choosing the action with which the problem is solved: “Petya has 7 pencils, which is 2 less than Boris. How many pencils does Boris have? - it will be reformulated: “Petya has 7 pencils, and Borya has 2 more. How many pencils does Boris have? We see that the reformulation was reduced to replacing the relation “less than by 2” with the inverse relation “greater by 2”.
Relationship Properties
We have established that a binary relation on a set X is a set of ordered pairs of elements belonging to the Cartesian product XxX. This is the mathematical essence of any relationship. But, like any other concepts, relationships have properties. They were able to isolate by studying various specific relationships. There are a lot of properties, in our course we will study only a few. Consider on the set of segments shown in Fig. 3, the relationship of perpendicularity, equality and "longer". We will construct graphs of these relations (Fig. 4) and compare them.
We see that the equality relation graph differs from the other two by the presence of loops at each of its vertices. These loops are the result of the fact that the relation of equal segments has the property that any segment is equal to itself. The relation of equality is said to have the property reflexivity or just what it is reflexively .
Definition. A relation R on a set X is said to be reflexive if each element of the set X can be said to be in relation to R with itself.
R reflexively on X<=>xRx for any x X
If the relation R is reflexive on the set X, then there is a loop at each vertex of the graph of this relation. The converse statement is also true: a graph, each vertex of which has a loop, defines relations that have the property of reflexivity.
Examples of reflexive relationships:
The relation is "multiple" on the set of natural numbers (each natural number is a multiple of itself);
Similarity relation of triangles (each triangle is similar to itself).
There are relations that do not have the property of reflexivity. Such, for example, is the relation of perpendicularity on a set of segments: there is not a single segment about which it can be said that it is perpendicular to itself. Therefore, there is not a single loop on the graph of the perpendicularity relation (Fig. 4). It does not have the property of reflexivity and the ratio is "longer" for segments.
Let us now pay attention to the graphs of perpendicularity and equality of segments. They are "similar" in that if there is one arrow connecting a pair of elements, then there must be another one connecting the same elements, but going in the opposite direction. This feature of the graph reflects the properties that the relations of parallelism and equality of segments have:
If one segment is perpendicular to another segment, then this "other" is perpendicular to the first;
If one segment is equal to another segment, then this “other” is equal to the first one.
About the relationship of perpendicularity and equality of segments, they say that they have the property of symmetry or are simply symmetrical.
Definition. A relation R on a set X is said to be symmetric if the following condition is satisfied: from the fact that element x is in relation R with element y, it follows that element y is also in relation R with element x.
Using symbols, this relationship can be written as follows:
R is symmetrical on X<=>(xRy => yRx)
A graph of a symmetric relation has the peculiarity that, along with every arrow going from x to y, the graph also contains an arrow going from y to x. The converse is also true. A graph containing, together with each arrow going from x to y, and an arrow going from y to x, is a symmetric relation graph.
In addition to the two examples of symmetric relations considered, we add the following:
The relation of parallelism on the set of lines (if the line x is parallel to the line y, then the line y is also parallel to the line x);
Similarity relation of triangles (if triangle F is similar to triangle P, then triangle P is similar to triangle F).
There are relations that do not have the property of symmetry. Such, for example, is the relation "longer" on the set of segments. Indeed, if the segment x is longer than the segment y, then the segment y cannot be longer than the segment x. About the relationship "longer" they say that it has the property of antisymmetry or simply antisymmetric.
Definition. A relation R on a set X is said to be antisymmetric if for different elements x and y from the set X the following condition is satisfied: from the fact that x is in relation R with element y, it follows that element y is not in relation R with element x .
antisymmetric on X<=>(xRy and x≠y => )
A graph of an antisymmetric relation has a singularity: if two vertices of the graph are connected by an arrow, then this arrow is only one. The converse statement is also true: a graph whose vertices are connected by only one arrow is a graph of an antisymmetric relation.
In addition to the “longer” relation on the set of segments, for example, the following possess the antisymmetry property:
The "greater than" relation for numbers (if x is greater than y, then y cannot be greater than x);
The ratio "greater than 2" for numbers (if x is greater than y by 2, then y cannot be 2 greater than x).
There are relations that have neither the property of symmetry nor the property of antisymmetry. Consider, for example, the relation "to be a sister" on the set of children of the same family. Let there be three children in the family: Katya, Masha and Tolya. Then the graph of the relation "to be a sister" will be as in Figure 5. It shows that this relation has neither the property of symmetry nor the property of antisymmetry.
Let us pay attention once again to one feature of the relation graph "longer" (Fig. 4). On it you can see: if the arrows are drawn from e to but and from but to from, that is, an arrow from e to from; if the arrows are from e to b and from b to from, that is, an arrow and from e to from etc. This feature of the graph reflects an important property of the “longer” relation: if the first segment is longer than the second, and the second is longer than the third, then the first is longer than the third. This relation is said to have the property of transitivity, or simply transitive.
Definition. A relation R on a set X is said to be transitive if the following condition is satisfied: from the fact that element x is in relation R with element y and element y is in relation R with element z, it follows that element x is in relation R with element z.
Using symbols, this definition can be written as follows:
R is transitive on X<=>(xRy and yRz => xRz)
Graph of a transitive relation with each pair of arrows going from X to at And at to z, contains an arrow going from X to z. The converse is also true.
In addition to the relation “longer” on the set of segments, the equality relation has the property of transitivity: if the segment X equal to the segment at and segment at equal to the segment z, then the segment X equal to the segment z. This property is also reflected in the equality relation graph (Fig. 4)
There are relations that do not have the property of transitivity. Such a relation is, for example, the perpendicularity relation: if segment a is perpendicular to segment d, and segment d is perpendicular to segment b, then segments a and b are not perpendicular!
Consider another property of relations, which is called the connected property, and a relation that has it is called connected.
Definition. A relation R on a set X is called connected if for any elements x and y from the set X the following condition is satisfied: since x and y are different, it follows that either x is in relation R with element y, or element y is in relation R with element x.
Using symbols, this definition can be written as follows:
R is connected on the set X<=>(x≠y xRy or yRx)
For example, the relation "greater than" for natural numbers has the connectedness property: for any distinct numbers x and y, one can say that either x > y or y > x.
In a relation graph, any two vertices are connected by an arrow. The converse is also true.
There are relations that do not have the property of being connected. Such a relation, for example, is the relation of divisibility on the set of natural numbers: we can call such numbers xny such that neither the number x is a divisor of the number y, nor the number y is a divisor of the number x.
The selected properties allow us to analyze various relationships from a general standpoint - the presence (or absence) of certain properties in them.
So, if we summarize everything that has been said about the equality relation given on the set of segments (Fig. 4), then it turns out that it is reflexive, symmetric and transitive. The relation “longer” on the same set of segments is antisymmetric and transitive, while the perpendicularity relation is symmetric, but it does not have the properties of reflexivity and transitivity. All these relations on a given set
segments are not connected.
Task 1. Formulate the properties of the relation R given by the graph (Fig. 6).
Solution. The relation R- is antisymmetric, since the vertices of the graph are connected by only one arrow.
The relation R is transitive, since with a pair of arrows coming from b to but and from but to from, there is an arrow on the graph going from b to from.
The relation R is connected, since any two vertices are connected by an arrow.
The relation R does not have the property of reflexivity, since there are vertices on the graph where there are no loops.
Problem 2. Formulate the properties of the relation "greater than 2 times", given on the set of natural numbers.
Solution. "More than 2 times" is a short form of the relationship "the number of x is greater than the number of y is 2 times." This relation is antisymmetric, since the condition is satisfied: from the fact that the number x is 2 times greater than the number y, it follows that the number y is not greater than the number x by 2 times.
This relation does not have the property of reflexivity, because no number can be said to be twice as large as itself.
The given relation is not transitive, since from the fact that the number X more number at by 2, and the number y is greater than the number z by 2, it follows that the number X cannot be more than a number z on 2.
This relation on the set of natural numbers does not have the connectedness property, since there are pairs of numbers x and y such that neither the number is twice as large as y nor the number y is twice as large as x. For example, these are the numbers 7 and 3.5 and 8, etc.
binary relationships.
Let A and B be arbitrary sets. Let's take one element from each set, a from A, b from B and write them like this:
Cartesian product arbitrary sets A and B (denoted: AB) is a set consisting of all possible ordered pairs, the first element of which belongs to A, and the second belongs to B. By definition: AB = (
Example 5. Let A = (x, y) and B = (1, 2, 3).
AB=(
BA=(<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.
AA = A 2 = (
BB = B 2 = (<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.
binary relation on a set M is called the set of some ordered pairs of elements of the set M. If r is a binary relation and a pair
Example 6. Set (<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>) is a binary relation on the set (1, 2, 3, 4, 5).
Example 7. The relation ³ on the set of integers is a binary relation. This is an infinite set of ordered pairs of the form
Example 8. The relation of equality on the set A is a binary relation: I A = (
Since binary relations are sets, the operations of union, intersection, addition, and difference are applicable to them.
Scope of definition the binary relation r is the set D(r) = ( x | there is y such that xry ). Value area the binary relation r is the set R(r) = ( y | there is x such that xry ).
attitude, reverse to the binary relation r Н M 2 is called the binary relation r -1 = (
Composition binary relations r 1 and r 2 defined on the set M is called the binary relation r 2 o r 1 = (
Example 9. Let a binary relation r be defined on the set M = (a, b, c, d), r = (
Let r be a binary relation on a set M. The relation r is called reflective, if x r x for any x О M. The relation r is called symmetrical, if together with each pair
Let us indicate the criteria for the fulfillment of these properties.
A binary relation r on a set M is reflexive if and only if I M Н r.
A binary relation r is symmetric if and only if r = r -1 .
A binary relation r on a set M is antisymmetric if and only if r З r -1 = I M .
A binary relation r is transitive if and only if r o r н r.
Example 10. The relation from Example 6 is antisymmetric, but it is not symmetric, reflexive, and transitive. The relation in Example 7 is reflexive, antisymmetric, and transitive, but not symmetric. The relation I A has all four considered properties. The relations r -1 o r and r o r -1 are symmetric, transitive, but not antisymmetric and reflexive.
attitude equivalence on a set M is called a binary relation that is transitive, symmetric, and reflexive on M.
attitude partial order on a set M is called a transitive, antisymmetric, and reflexive on M binary relation r.
Example 11 The relation from Example 7 is a partial order relation. The relation I A is an equivalence relation and a partial order. The relation of parallelism on the set of lines is an equivalence relation.
