Sea R que una relación en conjunto A. prueba que $R^2 \subseteq R <=>$ R es transitiva $<=> R^i \subseteq R ,\forall i \geq 1$

Question

esta es mi primera pregunta aquí. Estoy todavía relativamente nuevo en el más avanzado matemáticas y no tengo mucha experiencia con las pruebas todavía. Soy auto-estudio en el momento y por lo tanto no tienen a nadie para comprobar si mis pruebas son válidos. Espero que las matemáticas.stackexchange me puede ayudar a ser mejores en la escritura de las pruebas.

Actualmente estoy leyendo "Cómo probarlo" por Velleman y han estado trabajando a través de la sección de relaciones. Ahora he encontrado una declaración en algún lugar que yo quiero probar, pero estoy no se si lo he venido para arriba con es razonable y yo también tiene algunas preguntas sobre la lógica que se utiliza en este tipo de pruebas.

El teorema es: Vamos a $R$ ser una relación en el set $A$. Entonces se cumple que: $R^{2}\subseteq R\iff R\text{ is transitive}\iff R^{i}\subseteq R,\forall i\geq1$.

Voy a empezar con $R^{2}\subseteq R\iff R\text{ is transitive}$:

$\Rightarrow$ Asume que $R^{2}\subseteq R$. Aquí $xR^{2}z$ significa que $xRy\wedge yRz$ algunos $y\in A$. El objetivo es mostrar que $R$ es transitiva, que es básicamente una instrucción condicional: si $xRy$ $yRz$ espera, entonces puedo deducir que $xRz$. Por Lo Tanto Yo puede asumir $xRy$$yRz$, y ahora debe demostrar que $xRz$. Pero debido a $R^{2}\subseteq R$, sé que $xRy$ $yRz$ es cierto para una arbitraria $(x,z)\in A$. De ello se desprende que $(x,z)\in R$.

$\Leftarrow$ Asume que $R$ es transitiva. Por lo tanto, si por cualquier $(x,z)\in A$ es cierto que hay un $y\in A$ tal que $xRy$ y $yRz$, sé que $xRz$. Ahora desde $R^{2}\subseteq R$ una sentencia condicional de la forma $\forall(x,y)\in A\times A\;(x,y)\in R^{2}\Rightarrow(x,y)\in R$. Puedo asumir que hay un par ordenado, llame a $(x,z)\in R^{2}$. Ya hemos asumido que $R$ es transitiva, se sigue por modus ponens que $(x,z)\in R$.

Ahora voy a tratar de probar: $R\text{ is transitive}\iff R^{i}\subseteq R\forall i\geq1$.

$\Rightarrow$Asumen $R$ es transitiva. Para demostrar que $R^{i}\subseteq R,\forall i\geq1$ Puedo usar la inducción supongo?!

Caso Base: $i=1\Rightarrow R\subseteq R$ obviamente tiene.

Ahora no estoy muy seguro de si, de hecho tengo el uso de la inducción de aquí. Creo que lo que debe ser mostrado aquí es bastante sencillo. Si hay un $y\in A$ tal que $x1Ry$ $yRx2$ celebrar, entonces, porque $R$ es transitiva de ello se sigue que $x1Rx2$. Y entonces usted puede seguir de esta manera con $x2$ $x3$ y en general cualquier valor de $i$. Pero Yo realmente no sé cómo escribir esto de una manera formalmente correcta. Puede alguien me ayuda con eso? Y por favor dar información sobre la primera parte de la prueba.

Answer 1

Se ve bastante bien, pero sugiero que unos retoques.

En la prueba de la implicación primera, supongamos que $\langle x,y\rangle,\langle y,z\rangle\in R.$ por definición, $\langle x,z\rangle\in R^2,$ y por supuesto, $\langle x,z\rangle\in R.$ mostrando lo contrario se realiza del mismo modo, mucho más brevemente que su enfoque.

En este punto, realmente sería más fácil demostrar $$R^i\subseteq R\:\forall i\ge 1\iff R^2\subseteq R.$$ One of these implications is trivial. For the other, the $i=1$ case is readily true for any relation, and supposing that $R^i\subseteq R$ for some $i\ge 1,$ we can show readily that $$R^{i+1}=R^i\circ R\subseteq R\circ R=R^2,$$ and so $R^{i+1}\subseteq R$ por definición, acabado el paso de inducción.