una partición y sea R la relación inducida por la partición. Entonces R es reflexiva, simétrica y transitiva. Demostración: Suponga que A es un c...

una partición y sea R la relación inducida por la partición.
Entonces R es reflexiva, simétrica y transitiva.
Demostración:
Suponga que A es un conjunto con una partición. Para simplificar la notación, supon-gamos que la partición se compone de un número finito de conjuntos. La demostración
para una partición infinita es idéntica a la excepción de la notación. Denote la partición
de los subconjuntos por
A1, A2, . . . , An.
Entonces Ai Aj siempre que i = j y A1 A2 . . . An A. La relación inducida
R por la partición se define como sigue: Para todos x, y A,
x R y Hay un conjunto Ai de la partición
tal que x Ai y y Ai.
[Idea para la demostración de reflexividad: Que R sea reflexiva significa que cada
elemento de A está relacionado por R consigo mismo. Pero por definición de R, que
un elemento x esté relacionado consigo mismo significa que x está en el mismo sub-
conjunto de la partición como el mismo. Bueno, si x está en algún subconjunto de la
partición, entonces es, sin duda, el mismo subconjunto como el mismo. Pero que x
continúa en la página 462
Nota Estos enunciados
pueden parecer extraños,
pero, después de todo, ¡no
son falsos!

462 Capítulo 8 Relaciones
esté en algún subconjunto de la partición ya que la unión de los subconjuntos de la
partición es toda A. Este razonamiento se formaliza como sigue.]
Demostración de que R es reflexiva: Suponga que x A. Ya que A1, A2, . . . , An es una
partición de A, de lo que se deduce que x Ai para alguna i. Pero entonces el enunciado
hay un conjunto Ai, de la partición tal que x Ai y x Ai
es verdadero. Por tanto, por definición de R, x R x.
[Idea para la demostración de simetría: Que R sea simétrica significa que en cual-
quier momento un elemento está relacionado con un segundo, entonces el segundo está
relacionado con el primero. Ahora que un elemento x esté relacionado con un segundo
elemento y significa que x y y están en el mismo subconjunto de la partición. Pero si este
es el caso, entonces y está en el mismo subconjunto de la partición que x, por lo que y está
relacionado con x por definición de R. Este razonamiento se formaliza como sigue.]
Demostración de que R es simétrica: Suponga que x y y son elementos de A tal que
x R y. Entonces
hay un subconjunto de Ai de la partición tal que x Ai y y Ai
por definición de R. Se deduce que el enunciado
hay un subconjunto Ai de la partición tal que y Ai y x Ai
es también verdadero. Por tanto, por definición de R, y R x.
[Idea para la demostración de transitividad: Que R sea transitiva significa que cual-
quier tiempo un elemento de A está relacionado por R con un segundo y el segundo está
relacionado con un tercero, entonces el primer elemento está relacionado con el tercero.
Pero que un elemento esté relacionado con otro significa que hay un subconjunto de
la partición que contiene a ambos. Así que supongamos que x, y y z son elementos
tales que x esté en el mismo subconjunto como y y y está en el mismo subconjunto
que z. ¿x debe estar en el mismo subconjunto que z? Sí, porque los subconjuntos de
la partición son mutuamente disjuntos. Ya que el subconjunto que contiene a x y a
y tiene un elemento en común con el subconjunto que contiene y y z (a saber y), los
dos subconjuntos son iguales. Pero esto significa que x, y y z están todos en el mismo
subconjunto y por tanto, en particular, x y z están en el subconjunto de la misma. Por
tanto x está relacionada por R a z. Este razonamiento se formaliza como sigue.]
Demostración de que R es transitiva: Suponga que x, y y z están en A y x R y y y R
z. Por definición de R, existen los subconjuntos Ai y Aj de la partición tales que
x y y están en Ai y y y z están en Aj.
Supongamos que Ai = Aj. [Deduciremos una contradicción.] Entonces Ai Aj ya
que {A1, A2, A3, . . . , An} es una actualización de A. Pero y está en Ai y también y está
en Aj. Por tanto Ai Aj = . [Esto contradice el hecho de que Ai Aj = ] así Ai
Aj. De lo que se deduce que x y y z están todos en Ai y así en particular,
x y z están en Ai.
Por tanto, por definición de R, x R z.
Definición de una relación de equivalencia
Una relación en un conjunto que satisface las tres propiedades de reflexividad, simetría y
transitividad se llama una relación de equivalencia.
Definición
Sea A un conjunto y R una relación sobre A. R es una relación de equivalencia si y
sólo si, R es reflexiva, simétrica y transitiva.
Nota El hecho de que
x Ai y x Ai se sigue de
la equivalencia lógica de la
forma de enunciado p y
p p.
Nota El hecho de que
y Ai y x Ai se sigue de
la equivalencia lógica de la
forma de enunciado p q
y q p.

