A A. Si, para algún i y j, (a[i], a[j]) R y (a[j], a[i]) R, entonces R no es simétrica. En caso contrario, R es simétrica. La comprobación de si...

A A. Si, para algún i y j, (a[i], a[j]) R y (a[j], a[i]) R, entonces R no es simétrica. En caso contrario, R es simétrica. La comprobación de si R es transitiva se puede hacer con un bucle triplemente anidado que examina a su vez cada tripleta (a[i], a[j], a[k]) de A A A. Si, para alguna tripleta, (a[i], a[j]) R, (a[j], a[k]) R y (a[i], a[k]) R entonces, R no es transitiva. De lo contrario, R es transitiva. En los ejercicios de esta sección, deberá formalizar estos algoritmos. Propiedades de las relaciones sobre conjuntos infinitos Suponga una relación R que se define en un conjunto infinito A. Para demostrar que la relación es reflexiva, simétrica o transitiva, primero escriba lo que quiere demostrar. Por ejemplo, para la simetría necesita demostrar que x, y A, si x R y entonces y R x. Después, utilice las definiciones de A y R al reescribir el enunciado para el caso particular de que se trate. Por ejemplo, para la relación de “igualdad” en el conjunto de números reales, el enunciado reescrito es x, y R, si x y entonces y x. A veces la veracidad del enunciado reescrito será inmediatamente evidente (como aquí). Otras veces necesitará demostrarla usando el método de la generalización de lo particular a lo general. Damos ejemplos de ambos casos en esta sección. Empezamos con la relación de igualdad, una de las relaciones más simples y aún más importantes. Ejemplo 8.2.2 Propiedades de igualdad Se define una relación R en R (el conjunto de todos los números reales) como sigue: Para todos los números reales x y y. x R y x y. a. ¿R es reflexiva? b. ¿R es simétrica? c. ¿R es transitiva? Solución a. R es reflexiva: R es reflexiva si y sólo si, el siguiente enunciado es verdadero: Para toda x R, x R x. Puesto que x R x esto significa que x x, esto es lo mismo que decir Para toda x R, x x. Pero este enunciado es verdadero; cada número real es igual a sí mismo. b. R es simétrica: R es simétrica si y sólo si, el siguiente enunciado es verdadero: Para todas x, y R, si x R y, entonces y R x. Por definición de R, x R y significa que x y y y R x significa que y x. Por tanto R es simétrica si y sólo si, Para toda x, y R, si x y, entonces y x. Pero este enunciado es verdadero; si un número es igual a un segundo entonces, el segundo es igual al primero. c. R es transitiva: R es transitiva si y sólo si, el siguiente enunciado es verdadero: Para toda x, y, z R, si x R y y y R z, entonces x R z. Por definición de R, x R y significa que x y, y R z significa que y z y x R z significa que x z. Por tanto, R es transitiva si y sólo si, el siguiente enunciado es verdadero: Para toda x, y, z R, si x y y y z entonces x z. Pero este enunciado es seguramente verdadero: Si un número real es igual a un segundo y el segundo es igual a un tercero, entonces, el primero es igual al tercero. Ejemplo 8.23 Propiedades de “menor que” Se define una relación R sobre R (el conjunto de todos los números reales) como sigue: Para toda x, y R, x R y x y. a. ¿Es R reflexiva? b. ¿Es R simétrica? c. ¿Es R transitiva? Solución a. R no es reflexiva: R es reflexiva si y sólo si, x R, x R x. Por definición de R, esto significa que x R, x x. Pero esto es falso: x R tal que x x. Como un contraejemplo, sea x 0 y observe que 0 0. Por tanto, R no es reflexiva. b. R no es simétrica: R es simétrica si y sólo si, x, y R, si x R y entonces y R x. Por definición de R, esto significa que x, y R, si x y entonces y x. Pero esto es falso: x, y R tal que x y y y x. Como un contraejemplo, sea x 0 y y 1 y observe que 0 1 pero 1 0. Por tanto R no es simétrica. c. R es transitiva: R es transitiva si y sólo si, para toda x, y, z R, si x R y y y R z entonces x R z. Por definición de R, esto significa que para toda x, y, z R, si x y y y z, entonces x z. Pero este enunciado es verdadero por la ley transitiva del orden de los números reales (apéndice A, T18). Por tanto R es transitiva. A veces una propiedad es “universalmente falsa” en el sentido de que es falso para cada elemento de su dominio. Por supuesto, se deduce inmediatamente, que la propiedad es falsa para cada elemento en particular del dominio y por tanto abundan contraejemplos. En tal caso, puede parecer más natural demostrar la falsedad universal de la propiedad, en lugar de dar un único contraejemplo. Por ejemplo, en el caso anterior, le puede resultar natural responder a (a) y a (b) como sigue: Respuesta alternativa a (a): R no es reflexiva ya que x x para todos los números reales x (por la ley de la tricotomía: apéndice A, T17). Respuesta alternativa a (b): R no simétrica ya que para toda x y y en A, si x y entonces y x (por ley de la tricotomía). Ejemplo 8.2.4 Propiedades de congruencia módulo 3 Se define una relación T sobre Z (el conjunto de todos los enteros) como sigue: Para todos los enteros m y n, m T n 3 (m ฀ n). Esta relación se llama congruencia módulo 3. a. ¿T es reflexiva? b. ¿T es simétrica? c. ¿T es transitiva? Solución a. T es reflexiva: Para demostrar que T es reflexiva, es necesario demostrar que Para toda m Z, m T m. Por definición de T, esto significa que Para toda m Z, 3 (m ฀ m). O, puesto que m ฀ m 0, Para toda m Z, 3 0. Pero esto es verdadero: 3 0 ya que 0 3 0. Por tanto T es reflexiva. Este razonamiento se formaliza en la demostración siguiente. Demostración de reflexividad: Suponga que m es un entero particular arbitra- riamente elegido. [Debemos demostrar que m T m.] Ahora m ฀ m 0. Pero 3 0 ya que 0 3 0. Por tanto 3 (m ฀ m). Por tanto, por definición de T, m T m [como se quería demostrar]. b. T es simétrica: Para demostrar que T es simétrica, es necesario demostrar que Para todas m, n Z, si m T n entonces n T m. Por definición de T esto significa que Para todas m, n Z, si 3 (m ฀ n) entonces 3 (n ฀ m). ¿Es esto verdadero? Suponga que m y n son enteros particulares arbitrariamente elegidos tal que 3 (m ฀ n). ¿Se debe deducir que 3 (n ฀ m)? [En otras palabras, ¿podemos encontrar un entero tal que n ฀ m 3 (ese número entero)?] Por definición de “divide”, ya que 3 (m ฀ n) entonces m ฀ n 3k. La observación crucial es que n ฀ m ฀(m ฀ n). Por tanto, puede multiplicar ambos lados de esta ecuación por ฀1 para obtener ฀(m ฀ n) ฀3k que es equivalente a n ฀ m 3(฀k). [Así nos hemos encontrado un número entero, a saber: ฀k, tal que n ฀ m 3 (ese número entero).] Puesto que ฀k es un entero, esta ecuación demuestra que 3 (n ฀ m) De lo que se tiene que T es simétrica. El razonamiento anterior se formaliza en la demostración siguiente.