🖨️ 🏿 🚶 Caractéristiques quantitatives des relations 🐎 🕕 🦃

La théorie des relations en mathématiques et dans un certain nombre de domaines (prise de décision, bases de connaissances et de données, linguistique mathématique, modélisation de processus, etc.) joue un rôle très notable, mais est encore loin d'être achevée. Comme dans d'autres branches de la connaissance mathématique, ses résultats bien connus portent davantage sur les questions et problèmes de l'existence de l'un ou l'autre de ses objets que sur les problèmes de leur énumération. Il semblerait que tout chercheur dans une branche spécifique de la théorie devrait s'intéresser à l'image générale et complète des objets d'intérêt et de leurs dépendances, pour observer le panorama complet. Mais hélas, c'est très problématique de faire cela, puisque personne n'a créé ou offre un tel panorama (photo). Même le catalogue de relations proposé dans l'ouvrage ne résout pas le problème.

Un exemple simple. Il y a de nombreuses années dans le livre [1 p. 207] je suis tombé sur un tel paragraphe.

La théorie des ensembles partiellement ordonnés contient encore de nombreux problèmes non résolus. Même la question du nombre de tels ensembles qui peuvent être construits à partir d'un nombre donné de n éléments n'existe pas encore si n≥6. Les calculs directs ont seulement réussi à établir que si S (n) est le nombre d'ensembles partiellement ordonnés, alors S (2) = 3, S (3) = 19, S (4) = 219, S (5) = 4231, et les nombres Sí (n) pour les ensembles non isomorphes ont été trouvés uniquement pour n = 4 et n = 5 éléments: Sn (4) = 16 et Sn (5) = 63.

À propos de cela, écrit le chef du département de l'Université d'État de Moscou Rybnikov K.A. Je voulais comprendre cela plus profondément et il semblait que je pouvais essayer de chercher une solution, au moins en quelque sorte élargir la liste et, surtout, lister les commandes partielles, voir leur dispersion dans la réalité avec leurs propriétés. Juste pour accrocher les résultats au mur. J'avoue que beaucoup d'efforts ont été déployés, pour développer un programme de recherche, créer un modèle fonctionnel d'ordre partiel, écrire un programme et le déboguer, les ordinateurs faisaient tourner les algorithmes programmés pendant des dizaines d'heures. La remarque de quelqu'un (des plus grands) m'est venue à l'esprit que la base des mathématiques n'aurait pas dû être un nombre, mais un ordre, alors on suppose que de nombreux théorèmes auraient reçu des preuves plus simples et plus transparentes.

Nous avons appris à calculer le nombre de relations sur de grands ensembles-porteurs et à énumérer les relations, mais nous n'avons pas réussi à obtenir des formules strictes même pour le nombre S (n). Je me souviens de cette période comme d'une période de croissance créative intensive de ma part et de mes collègues, quand après presque chaque sortie des résultats informatiques et leur analyse, des idées ont surgi pour modifier, améliorer le modèle, les algorithmes, des corrections ont été apportées pour tester de nouvelles hypothèses, mais quelque chose d'important ( ~~peut-être des cerveaux~~ ) n'était pas assez.

Ce que j'ai réussi à ouvrir, je le donne ci-dessous dans le texte. À propos, les résultats d'autres chercheurs étrangers coïncidaient avec les nôtres, mais ils ne rapportaient que le nombre S (n) et ne mentionnaient pas l'énumération des ordres partiels.

Nous avons commencé petit. La liste complète des relations binaires pour tout ensemble de n-porteuses est connue et peut être facilement obtenue. On a cherché une réponse aux questions: combien, pour un n donné, il y a des relations avec une propriété fixe, avec une paire de propriétés, avec un triplet, etc. en suivant la règle du rasoir d'Occam, ils ne produisent pas d'essences supplémentaires.

Nous parlerons ici de l'obtention de tels résultats pour les relations binaires (BR).

Donc, il y a un n-set-carrier de BO et une liste complète de tous les BO, ainsi qu'une liste de propriétés BO:

- réflexivité; antireflet; réflexivité partielle;

- symétrie; antisymétrie; asymétrie; asymétrie;

- transitivité; anti-transitivité;

- ordre faible; ordre strict; commande partielle; parfait (linéaire);

- tolérance;

- équivalence;

- cyclicité;

- l'exhaustivité.

Caractéristiques quantitatives des types de relations binaires

Les relations peuvent avoir non seulement une propriété spécifique, mais également des ensembles de paires, de triplets, etc. de propriétés. L'utilisation de telles relations dans la pratique est une situation courante. Ainsi, par exemple, chaque attitude de tolérance (indifférence) a deux propriétés: la symétrie et la réflexivité. Cet ensemble de propriétés détermine le type de relation de tolérance.

Un autre type de relation naît des relations de tolérance, si l'on exige de ces relations la faisabilité d'une liste étendue de propriétés: symétrie, réflexivité et transitivité. Il est clair que toutes les relations de tolérance ne se révéleront peut-être pas transitives, mais celles qui auront un ensemble des trois propriétés nommées formeront un nouveau type de relations appelées équivalences.

