👨‍👦‍👦 🧑🏾‍🤝‍🧑🏻 🧗🏻 Características cuantitativas de las relaciones. 🖐️ 🐆 🖐️

La teoría de las relaciones en matemáticas y en una serie de áreas temáticas (toma de decisiones, conocimiento y bases de datos, lingüística matemática, modelado de procesos, etc.) juega un papel muy notable, pero aún está lejos de ser completo. Como en otras ramas del conocimiento matemático, sus conocidos resultados se relacionan en mayor medida con las cuestiones y problemas de la existencia de uno u otro de sus objetos que con los problemas de enumerarlos. Parecería que cualquier investigador en una rama específica de la teoría debería estar interesado en el cuadro general y completo de los objetos de interés y sus dependencias, para observar el panorama completo. Pero, por desgracia, es muy problemático hacer esto, ya que nadie ha creado ni ofrece tal panorama (imagen). Incluso el catálogo de relaciones propuesto en el trabajo no cierra el problema.

Un ejemplo sencillo. Hace muchos años en el libro [1 p. 207] me encontré con un párrafo así.

La teoría de los conjuntos parcialmente ordenados todavía contiene muchos problemas sin resolver. Incluso la cuestión del número de conjuntos de este tipo que se pueden construir a partir de un número dado de n de elementos aún no existe si n ≥6. Los cálculos directos solo lograron establecer que si S (n) es el número de conjuntos parcialmente ordenados, entonces S (2) = 3, S (3) = 19, S (4) = 219, S (5) = 4231, y los números S - (n) para conjuntos no isomorfos se encontraron solo para n = 4 yn = 5 elementos: Sn (4) = 16 y Sn (5) = 63.

El jefe del departamento de la Universidad Estatal de Moscú, Rybnikov K.A. Quería entender esto más profundamente y parecía que podía intentar buscar una solución, al menos expandir de alguna manera la lista y, lo más importante, enumerar los pedidos parciales, ver su dispersión en realidad con sus propiedades. Solo para colgar los resultados en la pared. Confieso que se invirtió mucho esfuerzo en desarrollar un programa de investigación, crear un modelo viable de orden parcial, escribir un programa y depurarlo, las computadoras hicieron girar los algoritmos programados durante decenas de horas. Alguien (de los grandes) recordó que la base de las matemáticas no debería haber sido un número, sino un orden, entonces supuestamente muchos teoremas habrían recibido demostraciones más simples y transparentes.

Hemos aprendido a calcular el número de relaciones sobre grandes conjuntos-portadores y a enumerar las relaciones, pero no pudimos obtener fórmulas estrictas incluso para el número S (n). Recuerdo esta época como un período de crecimiento creativo intensivo propio y de mis colegas, cuando después de casi cada salida de los resultados de la computadora y su análisis, surgieron ideas para modificar, mejorar el modelo, algoritmos, se hicieron correcciones para probar nuevas hipótesis, pero algo significativo ( ~~posiblemente cerebros~~ ) no fue posible. suficiente.

Lo que logré abrir (obtener) lo doy a continuación en el texto. Por cierto, los resultados de otros investigadores extranjeros coincidieron con los nuestros, pero informaron solo el número S (n) y no mencionaron la enumeración de órdenes parciales.

Empezamos de a poco. La lista completa de relaciones binarias para cualquier conjunto de n portadoras es conocida y se puede obtener fácilmente. Buscaban una respuesta a las preguntas: cuántas, para una n dada, hay relaciones con una propiedad fija, con un par de propiedades, con un triple, etc. El hecho es que teniendo estos datos, era posible construir no enumeraciones, sino algoritmos directos para enumerar tales relaciones que al seguir la regla de la navaja de Occam, no producen esencias adicionales.

Aquí hablaremos sobre la obtención de tales resultados para relaciones binarias (BR).

Entonces, hay un n-set-carrier de BO y una lista completa de todos los BO, así como una lista de propiedades de BO:

- reflexividad; antirreflectante; reflexividad parcial;

- simetría; antisimetría; asimetría; asimetría;

- transitividad; anti-transitividad;

- orden débil; orden estricto; Orden parcial; perfecto (lineal);

- tolerancia;

- equivalencia;

- ciclicidad;

- integridad.

Características cuantitativas de los tipos de relaciones binarias.

Las relaciones pueden tener no solo una propiedad específica, sino también conjuntos de pares, tripletes, etc. de propiedades. El uso de tales relaciones en la práctica es una situación común. Entonces, por ejemplo, cada actitud de tolerancia (indiferencia) tiene dos propiedades: simetría y reflexividad. Este conjunto de propiedades determina el tipo de relación de tolerancia.

Otro tipo de relación surge de las relaciones de tolerancia, si requerimos de tales relaciones la viabilidad de una lista ampliada de propiedades: simetría, reflexividad y transitividad. Está claro que quizás no todas las relaciones de tolerancia resultarán transitivas, pero aquellas que tengan un conjunto de tres propiedades nombradas formarán un nuevo tipo de relaciones llamadas equivalencias.