8.3 Relaciones de equivalencia 463
Así, de acuerdo con el teorema 8.3.1, la relación inducida por una partición es una
relación de equivalencia. A continuación se presenta una variedad de ejemplos adicionales
de las relaciones de equivalencia y en los ejercicios.
Ejemplo 8.3.2 Una relación de equivalencia sobre un conjunto de subconjuntos
Sea X el conjunto de todos los subconjuntos no vacíos de {1, 2, 3}. Entonces
X {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Se define una relación R en X como sigue: Para todos A y B en X,
A R B el elemento mínimo de A es igual al elemento mínimo de B.
Demuestre que R es una relación de equivalencia en X.
Solución
R es reflexiva: Suponga que A es un subconjunto no vacío de {1, 2, 3}. [Debemos demostrar
que A R A.] Es verdadero decir que el menor elemento de A es igual al menor elemento de
A. Por tanto, por definición de R, A R A.
R es simétrica: Suponga que A y B son subconjuntos no vacíos de {1, 2, 3} y A R B.
[Debemos demostrar que B R A.] Ya que A R B, el elemento mínimo de A es igual
al elemento mínimo de B. Pero esto implica que el elemento mínimo de B es igual a la del
elemento mínimo de A y así, por definición de R, B R A.
R es transitiva: Suponga que A, B y C son subconjuntos no vacíos de {1, 2, 3}, A R B y
B R C. [Debemos demostrar que A R C.] Ya que A R B, el elemento mínimo de A es igual
a la del elemento mínimo de B y puesto B R C, el elemento mínimo de B es igual a la del
elemento mínimo de C. Por tanto, el elemento mínimo de A es igual al elemento mínimo
de C y así, por definición de R, A R C.
Ejemplo 8.3.3 La equivalencia de circuitos de lógica digital es una relación de equivalencia
Sea S el conjunto de todos los circuitos lógicos digitales con un número fijo n de entradas.
Se define una relación E sobre S como sigue: Para todos los circuitos C1 y C2 en S,
C1 E C2 C1 tiene la misma tabla de entrada/salida que C2.
Si C1 E C2, entonces se dice que el circuito C1 es equivalente al circuito C2. Demuestre
que E es una relación de equivalencia en S.
Solución
E es reflexiva: Supongamos que C es un circuito lógico digital en S. [Debemos demostrar
que C E C.] Por supuesto que C tiene la misma tabla de entrada/salida. Por tanto, por
definición de E, C E C [como se quería demostrar].
E es simétrica: Supongamos que C1 y C2 son circuitos lógicos digitales en S tales que C1
E C2. [Debemos demostrar que C2 E C1.] Por definición de E, ya que C1 E C2, entonces
C1 tiene la misma tabla de entrada y salida que C2. De lo que se deduce que C2 tiene la
misma tabla de entrada y salida que C1. Por tanto, por definición de E, C2 E C1 [como se
quería demostrar].
E es transitiva: Suponga que C1, C2 y C3 son circuitos lógicos digitales en S tales que
C1 E C2 y C2 E C3. [Debemos demostrar que C1 E C3.] Por definición de E, ya que C1 E
C2 y C2 E C3, entonces
C1 tiene la misma tabla de entrada/salida que C2
y C2 tiene la misma tabla de entrada/salida que C3.
De lo que se deduce que C1 tiene la misma tabla de entrada/salida que C3.
Por tanto, por definición de E, C1 E C3 [como se quería demostrar].
Ya que E es reflexiva, simétrica y transitiva, E es una relación de equivalencia en S.
Algunas implementaciones de lenguajes de programación no colocan un límite en
la longitud permitida de un identificador. Esto permite a un programador ser tan preciso