L'ensemble des relations d'équivalence s'avère imbriqué dans l'ensemble des relations de tolérance. Par exemple, dans le catalogue, ces types de relations sont mis en évidence par remplissage (8 tolérances et seulement 5 d'entre elles sont des équivalences). La question se pose du nombre de BO avec un ensemble de propriétés ou l'une d'entre elles.

Réflexivité

La relation α = <, A> sur l'ensemble A = {

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

${_1,_2,...,_n}$ } est réflexif (a la propriété de réflexivité) si chaque paire (

а_{i}, а_{i}

$_ i, _ i$ ) satisfait cette relation. Ici M est un graphe (pas un graphe) de la relation

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

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

En d'autres termes, la diagonale principale de la matrice graphique, le rapport, est remplie de uns. Tous les sommets du graphe de relations réflexives ont des boucles. L'attitude est antireflet si non

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

$_i є A , i = 1(1)|A|$ pas effectué

а_{i} α а_{i}

$_ i α _ i$ ... Dans ce cas, la matrice de la relation antireflet α sur la diagonale principale n'a pas une seule unité, c'est-à-dire il y a des zéros et le graphe correspondant n'a aucune boucle à aucun sommet.

Enfin, la relation α est non réfléchissante si pour certains

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

$_i є A ,_ i α _ i$ est exécuté, mais pas pour d'autres. Nous considérerons ces relations comme partiellement réflexives. La matrice de relation non réfléchissante sur la diagonale principale contient en partie des uns, en partie - des zéros. Le graphe d'une telle relation non réfléchissante n'a pas de boucles à tous les sommets.

Un exemple classique de relation réflexive est la diagonale principale d'une représentation matricielle, le rapport unitaire (E = Δ), c'est-à-dire relation d'égalité (au catalogue n ° 68). Le graphique de ce rapport est formé de points (paires) situés sur la diagonale principale de la matrice et des paires correspondantes

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

$( i , i ) , i =1(1)|A|$ , le graphique ne contient aucun autre point.

La représentation matricielle de ce rapport correspond à la matrice identité (E). Le graphe de relations diagonales est formé par les sommets correspondant aux éléments de l'ensemble A auxquels les boucles sont affectées. La relation diagonale est souvent désignée par le symbole

Δ_{А}

$Δ_$ ...

Dans le cas d'une relation réflexive, le graphe correspondant est également réflexif, dans le cas d'une relation antireflet, son graphe est antireflexif. Si pour une relation α on sait qu'elle est réflexive, alors le complément ᾱ est toujours antireflexif, et

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

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

Pour la relation antireflexive β, c'est vrai

β \cap Δ_{А} = \emptyset

$β ∩Δ_= ∅$ ...

Exemple 1 . La relation ≤ (pas plus) sur l'ensemble N est réflexive, et la relation <(moins) sur le même ensemble est antireflet.

L'attitude «être un fils» est antireflet, puisque personne n'est son propre fils.

Pour des raisons pratiques, il est parfois nécessaire de compter le nombre de relations réflexives disponibles dans l'ensemble complet des relations données sur l'ensemble A de cardinalité | A | = n.

Voyons comment un tel calcul peut être effectué. Nous considérerons sur le plan la matrice de la relation réflexive binaire α. Il contient toujours tous les points diagonaux.

Autres points correspondant à des paires (i, j), dont le nombre de n × n - n = n (n - 1) , peuvent être inclus dans une composition et un nombre différents k, k = 0 (1) (n × n - n)dans des relations possibles, qui, bien sûr, seront réflexives. En additionnant sur k combinaisons de n (n-1) sur k , le nombre total de relations réflexives est déterminé

où K = n (n-1) / 2 est le nombre d'arcs (arêtes) dans un graphe à n sommets sans boucles.

Le nombre de relations non réflexives est défini comme la différence entre le nombre total de relations sur A et le nombre de relations réflexives.

Il découle de cette expression que l'ensemble des relations non réfléchissantes contient dans

(2^{n} - 1)

$(2^n -1)$ fois plus de relations que de relations réflexives. Cet excès de rapports est généré par la variété des combinaisons de points seulement diagonaux du graphique, tandis que les compositions et le nombre de points restants sont simplement répétés.

Le nombre de relations antiréfléchissantes de l'ensemble des relations non réflexives est exactement égal au nombre de relations réflexives, c'est-à-dire

2^{n^{2} - n}

$2^{n^2-n}$ ... Cela découle du fait qu'une correspondance biunivoque peut être établie entre les relations réflexives et antiréfléchissantes: à partir de chaque relation réflexive, en supprimant tous les points de la diagonale, une seule relation antiréfléchissante peut être obtenue et vice versa.

Symétrie

Par la propriété de symétrie, l'ensemble des relations n'est pas divisé en quatre classes: symétrique, asymétrique. Ces derniers, à leur tour, se divisent en trois classes: antisymétrique, asymétrique et asymétrique restante.

La relation α = <, A> sur l'ensemble A est symétrique (elle a la propriété de symétrie par rapport à la droite coïncidant avec la diagonale principale du graphe ) si pour une paire

(i, j) є A \times A

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

а_{i} α а_{j}

$_i α _j$ devrait

а_{j} α а_{i}

