Solución:
Esta es una respuesta a su segunda pregunta, sobre la relación $ R = { langle 1,2 rangle, langle 2,2 rangle, langle 3,2 rangle } $. Podemos comprobar la transitividad de varias formas.
(1) Enumere todos los pares vinculados:
$$ begin {align *} & langle 1,2 rangle land langle 2,2 rangle tag {1} \ & langle 2,2 rangle land langle 2,2 rangle etiqueta {2} \ & langle 3,2 rangle land langle 2,2 rangle etiqueta {3} end {align *} $$
Si $ R $ va a ser transitivo, $ (1) $ requiere que $ langle 1,2 rangle $ esté en $ R $, $ (2) $ requiere que $ langle 2,2 rangle $ esté en $ R $, y $ (3) $ requieren que $ langle 3,2 rangle $ esté en $ R $. Y dado que todos estos pares requeridos están en $ R $, $ R $ es de hecho transitivo.
(2) Compruebe todos los pares posibles de puntos finales. Por ejemplo, para ver si se necesita $ langle 1,3 rangle $ para que $ R $ sea transitivo, vea si hay un ‘trampolín’ de $ 1 $ a $ 3 $: ¿hay un $ a $ tal que $ langle 1, a rangle $ y $ langle a, 3 rangle $ estén ambos en $ R $? Si es así, la transitividad requerirá que $ langle 1,3 rangle $ 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,3 rangle $ esté en $ R $. Haga esta verificación para cada uno de los nueve pares ordenados en $ {1,2,3 } times {1,2,3 } $.
(3) Utilice la matriz
$$ M_R = begin {bmatrix} 0 & 1 & 0 \ 0 & 1 & 0 \ 0 & 1 & 0 end {bmatrix} $$
de la relación. Es posible que aún no haya aprendido esto, pero así como $ M_R $ le dice qué ‘rutas de un paso’ en $ {1,2,3 } $ están en $ R $,
$$ M_R ^ 2 = begin {bmatrix} 0 & 1 & 0 \ 0 & 1 & 0 \ 0 & 1 & 0 end {bmatrix} begin {bmatrix} 0 & 1 & 0 \ 0 & 1 & 0 \ 0 & 1 & 0 end {bmatrix} = begin {bmatrix} 0 & 1 & 0 \ 0 & 1 \ 0 & 1 & 0 end {bmatrix} $$
cuenta el número de rutas de pasos de $ 2 $ 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 $ a $ j $. (Por una ruta de pasos de $ 2 $ me refiero a algo como $ langle 3,2 rangle land langle 2,2 rangle $: 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, j rangle $ debe estar en $ R $ siempre que haya una ruta de $ 2 $ de $ i $ a $ j $. Para esta relación, ese es ciertamente el caso: $ M_R ^ 2 $ muestra que las únicas rutas de pasos de $ 2 $ son de $ 1 $ a $ 2 $, de $ 2 $ a $ 2 $, y de $ 3 $ a $ 2 $, y esos pares ya son en $ R $.
En el problema original tienes la matriz
$$ M_R = begin {bmatrix} 1 & 0 & 1 \ 0 & 1 & 0 \ 1 & 0 & 1 end {bmatrix} ;, $$
y
$$ M_R ^ 2 = begin {bmatrix} 1 & 0 & 1 \ 0 & 1 & 0 \ 1 & 0 & 1 end {bmatrix} begin {bmatrix} 1 & 0 & 1 \ 0 & 1 & 0 \ 1 & 0 & 1 end {bmatrix} = begin {bmatrix} 2 & 0 & 2 & 2 \ 0 & 1 \ 2 & 0 & 2 end {bmatrix} ;. $$
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 $ desde $ 2 $ a $ 2 $. De $ 1 $ a $ 1 $, por ejemplo, tiene $ langle 1,1 rangle land langle 1,1 rangle $ y $ langle 1,3 rangle land langle 3,1 rangle $ . Pero lo importante para la transitividad es que siempre que $ M_R ^ 2 $ muestra al menos una ruta de $ 2 $ -step, $ M_R $ muestra que ya hay una ruta de un paso y, por lo tanto, $ R $ es transitiva.
En resumen, encuentre 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.
Quizás podrías verlo así:
¿Cómo puede dejar de ser transitivo?
Solo puede fallar en ser transitivo 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. ¿Puede 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.
Entonces hacemos una matriz que nos dice si un par ordenado está en el conjunto, digamos que los elementos son $ {a, b, c } $, luego usaremos $ 1 $ para marcar un par que está en el conjunto y $ 0 $ por 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:
$$ begin {bmatrix} (a, a) & (a, b) & (a, c) \ (b, a) & (b, b) & (b, c) \ (c, a) & (c, b) & (c, c) \ end {bmatrix} rightarrow begin {bmatrix} 0 & 1 &? \ 0 & 0 & 1 \ 0 & 0 & 0 \ end {bmatrix} $$
Creo que la respuesta de otros carteles sobre la cuadratura de la matriz es la forma algorítmica de responder a esa pregunta.