Este equipo redactor ha pasado horas buscando la solución a tus dudas, te regalamos la respuestas por eso deseamos serte de gran apoyo.
Solución:
Esta es una respuesta a tu segunda pregunta, sobre la relación $R=\langle 1,2rangle,langle 2,2rangle,langle 3,2rangle$. Podemos verificar la transitividad de varias maneras.
(1) Enumere todos los pares vinculados:
$$beginalign* &langle 1,2ranglelandlangle 2,2rangletag1\ &langle 2,2ranglelandlangle 2,2rangle etiqueta2\ &langle 3,2ranglelandlangle 2,2rangletag3 endalign*$$
Si $R$ debe ser transitivo, $(1)$ requiere que $langle 1,2rangle$ esté en $R$, $(2)$ requiere que $langle 2,2rangle$ esté en $ R$, y $(3)$ requiere que $langle 3,2rangle$ esté en $R$. Y dado que todos estos pares requeridos están en $R$, $R$ es efectivamente transitivo.
(2) Compruebe todos los posibles pares de puntos finales. Por ejemplo, para ver si se necesita $langle 1,3rangle$ para que $R$ sea transitivo, vea si hay un ‘peldaño’ de $1$ a $3$: ¿hay un $a$? tal que $langle 1,arangle$ y $langle a,3rangle$ están ambos en $R$? Si es así, la transitividad requerirá que $langle 1,3rangle$ también esté en $R$. Da la casualidad de que no existe tal $a$, por lo que la transitividad de $R$ no requiere que $langle 1,3rangle$ esté en $R$. Haz esta verificación para cada uno de los nueve pares ordenados en $1,2,3\times1,2,3$.
(3) Usa la matriz
$$M_R=beginbmatrix0&1&0\0&1&0\0&1&0endbmatrix$$
de la relacion Es posible que aún no hayas aprendido esto, pero así como $M_R$ te dice qué ‘rutas de un paso’ en $1,2,3$ están en $R$,
$$M_R^2=beginbmatrix0&1&0\0&1&0\0&1&0endbmatrixbeginbmatrix0&1&0\0&1&0\0&1&0endbmatrix=beginbmatrix0&1&0\0&1&0 \0&1&0endbmatriz$$
cuenta el número de caminos de $2$ pasos entre elementos de $1,2,3$. La entrada en la fila $i$, columna $j$ es el número de rutas de pasos de $2$ desde $i$ hasta $j$. (Por una ruta de paso de $2$ me refiero a algo como $langle 3,2ranglelandlangle 2,2rangle$: el primer par te lleva de $3$ a $2$, el segundo te lleva de $2$ a $2$, y los dos juntos te llevan de $3$ a $2$).
Para que $R$ sea transitivo, $langle i,jrangle$ debe estar en $R$ siempre que haya una ruta de $2$ pasos desde $i$ hasta $j$. Para esta relación, ese es ciertamente el caso: $M_R^2$ muestra que las únicas rutas de paso de $2$ son de $1$ a $2$, de $2$ a $2$, y de $3$ a $2$, y esos pares ya están en $R$.
En el problema original tienes la matriz
$$M_R=beginbmatrix1&0&1\0&1&0\1&0&1endbmatrix;,$$
y
$$M_R^2=beginbmatrix1&0&1\0&1&0\1&0&1endbmatrixbeginbmatrix1&0&1\0&1&0\1&0&1endbmatrix=beginbmatrix2&0&2\0&1&0 \2&0&2endbmatriz;.$$
Los $2$ indican que hay dos rutas de pasos de $2$ de $1$ a $1$, de $1$ a $3$, de $3$ a $1$ y de $3$ a $3$; solo hay una ruta de paso de $2$ de $2$ a $2$. De $1$ a $1$, por ejemplo, tiene $langle 1,1ranglelandlangle 1,1rangle$ y $langle 1,3ranglelandlangle 3,1rangle$ . Pero lo importante para la transitividad es que siempre que $M_R^2$ muestre al menos un camino de $2$ pasos, $M_R$ muestra que ya hay un camino de un paso y, por lo tanto, $R$ es transitivo.
En resumen, busque las entradas distintas de cero en $M_R^2$. Si $M_R$ ya tiene un $1$ en cada una de esas posiciones, $R$ es transitivo; si no, no lo es.
Tal vez podrías verlo así:
¿Cómo puede dejar de ser transitiva?
Solo puede dejar de ser transitiva si hay números enteros $a, b, c$ tales que (a,b) y (b,c) son pares ordenados para la relación, pero (a,c) no lo es. ¿Puedes demostrar que esto no puede suceder?
Esto me confundió por un tiempo, así que intentaré desglosarlo de una manera que tenga sentido para mí y probablemente no sea muy rigurosa.
La transitividad en un conjunto de pares ordenados (la matriz que tiene allí) dice que si $(a,b)$ está en el conjunto y $(b,c)$ está en el conjunto, entonces $(a,c)$ tiene que ser.
Así que hacemos una matriz que nos diga si un par ordenado está en el conjunto, digamos que los elementos son $a,b,c$ y luego usaremos un $1$ para marcar un par que está en el conjunto y $0$ para todo lo demás. Digamos que sabemos que $(a,b)$ y $(b,c)$ están en el conjunto. La transitividad depende de si $(a,c)$ está en el conjunto:
$$ beginbmatrix (a,a) & (a,b) & (a,c) \ (b,a) & (b,b) & (b,c) \ (c,a) & (c,b) & (c,c) \ endbmatrix rightarrow beginbmatrix 0 & 1 & ? \ 0 & 0 & 1 \ 0 & 0 & 0 \ endbmatriz $$
Creo que la respuesta de otros carteles sobre elevar al cuadrado la matriz es la forma algorítmica de responder esa pregunta.