$_j α _i$ ... En d'autres termes, pour n'importe quelle paire

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

$((_i, _j) є Å)$ exécuté soit dans les deux sens, soit pas du tout.

Sur le graphe d'une relation symétrique, si une paire de sommets i et j est reliée par un arc (i, j), alors elle est nécessairement reliée par un arc (j, i). Un graphe de relations symétriques est un graphe ordinaire orienté symétrique ou simplement non orienté.

Le rapport α est antisymétrique si de

а_{i} α а_{j}

$_i α _j$ et

а_{j} α а_{i}

$_j α _i$ il s'ensuit que i = j.

La matrice de rapport antisymétrique ne contient pas nécessairement tous ceux de la diagonale principale et contient ceux dans l'une des deux positions symétriques par rapport à la diagonale principale: au-dessus de la diagonale ou en dessous de la diagonale. Le graphe de cette relation est formé par des sommets avec des boucles pour tout ou partie d'entre eux, et si une paire de sommets (i, j) dans le graphe est connectée, alors c'est toujours un arc d'une seule direction. Notez que pour une relation symétrique et antisymétrique, certains points diagonaux peuvent être inclus ou non.

Si une relation antisymétrique ne contient pas un seul point diagonal, alors ils disent qu'une telle relation est asymétrique , c'est-à-dire il est toujours antireflet.

Exemple 2... La relation (≤) sur l'ensemble N est antisymétrique, et la relation (<) sur le même ensemble est asymétrique. En effet, dans le premier cas de

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

$_i ≤_j$ et

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

$_j ≤_i$ ne peut que suivre

i = j

$i = j$ ... La relation d'égalité (=) sur N est symétrique, la relation α = A × A est également symétrique.

Pour tout rapport symétrique α, c'est toujours vrai

α = α^{- 1}

$α = α^{-1}$ et

α^{- 1}

$α^{-1}$ également symétrique. Pour une relation antisymétrique,

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

$α ∩ α^{-1}⊆∆_A$ ... Une relation générale, dont le graphe contient à la fois des points symétriques et des points asymétriques, n'est pas symétrique. Cette relation est asymétrique, mais non antisymétrique et non asymétrique.

La propriété de symétrie se manifeste également dans les relations n-aires. La relation R sur l'ensemble

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

$= { x_1, x_2,…,x_n}$ est une relation n-aire symétrique si elle, avec l'élément

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

$<x_{i1}, x_{i2}, …,x_{in}>є R$ contient des séquences

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

$< x_{j1}, x_{j2},…, x_{jn}>$ formé par la permutation des membres de l'ensemble X.

Notez également que la relation asymétrique est toujours antireflet; Une relation binaire non réfléchissante et transitive est toujours asymétrique. Pour la pratique et pour effectuer des calculs, le nombre de relations qui ont une certaine propriété liée à la symétrie du graphe est intéressant. Calculons de tels rapports pour un ensemble arbitraire A de cardinalité | A | = n.

Dans nos arguments, nous nous appuierons sur la propriété de réflexivité qui, comme beaucoup d'autres, n'a pas encore été suffisamment étudiée. Même une analyse superficielle de l'ensemble de toutes les relations nous permet de conclure qu'elle peut toujours être divisée en

2^{n}

$2^n$ classes de même taille, et la composition des relations qui forment ces classes obéit à un certain modèle.

Les ensembles de relations dans toutes les classes ont la même structure, ne diffèrent que par le nombre et la composition des points diagonaux, dont toute la variété est déterminée par le nombre

2^{n}

$2^n$ ... Définissons l'état de la diagonale d'une relation pour un n fixé par le nombre et la composition des points sur celle-ci et appartenant à une relation spécifique. Il est clair que pour un ensemble fixe d'états remplis des cellules de la diagonale est déterminé par le booléen

2^{∆}

$2^∆$ , où ∆ est l'ensemble complet des points de la diagonale du graphe du carré cartésien de cardinalité | ∆ | = n.

Ainsi, dans la théorie des relations, seuls deux états extrêmes ont été traditionnellement considérés et étudiés: soit tous les points de la diagonale sont inclus dans la relation et elle est réflexive, soit la relation ne contient aucun point diagonal, et alors elle est antireflet.

Nous appellerons tous les états intermédiaires avec un point diagonal, avec deux, et ainsi de suite, réflexivité partielle du kème ordre k = 0 (1) n, et les relations de ce type sont partiellement réflexives. Ainsi, une relation partiellement réflexive d'ordre zéro est une relation antireflet, et partiellement une relation réflexive d'ordre n est juste une relation réflexive.

Notez que tous les états peuvent être ordonnés comme des éléments du booléen de l'ensemble ∆. L'approche proposée permet d'esquisser la manière d'analyser diverses propriétés et de compter le nombre de relations avec les propriétés individuelles ou leurs agrégats.

Que la relation soit considérée comme réflexive et symétrique. La symétrie du rapport est déterminée par la présence de paires de points, qui sont situées dans la matrice de rapport symétriquement à la diagonale relative. Pour un arbitraire n de telles paires, il y a

C_{n}^{2}

$C_n^2$ ... Notons l'ensemble de ces paires par le symbole S.Alors

toute la variété des relations symétriques et réflexives sera déterminée par le booléen

2^{S}

$2^S$ ... Un grand nombre de ces relations seront examinées plus en détail un peu plus tard, mais ici nous dirons qu'elles forment un espace d'indifférence ou de tolérance. Il est clair que le nombre de rapports de tolérance est déterminé par la puissance du booléen

2^{S}

$2^S$ , c'est à dire.

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

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

Ci-dessous dans le tableau. 1 montre les valeurs du nombre de rapports de tolérance pour les valeurs initiales n d'un segment d'entiers naturels.

Tableau 1 . Le nombre de BO tolérants

Il est maintenant facile de calculer la cardinalité de toutes les relations symétriques, car la présence ou l'absence de points diagonaux ne modifie pas les propriétés de symétrie. L'ensemble des relations symétriques est désigné par le symbole SM. Alors la cardinalité de cet ensemble pour un n fixe est déterminée par la formule

| 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},$

où n est le nombre de points diagonaux du rapport. Table 2 montre les valeurs | SM | pour certains n.

Tableau 2 . Le nombre de BO symétriques

Passons maintenant au calcul des relations asymétriques dont l'ensemble sera noté AS. Ces relations sont caractérisées par le fait que tous les points de la diagonale y sont absents et qu'aucune des cellules de la matrice de la relation située en dehors de la diagonale n'en a une symétrique. En d'autres termes, il s'agit d'un ensemble de relations antireflet et antisymétrique.

La cardinalité de cet ensemble peut être déterminée à partir des 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},$

où K =

C_{n}^{2}

$C_n^2$ ...

On obtient la formule réduite pour calculer la cardinalité de l'ensemble AS - relations asymétriques pour une cardinalité donnée de la porteuse | A | = n. Par définition, toutes les relations de l'ensemble AS sont antiréfléchissantes; par conséquent, la diagonale principale dans la matrice des relations est vide, et les éléments unitaires ne peuvent être situés que dans la moitié des positions restantes de la matrice, c'est-à-dire à

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

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

Donc, supposons qu'une relation asymétrique contienne des k-éléments (points, paires ordonnées) 0 ≤ k ≤

C_{n}^{2}

${C_n^2}$ ... Le nombre de relations avec un tel nombre d'éléments sera évidemment égal au nombre de combinaisons de

C_{n}^{2}

$C_n^2$ par k.

Dans ce cas, à chacun des k éléments, nous associons une paire de positions symétriques: l'une au-dessus de la diagonale principale de la matrice, l'autre en dessous de la diagonale. Puisque dans chaque paire, un élément peut être dans l'une des deux positions, alors un booléen semble accueillir k éléments

2^{n}

$2^n$ Opportunités.

De cette façon,

C_{n}^{2}

$C_n^2$ Est le nombre de choix de k paires de positions de

C_{n}^{2} = K

$C_n^2 = K$ paires disponibles dans la représentation matricielle des relations, et

2^{n}

$2^n$ - le nombre d'occasions de disposer k éléments en positions dans chaque paire. Le nombre de relations contenant k éléments est défini comme le produit du nombre de sélections de paires de positions par le nombre d'options pour disposer ces k éléments, c'est-à-dire

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

$2^kC_K^k$ ...

Le nombre total de relations dans l'ensemble AS est obtenu en additionnant les produits obtenus sur toutes les valeurs de k de zéro au maximum admissible K =

C_{n}^{2} = K

$C_n^2 = K$ , c'est à dire.

| 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},$

où K =

C_{n}^{2}

$C_n^2$ ...

Exemple 3. Soit la cardinalité de l'ensemble du support | A | = 5. Calculez le nombre de relations asymétriques à l'aide de la formule trouvée. Déterminez la valeur de la limite supérieure K dans la somme, K =

C_{n}^{2}

$C_n^2$ = 10. Les données de calcul de la somme sont données dans le tableau. 3.

Tableau 3 . Caractéristiques BO

Il existe une autre façon de calculer la cardinalité d'un ensemble AS. Il est basé sur le comptage du nombre de mappages d'un ensemble de paires de positions symétriques dans un ensemble d'états dans lesquels chacune de ces paires peut se trouver. Dans une relation asymétrique, il y a

K = C_{n}^{2}

$K = C_n^2$ paires de positions.

Chaque position dans une paire de cellules peut être occupée par 0 ou 1, mais pour une paire de positions il y a S = 3 états, que nous notons comme suit:

- 1, si l'élément (1) est placé au-dessus de la diagonale;

- 2, si l'élément (1) est placé sous la diagonale;

- 3 si les deux positions sont vides (occupées par des zéros).

Ainsi, une paire de positions symétriques (dans la matrice de relations) peut être dans chaque

relation dans l'un des trois états. La formule pour calculer toutes les correspondances possibles de l'ensemble des paires de positions (désignées par le symbole K) dans l'ensemble S d'états que nous avons:

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

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

Exemple 4 . Pour les conditions de l'exemple précédent a la forme | A | = 5, K = | K | =

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

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

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

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

Les résultats de calcul coïncident de deux manières différentes, ce qui convainc une fois de plus de l'exactitude des formules obtenues. Ainsi, nous avons obtenu la 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,$