El conjunto de relaciones de equivalencia resulta estar anidado en el conjunto de relaciones de tolerancia. Por ejemplo, en el catálogo, estos tipos de relaciones se resaltan con relleno (8 tolerancias y solo 5 de ellas son equivalencias). Surge la pregunta sobre el número de BO con un conjunto de propiedades o una de ellas.

Reflexividad

La relación α = <, A> en el conjunto A = {

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

${_1,_2,...,_n}$ } es reflexivo (posee la propiedad de reflexividad) si cada par (

а_{i}, а_{i}

$_ i, _ i$ ) satisface esta relación. Aquí M es un gráfico (no un gráfico) de la relación

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

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

En otras palabras, la diagonal principal de la matriz gráfica Å la relación se rellena con unos. En un gráfico de relación reflexiva, todos los vértices tienen bucles. La actitud es antirreflectante si no

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

$_i є A , i = 1(1)|A|$ No realizado

а_{i} α а_{i}

$_ i α _ i$ ... En este caso, la matriz de la relación antirreflexiva α en la diagonal principal no tiene una sola unidad, es decir hay ceros y la gráfica correspondiente no tiene bucles en ningún vértice.

Finalmente, la relación α no es reflectante si para algunos

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

$_i є A ,_ i α _ i$ se ejecuta, pero para otros no. Consideraremos tales relaciones parcialmente reflexivas. La matriz de relación no reflectante en la diagonal principal contiene en parte unos, en parte - ceros. El gráfico de tal relación no reflectante no tiene bucles en todos los vértices.

Un ejemplo clásico de una relación reflexiva es la diagonal principal de una representación matricial, la relación unitaria (E = Δ), es decir, Relación de igualdad (en el catálogo nº 68). La gráfica de esta relación está formada por puntos (pares) que se encuentran en la diagonal principal de la matriz y los pares correspondientes

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

$( i , i ) , i =1(1)|A|$ , el gráfico no contiene ningún otro punto.

La representación matricial de esta relación corresponde a la matriz identidad (E). El gráfico de relación diagonal está formado por los vértices correspondientes a los elementos del conjunto A al que se asignan los bucles. La relación diagonal a menudo se denota por

Δ_{А}

$Δ_$ ...

En el caso de una relación reflexiva, el gráfico correspondiente también es reflexivo, en el caso de una relación antirreflexiva, su gráfico es antirreflexivo. Si para alguna relación α se sabe que es reflexiva, entonces el complemento ᾱ es siempre antirreflejoso, y

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

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

Para la relación antirreflexiva β, es cierto

β \cap Δ_{А} = \emptyset

$β ∩Δ_= ∅$ ...

Ejemplo 1 . La relación ≤ (no más) en el conjunto N es reflexiva y la relación <(menos) en el mismo conjunto es antirreflexiva.

La actitud de “ser hijo” es antirreflectante, ya que nadie es su propio hijo.

A efectos prácticos, a veces es necesario contar el número de relaciones reflexivas disponibles en el conjunto completo de relaciones dadas en el conjunto A con cardinalidad | A | = n.

Demostremos cómo se puede realizar tal cálculo. Consideraremos la matriz de la relación reflexiva binaria α en el plano. Siempre contiene todos los puntos diagonales.

Otros puntos correspondientes a pares (i, j), el número de n × n - n = n (n - 1) de los cuales, se pueden incluir en diferente composición y número k, k = 0 (1) (n × n - n)en posibles relaciones, que, por supuesto, serán reflexivas. Sumando k combinaciones de n (n-1) sobre k , se determina el número total de relaciones reflexivas

donde K = n (n-1) / 2 es el número de arcos (aristas) en un gráfico de n- vértices sin bucles.

El número de relaciones no reflexivas se define como la diferencia entre el número total de relaciones en A y el número de relaciones reflexivas.

De esta expresión se deduce que el conjunto de relaciones no reflexivas contiene en

(2^{n} - 1)

$(2^n -1)$ veces más relaciones que reflexivas. Este exceso de ratios se genera por la variedad de combinaciones de solo puntos diagonales en el gráfico, mientras que las composiciones y el número de puntos restantes simplemente se repiten.

El número de relaciones antirreflexivas del conjunto de no reflexivas es exactamente igual al número de relaciones reflexivas, es decir,

2^{n^{2} - n}

$2^{n^2-n}$ ... Esto se deriva del hecho de que se puede establecer una correspondencia biunívoca entre relaciones reflexivas y antirreflexivas: de cada relación reflexiva, eliminando todos los puntos de la diagonal, se puede obtener una única relación antirreflexiva y viceversa.

Simetría

Por la propiedad de la simetría, todo el conjunto de relaciones no se divide en cuatro clases: simétricas, asimétricas. Estos últimos, a su vez, se dividen en tres clases: antisimétrica, asimétrica y asimétrica restante.

La relación α = <Å, A> sobre el conjunto A es simétrica (tiene la propiedad de simetría con respecto a la recta que coincide con la diagonal principal del gráfico M) si para algún par

(i, j) є A \times A

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

а_{i} α а_{j}

$_i α _j$ debería

а_{j} α а_{i}

$_j α _i$ ... En otras palabras, para cualquier par

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

$((_i, _j) є Å)$ ejecutado en ambas direcciones, o en absoluto.

En la gráfica de una relación simétrica, si un par de vértices i y j está conectado por un arco (i, j), entonces necesariamente está conectado por un arco (j, i). Una gráfica de relación simétrica es una gráfica ordinaria con orientación simétrica o simplemente no dirigida.

La relación α es antisimétrica si de

а_{i} α а_{j}

$_i α _j$ y

а_{j} α а_{i}

$_j α _i$ se sigue que i = j.

La matriz de razón antisimétrica no contiene necesariamente todos en la diagonal principal y contiene unos en una de dos posiciones simétricas con respecto a la diagonal principal: por encima de la diagonal o por debajo de la diagonal. El gráfico de esta relación está formado por vértices con bucles para todos o algunos de ellos, y si un par de vértices (i, j) en el gráfico está conectado, entonces siempre es un arco de una sola dirección. Tenga en cuenta que para una relación simétrica y antisimétrica, algunos puntos diagonales pueden incluirse en ella o no.

Si una relación antisimétrica no contiene un solo punto diagonal, entonces dicen que dicha relación es asimétrica , es decir. siempre es antirreflectante.

Ejemplo 2... La relación (≤) en el conjunto N es antisimétrica y la relación (<) en el mismo conjunto es asimétrica. De hecho, en el primer caso de

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

$_i ≤_j$ y

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

$_j ≤_i$ solo puedo seguir

i = j

$i = j$ ... La relación de igualdad (=) en N es simétrica, la relación α = A × A también es simétrica.

Para cualquier razón simétrica α, siempre es cierto

α = α^{- 1}

$α = α^{-1}$ y

α^{- 1}

$α^{-1}$ también simétrico. Para una relación antisimétrica,

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

$α ∩ α^{-1}⊆∆_A$ ... Una relación general, cuyo gráfico contiene tanto puntos simétricos como asimétricos, no es simétrica. Esta relación es asimétrica, pero no antisimétrica ni asimétrica.

La propiedad de simetría también se manifiesta en relaciones n-arias. La relación R en el set

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

$= { x_1, x_2,…,x_n}$ es una relación n-aria simétrica si, junto con el elemento

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

$<x_{i1}, x_{i2}, …,x_{in}>є R$ contiene cualquier secuencia

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

$< x_{j1}, x_{j2},…, x_{jn}>$ formado por la permutación de los miembros del conjunto X.

Nótese también que la relación asimétrica es siempre antirreflexiva; Una relación binaria transitiva y no reflexiva es siempre asimétrica. Para practicar y realizar cálculos, es de interés el número de relaciones que tienen una determinada propiedad relacionada con la simetría del gráfico. Calculemos tales razones para un conjunto arbitrario A de cardinalidad | A | = n.

En nuestro razonamiento nos basaremos en la propiedad de la reflexividad, que, como muchas otras, aún no se ha estudiado con suficiente profundidad. Incluso un análisis superficial del conjunto de todas las relaciones nos permite concluir que siempre se puede dividir en

2^{n}

$2^n$ clases del mismo tamaño, y la composición de las relaciones que forman estas clases obedece a un patrón determinado.

Los conjuntos de relaciones en todas las clases tienen la misma estructura, difieren solo en el número y la composición de los puntos diagonales, cuya variedad completa está determinada por el número

2^{n}

$2^n$ ... Definamos el estado de la diagonal de una relación para una n fija por el número y la composición de los puntos sobre ella y pertenecientes a una relación específica. Está claro que para un conjunto fijo de estados rellenos de las celdas de la diagonal está determinado por el booleano

2^{∆}

$2^∆$ , donde ∆ es el conjunto completo de puntos de la diagonal de la gráfica del cuadrado cartesiano de cardinalidad | ∆ | = n.

Así, en la teoría de las relaciones, tradicionalmente solo se han considerado y estudiado dos estados extremos: o todos los puntos de la diagonal están incluidos en la relación y es reflexiva, o la relación no contiene ningún punto diagonal, y entonces es antirreflectante.

Llamaremos a todos los estados intermedios con un punto diagonal, con dos, y así sucesivamente, reflexividad parcial de k-ésimo orden k = 0 (1) n, y las relaciones de este tipo son parcialmente reflexivas. Por tanto, una relación parcialmente reflexiva de orden cero es una relación antirreflexiva, y parcialmente una relación reflexiva de orden n es simplemente una relación reflexiva.

Tenga en cuenta que todos los estados se pueden ordenar como elementos del booleano del conjunto ∆. El enfoque propuesto nos permite delinear la forma de analizar varias propiedades y contar el número de relaciones con propiedades individuales o sus agregados.

Dejemos que la relación se considere reflexiva y simétrica. La simetría de la relación está determinada por la presencia de pares de puntos en ella, que se encuentran en la matriz de relaciones simétricamente a la diagonal relativa. Para n arbitrarios de estos pares, hay

C_{n}^{2}

$C_n^2$ ... Denotemos el conjunto de estos pares con el símbolo S.

Entonces, toda la variedad de relaciones simétricas y reflexivas estará determinada por el booleano

2^{S}

$2^S$ ... Muchas de estas relaciones serán consideradas con más detalle un poco más adelante, pero aquí diremos que forman un espacio de indiferencia o tolerancia. Está claro que el número de relaciones de tolerancia está determinado por la potencia del booleano

2^{S}

$2^S$ , es decir

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

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

A continuación en la tabla. 1 muestra los valores del número de relaciones de tolerancia para los valores iniciales n de un segmento de números naturales.

Cuadro 1 . El número de BO tolerantes

Ahora es fácil calcular la cardinalidad de todas las relaciones simétricas, ya que la presencia o ausencia de puntos diagonales no cambia las propiedades de simetría. El conjunto de relaciones simétricas se denota con el símbolo SM. Entonces, la cardinalidad de este conjunto para un n fijo está determinada por la fórmula

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

donde n es el número de puntos diagonales de la razón. Mesa 2 muestra los valores | SM | para algunos n.

Cuadro 2 . El número de BO simétricos

Pasemos ahora al cálculo de relaciones asimétricas, cuyo conjunto se denotará por AS. Estas relaciones se caracterizan por el hecho de que todos los puntos de la diagonal están ausentes en ellas y ninguna de las celdas de la matriz de la relación que se encuentra fuera de la diagonal tiene una simétrica. En otras palabras, es un conjunto de relaciones antirreflectantes y antisimétricas.

La cardinalidad de este conjunto se puede determinar a partir de las expresiones

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

donde K =

C_{n}^{2}

$C_n^2$ ...

Obtenemos la fórmula reducida para calcular la cardinalidad del conjunto AS - relaciones asimétricas para una cardinalidad dada del portador | A | = n. Por definición, todas las relaciones del conjunto AS son antirreflejos; por lo tanto, la diagonal principal en la matriz de relaciones está vacía, y los elementos unitarios pueden ubicarse solo en la mitad de las posiciones restantes de la matriz, a

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

${C_n^2} =(n^2-n):2$ células.

Entonces, suponga que una relación asimétrica contiene k-elementos (puntos, pares ordenados) 0 ≤ k ≤

C_{n}^{2}

${C_n^2}$ ... El número de relaciones con tal número de elementos será obviamente igual al número de combinaciones de

C_{n}^{2}

$C_n^2$ por k.

En este caso, con cada uno de los k elementos asociamos un par de posiciones simétricas: una arriba de la diagonal principal de la matriz, la otra debajo de la diagonal. Dado que en cada par un elemento puede estar en una de dos posiciones, entonces un booleano parece acomodar k elementos

2^{n}

$2^n$ oportunidades.

De este modo,

C_{n}^{2}

$C_n^2$ ¿Es el número de opciones de k pares de posiciones de

C_{n}^{2} = K

$C_n^2 = K$ pares disponibles en la representación matricial de relaciones, y

2^{n}

$2^n$ - el número de oportunidades para organizar k elementos en posiciones en cada par. El número de relaciones que contienen k elementos se define como el producto del número de selecciones de pares de posiciones por el número de opciones para organizar estos k elementos, es decir,

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

$2^kC_K^k$ ...

El número total de relaciones en el conjunto AS se obtiene sumando los productos obtenidos sobre todos los valores de k desde cero hasta el máximo permitido K =

C_{n}^{2} = K

$C_n^2 = K$ , es decir

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

donde K =

C_{n}^{2}

$C_n^2$ ...

Ejemplo 3. Sea la cardinalidad del conjunto del soporte | A | = 5. Calcule el número de relaciones asimétricas usando la fórmula encontrada. Determine el valor del límite superior K en la suma, K =

C_{n}^{2}

$C_n^2$ = 10. Los datos de cálculo para la suma se dan en la tabla. 3.

Cuadro 3 . Características BO

Hay otra forma de calcular la cardinalidad de un conjunto AS. Se basa en contar el número de asignaciones de un conjunto de pares de posiciones simétricas en un conjunto de estados, en los que cada par puede estar. En una relación asimétrica, hay

K = C_{n}^{2}

$K = C_n^2$ pares de posiciones.

Cada posición en un par de celdas puede estar ocupada por 0 o 1, pero para un par de posiciones hay S = 3 estados, que denotamos de la siguiente manera:

- 1, si el elemento (1) se coloca sobre la diagonal;

- 2, si el elemento (1) se coloca debajo de la diagonal;

- 3 si ambas posiciones están vacías (ocupadas por ceros).

Por tanto, un par de posiciones simétricas (en la matriz de relaciones) pueden estar en cada

relación en uno de los tres estados. La fórmula para calcular todas las posibles asignaciones del conjunto de pares de posiciones (denotado por el símbolo K) en el conjunto S de estados tenemos:

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

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

Ejemplo 4 . Para las condiciones del ejemplo anterior tiene la forma | A | = 5, K = | K | =

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

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

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

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

Los resultados del cálculo coinciden en dos formas distintas, lo que vuelve a convencer de la veracidad de las fórmulas obtenidas. Así, hemos obtenido la relación

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

donde K =

C_{n}^{2} .

$C_n^2.$

Démosle en la mesa. 4 números de relaciones asimétricas | AS | para valores pequeños de n.

Tabla 4. Número de BO asimétricos

Al tener una fórmula para determinar el número de relaciones asimétricas, se puede obtener otra, para calcular el número de relaciones antisimétricas, ya que la presencia o ausencia de puntos diagonales no cambia las propiedades de antisimetría de la relación.

Entonces, denotamos el conjunto de relaciones antisimétricas por el símbolo ANS, luego la cardinalidad de este conjunto estará determinada por la fórmula

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

donde K =

C_{n}^{2}

$C_n^2$

A continuación se muestra una tabla. 5 que contiene los valores (ANS) para n = 3 (1) 5.

Cuadro 5 . El número de BO antisimétricos

En lo que sigue, necesitamos conceptos que sea conveniente introducir aquí.

La parte simétrica de la relación binaria α se llama (y se denota

α^{(S)}

$α^{(S)}$ ) actitud

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

$α^{(S)} =α∩α^{-1}$ y la proporción

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

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

α^{(а)}

$α^{()}$ ) se llama parte asimétrica. En el caso particular cuando la relación α es simétrica,

α^{(S)} = α

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

α^{(S)}

$α^{(S)}$ siempre simétrico; si α es asimétrico, entonces

α^{(а)} = α

$α^{()}= α$ y

α^{(а)}

$α^{()}$ siempre asimétrico.

Transitividad (latín Transitivus - transicional, de transitus - transición)

- una de las propiedades de las relaciones. Una relación = <M, A> definida en el conjunto A es transitiva si para cualquier

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

$_i, _ j, _k є A$ la condición está satisfecha: desde

а_{i} α а_{j}

$_iα _ j$ y

а_{j} α а_{k}

$_jα _k$ debería

а_{i} α а_{k}

$_iα _ k$ ...

En otras palabras, para una relación transitiva a partir de la presencia de elementos en su composición (

а_{i} α а_{k}

$_iα _ k$ ) y (

а_{k} α а_{j}

$_kα _ j$ ) se sigue que contiene el elemento (

а_{i} α а_{j}

$_iα _ j$ ). Para un gráfico de relación, esta propiedad significa que si un par de vértices (

а_{i} α а_{j}

$_iα _ j$ ) está conectado por un camino orientado que pasa por el vértice k y está formado por 2 arcos consecutivos (

а_{i} α а_{k}

$_iα _ k$ ), (

а_{k} α а_{j}

$_kα _ j$ ), entonces los mismos vértices están conectados directamente por un solo arco (

а_{i} α а_{j}

$_iα _ j$ ). Para elementos de matriz [

а_{i j}

$_{ij}$ ] de una relación transitiva α de

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

$_{ik}·_{kj} =1$ debería

а_{i j} = 1

$_{ij} = 1$ ...

La definición de la propiedad de transitividad para relaciones binarias asume que la relación contiene al menos tres elementos (pares ordenados). ¿Y cómo se manifiesta esta propiedad en una relación de un elemento, vacía o que contiene solo dos elementos?

Todas las relaciones vacías y singleton son transitivas. Una relación de dos elementos puede ser transitiva y no transitiva si los pares incluidos en ella contienen un elemento común j. Los arcos del gráfico correspondientes a pares ordenados se dirigen en una dirección (forman una ruta orientada de no transitividad).

Por ejemplo, deje (

а_{i}, а_{j}

$_i, _ j$ ) є α y (

а_{j}, а_{k}

$_j, _ k$ ) є α. La definición formulada requiere: para que la relación α sea transitiva, debe tener un tercer par (arco), a saber, (

а_{i}, а_{k}

$_i, _ k$ ), pero como no existe, no se satisface la propiedad de transitividad para α.

Si, como antes, la relación contiene solo dos pares con un elemento común

а_{j} є A

$_j є A$ , pero tal que el elemento común

а_{j} є A

$_j є A$ está en la misma posición en ambos pares (

а_{j}, а_{i}

$_j, _ i$ ), (

а_{j}, а_{k}

$_j, _ k$ ) o (

а_{i}, а_{j}

$_i, _ j$ ),

(

а_{k}, а_{j}

$_k, _ j$ ), y los arcos del gráfico se dirigen en diferentes direcciones, entonces dicha relación es transitiva, ya que no se requiere la inclusión del tercer par en la relación.

También habrá una relación transitiva en el caso de que dos pares no tengan elementos comunes. Ejemplos de relaciones transitivas son: "igualdad" (=), ya que i = k, k = j implica i = j; "Yo es mayor que j"; en geometría - "paralelismo de líneas rectas". Ejemplos de relaciones no transitivas: "perpendicularidad de líneas rectas" en geometría; "Yo no es igual a j".

En la literatura sobre relaciones se pueden encontrar varios conceptos que caracterizan la transitividad: transitividad débil, transitividad fuerte, transitividad negativa, anti-transitividad, anti-transitividad débil, transitividad generalizada, cierre transitivo.y algunos otros. Se intenta aquí sistematizar los distintos matices de manifestación de la propiedad de la transitividad en las relaciones.

Para una relación transitiva α, la relación

α^{- 1}

$α^{–1}$ también es siempre transitivo. La intersección de un número arbitrario de relaciones transitivas es una relación transitiva. Si consideramos la relación ᾰ, que es la intersección de todas las relaciones transitivas que contienen la relación α, entonces ᾰ se denomina cierre transitivo de la relación α.

El cierre transitivo ᾰ se puede construir para cualquier relación α de acuerdo con la regla de

а_{i} ᾰ а_{j}

$_i ᾰ _j$ sigue:

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

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

La relación ᾰ es la relación transitiva más pequeña que contiene α. Si α es transitivo, entonces coincide con su cierre transitivo α = ᾰ y viceversa.

Cuando se representa una relación binaria transitiva mediante un gráfico dirigido, es posible representar no todo el dígrafo, sino solo su esqueleto transitivo, es decir, Los arcos que conectan el principio y el final de cada ruta de más de uno no se dibujan. En este caso, decimos que el esqueleto transitivo del gráfico se toma para la relación α . Esta operación es esencialmente la inversa de la operación de cierre transitivo , en la que el principio y el final de cada red están conectados por un arco.

En el caso general, la propiedad de transitividad no se satisface con respecto a la operación de relaciones de combinación. Combinando dos relaciones transitivas

α_{1}

$α_1$ y

α_{2}

$α_2$ es transitivo si y solo si uno de ellos es transitivo con respecto al otro. Por un par de relaciones binarias

α_{1}

$α_1$ y

α_{2}

$α_2$ se puede considerar la transitividad de uno de ellos en relación con el otro.

Entonces

α_{1}

$α_1$ es transitivo con respecto a

α_{2}

$α_2$ en las siguientes condiciones:

1) de

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

$( _i, _k) є α_1 ( _k, _j) є α_2$ debería

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

$(_i, _j) є _1$ ;

2) de

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

$( _i, _k) є α_2 ( _k, _j) є α_1$ debería

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

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

En el caso cuando

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

$α_1= α_2=α$ La transitividad relativa es la transitividad habitual.

Se conoce la siguiente afirmación sobre las propiedades de transitividad, simetría y asimetría de una relación. Si una relación binaria es transitiva, entonces su parte simétrica

α^{(S)}

$α^{(S)}$ y

α^{(а)}

$α^{()}$ la parte asimétrica también es transitiva.

Lo contrario es cierto solo si

α^{(S)}

$α^{(S)}$ ,

α^{(а)}

$α^{()}$ transitivo y

α^{(а)}

$α^{()}$ transitivamente relativo

α^{(S)}

$α^{(S)}$ ... En general, de la transitividad

α^{(S)}

$α^{(S)}$ y

α^{(а)}

$α^{()}$ la transitividad de α no sigue.

La composición de la relación transitiva α consigo misma satisface la relación α · α ⊆ α. Una relación α es negativamente transitiva (no transitiva) si su complemento es transitivo, es decir ᾱ. En la matriz de tal relación [

α_{i j}

$α_{ij}$ ] desde

α_{i k} = 0

$α_{ik} = 0$ y

α_{k j} = 0

$α_{kj} = 0$ debería

α_{i j} = 0

$α_{ij} = 0$ ... La transitividad negativa de α no excluye el hecho de que α en sí mismo también puede ser transitivo.

En este caso, se dice que α es una relación fuertemente transitiva . Elementos de la matriz [

α_{i j}

$α_{ij}$ ] tal actitud se caracteriza por el hecho de que

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

$_{ik}·_{kj} =1$ debería

а_{i j} = 1

$_{ij} = 1$ , de

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

$_{ik} = _{kj} =0$ debería

а_{i j} = 0

$_{ij} = 0$ ...

Junto con las relaciones fuertemente transitivas, consideramos las relaciones débilmente transitivas (pseudotransitivas) , que incluyen aquellas relaciones donde las condiciones de

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

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

а_{К} α а_{j}

$_α_j$ debería

а_{i} α а_{j}

$_iα_j$ ... Su transitividad se deriva de la asimetría y la transitividad negativa.

Una relación α es transitivamente completa si para cualquier δ de

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

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

comparabilidad sigue

а_{K 1}

$_{K1}$ y

а_{K δ}

$_{Kδ}$ , es decir se realizan ya sea

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

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

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

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

Ciclicidad

Las relaciones definidas en el conjunto A pueden verse desde el punto de vista de la presencia de ciclos en ellas. Es conveniente realizar tal consideración en gráficos de relaciones. Un gráfico de relación cíclica siempre contiene al menos un contorno cerrado (ruta). Ignorar las flechas convierte el camino en un bucle. Un gráfico de una relación acíclica no contiene ciclos y se llama acíclico o incontrolado .

La relación = <Å, A> es cíclica si al menos una cadena de la forma puede formarse a partir de los elementos del conjunto A

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

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_{Kδ},_{Kδ}α_{Ki}$ longitud arbitraria δ. El gráfico M del cierre transitivo para una relación cíclica contiene al menos un par (

а_{i}, а_{i}

$_i, _i$ ), y para una relación acíclica α no contiene ninguno de esos pares.

La relación = <, A> es acíclica si para cualquier δ≥1 la condición de

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

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

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

$_i ≠ _j$ ... En la matriz [

α_{i j}

$α_{ij}$ ] relación acíclica de

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

$_{iK1}_{K1K2}..._{K(δ-1)j}=1$ i ≠ j sigue. La relación acíclica es siempre asimétrica, pero lo contrario no es cierto. En otras palabras, si algunos picos

а_{i}

$_i$ y

а_{j}

$_j$ Las relaciones acíclicas del gráfico α están conectadas por medio; entonces no hay arco en el gráfico (

а_{j}, а_{i}

$_j, _i$ ). Los torneos transitivos

son ejemplos clásicos de gráficos con esta propiedad . Los vértices de tales gráficos se pueden volver a numerar, bajo los cuales para cualquier arco (

а_{i}, а_{j}

$_i, _j$ ) el número del vértice j es mayor que el del vértice i.

Si α es una relación binaria transitiva antirreflexiva, entonces es acíclica. La aciclicidad y completitud transitiva de la relación implica su transitividad.

Lo completo

Propiedad de completitud (perfección, linealidad). Todo el conjunto de relaciones se divide en incompletas y completas , entre las que, a su vez, destacan las fuertemente completas. Ilustraremos la propiedad de completitud de las relaciones considerando gráficas de relaciones.

La gráfica de una relación completa está completa, es decir dos de sus vértices están conectados directamente por al menos un arco, es decir son adyacentes. Dado que cada arco en el gráfico corresponde a un punto (elemento, par) del gráfico de la relación, entonces, sobre la base de lo anterior, se puede formular una definición.

La relación = <Å, A> es completa (perfecta, lineal) si y solo si todos los elementos del conjunto A son comparables o iguales entre sí. Por tanto, la actitud general es reflexiva. En otras palabras, para dos elementos cualesquiera

а_{i}

$_i$ y

а_{j}

$_j$ justa

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

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

Si en relación α hay al menos un par

а_{i}

$_i$ ,

а_{j}

$_j$ elementos incomparables y desiguales, entonces tal relación es incompleta. Para cualquier razón total α,

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

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

а_{i} ᾱ а_{j}

$_i ᾱ _j$ debería

а_{j} α а_{i}

$_j α _i$ ... La relación binaria α es completa si y solo si

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

$^{(a)} =^{(d)}$ , es decir cuando su parte asimétrica coincide con la relación dual (ítem 9) .

Una relación binaria α está muy completa cuando su gráfica coincide con A × A. Una gráfica de tal relación es una gráfica completa, en la que cada par de vértices está conectado por una arista y cada vértice tiene un bucle. Este gráfico se denomina gráfico muy completo. La razón total α siempre satisface las relaciones

ᾱ \subset α^{- 1}

$ᾱ ⊂ α^{-1}$ y

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

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

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

$α∪(ᾱ∩α^{d}) = α∪(ᾱ)^{(S)}$ siempre lleno.

Si

α_{1}

$α_1$ y

α_{2}

$α_2$ relación completa, entonces

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

$α_1·α_2$ completo. En la matriz [

α_{i j}

$α_{ij}$ ] relación completa

α_{i j} = 1

$α_{ij} = 1$ o

α_{j i} = 1

$α_{ji} = 1$ para cualquier i, j, o ambas igualdades son verdaderas. Una relación α es débilmente completa (débilmente conectada) si por alguna

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

$_i,_j є A$ tal que

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

$_i ≠ _j$ o

а_{i} α а_{j}

$_i α _j$ o

а_{j} α а_{i}

$_j α _i$ ...

En la matriz [

α_{i j}

$α_{ij}$ ] de una relación débilmente completa para cualquier i ≠ j, o

α_{i j} = 1

$α_{ij} = 1$ o

α_{j i} = 1

$α_{ji} = 1$ , o ambas igualdades son verdaderas. Una relación α es transitivamente completa si, para un n arbitrario de

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

$_iα_{K1}, _{K1}α_{K2},…, _{K(n-1)}α_{in}$ sigue la comparabilidad

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

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

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

$_{i1}α _{in}$ o

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

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

Cuentemos el número de relaciones completas. Primero, considere el problema de la línea. Una línea en una matriz de razón es un segmento de línea recta perpendicular a la diagonal principal de la matriz de razón, que conecta los centros de dos celdas (celdas) de la matriz ubicadas simétricamente con respecto a esta diagonal.

Si dos o más pares de posiciones simétricas caen en una línea (línea recta) en la matriz de razones, entonces el número de líneas, no obstante, permanece igual al número de dichos pares de posiciones. El número total de pares de posiciones para una n arbitraria se define como

C_{n}^{2} = L

$C_n^2 = L$ ...

Entonces, en la matriz para una relación arbitraria sobre el conjunto A, hay un conjunto L de segmentos paralelos (líneas). Designemos las posiciones finales de los segmentos (líneas) con los símbolos L - izquierda y P - derecha. También disponible | L | fichas que se pueden colocar en posiciones al final de las líneas. El desafío es determinar el número de formas en que sería posible organizar | L | chips para que haya al menos un chip en cada línea.

Está claro que el problema puede reducirse a determinar el número F de asignaciones f: L → π del conjunto L de líneas en el conjunto de posiciones π (n = {A, P}). Se sabe que el número de tales asignaciones está determinado por la fórmula

F = | п |^{| L |}

$F = ||^{|L|}$ ... Un mapeo específico (imagen) puede tener la forma <P, P, L, L, L,…, L, P> de la secuencia de índices para | L | posiciones. El símbolo L corresponde a la posición debajo de la diagonal principal, y el símbolo P, que es simétrico sobre la diagonal.

De la definición de la razón total se deduce que su gráfico contiene al menos K puntos, K =

C_{n}^{2}

$C_n^2$ ubicado: de modo que todas las líneas estén ocupadas por al menos un chip. El número k de puntos en el gráfico, adicional al número mínimo requerido, puede pasar por el valor k = 0 (1) K =

C_{n}^{2}

$C_n^2$ ...

Para cada número fijo de k puntos, el conjunto de opciones de posiciones en las que se pueden colocar está determinado por el valor

C_{К}^{k}

$C_^k$ , donde K es el conjunto de posiciones desocupadas. Dado que k puntos adicionales llenan completamente k líneas, entonces, para garantizar la propiedad de integridad de la relación, queda llenar K - k posiciones con chips (puntos del conjunto del mínimo requerido), y el número de tales rellenos es

2^{К - k}

$2^{-k}$ ...

La elección de posiciones para k puntos adicionales y los métodos para llenar las líneas K-k con chips son independientes. Por lo tanto, el número total de posibilidades para colocar K + k puntos en 2 ∙ K posiciones de modo que todas las líneas estén ocupadas por al menos un punto está determinado por la expresión

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

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

Si sumamos esta expresión, obtenemos el número de relaciones completas, que no depende de la situación con la ubicación de los puntos diagonales. En otras palabras, es el número de relaciones completas parcialmente reflexivas, por ejemplo, antirreflectantes y totalmente reflexivas y completas, etc.

Ejemplo 5 . La variedad de situaciones para colocar puntos diagonales está determinada por el número

2^{n}

$2^n$ ... Entonces, la cardinalidad del conjunto de todas las relaciones completas para un n fijo está determinada por la fórmula

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

Para relaciones con tres propiedades requeridas

Para relaciones de equivalencia con tres propiedades requeridas. Hay un resultado notable: cada relación de equivalencia sobre un conjunto de n elementos está en correspondencia uno a uno con una partición de este conjunto. El número de tales relaciones está determinado por la fórmula

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

$B_n = ∑_{m=0}^nS(n, m)$ , donde S (n, m) es el número de Stirling del segundo tipo, Bn es el número de

Bell , o en forma recurrente

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

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

Para conjuntos ordenados (órdenes parciales), dichas fórmulas no están abiertas y su número se determina mediante cálculos directos, es decir, modelado. Para valores pequeños de n, los datos se muestran en la

Tabla 6 . Características cuantitativas de las relaciones binarias.

La Tabla 6. muestra: n = | A | - la cardinalidad del portador de set;

2^{n^{2}}

$2^{n^2}$ - el número de todas las relaciones binarias en el conjunto A;

| En (n) | - el número de clases de relaciones no isomórficas;

| (n) | - el número de relaciones de orden parcial;

| Gn (n) | - el número de clases son relaciones no isomórficas de orden parcial;

| Gl (n) | = n! - el número de relaciones de orden lineal.

Conclusión

En este trabajo se realizó un análisis detallado de las propiedades básicas y la estructura de la razón binaria, a partir del cual fue posible obtener características cuantitativas para BO con una o más propiedades. Se encuentran y se presentan las razones originales para el número de algunos tipos de relaciones con dos y tres propiedades requeridas. Estos resultados abren la posibilidad de modelar y estudiar BO y relaciones de mayor aridad.

Lista de literatura usada

Aigner M. Teoría combinatoria.- M .: Mir, 1982.
Birkhoff G. Teoría de estructuras. - M.: IL, 1952.-408 p.
Noden P., Kitte K. Algoritmos algebraicos. - M.: Mir, 1999. - 720 p.
Rybnikov K.A. Introducción al análisis combinatorio. -M.: Ed. Universidad Estatal de Moscú, 1972. -256s.
Stanley R. Combinatoria enumerativa. Vol. 1.- M.: Mir, 1990 .-- 440p.
Stanley R. Combinatoria enumerativa. T. 2.- M .: Mir, 2005. - 767s.
Shikhanovich Yu.A. Introducción a las matemáticas modernas. Conceptos iniciales.-M .: Nauka, 1965. - 376p.

Características cuantitativas de las relaciones.

Características cuantitativas de los tipos de relaciones binarias.

Reflexividad

Simetría

Transitividad (latín Transitivus - transicional, de transitus - transición)

Ciclicidad

Lo completo

Conclusión

Lista de literatura usada

More articles: