Relaciones (Binarias) - Composición

Question

Deje $R = \{(a,b), (b,c), (c,d)\}$

¿Cómo puedo averiguar por qué las $R^{2} = \{(a,c), (b,d)\}$? De este hay una prueba matemática (o fórmula) para determinar el mayor conjunto de las relaciones? Es siempre el primer miembro de la primera par ordenado con el segundo miembro de la segunda par ordenado, seguido por el primer miembro de la segunda par ordenado con el segundo miembro de la tercera par ordenado, y así sucesivamente?

Y como para $R^{3} = \{(a,d)\}$ es siempre el primer miembro de la primera par ordenado a la segunda persona de la tercera par ordenado, y así sucesivamente?

Answer 1

No, usted no puede hacer las cosas exactamente de esa manera. No es "siempre el primer miembro de la primera par ordenado con el segundo miembro de la segunda par ordenado, seguido por el primer miembro de la segunda par ordenado con el segundo miembro de la tercera par ordenado, y así sucesivamente", y no a las otras preguntas. En verdad, establece, en general, no tienen ese "orden" o "secuenciación", de modo que usted no puede legítimamente decir el "primer par ordenado" o el "enésimo par ordenado". Dicho esto, usted puede tener un primer miembro de un par ordenado.

Como correctamente implícita por Andre Nicolas desea buscar todos los "media" de los términos. Usted puede "componer" dos pares ordenados si y sólo si el segundo término de una pareja es el mismo plazo que el primer término de la otra pareja B. El resultado "composición" consiste en que el primer miembro de Una, y el segundo miembro de B. E. G. Dicen que usted tiene A={(a, a)}. Así, a=a, por lo que Un$^{2}$={(a, a)}, ya que el segundo miembro de (a, a) es igual al primer miembro de (un, una). Si usted tiene B={(a, b), (b, a)}, entonces estamos en la B$^{2}$={(a, a), (b, b)}, ya que el segundo miembro de (a, b) es igual al primer miembro (b, a) nos da (a, a), y el segundo miembro de (b, a) es igual al primer miembro de (a, b).

Como otra manera de pensar, decir que usted toma todos los pares ordenados como (x, y), y reescribirlos con el primer miembro de primero, seguido por una flecha y, a continuación, el segundo miembro. Así que para (x, y), escribiremos x->y. Si podemos "componer" dos pares ordenados (a, b), (c, d) en esta notación, entonces tenemos a->b y c>d. Así, si b=c, en lugar de escribir a->b y c>d, ya que c va a "tomar" d de todos modos, se puede ir directamente allí y escribir a->d. Si c no es igual a d, entonces no podemos "componer" nada aquí, ya que no existe ningún punto común de contacto, por así decirlo.

Como otros han señalado, no existe otra manera de hacer esto, pero dudo de que lo estamos buscando.

Answer 2

Su undersanding del proceso es exacta. El par $(x,y)$ $R^2$ si hay un $z$ tal que $(x,z)$ $(z,y)$ están en $R$. Así que la búsqueda de todos los casos en que la segunda de las "coordenadas" de un par ordenado es igual a la primera coordenada de otro. Así, por ejemplo, si $(a,d)$ es en la relación $R$, e $(d,w)$ es en la relación $R$,$(a,w)$$R^2$.

No hay otra manera de hacerlo que parece más "matemática" sino que equivale a la misma cosa. Sin embargo, hacerlo de manera que voy a describir no es agradable para los seres humanos. (Equipos de amor.)

En nuestra situación, tenemos $4$ objetos, es decir,$a$, $b$, $c$ y $d$. En su lugar, vamos a llamarlos $a_1$, $a_2$, $a_3$, y $a_4$. Hacer una $4\times 4$ matriz de la siguiente manera.

En la posición donde el $i$-ésima fila y $j$-ésima columna de cumplir, poner un $1$ si $R(a_i,a_j)$ $0$ lo contrario. Esto se llama la matriz de adyacencia de la relación $R$ (el lenguaje viene de la teoría de gráficos).

La plaza de la matriz de adyacencia. Si en el cuadrado de la matriz, hay un $0$ cuando la $i$-ésima fila y la $j$-ésima columna de cumplir, entonces la relación $R^2$ no se cumple para $(a_i,a_j)$. Si el $i$-ésima fila y $j$-ésima columna de cumplir, hay un número de $\ne 0$, entonces la relación $R^2$ mantiene para $(a_i,a_j)$. El número de medidas de la cantidad de $w$ tal que $(a_i,w)$ $(w,a_j)$ están en $R$ o más geométricamente el número de $2$-paso de "rutas" de$a_i$$a_j$.

Comentario: La misma idea funciona para las relaciones en cualquier conjunto finito, y por $R^n$ (acaba de tomar la $n$-ésima potencia de la matriz de adyacencia, más fácil de decir que de hacer).

Más en general, supongamos que se tienen dos relaciones de $R$ $S$ sobre un conjunto. Podemos definir a la $RS$ en una manera análoga a la definición de $R^2$. Y nos encontramos con $RS$ multiplicando las matrices de adyacencia de $R$$S$, y al pasar por el mismo proceso que hicimos para $R^2$.

La matriz de adyacencia puede ser una herramienta poderosa. Para que podemos utilizar la matriz teórica de las ideas, como valores propios, para obtener información útil acerca de la $R$.