où K =

C_{n}^{2} .

$C_n^2.$

Donnons en table. 4 nombres de relations asymétriques | AS | pour les petites valeurs de n.

Tableau 4. Le nombre de BO asymétriques

Ayant une formule pour déterminer le nombre de relations asymétriques, on peut en obtenir une autre - pour calculer le nombre de relations antisymétriques, car la présence ou l'absence de points diagonaux ne change pas les propriétés d'antisymétrie de la relation.

Ainsi, nous désignons l'ensemble des relations antisymétriques par le symbole ANS, puis la cardinalité de cet ensemble sera déterminée par la formule

| 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},$

où K =

C_{n}^{2}

$C_n^2$

Ci-dessous un tableau. 5 contenant les valeurs (ANS) pour n = 3 (1) 5.

Tableau 5 . Le nombre de BO antisymétriques

Dans ce qui suit, nous avons besoin de concepts qu'il est pratique de présenter ici.

La partie symétrique de la relation binaire α est appelée (et notée

α^{(S)}

$α^{(S)}$ ) attitude

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

$α^{(S)} =α∩α^{-1}$ et le ratio

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

$α^{()} = α \α^{(S)}$ (noté

α^{(а)}

$α^{()}$ ) s'appelle sa partie asymétrique. Dans le cas particulier où le rapport α est symétrique,

α^{(S)} = α

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

α^{(S)}

$α^{(S)}$ toujours symétrique; si α est asymétrique, alors

α^{(а)} = α

$α^{()}= α$ et

α^{(а)}

$α^{()}$ toujours asymétrique.

Transitivité (Latin Transitivus - transitionnel, de transitus - transition)

- une des propriétés des relations. Une relation = <M, A> définie sur l'ensemble A est transitive si pour tout

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

$_i, _ j, _k є A$ la condition est satisfaite: à partir de

а_{i} α а_{j}

$_iα _ j$ et

а_{j} α а_{k}

$_jα _k$ devrait

а_{i} α а_{k}

$_iα _ k$ ...

En d'autres termes, pour une relation transitive à partir de la présence d'éléments dans sa composition (

а_{i} α а_{k}

$_iα _ k$ ) et (

а_{k} α а_{j}

$_kα _ j$ ) il s'ensuit qu'il contient l'élément (

а_{i} α а_{j}

$_iα _ j$ ). Pour un graphe de relations, cette propriété signifie que si une paire de sommets (

а_{i} α а_{j}

$_iα _ j$ ) est reliée par un chemin orienté passant par le sommet k et formé de 2 arcs consécutifs (

а_{i} α а_{k}

$_iα _ k$ ), (

а_{k} α а_{j}

$_kα _ j$ ), alors les mêmes sommets sont directement reliés par un seul arc (

а_{i} α а_{j}

$_iα _ j$ ). Pour les éléments de matrice [

а_{i j}

$_{ij}$ ] d'une relation transitive α de

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

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

а_{i j} = 1

$_{ij} = 1$ ...

La définition de la propriété de transitivité pour les relations binaires suppose que la relation contient au moins trois éléments (paires ordonnées). Et comment cette propriété se manifeste-t-elle dans une relation à un élément, vide ou contenant seulement deux éléments?

Toutes les relations singleton et vides sont transitives. Une relation à deux éléments peut être transitive et non transitive si les paires qu'elle contient contiennent un élément commun j. Les arcs de graphe correspondant à des paires ordonnées sont dirigés dans une direction (forment un itinéraire orienté de non transitivité).

Par exemple, laissez (

а_{i}, а_{j}

$_i, _ j$ ) є α et (

а_{j}, а_{k}

$_j, _ k$ ) є α. La définition formulée exige: pour que la relation α soit transitive, elle doit contenir une troisième paire (arc), à savoir, (

а_{i}, а_{k}

$_i, _ k$ ), mais comme elle n'existe pas, la propriété de transitivité pour α n'est pas satisfaite.

Si, comme précédemment, la relation ne contient que deux paires avec un élément commun

а_{j} є A

$_j є A$ , mais tel que l'élément commun

а_{j} є A

$_j є A$ est dans la même position dans les deux paires (

а_{j}, а_{i}

$_j, _ i$ ), (

а_{j}, а_{k}

$_j, _ k$ ) ou (

а_{i}, а_{j}

$_i, _ j$ ),

(

а_{k}, а_{j}

$_k, _ j$ ), et les arcs sur le graphique sont dirigés dans des directions différentes, alors une telle relation est transitive, car l'inclusion de la troisième paire dans la relation n'est pas requise.

Une relation transitive sera également dans le cas où deux paires n'ont pas d'éléments communs. Des exemples de relations transitives sont: "égalité" (=), puisque i = k, k = j implique i = j; "I est supérieur à j"; en géométrie - "parallélisme des lignes droites". Exemples de relations non transitives: "perpendicularité des droites" en géométrie; "I n'est pas égal à j".

Dans la littérature sur les relations, on peut trouver différents concepts qui caractérisent la transitivité: faible transitivité, forte transitivité, transitivité négative, anti-transitivité, faible anti-transitivité, transitivité généralisée, fermeture transitiveet quelques autres. On tente ici de systématiser les diverses nuances de manifestation de la propriété de transitivité dans les relations.

Pour une relation transitive α, la relation

α^{- 1}

$α^{–1}$ est également toujours transitive. L'intersection d'un nombre arbitraire de relations transitives est une relation transitive. Si nous considérons la relation ᾰ, qui est l'intersection de toutes les relations transitives contenant la relation α, alors ᾰ est appelée la fermeture transitive de la relation α.

La fermeture transitive ᾰ peut être construite pour toute relation α conformément à la règle de

а_{i} ᾰ а_{j}

$_i ᾰ _j$ suit:

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

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

La relation ᾰ est la plus petite relation transitive contenant α. Si α est transitif, alors il coïncide avec sa fermeture transitive α = ᾰ et vice versa.

Lors de la représentation d'une relation binaire transitive par un graphe orienté, il est possible de ne pas représenter le digraphe entier, mais seulement son squelette transitif, c'est-à-dire les arcs reliant le début et la fin de chaque route plus longs que un ne sont pas dessinés. Dans ce cas, on dit que le squelette transitif du graphe est pris pour la relation α . Cette opération est essentiellement l' inverse de l'opération de fermeture transitive , dans laquelle le début et la fin de chaque réseau sont reliés par un arc.

En général, la propriété de transitivité n'est pas remplie par rapport à l'opération de combinaison de relations. Combiner deux relations transitives

α_{1}

$α_1$ et

α_{2}

$α_2$ est transitif si et seulement si l'un d'eux est transitif par rapport à l'autre. Pour une paire de relations binaires

α_{1}

$α_1$ et

α_{2}

$α_2$ on peut considérer la transitivité de l'un par rapport à l'autre.

Alors

α_{1}

$α_1$ est transitif par rapport à

α_{2}

$α_2$ dans les conditions suivantes:

1) à partir de

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

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

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

$(_i, _j) є _1$ ;

2) à partir de

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

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

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

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

Dans le cas où

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

$α_1= α_2=α$ la transitivité relative est la transitivité habituelle.

L'énoncé suivant est connu sur les propriétés de transitivité, de symétrie et d'asymétrie d'une relation. Si une relation binaire est transitive, alors sa partie symétrique

α^{(S)}

$α^{(S)}$ et

α^{(а)}

$α^{()}$ la partie asymétrique est également transitive.

Le contraire n'est vrai que si

α^{(S)}

$α^{(S)}$ ,

α^{(а)}

$α^{()}$ transitif et

α^{(а)}

$α^{()}$ transitivement relatif

α^{(S)}

$α^{(S)}$ ... En général, de la transitivité

α^{(S)}

$α^{(S)}$ et

α^{(а)}

$α^{()}$ la transitivité de α ne suit pas.

La composition de la relation transitive α avec elle-même satisfait la relation α · α ⊆ α. Une relation α est négativement transitive (non transitive) si son complément est transitif, i.e. ᾱ. Dans la matrice d'une telle relation [

α_{i j}

$α_{ij}$ ] de

α_{i k} = 0

$α_{ik} = 0$ et

α_{k j} = 0

$α_{kj} = 0$ devrait

α_{i j} = 0

$α_{ij} = 0$ ... La transitivité négative de α n'exclut pas le fait que α lui-même peut aussi être transitif.

Dans ce cas, on dit que α est une relation fortement transitive . Éléments de la matrice [

α_{i j}

$α_{ij}$ ] une telle attitude se caractérise par le fait que

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

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

а_{i j} = 1

$_{ij} = 1$ , un de

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

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

а_{i j} = 0

$_{ij} = 0$ ...

En plus des relations fortement transitives, les relations faiblement transitives (pseudotransitives) sont considérées , qui incluent les relations d'où les conditions

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

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

а_{К} α а_{j}

$_α_j$ devrait

а_{i} α а_{j}

$_iα_j$ ... Sa transitivité résulte de l'asymétrie et de la transitivité négative.

Une relation α est transitivement complète si pour tout δ de

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

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

comparabilité suit

а_{K 1}

$_{K1}$ et

а_{K δ}

$_{Kδ}$ , c'est à dire. sont exécutés soit

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

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

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

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

Cyclicité

Les relations définies sur l'ensemble A peuvent être visualisées du point de vue de la présence de cycles en eux. Il convient d'effectuer une telle considération sur des graphiques de relations. Un graphe de relations cycliques contient toujours au moins un contour fermé (un itinéraire). Ignorer les flèches transforme le chemin en boucle. Un graphique d'une relation acyclique ne contient pas de cycles et est appelé acyclique ou incontrôlé .

La relation = <Å, A> est cyclique si au moins une chaîne de la forme peut être formée à partir des éléments de l'ensemble A

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

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_{Kδ},_{Kδ}α_{Ki}$ longueur arbitraire δ. Le graphe M de la fermeture transitive pour une relation cyclique contient au moins une paire (

а_{i}, а_{i}

$_i, _i$ ), et pour une relation acyclique α ne contient pas de telle paire.

La relation = <Å, A> est acyclique si, pour tout δ≥1, la condition de

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

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

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

$_i ≠ _j$ ... Dans la matrice [

α_{i j}

$α_{ij}$ ] relation acyclique de

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

