🐹 🔃 😚 Quantitative characteristics of relations 🌸 💃🏾 🤦🏼

Relationship theory in mathematics and in a number of subject areas (decision making, knowledge and data bases, mathematical linguistics, process modeling, etc.) plays a very noticeable role, but is still far from complete. As in other branches of mathematical knowledge, her well-known results relate to a greater extent to questions and problems of the existence of certain of its objects than to the problems of enumerating them. It would seem that any researcher in a specific branch of the theory should be interested in the general and complete picture of the objects of interest and their dependencies, to observe the full panorama. But alas, it is very problematic to do this, since no one has created or offers such a panorama (picture). Even the catalog of relations proposed in the work does not close the problem.

A simple example. Many years ago in the book [1 p. 207] I came across such a paragraph.

The theory of partially ordered sets still contains many unsolved problems. Even the question of the number of such sets that can be built from a given number n of elements does not yet exist if n≥6. Direct calculations only succeeded in establishing that if S (n) is the number of partially ordered sets, then S (2) = 3, S (3) = 19, S (4) = 219, S (5) = 4231, and the numbers S (n) for non-isomorphic sets were found only for n = 4 and n = 5 elements: Sn (4) = 16 and Sn (5) = 63.

About this writes the head of the department of Moscow State University Rybnikov K.A. I wanted to understand this deeper and it seemed that I could try to look for a solution, at least somehow expand the list, and most importantly - list the partial orders, see their scattering in reality with their properties. Just to hang the results on the wall. I confess that a lot of effort was expended, to develop a research program, create a workable model of partial order, write a program and debug it, computers were spinning the programmed algorithms for tens of hours. Someone's (from the greats) remark came to my mind that the basis of mathematics should have been not a number, but an order, then supposedly many theorems would have received simpler and more transparent proofs.

We have learned to calculate the number of relations over large sets-carriers and to enumerate the relations, but we failed to obtain strict formulas even for the number S (n). I remember this time as a period of intensive creative growth of my own and my colleagues, when after almost every output of the computer results and their analysis, ideas arose for modifying, improving the model, algorithms, corrections were made to test new hypotheses, but something significant ( ~~possibly brains~~ ) was not enough.

What I managed to open (get) I give below in the text. By the way, the results of other foreign researchers coincided with ours, but they reported only the number S (n) and did not mention the enumeration of partial orders.

We started small. The complete list of binary relations for any n-carrier set is known and can be easily obtained. An answer was sought to the questions: how many, for a given n, there are relations with a fixed one property, with a pair of properties, with a triple, etc. The fact is that having this data, it was possible to build not enumeration, but direct algorithms for enumerating such relations that by following the Occam's Razor Rule, they do not produce extra essences.

Here we will talk about obtaining such results for binary relations (BR).

So, there is an n-set-carrier of BO and a complete list of all BOs, as well as a list of BO properties:

- reflexivity; antireflexivity; partial reflexivity;

- symmetry; antisymmetry; asymmetry; asymmetry;

- transitivity; anti-transitivity;

- weak order; strict order; partial order; perfect (linear);

- tolerance;

- equivalence;

- cyclicality;

- completeness.

Quantitative characteristics of the types of binary relations

Relationships can have not only one specific property, but also sets of pairs, triplets, etc. of properties. The use of such relationships in practice is a common situation. So, for example, each attitude of tolerance (indifference) has two properties: symmetry and reflexivity. This set of properties determines the type of tolerance relationship.

Another type of relationship arises from tolerance relations, if we require from such relations the feasibility of an extended list of properties: symmetry, reflexivity and transitivity. It is clear that perhaps not all tolerance relations will turn out to be transitive, but those that will have a set of the three named properties will form a new type of relations called equivalences.

The set of equivalence relations turns out to be nested in the set of tolerance relations. For example, in the catalog, these types of relations are highlighted by filling (8 tolerances and only 5 of them are equivalences). The question arises about the number of BOs with a set of properties or one of them.

Reflexivity

The relation α = <, A> on the set A = {

а_{1}, а_{2}, . . ., а_{n}

${_1,_2,...,_n}$ } is reflexive (has the property of reflexivity) if each pair (

а_{i}, а_{i}

$_ i, _ i$ ) satisfies this relation. Here M is a graph (not a graph) of the relationship

а_{i} α а_{i}, а_{i} є A, i = 1 (1) | A |

$_ i α _ i , _i є A , i = 1(1)|A|$ ...

In other words, the main diagonal of the graph matrix, the ratio, is filled with ones. On a reflexive relation graph, all vertices have loops. The attitude is anti-reflective if for no

а_{i} є A, i = 1 (1) | A |

$_i є A , i = 1(1)|A|$ not performed

а_{i} α а_{i}

$_ i α _ i$ ... In this case, the matrix of the antireflexive relation α on the main diagonal does not have a single unit, i.e. there are zeros, and the corresponding graph has no loops at any vertex.

Finally, a relation α is non-reflective if for some

а_{i} є A, а_{i} α а_{i}

$_i є A ,_ i α _ i$ is executed, but for others it is not. We will consider such relations to be partially reflexive. The matrix of non-reflective relation on the main diagonal contains partly ones, partly - zeros. The graph of such a non-reflective relation does not have loops at all vertices.

A classic example of a reflexive relation is the main diagonal of a matrix representation, the unit (E = Δ) ratio, i.e. equality relation (in catalog no. 68). The graph of this ratio is formed by points (pairs) lying on the main diagonal of the matrix and the corresponding pairs

(i, i) А, i = 1 (1) | A |

$( i , i ) , i =1(1)|A|$ , the graph does not contain any other points.

The matrix representation of this ratio corresponds to the identity matrix (E). The diagonal relation graph is formed by the vertices corresponding to the elements from the set A to which the loops are assigned. The diagonal relationship is often denoted by

Δ_{А}

$Δ_$ ...

In the case of a reflexive relation, the corresponding graph is also reflexive, in the case of an antireflexive relation, its graph is antireflexive. If for some relation α it is known that it is reflexive, then the complement ᾱ is always antireflexive, and

α \cap ᾱ = \emptyset, α \cap Δ_{А} = Δ_{А}

$α ∩ ᾱ =∅ , α ∩ Δ_ = Δ_$ ...

For the antireflexive relation β, it is true

β \cap Δ_{А} = \emptyset

$β ∩Δ_= ∅$ ...

Example 1 . The relation ≤ (no more) on the set N is reflexive, and the relation <(less) on the same set is antireflexive.

The attitude “being a son” is anti-reflective, since no one is his own son.

For practical purposes, it is sometimes necessary to count the number of reflexive relations available in the complete set of relations given on the set A with cardinality | A | = n.

Let us show how such a calculation can be performed. We will consider on the plane the matrix of the binary reflexive relation α. It always contains all diagonal points.

Other points corresponding to pairs (i, j), the number of n × n - n = n (n – 1) of which, can be included in different composition and number k, k = 0 (1) (n × n - n)into possible relationships, which, of course, will be reflective. By summing over k combinations from n (n-1) over k , the total number of reflexive relations is determined

where K = n (n-1) / 2 is the number of arcs (edges) in an n- vertex graph without loops.

The number of non-reflective relationships is defined as the difference between the total number of relationships on A and the number of reflexive ones.

It follows from this expression that the set of non-reflective relations contains in

(2^{n} - 1)

$(2^n -1)$ times more relationships than there are reflexive ones. This excess of ratios is generated by the variety of combinations of only diagonal points on the graph, while the compositions and the number of the remaining points are simply repeated.

The number of antireflexive relations from the set of nonreflexive ones is exactly equal to the number of reflexive ones, i.e.

2^{n^{2} - n}

$2^{n^2-n}$ ... This follows from the fact that a one-to-one correspondence can be established between reflexive and antireflexive relations: from each reflexive relation, by removing all points of the diagonal, a single antireflexive relation can be obtained and vice versa.

Symmetry

By the property of symmetry, the entire set of relations is not divided into four classes: symmetric, asymmetric. The latter, in turn, fall into three classes: antisymmetric, asymmetric, and the remaining asymmetric.

The relation α = <, A> on the set A is symmetric (it has the property of symmetry with respect to the line coinciding with the main diagonal of the graph ) if for some pair

(i, j) є A \times A

$(i, j) є A×A$ of

а_{i} α а_{j}

$_i α _j$ should

а_{j} α а_{i}

$_j α _i$ ... In other words, for any pair

((а_{i}, а_{j}) є Å)

$((_i, _j) є Å)$ executed either in both directions, or not at all.

On the graph of a symmetric relation, if a pair of vertices i and j is connected by an arc (i, j), then it is necessarily connected by an arc (j, i). A symmetric relation graph is a symmetric oriented, or simply undirected, ordinary graph.

The ratio α is antisymmetric if from

а_{i} α а_{j}

$_i α _j$ and

а_{j} α а_{i}

$_j α _i$ it follows that i = j.

The antisymmetric ratio matrix does not necessarily contain all ones on the main diagonal and contains ones in one of two positions symmetric with respect to the main diagonal: above the diagonal or below the diagonal. The graph of this relation is formed by vertices with loops for all or some of them, and if a pair of vertices (i, j) in the graph is connected, then it is always an arc of only one direction. Note that for a symmetric and antisymmetric relationship, some diagonal points can either be included in it or not.

If an antisymmetric relation does not contain a single diagonal point, then they say that such a relation is asymmetric , i.e. it is always anti-reflective.

Example 2... The relation (≤) on the set N is antisymmetric, and the relation (<) on the same set is asymmetric. Indeed, in the first case from

а_{i} \leq а_{j}

$_i ≤_j$ and

а_{j} \leq а_{i}

$_j ≤_i$ can only follow

i = j

$i = j$ ... The equality relation (=) on N is symmetric, the relation α = A × A is also symmetric.

For any symmetric ratio α, it is always true

α = α^{- 1}

$α = α^{-1}$ and

α^{- 1}

$α^{-1}$ also symmetrical. For an antisymmetric relation,

α \cap α^{- 1} \subseteq ∆_{A}

$α ∩ α^{-1}⊆∆_A$ ... A general relationship, the graph of which contains both symmetrical and asymmetrical points, is not symmetrical. This relationship is asymmetrical, but not antisymmetric, and not asymmetrical.

The property of symmetry is also manifested in n-ary relations. The relation R on the set

Х = x_{1}, x_{2}, \dots, x_{n}

$= { x_1, x_2,…,x_n}$ is a symmetric n-ary relation if it, together with the element

< x_{i 1}, x_{i 2}, \dots, x_{i n} > є R

$<x_{i1}, x_{i2}, …,x_{in}>є R$ contains any sequences

< x_{j 1}, x_{j 2}, \dots, x_{j n} >

$< x_{j1}, x_{j2},…, x_{jn}>$ formed by the permutation of the members of the set X.

Note also that the asymmetric relation is always antireflexive; A non-reflective and transitive binary relation is always asymmetric. For practice and for performing calculations, the number of relations that have a certain property related to the symmetry of the graph is of interest. Let us calculate such ratios for an arbitrary set A of cardinality | A | = n.

In our reasoning we will rely on the property of reflexivity, which, like many others, has not yet been studied deeply enough. Even a superficial analysis of the set of all relationships allows us to conclude that it can always be divided into

2^{n}

$2^n$ classes of the same size, and the composition of the relations that form these classes obeys a certain pattern.

The sets of relations in all classes have the same structure, differ only in the number and composition of diagonal points, the whole variety of which is determined by the number

2^{n}

$2^n$ ... Let us define the state of the diagonal of a relation for a fixed n by the number and composition of points on it and belonging to a specific relation. It is clear that for a fixed set of filled states of the cells of the diagonal is determined by the Boolean

2^{∆}

$2^∆$ , where ∆ is the complete set of points of the diagonal of the graph of the Cartesian square of cardinality | ∆ | = n.

Thus, in the theory of relations, only two extreme states have traditionally been considered and studied: either all points of the diagonal are included in the relation and it is reflexive, or the relation does not contain any diagonal point, and then it is anti-reflective.

We will call all intermediate states with one diagonal point, with two, and so on, partial reflexivity of the kth order k = 0 (1) n, and relations of this kind are partially reflexive. So a partly reflexive relation of order zero is an antireflexive relation, and partly a reflexive relation of order n is just a reflexive relation.

Note that all states can be ordered as elements of the Boolean of the set ∆. The proposed approach allows us to outline the way of analyzing various properties and counting the number of relations with individual properties or their aggregates.

Let the relationship be considered reflexive and symmetrical. The symmetry of the ratio is determined by the presence of pairs of points in it, which are located in the ratio matrix symmetrically to the relative diagonal. For an arbitrary n such pairs, there are

C_{n}^{2}

$C_n^2$ ... Let us denote the set of these pairs by the symbol S.

Then the whole variety of symmetric and reflexive relations will be determined by the Boolean

2^{S}

$2^S$ ... A lot of such relations will be considered in more detail a little later, but here we will say that it forms a space of indifference or tolerance. It is clear that the number of tolerance ratios is determined by the power of the boolean

2^{S}

$2^S$ , i.e.

2^{C_{n}^{2}}

$2^{C_n^2}$ ...

Below in table. 1 shows the values of the number of tolerance ratios for the initial values n from a segment of natural numbers.

Table 1 . The number of tolerant BOs

It is now easy to calculate the cardinality of all symmetric relations, since the presence or absence of diagonal points does not change the symmetry properties. The set of symmetric relations is denoted by the symbol SM. Then the cardinality of this set for a fixed n is determined by the formula

| S M | = 2^{n} \cdot 2^{C_{n}^{2}} = 2^{C_{n + 1}^{2}},

$|SM| = 2^n·2^{C_n^2} = 2^{C_{n+1}^2},$

where n is the number of diagonal points of the ratio. Table 2 shows the values | SM | for some n.

Table 2 . The number of symmetric BOs

Now let's move on to calculating asymmetric relations, the set of which will be denoted by AS. These relations are characterized by the fact that all points of the diagonal are absent in them and none of the cells of the matrix of the relation lying outside the diagonal has a symmetric one. In other words, it is a set of anti-reflective and antisymmetric relationships.

The cardinality of this set can be determined from the expressions

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$

where K =

C_{n}^{2}

$C_n^2$ ...

We obtain the reduced formula for calculating the cardinality of the set AS - asymmetric relations for a given cardinality of the carrier | A | = n. By definition, all relations of the set AS are antireflexive; therefore, the main diagonal in the matrix of relations is empty, and the unit elements can be located only in half of the remaining positions of the matrix, i.e. at

C_{n}^{2} = (n^{2} - n) : 2

${C_n^2} =(n^2-n):2$ cells.

So, suppose an asymmetric relation contains k-elements (points, ordered pairs) 0 ≤ k ≤

C_{n}^{2}

${C_n^2}$ ... The number of relations with such a number of elements will obviously be equal to the number of combinations from

C_{n}^{2}

$C_n^2$ by k.

In this case, with each of the k elements we associate a pair of symmetric positions: one above the main diagonal of the matrix, the other below the diagonal. Since in each pair an element can be in one of two positions, then a boolean appears to accommodate k elements

2^{n}

$2^n$ opportunities.

In this way,

C_{n}^{2}

$C_n^2$ Is the number of choices of k pairs of positions from

C_{n}^{2} = K

$C_n^2 = K$ available pairs in the matrix representation of relations, and

2^{n}

$2^n$ - the number of opportunities to arrange k elements in positions in each pair. The number of relations containing k elements is defined as the product of the number of selections of pairs of positions by the number of options for arranging these k elements, i.e.

2^{k} C_{K}^{k}

$2^kC_K^k$ ...

The total number of relations in the set AS is obtained by summing the obtained products over all values of k from zero to the maximum allowable K =

C_{n}^{2} = K

$C_n^2 = K$ , i.e.

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$

where K =

C_{n}^{2}

$C_n^2$ ...

Example 3. Let the cardinality of the set of the support | A | = 5. Calculate the number of asymmetric relations using the formula found. Let us determine the value of the upper limit K in the sum, K =

C_{n}^{2}

$C_n^2$ = 10. The data for calculating the summands are given in table. 3.

Table 3 . BO characteristics

There is another way to calculate the cardinality of a set AS. It is based on counting the number of mappings of a set of pairs of symmetric positions into a set of states, in which each such pair can be. In an asymmetric relation, there is

K = C_{n}^{2}

$K = C_n^2$ pairs of positions.

Each position in a pair of cells can be occupied by 0 or 1, but for a pair of positions there are S = 3 states, which we denote as follows:

- 1, if element (1) is placed above the diagonal;

- 2, if element (1) is placed under the diagonal;

- 3 if both positions are empty (occupied by zeros).

Thus, a pair of symmetric positions (in the relationship matrix) can be in each

relationship in one of three states. The formula for calculating all possible mappings of the set of pairs of positions (denoted by the symbol K) into the set S of states we have:

φ : K \to S => | A S | = | S |^{| K |}

$φ: K → S =>|AS| =|S|^{|K|}$

Example 4 . For the conditions of the previous example has the form | A | = 5, K = | K | =

K = C_{5}^{2} = 10,

$K = C_5^2 = 10,$ | S | = 3, then,

| A S | = 3^{1} 0 = 59049

$|AS| = 3^10 = 59049$ ...

The calculation results in two different ways coincide, which once again convinces of the correctness of the formulas obtained. Thus, we have obtained the relation

3^{C_{n}^{2}} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k},

$3^{C_n^2} = Σ_{k=0}^K C_K^k·2^k,$

where K =

C_{n}^{2} .

$C_n^2.$

Let's give in table. 4 numbers of asymmetric relations | AS | for small values of n.

Table 4. The number of asymmetric BOs

Having a formula for determining the number of asymmetric relations, one can get another - for calculating the number of antisymmetric relations, since the presence or absence of diagonal points does not change the properties of antisymmetry of the relation.

So, we denote the set of antisymmetric relations by the symbol ANS, then the cardinality of this set will be determined by the formula

| A N S | = 2^{n}

$|ANS| =2^n$

| A N S | = 2^{n} Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k + n} = 2^{n} 3^{C_{n}^{2}},

$|ANS| =2^n Σ_{k=0}^K C_K^k·2^k =Σ_{k=0}^K C_K^k·2^{k+n} =2^n3^{C_n^2},$

where K =

C_{n}^{2}

$C_n^2$

Below is a table. 5 containing the (ANS) values for n = 3 (1) 5.

Table 5 . The number of antisymmetric BOs

In what follows, we need concepts that are convenient to introduce here.

The symmetric part of the binary relation α is called (and is denoted

α^{(S)}

$α^{(S)}$ ) attitude

α^{(S)} = α \cap α^{- 1}

$α^{(S)} =α∩α^{-1}$ and the ratio

α^{(а)} = α {\α}^{(S)}

$α^{()} = α \α^{(S)}$ (denoted

α^{(а)}

$α^{()}$ ) is called its asymmetric part. In the particular case when the ratio α is symmetric,

α^{(S)} = α

$α^{(S)} = α$ and

α^{(S)}

$α^{(S)}$ symmetrical always; if α is asymmetric, then

α^{(а)} = α

$α^{()}= α$ and

α^{(а)}

$α^{()}$ always asymmetrical.

Transitivity (Latin Transitivus - transitional, from transitus - transition)

- one of the properties of relationships. A relation = <M, A> defined on the set A is transitive if for any

а_{i}, а_{j}, а_{k} є A

$_i, _ j, _k є A$ the condition is satisfied: from

а_{i} α а_{j}

$_iα _ j$ and

а_{j} α а_{k}

$_jα _k$ should

а_{i} α а_{k}

$_iα _ k$ ...

In other words, for a transitive relation from the presence of elements in its composition (

а_{i} α а_{k}

$_iα _ k$ ) and (

а_{k} α а_{j}

$_kα _ j$ ) it follows that it contains the element (

а_{i} α а_{j}

$_iα _ j$ ). For a relation graph, this property means that if a pair of vertices (

а_{i} α а_{j}

$_iα _ j$ ) is connected by an oriented path passing through the vertex k and formed by 2 consecutive arcs (

а_{i} α а_{k}

$_iα _ k$ ), (

а_{k} α а_{j}

$_kα _ j$ ), then the same vertices are directly connected by a single arc (

а_{i} α а_{j}

$_iα _ j$ ). For matrix elements [

а_{i j}

$_{ij}$ ] of a transitive relation α from

а_{i k} \cdot а_{k j} = 1

$_{ik}·_{kj} =1$ should

а_{i j} = 1

$_{ij} = 1$ ...

The definition of the transitivity property for binary relations assumes that the relation contains at least three elements (ordered pairs). And how does this property manifest itself in a relationship of one-element, empty, or containing only two elements?

All singleton and empty relations are transitive. A two-element relation can be transitive and nontransitive if the pairs included in it contain a common element j. The graph arcs corresponding to ordered pairs are directed in one direction (form an oriented non-transitivity route).

For example, let (

а_{i}, а_{j}

$_i, _ j$ ) є α and (

а_{j}, а_{k}

$_j, _ k$ ) є α. The formulated definition requires: for the relation α to be transitive, it must have a third pair (arc) in it, namely, (

а_{i}, а_{k}

$_i, _ k$ ), but since it does not exist, the transitivity property for α is not satisfied.

If, as before, the relation contains only two pairs with a common element

а_{j} є A

$_j є A$ , but such that the common element

а_{j} є A

$_j є A$ is in the same position in both pairs (

а_{j}, а_{i}

$_j, _ i$ ), (

а_{j}, а_{k}

$_j, _ k$ ) or (

а_{i}, а_{j}

$_i, _ j$ ),

(

а_{k}, а_{j}

$_k, _ j$ ), and the arcs on the graph are directed in different directions, then such a relation is transitive, since the inclusion of the third pair in the relation is not required.

A transitive relation will also be in the case when two pairs have no common elements. Examples of transitive relations are: "equality" (=), since i = k, k = j implies i = j; "I is greater than j"; in geometry - "parallelism of straight lines". Examples of non-transitive relations: "perpendicularity of straight lines" in geometry; "I is not equal to j".

In the literature on relations, you can find various concepts that characterize transitivity: weak transitivity, strong transitivity, negative transitivity, anti-transitivity, weak anti-transitivity, generalized transitivity, transitive closureand some others. An attempt is made here to systematize the diverse shades of manifestation of the property of transitivity in relationships.

For a transitive relation α, the relation

α^{- 1}

$α^{–1}$ is also always transitive. The intersection of an arbitrary number of transitive relations is a transitive relation. If we consider the relation ᾰ, which is the intersection of all transitive relations containing the relation α, then ᾰ is called the transitive closure of the relation α.

The transitive closure ᾰ can be constructed for any relation α in accordance with the rule from

а_{i} ᾰ а_{j}

$_i ᾰ _j$ follows:

(\exists а_{к 1}, а_{к 2}, \dots, а_{к s}) (а_{i} α а_{к 1} Λ а_{к 1} α а_{к 2} Λ \dots Λ а_{к s} α а_{j})

$(∃_{1}, _{2}, …,_{s})( _iα _{1}Λ_{1}α _{2}Λ… Λ _{s}α _j)$ ...

The relation ᾰ is the smallest transitive relation containing α. If α is transitive, then it coincides with its transitive closure α = ᾰ and vice versa.

When representing a transitive binary relation by a directed graph, it is possible to represent not the entire digraph, but only its transitive skeleton, i.e. arcs connecting the beginning and end of each route longer than one are not drawn. In this case, we say that the transitive skeleton of the graph is taken for the relation α . This operation is essentially the reverse of the transitive closure operation , in which the beginning and end of each net are connected by an arc.

In the general case, the transitivity property is not satisfied with respect to the operation of combining relations. Combining two transitive relations

α_{1}

$α_1$ and

α_{2}

$α_2$ is transitive if and only if one of them is transitive with respect to the other. For a pair of binary relations

α_{1}

$α_1$ and

α_{2}

$α_2$ one can consider the transitivity of one of them relative to the other.

So

α_{1}

$α_1$ is transitive with respect to

α_{2}

$α_2$ under the following conditions:

1) from

(а_{i}, а_{k}) є α_{1} и (а_{k}, а_{j}) є α_{2}

$( _i, _k) є α_1 ( _k, _j) є α_2$ should

(а_{i}, а_{j}) є а_{1}

$(_i, _j) є _1$ ;

2) from

(а_{i}, а_{k}) є α_{2} и (а_{k}, а_{j}) є α_{1}

$( _i, _k) є α_2 ( _k, _j) є α_1$ should

(а_{i}, а_{j}) є α_{1}

$( _i, _j) є α_1$ ...

In the case when

α_{1} = α_{2} = α

$α_1= α_2=α$ relative transitivity is the usual transitivity.

The following statement is known about the properties of transitivity, symmetry, and asymmetry of a relation. If a binary relation is transitive, then its symmetric part

α^{(S)}

$α^{(S)}$ and

α^{(а)}

$α^{()}$ the asymmetric part is also transitive.

The opposite is true only if

α^{(S)}

$α^{(S)}$ ,

α^{(а)}

$α^{()}$ transitive and

α^{(а)}

$α^{()}$ transitively relative

α^{(S)}

$α^{(S)}$ ... In general, from transitivity

α^{(S)}

$α^{(S)}$ and

α^{(а)}

$α^{()}$ the transitivity of α does not follow.

The composition of the transitive relation α with itself satisfies the relation α · α ⊆ α. A relation α is negatively transitive (nontransitive) if its complement is transitive, i.e. ᾱ. In the matrix of such a relation [

α_{i j}

$α_{ij}$ ] from

α_{i k} = 0

$α_{ik} = 0$ and

α_{k j} = 0

$α_{kj} = 0$ should

α_{i j} = 0

$α_{ij} = 0$ ... The negative transitivity of α does not exclude the fact that α itself can also be transitive.

In this case, α is said to be a strongly transitive relation. Matrix elements [

α_{i j}

$α_{ij}$ ] such an attitude is characterized by the fact that

а_{i k} \cdot а_{k j} = 1

$_{ik}·_{kj} =1$ should

а_{i j} = 1

$_{ij} = 1$ , a from

а_{i k} = а_{k j} = 0

$_{ik} = _{kj} =0$ should

а_{i j} = 0

$_{ij} = 0$ ...

Along with strongly transitive relations, we consider weakly transitive (pseudotransitive) relations, which include those relations where the conditions from

а_{i} α^{(S)} а_{К}

$_iα^{(S)}_$ and

а_{К} α а_{j}

$_α_j$ should

а_{i} α а_{j}

$_iα_j$ ... Its transitivity follows from asymmetry and negative transitivity.

A relation α is transitively complete if for any δ from

а_{K 1} α а_{K 2}, а_{K 2} α а_{K 3}, \dots, а_{K (δ - 1)} α а_{K δ}

$_{K1}α_{K2}, _{K2}α_{K3},…, _{K(δ-1)}α_{Kδ}$ , the

comparability follows

а_{K 1}

$_{K1}$ and

а_{K δ}

$_{Kδ}$ , i.e. are executed either

а_{K 1} α а_{K δ}

$_{K1}α_{Kδ}$ or

а_{K δ} α а_{K 1}

$_{Kδ}α_{K1}$ ...

Cyclicity

Relationships defined on the set A can be viewed from the point of view of the presence of cycles in them. It is convenient to carry out such a consideration on graphs of relations. A cyclic relation graph always contains at least one closed contour (route). Ignoring the arrows turns the path into a loop. A graph of an acyclic relation does not contain cycles and is called acyclic or uncontrolled .

The relation = <Å, A> is cyclic if at least one chain of the form can be formed from the elements of the set A

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{K δ}, а_{K δ} α а_{K i}

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_{Kδ},_{Kδ}α_{Ki}$ arbitrary length δ. The graph M of the transitive closure for a cyclic relation contains at least one pair (

а_{i}, а_{i}

$_i, _i$ ), and for an acyclic relation α does not contain any such pair.

The relation = <Å, A> is acyclic if, for any δ≥1, the condition from

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{j}

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_j$ should

а_{i} \neq а_{j}

$_i ≠ _j$ ... In the matrix [

α_{i j}

$α_{ij}$ ] acyclic relationship from

а_{i K 1} а_{K 1 K 2} . . . а_{K (δ - 1) j} = 1

$_{iK1}_{K1K2}..._{K(δ-1)j}=1$ i ≠ j follows. The acyclic relationship is always asymmetric, but the opposite is not true. In other words, if some peaks

а_{i}

$_i$ and

а_{j}

$_j$ graph α acyclic relations are connected by way; then there is no arc in the graph (

а_{j}, а_{i}

$_j, _i$ ). Transitive tournaments

are classic examples of graphs with this property . The vertices of such graphs can be renumbered, under which for any arc (

а_{i}, а_{j}

$_i, _j$ ) the number of the vertex j is greater than the vertex i.

If α is an antireflexive transitive binary relation, then it is acyclic. The acyclicity and transitive completeness of the relation implies its transitivity.

Completeness

Completeness property (perfection, linearity). The whole set of relationships is divided into incomplete and complete , among which, in turn, strongly complete ones stand out. We will illustrate the property of completeness of relations by considering graphs of relations.

The graph of a complete relation is complete, i.e. any two of its vertices are directly connected by at least one arc, i.e. are adjacent. Since each arc in the graph corresponds to a point (element, pair) of the graph of the relationship, then on the basis of the above, a definition can be formulated.

The relation = <Å, A> is complete (perfect, linear) if and only if all elements of the set A are comparable or equal to each other. Thus, the overall attitude is reflective. In other words, for any two elements

а_{i}

$_i$ and

а_{j}

$_j$ fair

(а_{i} α а_{j} V а_{j} α а_{i} V а_{i} = а_{j})

$(_i α _j V _j α _i V _i = _j)$ ...

If in relation α there is at least one pair

а_{i}

$_i$ ,

а_{j}

$_j$ incomparable and unequal elements, then this relationship is incomplete. For any total ratio α,

∆ U α U α^{- 1} = A \times A

$∆UαUα^{-1}=A×A$ or from

а_{i} ᾱ а_{j}

$_i ᾱ _j$ should

а_{j} α а_{i}

$_j α _i$ ... The binary relation α is complete if and only if

а^{(a)} = а^{(d)}

$^{(a)} =^{(d)}$ , i.e. when its asymmetric part coincides with the dual (item 9) relation.

A binary relation α is strongly complete when its graph coincides with A × A. A graph of this relation is a complete graph in which each pair of vertices is connected by an edge, and each vertex has a loop. Such a graph is called a strongly complete graph. The total ratio α always satisfies the relations

ᾱ \subset α^{- 1}

$ᾱ ⊂ α^{-1}$ and

α^{- 1} \subset ᾱ \cup (α \cap α^{- 1})

$α^{-1}⊂ᾱ ∪(α∩α^{-1})$ ... Attitude

α \cup (ᾱ \cap α^{d}) = α \cup (ᾱ)^{(S)}

$α∪(ᾱ∩α^{d}) = α∪(ᾱ)^{(S)}$ always full.

If

α_{1}

$α_1$ and

α_{2}

$α_2$ complete relationship, then

α_{1} \cdot α_{2}

$α_1·α_2$ full. In the matrix [

α_{i j}

$α_{ij}$ ] full relationship

α_{i j} = 1

$α_{ij} = 1$ or

α_{j i} = 1

$α_{ji} = 1$ for any i, j, or both equalities are true. A relation α is weakly complete (weakly connected) if for any

а_{i}, а_{j} є A

$_i,_j є A$ such that

а_{i} \neq а_{j}

$_i ≠ _j$ or

а_{i} α а_{j}

$_i α _j$ or

а_{j} α а_{i}

$_j α _i$ ...

In the matrix [

α_{i j}

$α_{ij}$ ] of a weakly complete relation for any i ≠ j, or

α_{i j} = 1

$α_{ij} = 1$ or

α_{j i} = 1

$α_{ji} = 1$ , or both equalities are true. A relation α is transitively complete if, for an arbitrary n from

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (n - 1)} α а_{i n}

$_iα_{K1}, _{K1}α_{K2},…, _{K(n-1)}α_{in}$ comparability follows

а_{i 1} \equiv а_{i n}

$_{i1}≡ _{in}$ those.

а_{i 1} α а_{i n}

$_{i1}α _{in}$ or

а_{i n} α а_{i 1}

$_{in}α _{i1}$ ...

Let's count the number of complete relationships. First, consider the line problem. A line in a ratio matrix is a straight line segment perpendicular to the main diagonal of the ratio matrix, connecting the centers of two cells (cells) of the matrix symmetrically located relative to this diagonal.

If two or more pairs of symmetric positions fall on one line (straight line) in the ratio matrix, then the number of lines, nevertheless, remains equal to the number of such pairs of positions. The total number of pairs of positions for an arbitrary n is defined as

C_{n}^{2} = L

$C_n^2 = L$ ...

So, in the matrix for an arbitrary relation over the set A, there is a set L of parallel segments (lines). Let us designate the end positions of the segments (lines) by the symbols L - left and P - right. Also available | L | chips that can be placed in positions at the ends of the lines. The challenge is to determine the number of ways in which it would be possible to arrange | L | chips so that there is at least one chip on each line.

It is clear that the problem can be reduced to determining the number F of mappings f: L → π of the set L of lines into the set of π positions (n = {A, P}). It is known that the number of such mappings is determined by the formula

F = | п |^{| L |}

$F = ||^{|L|}$ ... A specific mapping (image) can have the form <P, P, L, L, L,…, L, P> of the sequence of indices for | L | positions. The symbol L corresponds to the position under the main diagonal, and the symbol P, which is symmetrical to it above the diagonal.

From the definition of the total ratio it follows that its graph contains at least K points, K =

C_{n}^{2}

$C_n^2$ located: so that all lines are occupied by at least one chip. The number k of points on the graph, additional to the minimum required number, can run the value k = 0 (1) K =

C_{n}^{2}

$C_n^2$ ...

For each fixed number of k points, the set of choices of positions in which they can be placed is determined by the value

C_{К}^{k}

$C_^k$ , where K is the set of unoccupied positions. Since k additional points completely fill k lines, then to ensure the property of completeness of the ratio, it remains to fill K - k positions with chips (points from the set of the minimum required), and the number of such fillings is

2^{К - k}

$2^{-k}$ ...

The choice of positions for k additional points and the methods of filling K-k lines with chips are independent. Therefore, the total number of possibilities for placing K + k points in 2 ∙ K positions so that all lines are occupied by at least one point is determined by the expression

C_{К}^{k} \cdot 2^{К - k}, k = 0 (1) К .

$C_^k ·2^{-k}, k = 0(1).$

If we sum this expression over, then we get the number of complete relations, which does not depend on the situation with the placement of diagonal points. In other words, it is the number of partially reflexive complete relationships, for example, anti-reflective and full reflexive and complete, etc.

Example 5 . The variety of situations for placing diagonal points is determined by the number

2^{n}

$2^n$ ... Then the cardinality of the set of all complete relations for a fixed n is determined by the formula

П = 2^{n} \cdot \sum_{k = 0}^{К} C_{К}^{k} 2^{К - k} = \sum_{k = 0}^{К} C_{К}^{k} 2^{К + n - k}

$= 2^n·∑_{k=0}^C_^k2^{-k} = ∑_{k=0}^C_^k2^{ + n - k}$ ...

For relations with three required properties

For equivalence relations with three required properties. There is a remarkable result: each equivalence relation over a set of n elements is in one-to-one correspondence with a partition of this set. The number of such relations is determined by the formula

B_{n} = \sum_{m = 0}^{n} S (n, m)

$B_n = ∑_{m=0}^nS(n, m)$ , where S (n, m) is the Stirling number of the second kind, Bn is the

Bell number, or in recurrent form

B_{n + 1} = \sum_{k = 0}^{n} C_{n}^{k} B_{k} .

$B_{n+1} = ∑_{k=0}^nC_n^kB_k.$

For ordered sets (partial orders), such formulas are not open and their number is determined by direct calculations, i.e. modeling. For small values of n, the data are given in

Table 6 . Quantitative characteristics of binary relations

Table 6. shows: n = | A | - the cardinality of the set-carrier;

2^{n^{2}}

$2^{n^2}$ - the number of all binary relations on the set A;

| In (n) | - the number of classes of non-isomorphic relations;

| (n) | - the number of relations of partial order;

| Gn (n) | - the number of classes are non-isomorphic relations of partial order;

| Gl (n) | = n! - the number of linear order relations.

Conclusion

In this work, a detailed analysis of the main properties and structure of the binary ratio was carried out, on the basis of which it was possible to obtain quantitative characteristics for BO with one or more properties. Found and presented original ratios for the number of some types of relations with two and three required properties. These results open up the possibility of modeling and studying BO and relations of higher arity.

List of used literature

Aigner M. Combinatorial Theory. - M .: Mir, 1982.
Birkhoff G. Theory of structures. - M .: IL, 1952.-408 p.
Noden P., Kitte K. Algebraic Algorithmics. - M .: Mir, 1999. - 720 p.
Rybnikov K.A. An introduction to combinatorial analysis. -M .: Ed. Moscow State University, 1972. -256s.
Stanley R. Enumerative Combinatorics. Vol. 1.- M .: Mir, 1990 .-- 440p.
Stanley R. Enumerative Combinatorics. T.2.- M .: Mir, 2005. - 767s.
Shikhanovich Yu.A. Introduction to modern mathematics. Initial concepts.-M .: Nauka, 1965. - 376p.

Quantitative characteristics of relations

Quantitative characteristics of the types of binary relations

Reflexivity

Symmetry

Transitivity (Latin Transitivus - transitional, from transitus - transition)

Cyclicity

Completeness

Conclusion

List of used literature

More articles: