A relation defined on a set can have a number of properties, namely:
2. Reflexivity
Definition. Attitude R in a variety of ways X is called reflexive if each element X sets X is in relation R with yourself.
Using symbols, this relationship can be written as follows:
R reflectively on X Û(" XÎ X) x R x
Example. The equality relation on a set of segments is reflexive, because each segment is equal to itself.
The reflexive relation graph has loops at all vertices.
2. Anti-reflexivity
Definition. Attitude R in a variety of ways X is called anti-reflexive if no element X sets X not in relation R with yourself.
R anti-reflexive on X Û(" XÎ X)
Example. Direct relationship X perpendicular to a straight line at» on the set of straight lines of the plane is anti-reflexive, because no straight line of the plane is perpendicular to itself.
The anti-reflexive attitude graph does not contain a single loop.
Note that there are relations that are neither reflexive nor anti-reflexive. For example, consider the relation "point X symmetrical to the point at"on a set of points on the plane.
Dot X symmetrical to the point X– true; dot at symmetrical to the point at– false, therefore, we cannot claim that all points of the plane are symmetrical to themselves, and we also cannot claim that not a single point of the plane is symmetrical to itself.
3. Symmetry
Definition. Attitude R in a variety of ways 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. Direct relationship X intersects a line at on the set of straight lines of the plane” is symmetrical, because if straight X intersects a line at, then the line at will definitely cross the line X.
Graph of a symmetric relation along with each arrow from a point X to the point at should contain an arrow connecting the same points, but in the opposite direction.
4. Asymmetry
Definition. Attitude R in a variety of ways 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 asymmetrical X Û(" X, atÎ X) x R y Þ
Example. Attitude " X < at» asymmetrically, because for no pair of elements X, at it is impossible to say 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 in a variety of ways X is called antisymmetric if, from the fact that X is in relationship with at, A at is in relationship with X it follows that X = u.
R antisymmetric X Û(" X, atÎ X) x R y Ù y R xÞ x = y
Example. Attitude " X£ at» antisymmetrically, because conditions X£ at And at£ X are executed simultaneously only when X = u.
An 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 in a variety of ways 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 it follows that X is in relationship with z.
R transitivenona X Û(" X, at, zÎ X) x R y Ù y R zÞ x R z
Example. Attitude " X multiple at» 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 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 going from X To z.
7. Connectivity
Definition. Attitude R in a variety of ways 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 Ú y R zÚ X= at
In other words: attitude R in a variety of ways 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» coherently, because no matter what real numbers we take, one of them will definitely be greater than the other or they will be equal.
In a connected relation graph, all vertices are connected to each other by arrows.
Example. Check what properties it has
attitude " X - divider at", defined on the set
X= {2; 3; 4; 6; 8}.
1) this relationship is reflexive, because each number from a given set is a divisor of itself;
2) this relationship does not have the property of anti-reflexivity;
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 relationship is antisymmetric: two numbers can be simultaneously divisors of each other only if these numbers are equal;
5) the relation is transitive, because 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 connectedness, because 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 relationship has the properties of reflexivity, asymmetry and transitivity.
§ 3. Equivalence relation.
The connection between the equivalence relation and the partition of a set into classes
Definition. Attitude R on a set X is called an equivalence relation if it is reflexive, symmetric and transitive.
Example. Consider the relation " X classmate at"on many students of the Faculty of Education. It has the following properties:
1) reflexivity, because every student is his own classmate;
2) symmetry, because if a student X at, then the student at is a classmate of a student X;
3) transitivity, because if a student X- classmate at, and the student at– classmate z, then the student X will be the student's classmate z.
Thus, this relation has the properties of reflexivity, symmetry and transitivity, and therefore is an equivalence relation. At the same time, many students of the Faculty of Education can be divided into subsets consisting of students studying in the same course. We get 5 subsets.
Equivalence relations are also, for example, the relation of parallelism of lines, the relation of equality of figures. Each such relationship is associated with partitioning the set into classes.
Theorem. If on 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 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 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 to equivalence classes. In each equivalence class there will be 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. Thus, a class of equal fractions can be specified by specifying any fraction belonging to this class.
In the initial course of mathematics, equivalence relations are also encountered, for example, “expressions X And at have the same numerical values", "figure X equal to the figure at».
Definitions
1. Binary relation between elements of sets A And IN any subset of a Cartesian product is called RÍA´B, RÍA´A.
2. If A=B, That R- This binary relation on A.
3. Designation: (x, y)ÎR Û xRy.
4. Domain of definition binary relation R- this is a lot d R = (x: exists y such that (x, y)ОR}.
5. Range of values binary relation R- this is a lot r R = (y: exists x such that (x, y)ОR}.
6. Addition binary relation R between elements A And IN- this is a lot -R = (A´B)\R.
7. Reverse attitude for a binary relation R- this is a lot R -1 = ((y, x) : (x, y)ÎR).
8. Product of relations R 1 ÍA´B And R 2 ÍB´C – it's an attitude R 1 × R 2 = {(x, y): exists zÎB such that (x, z)ОR 1 And (z, y)ОR 2}.
9. Attitude f called function from A V IN, if two conditions are met:
A) d f = A, r f Н V
b) for everyone x,y 1,y 2 from what (x, y 1)Оf And (x, y 2)Оf should y 1 =y 2.
10. Attitude f called a function of A on IN, if in the first paragraph it is fulfilled d f = A, r f = B.
11. Designation: (x, y)Îf Û y = f(x).
12. Identical function i A: A®A is defined like this: i A (x) = x.
13. Function f called 1-1 -function, if for any x 1, x 2, y from what y = f(x 1) And y = f(x 2) should x 1 =x 2.
14. Function f: A®B carries out one-to-one correspondence between A And IN, If d f = A, r f = B And f is a 1-1 function.
15. Properties of a binary relation R on a set A:
- reflexivity: (x, x)ОR for everyone xÎA.
- irreflexivity: (x, x)ÏR for everyone xÎA.
- symmetry: (x, y)ÎR Þ (y, x)ÎR.
- antisymmetry: (x, y)ОR and (y, x)ОR Þ x=y.
- transitivity: (x, y)ОR and (y, z)ОR Þ (x, z)ОR.
- dichotomy: or (x, y)ОR, or (y, x)ОR for everyone xÎA And yÎA.
16. Sets A 1, A 2, ..., A r from P(A) form partition sets A, If
- A i ¹ Æ, i=1, ..., r,
- A = A 1 ÈA 2 È...ÈA r,
- A i ÇA j = Æ, i¹j.
Subsets A i, i=1, ..., r, are called splitting blocks.
17. Equivalence on a set A is a reflexive, transitive and symmetrical relation on A.
18. Equivalence class element x by equivalence R- this is a lot [x] R =(y: (x, y)ÎR).
19. Factor setA By R is the set of equivalence classes of elements of the set A. Designation: A/R.
20. Equivalence classes (elements of the factor set A/R) form a partition of the set A. Back. Any partition of the set A corresponds to the equivalence relation R, whose equivalence classes coincide with the blocks of the specified partition. In a different way. Each element of the set A falls into some equivalence class from A/R. The equivalence classes either do not intersect or coincide.
21. Pre-order on a set A is a reflexive and transitive relation on A.
22. Partial order on a set A is a reflexive, transitive and antisymmetric relation on A.
23. Linear order on a set A is a reflexive, transitive and antisymmetric relation on A, satisfying the dichotomy property.
Example 1.
Let A=(1, 2 , 3} , B=(a, b). Let's write out the Cartesian product: A´B = ( (1, a), (1 , b), (2 , a), (2 , b), (3 , a), (3 , b) ). Let's take any subset of this Cartesian product: R = ( (1, a), (1 , b), (2 , b) ). Then R is a binary relation on sets A And B.
Will this relation be a function? Let's check the fulfillment of two conditions 9a) and 9b). Relation Definition Domain R- this is a lot d R = (1, 2) ¹ (1, 2, 3), that is, the first condition is not satisfied, therefore in R you need to add one of the pairs: (3 , a) or (3 , b). If you add both pairs, then the second condition will not be satisfied, since a¹b. For the same reason, from R you need to throw away one of the pairs: (1 , a) or (1 , b). So the attitude R¢ = ( (1, a), (2 , b), (3 , b) ) is a function. Note that R¢ is not a 1-1 function.
On given sets A And IN The following relations will also be functions: { (1 , a), (2 , a), (3 , a) ), { (1 , a), (2 , a), (3 , b) ), { (1 , b), (2 , b), (3 , b) ) etc.
Example 2.
Let A=(1, 2 , 3} . An example of a relation on a set A is R = ( (1, 1), (2, 1), (2, 3) ). An example of a function on a set A is f = ( (1, 1), (2, 1), (3, 3) ).
Examples of problem solving
1. Find d R,r R,R -1,R×R,R×R -1,R -1×R For R = ((x, y) | x, y О D and x+y£0).
If (x, y)ОR, That x And y runs through all real numbers. That's why d R= r R = D.
If (x, y)ОR, That x+y£0, Means y+x£0 And (y, x)ОR. That's why R -1 =R.
For any xÎD, yÎD let's take z=-|max(x, y)|-1, Then x+z£0 and z+y£0, i.e. (x, z)ОR And (z, y)ОR.That's why R×R = R×R -1= R -1 ×R = D 2.
2. For what binary relations R fair R -1 = -R?
Let RÍA´B. There are two possible cases:
(1) AÇB¹Æ. Let's take xÎAÇB. Then (x, x)ÎR Û (x, x)ÎR -1 Û (x, x)Î-R Û (x, x)Î(A´B) \ R Û (x, x)ÏR. Contradiction.
(2) AÇB=Æ. Because R -1 ÍB´A, A -RÍA´B, That R -1 = -R= Æ. From R -1 = Æ it follows that R = Æ. From -R = Æ it follows that R=A´B. Contradiction.
Therefore if A¹Æ And B¹Æ, then such relationships R does not exist.
3. On the set D real numbers we define the ratio R as follows: (x, y)ОR Û (x–y)– rational number. Prove that R there is an equivalence.
Reflexivity:
For anyone xÎD x-x=0– rational number. Because (x, x)ОR.
Symmetry:
If (x, y)ОR, That x-y =. Then y-x=-(x-y)=- – rational number. That's why (y, x)ОR.
Transitivity:
If (x, y)ОR, (y, z)ОR, That x-y = and y-z =. Adding these two equations, we get that x-z = + – rational number. That's why (x, z)ОR.
Hence, R is an equivalence.
4. Partitioning the plane D 2 consists of the blocks shown in Figure a). Write out the equivalence relation R, corresponding to this partition, and equivalence classes.
A similar task for b) and c).
a) two points are equivalent if they lie on a line of the form y=2x+b, Where b– any real number.
b) two points (x 1 ,y 1) And (x 2 ,y 2) are equivalent if (integer part x 1 equal to the whole part x 2) and (integer part y 1 equal to the whole part y 2).
c) decide on your own.
Tasks for independent solution:
1. Prove that if f there is a function from A V B And g there is a function from B V C, That f×g there is a function from A V C.
2. Let A And B– finite sets consisting of m and n elements, respectively.
a) How many binary relations exist between elements of sets? A And B?
b) How many functions are there from A V B?
c) How many 1-1 functions are there from A V B?
d) At what m And n there is a one-to-one correspondence between A And B?
3. Prove that f satisfies the condition f(AÇB)=f(A)Çf(B) for any A And B then and only when f there are 1-1 functions.
COMBINATORICS
The product of all natural numbers from 1 to n denoted by:
n! = 1·2·3·…·(n-1)·n, 0! = 1
Let X=(x 1 , x 2 , ..., x n )- this is a lot of n elements, k £ n.
Accommodation elements from X volume k is an ordered subset of k elements belonging to X.
Number of volume placements k from n
= n k(meaning places)
If for each i-th of k positions you can put one of q i elements of set X, then the number of such placements is equal to:
(q 1 , q 2 , ..., q n) = q 1 × q 2 × ... × q n
Number of volume placements k from n
= n(n - 1)(n - 2) … (n - k + 1)=
Rearrangement elements from X- this is the placement of elements from X volume n.
Number of permutations from n various elements:
=Pn= n!
If n elements contain q i elements i-th grade, q 1 + q 2 + ... + q m = n and elements of the same kind are identical, then the number of permutations is equal to:
P n (q 1 , q 2 , ..., q m) =
Combination elements from X volume k is an unordered subset of k elements belonging to X.
Combinations, placements and permutations can also be with repetitions of elements of the set X(unlimited and limited).
Number of volume combinations k from n different elements without repetition:
Number of volume combinations k from n various elements with unlimited repetitions:
Binomial theorem:
Properties:
(2)
(4) 
(5)
When solving combinatorial problems, the following combinatorics rules are often used:
- Sum rule. If object A can be chosen in n ways, and object B in other m ways, then the choice “either A or B” can be made in n+m ways.
- Product rule. If object A can be chosen in n ways, and after each of these choices, object B can in turn be chosen in m ways, then choosing “A and B” in that order can be done in n×m ways.
Example task. From 12 girls and 10 boys, a team of five is selected. In how many ways can this team be selected so that it includes no more than three young men?
Solution. The condition “no more than three” means that the team can include or 3 young men, or 2 young men, or 1 young man, or not a single young man. Thus, the problem distinguishes four different cases. In accordance with the addition rule, you need to count the number of options in each of these cases and fold their.
Let's consider the first case. You need to count how many ways you can choose from 12 girls and 10 boys a team consisting of 3 boys and 2 girls. Out of 10 boys, you can choose 3 boys in different ways. For every three selected boys, you can also select 2 girls out of 12. Therefore, the multiplication rule works and in the first case the number of command options is equal to ×.
Similarly, in the second case: × .
In the third case: × .
In the fourth case: .
Final answer: × + × + × + .
Examples of problem solving
№1.17. n (n>2) people sit at a round table. We will consider two placements to be identical if each person has the same neighbors in both cases. How many ways are there to sit at the table?
Solution.
The total number of possible seating arrangements is equal to the number of permutations of n elements P n = n! However, matching ones must be excluded from these seating arrangements. The neighborhood relation is preserved under cyclic permutations (there are n of them) and during symmetric reflection (there are also n of them):
Therefore, in total ways (divide, because the multiplication rule)
№1.19. 10 cards are drawn from a deck containing 52 cards. In how many cases will there be at least one ace among these cards?
Solution.
There are only 10 ways to remove 10 cards from the deck. Of these cases, there will not be a single ace in the sample. Therefore the answer is .
№1.20. In how many ways can three pairs of n chess players be formed?
Solution.
First, we will select 6 people from n chess players. There are ways to do this. Now we will split each six into pairs. To do this, let's put 6 chess players in a row, assuming that they have names: a, b, c, d, e, f. This can be done 6! ways. However, the order within each pair and the order of the pairs themselves are not important to us. Permutations in which chess players change places in pairs 2 3. Permutations in which pairs 3 are swapped!. Therefore, there are ways to divide 6 chess players into pairs. Answer 
.
№1.24. How many numbers are there from 0 to 10 n that do not contain two consecutive identical digits?
Solution.
Let's consider all n-digit numbers. We can choose the first digit in 9 ways. For the second digit to be different from the first, it can also be selected in 9 ways. The number of such n-digit numbers is equal to the number of placements of volume n of 9 elements with unlimited repetitions, i.e. equals 9 n for n>1 and 10 for n=1.
Therefore the answer is 10+9 2 +9 3 +...+9 n. The number 10 n is not suitable.
THEORY OF ALGORITHMS
· Let N be the set of natural numbers, including zero.
· In this section of the course, functions of many variables f n (x 1, ..., x n) defined on a certain set MÍN n with natural values will be considered, i.e. f n (x 1 , ..., x n)ÎN, x i ÎN for i=1, ..., n, or f n Í N n +1 .
· A function f n (x 1, ..., x n) is called everywhere defined if its domain of definition is N n, i.e. for any set of n natural numbers, there is a natural number that is the value of the function f n.
· The simplest functions defined everywhere:
1. s(x)=x+1 for any x;
2. o(x)=0 for any x;
3. I n m (x 1, ..., x m, ..., x n)=x m.
These simplest functions are defined everywhere and from them, using a finite number of applications of the operators introduced below, more complex functions can be constructed.
· Superposition operator:
The function h n (x 1 , ..., x n) is obtained from the functions g m , f n 1 , ..., f n m using the superposition operator if h n (x 1 , ..., x n) = g m (f n 1 (x 1 , ..., x n), ..., f n m (x 1, ..., x n)).
· Primitive recursion operator:
The function f n +1 (x 1, ..., x n, y) is obtained from the functions g n (x 1, ..., x n) and h n +2 (x 1, ..., x n, y, z) using primitive recursion operator, if it can be specified by a primitive recursion scheme:
æf n+1 (x 1 , ..., x n , 0) = g n (x 1 , ..., x n),
èf n+1 (x 1 , ..., x n , y+1) = h n+2 (x 1 , ..., x n , y, f n+1 (x 1 , ..., x n , y )).
· Minimization operator:
The function f n (x 1 , ..., x n) is obtained from the function g n +1 (x 1 , ..., x n , y) using the minimization operator and is denoted f n (x 1 , ..., x n)=my, If:
f n (x 1 , ..., x n) is defined and equal to y Û g n +1 (x 1 , ..., x n , 0), ..., g n +1 (x 1 , ..., x n , y -1) are defined and not equal to zero, and g n +1 (x 1, ..., x n, y)=0.
(You can also say: “The function f n (x 1, ..., x n) is equal to the minimum value of y at which the function g n +1 becomes zero”)
· Primitive recursive function (prf)
A function f n +1 (x 1 , ..., x n , y) is called primitive recursive if it can be obtained from simple functions using a finite number of applications of the superposition and primitive recursion operators.
It should be noted that all primitive recursive functions are defined everywhere.
· Partially recursive function (prf)
A function f n +1 (x 1 , ..., x n , y) is called partially recursive if it can be obtained from simple functions using a finite number of applications of the superposition operators, primitive recursion and minimization.
· From the definitions it is easy to see that primitively recursive functions are also partially recursive. However, there are partially recursive functions that are not primitive recursive.
Examples of problem solving
1. Prove that the following functions are primitive recursive.
Solution. The function f(x) can be obtained by applying the superposition operator n times to the simplest function s(x).
Solution. The function f(x) can be specified by the following primitive recursion scheme:
æf(x, 0) = x = I 1 1 (x),
èf(x, y+1) = x+y+1=f(x,y)+1=s(f(x,y))=s(I 3 3 (x,y,f(x,y) )).
Here the function g(x) has the form g(x)= I 1 1 (x) and is, as expected, a function of one variable. And the function h(x,y,z) has the form h(x,y,z)=s(I 3 3 (x,y,z)) and is a function of three variables.
Note that the functions g(x) and h(x,y,z) are prf, since g(x) is the third simplest function, and h(x,y,z) can be obtained from the simplest functions s(x) and I 3 3 (x,y,z) by applying the superposition operator.
Since the function f(x,y) can be obtained using the primitive recursion operator from the primitive recursive functions g(x) and h(x,y,z), then f(x,y) is a prf.
Solution. The function f(x) can be specified by the following primitive recursion scheme:
æf(x, 0) = 0 = o(x),
èf(x, y+1) = x(y+1)=xy+x=f(x,y)+x= I 3 3 (x,y,f(x,y)))+ I 3 1 ( x,y,f(x,y))).
Since the function f(x,y) can be obtained using the primitive recursion operator from the primitive recursive functions g(x)=o(x) and h(x,y,z) = I 3 3 (x,y,z)) + I 3 1 (x,y,z)), then f(x,y) – prf.
2. Let g(x 1 , ..., x n ,y) be a primitive recursive function. Prove that the following function is primitive recursive:
Solution. The peculiarity of this function is that the summation is carried out over a variable number of terms. However, the function f n +1 can be specified by the following primitive recursion scheme:
æf(x 1 , ..., x n , 0) = g(x 1 , ..., x n ,0) – prf,
èf(x 1 , ..., x n , y+1) = = f(x 1 , ..., x n , y) + g(x 1 , ..., x n ,y+1) – sum of prf g and the function f itself.
3. Prove that the following function is partially recursive.
Solution. Let us show that the function f(x,y) can be obtained using the minimization operator.
Let x³y, then f(x,y) is defined and takes on a certain value: f(x,y) = x-y = z. How to calculate z? We can suggest the following method: starting from zero, iterate through all z values in order until the condition x-y=z, or x-y-z=0 is met. There will definitely be such a z, because x-y³0. If x-y<0, то ни какое натуральное z не подойдет.
A programmer would write it like this:
unsigned int f(x,y)
while((x-y-z)!=0) z++;
The same can be written in terms of the minimization operator:
f(x, y)=mz[|x–y–z|=0]
The module is necessary so that the function g(x,y,z)=|x–y–z| was determined even if x–y<0. Заметим, что g(x,y,z)=|x–y–z| является примитивно рекурсивной, т.к. может быть получена с помощью конечного числа применений оператора суперпозиции к простейшим функциям.
a) a function that is not defined anywhere (i.e. a function with an empty domain of definition);
b) 
c) 
Let R is some binary relation on the set X, and x, y, z are any of its elements. If an element x is in a relationship R with an element y, then 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 each vertex of the graph has a loop. For example, the relations of equality and parallelism for segments are reflexive, but the relations of perpendicularity and “longer” are not reflexive. 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 element x is in a given relationship with element y, it follows that element y is in the same relationship with element x.
R - symmetrical on (xYay =>y Rx)
A symmetric relation graph contains paired arrows going in opposite directions. The relations of parallelism, perpendicularity and equality for segments are symmetrical, but the “longer” relation is not symmetrical (Fig. 42).
3. A relation R on a set X is called antisymmetric if for different elements x and y from the set X, from the fact that the element x is in a given relation with the element y, it follows that the element y is not in this relation with the element x.
R - antisymmetric on X « (xRy and xy ≠ yRx)
Note: an overbar indicates the negation of a statement.
In an antisymmetric relation graph, two points can only be connected by one arrow. An example of such a relation is the “longer” relation for segments (Fig. 42). The relations of parallelism, perpendicularity and equality are not antisymmetric. There are relations that are neither symmetrical nor antisymmetrical, for example the relation “being a brother” (Fig. 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 the element x is in a given relation with an element Z
R - transitive on A≠ (xRy and yRz=> xRz)
In the graphs of the “longer”, parallelism and equality relations in Figure 42, you can notice that if an arrow goes from the first element to the second and from the second to the third, then there is definitely an arrow going from the first element to the third. These relations are transitive. Perpendicularity of segments does not have the property of transitivity.
There are other properties of relations between elements of one set that we do not consider.
The same relation can have several properties. So, for example, on a set of segments the relation “equal” is reflexive, symmetrical, 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 relations divide the set X into classes.
These relationships are manifested, for example, when completing 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 the same color”) determine in this case the partition of the sets of stripes and balls into classes.
If a relation on set 1 is transitive and antisymmetric, then it is called an order relation on this set.
A set with a given order relation is called an ordered set.
For example, when completing the tasks: “Compare the strips in width and arrange them from the narrowest to the widest,” “Compare the numbers and arrange the number cards in order,” children order the elements of the sets of strips and number cards using order relations; “to be wider”, “to follow”.
In general, relations of equivalence and order play a large role in the formation in children of correct ideas about the classification and ordering of sets. In addition, there are many other relations that are neither equivalence relations nor order relations.
6. What is a characteristic property of a set?
7. In what relationships can sets exist? Give explanations for each case and depict them using Euler circles.
8. Define a subset. Give an example of sets, one of which is a subset of another. Write their relationship using symbols.
9. Define equal sets. Give examples of two equal sets. Write their relationship using symbols.
10. Define the intersection of two sets and depict it using Euler circles for each particular case.
11. Define the union of two sets and depict it using Euler circles for each particular case.
12. Define the difference between two sets and depict it using Euler circles for each particular case.
13. Define complement and depict it using Euler circles.
14. What is called partitioning a set into classes? Name the conditions for correct classification.
15. What is called correspondence between two sets? Name the methods for specifying correspondences.
16. What kind of correspondence is called one-to-one?
17. What sets are called equal?
18. What sets are called equivalent?
19. Name ways to define relations on a set.
20. What relation on a set is called reflexive?
21. What relation on a set is called symmetric?
22. What relation on a set is called antisymmetric?
23. What relation on a set is called transitive?
24. Define an equivalence relation.
25. Define the order relation.
26. Which set is called ordered?
Fundamentals of discrete mathematics.
The concept of set. Relationship between sets.
A set is a collection of objects that have a certain property, combined into a single whole.
The objects that make up a set are called elements multitudes. In order for a certain collection of objects to be called a set, the following conditions must be met:
· There must be a rule by which it can be determined whether an element belongs to a given population.
· There must be a rule by which elements can be distinguished from each other.
Sets are denoted by capital letters and its elements by small letters. Methods for specifying sets:
· Enumerating the elements of a set. - for finite sets.
· Indication of characteristic property 
.
An empty set– a set that does not contain a single element (Ø) is called.
Two sets are said to be equal if they consist of the same elements. , A=B
Many B called a subset of the set A( , if and only if all elements of the set B belong to many A.
For example: , B =>
Property:
Note: usually a subset of the same set is considered, which is called universal(u). The universal set contains all elements.
Operations on sets.
| A |
| B |
2.By crossing 2 sets is a new set consisting of elements that simultaneously belong to both the first and second set.
No.: , ,
Property: union and intersection operations.
· Commutativity. 
· Associativity. ;
· Distributive. ;
| U |
Binary relations and their properties.
Let A And IN these are sets of derivative nature, consider an ordered pair of elements (a, b) a ϵ A, c ϵ B one can consider ordered "enki".
(a 1, a 2, a 3,...a n), Where A 1 ϵ A 1; A 2 ϵ A 2; ...; A n ϵ А n;
Cartesian (direct) product of sets A 1, A 2, …, A n, is called a set, which consists of ordered n k of the form .
No.: M= {1,2,3}
M× M= M 2= {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.
Subsets of the Cartesian product 
called power ratio n or enary relation. If n=2, then consider binary relationship. What do they say that a 1, a 2 are in a binary relation R, When a 1 R a 2.
Binary relation on a set M is a subset of the direct product of the set n on yourself.
M× M= M 2= {(a, b)| a, b ϵ M) in the previous example the ratio is smaller on the set M generates the following set: ((1,2);(1,3); (2,3))
Binary relations have various properties including:
Reflexivity: 
.
· Anti-reflexivity (irreflexivity): .
· Symmetry: .
· Antisymmetry: .
· Transitivity: .
· Asymmetry: .
Types of relationships.
· Equivalence relation;
· Order relation.
v The reflexive transitive relation is called a quasi-order relation.
v A reflexive symmetric transitive relation is called an equivalence relation.
v A reflexive antisymmetric transitive relation is called a (partial) order relation.
v An anti-reflexive antisymmetric transitive relation is called a strict order relation.
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 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 equality relation 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.
Domain of definition of a binary relation r is the set D(r) = ( x | there is a y such that xry ). Range of values of a binary relation r is the set R(r) = ( y | there exists x such that xry ).
Attitude, reverse to the binary relation r Í M 2, the binary relation r -1 = (
Composition binary relations r 1 and r 2 defined on the set M, 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 the 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 fulfilling 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 in Example 6 is antisymmetric, but is not symmetric, reflexive, or transitive. The relation in Example 7 is reflexive, antisymmetric, and transitive, but is not symmetric. The relation I A has all four properties under consideration. 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 a transitive, symmetric and reflexive binary relation on M.
Attitude partial order on a set M is a transitive, antisymmetric and reflexive binary relation r on M.
Example 11 The relation in Example 7 is a partial order relation. The relation I A is an equivalence and partial order relation. The parallelism relation on a set of lines is an equivalence relation.