$_{iK1}_{K1K2}..._{K(δ-1)j}=1$ i ≠ j suit. La relation acyclique est toujours asymétrique, mais le contraire n'est pas vrai. En d'autres termes, si certains pics

а_{i}

$_i$ et

а_{j}

$_j$ graphe α, les relations acycliques sont reliées de façon intermédiaire; alors il n'y a pas d'arc dans le graphe (

а_{j}, а_{i}

$_j, _i$ ). Les tournois transitifs

sont des exemples classiques de graphiques avec cette propriété . Les sommets de ces graphes peuvent être renumérotés, sous lequel pour tout arc (

а_{i}, а_{j}

$_i, _j$ ) le nombre du sommet j est supérieur au sommet i.

Si α est une relation binaire transitive antireflet, alors elle est acyclique. L'acyclicité et la complétude transitive de la relation impliquent sa transitivité.

Complétude

Propriété d'exhaustivité (perfection, linéarité). L'ensemble des relations est divisé en relations incomplètes et complètes , parmi lesquelles se détachent à leur tour les relations fortement complètes. Nous illustrerons la propriété d'exhaustivité des relations en considérant des graphes de relations.

Le graphe d'une relation complète est complet, c'est-à-dire deux de ses sommets sont directement connectés par au moins un arc, c'est-à-dire sont adjacents. Étant donné que chaque arc du graphique correspond à un point (élément, paire) du graphique de la relation, une définition peut être formulée sur la base de ce qui précède.

La relation = <Å, A> est complète (parfaite, linéaire) si et seulement si tous les éléments de l'ensemble A sont comparables ou égaux les uns aux autres. Ainsi, l'attitude globale est réflexive. En d'autres termes, pour deux éléments quelconques

а_{i}

$_i$ et

а_{j}

$_j$ juste

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

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

Si dans la relation α il y a au moins une paire

а_{i}

$_i$ ,

а_{j}

$_j$ éléments incomparables et inégaux, alors une telle relation est incomplète. Pour tout rapport total α,

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

$∆UαUα^{-1}=A×A$ ou de

а_{i} ᾱ а_{j}

$_i ᾱ _j$ devrait

а_{j} α а_{i}

$_j α _i$ ... La relation binaire α est complète si et seulement si

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

$^{(a)} =^{(d)}$ , c'est à dire. lorsque sa partie asymétrique coïncide avec la relation duale (item 9) .

Une relation binaire α est fortement complète lorsque son graphe coïncide avec A × A. Un graphe de cette relation est un graphe complet dans lequel chaque paire de sommets est reliée par une arête et chaque sommet a une boucle. Un tel graphe est appelé un graphe fortement complet. Le rapport total α satisfait toujours les relations

ᾱ \subset α^{- 1}

$ᾱ ⊂ α^{-1}$ et

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

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

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

$α∪(ᾱ∩α^{d}) = α∪(ᾱ)^{(S)}$ toujours plein.

Si

α_{1}

$α_1$ et

α_{2}

$α_2$ relation complète, alors

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

$α_1·α_2$ plein. Dans la matrice [

α_{i j}

$α_{ij}$ ] relation complète

α_{i j} = 1

$α_{ij} = 1$ ou

α_{j i} = 1

$α_{ji} = 1$ pour tout i, j ou les deux égalités sont vraies. Une relation α est faiblement complète (faiblement connexe) si pour tout

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

$_i,_j є A$ tel que

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

$_i ≠ _j$ ou

а_{i} α а_{j}

$_i α _j$ ou

а_{j} α а_{i}

$_j α _i$ ...

Dans la matrice [

α_{i j}

$α_{ij}$ ] d'une relation faiblement complète pour tout i ≠ j, ou

α_{i j} = 1

$α_{ij} = 1$ ou

α_{j i} = 1

$α_{ji} = 1$ , ou les deux égalités sont vraies. Une relation α est transitivement complète si, pour un n arbitraire de

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

$_iα_{K1}, _{K1}α_{K2},…, _{K(n-1)}α_{in}$ la comparabilité suit

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

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

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

$_{i1}α _{in}$ ou

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

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

Comptons le nombre de relations complètes. Tout d'abord, considérez le problème de ligne. Une ligne dans une matrice de rapport est un segment de droite perpendiculaire à la diagonale principale de la matrice de rapport, reliant les centres de deux cellules (cellules) de la matrice situées symétriquement par rapport à cette diagonale.

Si deux ou plusieurs paires de positions symétriques tombent sur une ligne (ligne droite) dans la matrice de rapport, le nombre de lignes reste néanmoins égal au nombre de telles paires de positions. Le nombre total de paires de positions pour un n arbitraire est défini comme

C_{n}^{2} = L

$C_n^2 = L$ ...

Ainsi, dans la matrice pour une relation arbitraire sur l'ensemble A, il y a un ensemble L de segments parallèles (lignes). Désignons les positions finales des segments (lignes) par les symboles L - gauche et P - droite. Aussi disponible | L | puces qui peuvent être placées dans des positions aux extrémités des lignes. Le défi est de déterminer le nombre de façons dont il serait possible d'organiser | L | puces pour qu'il y ait au moins une puce sur chaque ligne.

Il est clair que le problème peut se réduire à la détermination du nombre F de mappages f: L → π de l'ensemble L de lignes dans l'ensemble des π positions (n = {A, P}). On sait que le nombre de ces mappages est déterminé par la formule

F = | п |^{| L |}

$F = ||^{|L|}$ ... Une cartographie spécifique (image) peut avoir la forme <P, P, L, L, L,…, L, P> de la séquence d'indices pour | L | positions. Le symbole L correspond à la position sous la diagonale principale, et le symbole P, qui lui est symétrique au-dessus de la diagonale.

De la définition du rapport total, il s'ensuit que son graphique contient au moins K points, K =

C_{n}^{2}

$C_n^2$ localisé: de sorte que toutes les lignes soient occupées par au moins une puce. Le nombre k de points sur le graphique, en plus du nombre minimum requis, peut passer par la valeur k = 0 (1) K =

C_{n}^{2}

$C_n^2$ ...

Pour chaque nombre fixe de k points, l'ensemble des choix de positions dans lesquelles ils peuvent être placés est déterminé par la valeur

C_{К}^{k}

$C_^k$ , où K est l'ensemble des positions inoccupées. Puisque k points supplémentaires remplissent complètement k lignes, alors pour assurer la propriété d'exhaustivité du rapport, il reste à remplir K - k positions avec des puces (points de l'ensemble du minimum requis), et le nombre de ces remplissages est

2^{К - k}

$2^{-k}$ ...

Le choix des positions pour k points supplémentaires et les méthodes de remplissage des lignes K-k avec des puces sont indépendants. Par conséquent, le nombre total de possibilités pour placer K + k points dans 2 ∙ K positions de sorte que toutes les lignes soient occupées par au moins un point est déterminé par l'expression

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

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

Si nous additionnons cette expression, alors nous obtenons le nombre de relations complètes, qui ne dépend pas de la situation avec le placement des points diagonaux. En d'autres termes, c'est le nombre de relations complètes partiellement réflexives, par exemple antireflet et pleines réflexives et complètes, etc.

Exemple 5 . La variété des situations pour placer des points diagonaux est déterminée par le nombre

2^{n}

$2^n$ ... Alors la cardinalité de l'ensemble de toutes les relations complètes pour un n fixe est déterminée par la formule

П = 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}$ ...

Pour les relations avec trois propriétés requises

Pour les relations d'équivalence avec trois propriétés requises. Il y a un résultat remarquable: chaque relation d'équivalence sur un ensemble de n éléments est en correspondance biunivoque avec une partition de cet ensemble. Le nombre de ces relations est déterminé par la formule

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

$B_n = ∑_{m=0}^nS(n, m)$ , où S (n, m) est le nombre de Stirling du second type, Bn est le nombre de

cloche , ou sous forme récurrente

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

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

Pour les ensembles ordonnés (ordres partiels), ces formules ne sont pas ouvertes et leur nombre est déterminé par des calculs directs, c'est-à-dire la modélisation. Pour les petites valeurs de n, les données sont données dans le

tableau 6 . Caractéristiques quantitatives des relations binaires

Le tableau 6 montre: n = | A | - la cardinalité de l'ensemble-porteur;

2^{n^{2}}

$2^{n^2}$ - le nombre de toutes les relations binaires sur l'ensemble A;

| Dans (n) | - le nombre de classes de relations non isomorphes;

| (n) | - le nombre de relations d'ordre partiel;

| Gn (n) | - le nombre de classes sont des relations non isomorphes d'ordre partiel;

| Gl (n) | = n! - le nombre de relations d'ordre linéaire.

Conclusion

Dans ce travail, une analyse détaillée des propriétés de base et de la structure du rapport binaire a été réalisée, sur la base de laquelle il a été possible d'obtenir des caractéristiques quantitatives pour BO avec une ou plusieurs propriétés. Trouvé et présenté des ratios originaux pour le nombre de certains types de relations avec deux et trois propriétés requises. Ces résultats ouvrent la possibilité de modéliser et d'étudier la BO et les relations de plus haute arité.

Liste de la littérature utilisée

Aigner M. Théorie combinatoire. - M.: Mir, 1982.
Birkhoff G. Théorie des structures. - M .: IL, 1952.-408 p.
Noden P., Kitte K. Algorithmique algébrique. - M .: Mir, 1999. - 720 p.
Rybnikov K.A. Une introduction à l'analyse combinatoire. -M.: Ed. Université d'État de Moscou, 1972. -256s.
Stanley R. Combinatoires énumératifs. Vol. 1.- M.: Mir, 1990 - 440p.
Stanley R. Combinatoires énumératifs. T. 2.- M.: Mir, 2005. - 767s.
Shikhanovich Yu.A. Introduction aux mathématiques modernes. Concepts initiaux.-M .: Nauka, 1965. - 376p.

Caractéristiques quantitatives des relations

Caractéristiques quantitatives des types de relations binaires

Réflexivité

Symétrie

Transitivité (Latin Transitivus - transitionnel, de transitus - transition)

Cyclicité

Complétude

Conclusion

Liste de la littérature utilisée

More articles: