Producto Cartesiano. 4.1 Producto Cartesiano o Cruz Capítulo 4. Relaciones Definición Dados los...

Producto Cartesiano

4.1 Producto Cartesiano o Cruz

Capítulo 4. Relaciones

Definición Dados los conjuntos A, B U, el producto cartesiano o cruz de A, B se define por A B y es igual a BbAabaBA ,,

Se dice que los elementos de A B son pares ordenados. Para (a, b), (c, d) A B, se tiene que (a, b) = (c, d) si y sólo si, a = c y b = d.

Si A, B son finitos, por la regla del producto resulta que A B = . Aunque, en general, no es cierto que A B = B A, se tendrá que .

BA ABBA

Además aunque A, B U, no es necesario que A B U, de modo que U no es necesariamente cerrado en esta operación.



EJEMPLO Sea U = {1, 2, 3, ... , 7}, A = {2, 3, 4}, B = {4, 5}. Entonces,

a) A B = {(2, 4), (2, 5), (3, 4),(3, 5),(4, 4), (4, 5)}.

b) B A = {(4, 2), (4, 3), (4, 4), (5, 2), (5, 3), (5, 4)}.

c) B2=B B = {(4, 4), (4, 5), (5, 4), (5, 5)}

d) B3=B B B = ; (4, 5, 5)B3. Bcbacba ,,,,



EJEMPLO Si U =R, R R = se conoce como el plano real de la geometría coordenada y del cálculo bidimensional. El subconjunto R+R+ es el interior del primer cuadrante de este plano. Así mismo, R3 representa el espacio euclidiano tridimensional donde las superficies tridimensionales, como esferas y planos, son subconjuntos importantes.



EJEMPLO Un experimento E se desarrolla de la siguiente forma: se lanza un solo dado y se anota el resultado; a continuación, se lanza una moneda al aire y se anota el resultado. Determínese un espacio muestral M para E.

Denótese por E1 la primera parte del experimento E y sea

M1 = {1, 2, 3, 4, 5, 6} un espacio muestral para E1. Así

mismo sea M2={CA,CZ} un espacio muestral para E2, la

segunda parte del experimento. Entonces, M = M1 M2

es un espacio muestral para E.



Este espacio muestral se puede representar gráficamente con un diagrama de árbol.



EJEMPLO En el torneo de tenis de Wimbledon, las mujeres juegan a lo sumo 3 sets en un partido. Triunfa quien gane primero 2 sets. Si N y E representan a las 2 jugadoras, el diagrama de árbol refleja las 6 maneras en que puede ganarse el encuentro.




4.2 Relaciones

Definición 3.2 Dados los conjuntos A, B U, cualquier subconjunto de A B se denomina relación de A a B. A cualquier subconjunto de A A se denomina relación binaria.


4.2 Relaciones

EJEMPLO Sea U = {1, 2, 3, ... , 7}, A = {2, 3, 4}, B = {4, 5}. las siguientes son relaciones de A a B.

a) b) {(2,4)} c) {(2, 4), (2, 5)}

d) {(2, 4), (3, 4), (4, 4)} e) {(2, 4), (3, 4), (4, 5)}

f) A B.

Como = 6, por la definición se deduce que hay 26 relaciones posibles de A a B.

BA


4.2 Relaciones

En general, para conjuntos finitos A, B donde = m y . = n, hay 2mn relaciones de A a B, incluyendo la relación vacía y la propia relación A B.

AB

EJEMPLO Sea B = {1, 2} N, U = P(B) y A = U ={, {1}, {2}, {1, 2}}. El siguiente es un ejemplo de relación binaria en A: R = {(, ), (, {1}), (, {2}), (, {1, 2}), ({1}, {1}), ({1},{1,2}), ({2}, {2}), ({2}, {1,2}), ({1,2}, {1,2})}. Se puede decir que la relación R es una relación de subconjunto donde (C, D) R si y sólo si C, D B y C D.


4.2 Relaciones


4.2 Relaciones

EJEMPLO Si A = U =Z+, se define una relación binaria R en el conjunto A como . Se trata de la conocida relación “es menor o igual que” para el conjunto de los enteros positivos,

yxyx ,

Se observa que (7,7),(7,11)R, y (8,2)R, (7,11)R también se puede denotar como 7R 11; (8,2)R se transforma en 8R 2 son ejemplos de notación infija en una relación.

EJEMPLO Cuando el compilador Pascal traduce un programa fuente del programa objeto a lenguaje de máquina, éste elabora una tabla de símbolos que contiene los siguientes conjuntos:

1.- S: el conjunto de nombres simbólicos, como variables, constantes y tipos.

2.- A: el conjunto de posibles atributos para los elementos de S, como entero, real, Booleano, carácter.

3.- L: el conjunto de posiciones, o direcciones de la memoria donde se almacenan los elementos de S.

La información de la tabla proporciona relaciones de S a A y de S a L.

Para cualquier conjunto A U , A = . (Si A , sea (a, b) A . Entonces, a A y b , lo cual es imposible). Así mismo A = .


4.2 Relaciones

El producto cartesiano y las operaciones binarias de unión e intersección están interrelacionados con el siguiente teorema.

Teorema Para conjuntos arbitrarios A, B, C U.a)

b)

c)

d)

CABACBA

CABACBA

CBCACBA

CBCACBA


4.2 Relaciones

Demostración Se demuestra el teorema a) y se deja el resto como ejercicio.

Para cualquier a, b U, (a, b)

a A y b

a A y b B, b C

a A, b B, y a A, b C

(a, b) A B y (a, b) A C

(a, b) (A B) ( A C).

= (A B) ( A C)

CBA

CB

CBA

Definición Una relación R en un conjunto A se denomina reflexiva si para todo x A, (x, x) R .

Se dice que R es reflexiva si cada elemento x de A está relacionado consigo mismo

EJEMPLO Para A = {1, 2, 3, 4}, una relación R A A será reflexiva si R {(1, 1), (2, 2), (3, 3), (4, 4)}. Por tanto, R1={(1,1), (2,2), (3,3)} no es una relación reflexiva

en A, mientras que R2= si es reflexiva en A.


4.2 Relaciones


4.2 Relaciones

EJEMPLO Dado un conjunto finito A con =n, resulta que = n2, de modo que hay relaciones en A. Cuántas son reflexivas?.

2

2nA

AA

Si A ={a1, a2, ... ,an}, una relación R en A es reflexiva

si . R . Al considerar los otros n2–n pares ordenados de A A (los de la forma , 1 i, j n, i j) conforme se construye una relación reflexiva R en A, se incluye o excluye cada uno de estos pares ordenados, y por la regla del producto, hay relaciones reflexivas en A.

niaa ii 1, ji aa ,

nn 2

2


4.2 Relaciones


4.2 Relaciones

Definición La relación R en un conjunto A se llama simétrica si (x, y) R (y, x) R para x, y A.

EJEMPLO Con A = {1, 2, 3}, se tiene que:

a)R1={(1,2),(2,1),(1,3),(3,1)} es simétrica, no reflexiva;

b)R 2={(1,1),(2,2),(3,3),(2,3)}es reflexiva, no simétrica;

c)R3={(1,1),(2,2),(3,3)};R4={(1,1),(2,2),(3,3),(2,3),(3,2)}

son reflexivas y simétricas.

Para contar las relaciones simétricas en A={a1,a2, ... ,an},

se escribe AA como A1A2, donde A1= y

A2= de modo que cada par en AA

está exactamente en uno de los conjuntos A1,A2. Para

A2, . = – = n2–n=n(n–1), un entero par. El

conjunto A2 contiene (1/2)(n2–n) subconjuntos de la

forma {(ai,aj),(aj,ai)},1ijn. Al establecer una relación

simétrica R en A, para cada par ordenado de A1, se

dispone de la selección usual de exclusión o inclusión. Para los (1/2)( n2 – n) subconjuntos de pares ordenados en A2, se dispone de las mismas opciones. Por tanto, por la

regla del producto, hay = relaciones simétricas en A. Al contar las relaciones en A que son reflexivas y simétricas, se tiene sólo una opción para cada par ordenado en A1. De modo que hay ,

relaciones en A que son reflexivas y simétricas.

niaa ii 1, jinjiaa ji ,,1,

2A AA 1A

nnn 22/122 nn 22/12

nn 22/12

Definición Para un conjunto A, una relación R en A se llama transitiva si (x, y), (y, z) R (x, z) R. (De modo que si x “está relacionado con” y e y “está relacionado con” z, se desea “relacionar” x con z, representando y el papel de “intermediario”.)


4.2 Relaciones


4.2 Relaciones

EJEMPLO Si A ={1, 2, 3, 4}, entonces R1={(1,1), (2,3),

(3,4),(2,4)} es una relación transitiva en A, mientras que R2={(1,3),(3,2)} no lo es, pues (1,2) R2.

EJEMPLO Defínase la relación R en el conjunto Z+ por a R b si a divide b, por ejemplo, para alguna c Z+, b = ca. Ahora si xRy e yRz, resulta xRz?. xRy y = sx, sZ+; yRz z= ty, tZ+. En consecuencia, z= ty = t(sx) = (ts)x, tsZ+, de modo que xRz y R es transitiva. Además R es reflexiva, pero no simétrica, puesto que 2R6, pero 6R2.

Definición Dada una relación R en un conjunto A, R se denomina antisimétrica si a R b, b R a a = b. (En este caso, la única manera de tener a a “relacionado con” b y a b “relacionado con” a es que a y b sean uno y el mismo elemento de A).


4.2 Relaciones


4.2 Relaciones

EJEMPLO Para un universo dado U defínase la relación R en P(U) por (A, B)R si A B, para A, B U; de modo que R es la relación de subconjunto y si A R B y B R A, entonces se tiene A B, B A, lo que equivale a A = B. En consecuencia, esta relación es antisimétrica, además de reflexiva y transitiva, pero no simétrica.

Antes de cometer el error de pensar que “no simétrica” es sinónimo de “antisimétrica”, téngase en cuenta lo siguiente.

EJEMPLO Para A ={1, 2, 3}, la relación R en A dada por R = {(1, 2), (2, 1), (2, 3)} no es simétrica porque (3, 2) R, y tampoco es antisimétrica, pues (1,2), (2,1) R pero 1 2. La relación R1={(1, 1), (2, 2)}es simétrica y

antisimétrica.

¿Cuántas relaciones son antisimétricas en A?Al escribir ={(1,1),(2,2),(3,3)} {(1,2),(2,1),(1,3), (3,1),(2,3),(3,2)}. Se hacen dos observaciones al intentar construir una relación R antisimétrica en A.

AA


4.2 Relaciones


4.2 Relaciones

1. Cualquier elemento (x, x) puede incluirse o excluirse sin importar si R es o no antisimétrica.

2. Para un elemento de la forma (x, y), x y, se deben

tener en cuenta (x,y) e (y,x) y nótese que hay tres opciones para que R permanezca antisimétrica: a) situar (x, y) en R; b) situar (y, x) en R; c) no situar (x, y) ni (y, x) en R. (Qué sucede si se sitúan (x, y) e (y, x) en R?)

AA


4.2 Relaciones

A

De esta manera por la regla del producto, el número de relaciones antisimétricas en A es (23)(33) = (23)( ). Si = n 0, entonces hay relaciones antisimétricas en A.

2/332

3

2/2

32 nnn

Definición La relación R en un conjunto A se denomina orden parcial o relación de orden parcial si R es reflexiva, antisimétrica y transitiva.

EJEMPLO la relación de subconjunto es un orden parcial.


4.2 Relaciones


4.2 Relaciones

Definición Una relación de equivalencia R en un conjunto A es una relación reflexiva, simétrica y transitiva.

EJEMPLO Sea nZ+. Para x, y Z, se define la relación R de módulo n por medio de x R y si y sólo si, x – y es un múltiplo de n. Con n = 7, se halla que 9 R 2, -3 R 11, (14,0) R pero 3 R 7.

Si R es una relación en un conjunto A, entonces R es una relación de equivalencia y un orden parcial en A si y sólo si es la relación de igualdad en A.

Para cualquier conjunto A, es una relación de equivalencia en A, y si A = {a1, a2, ... , an}, la relación de

equivalencia más pequeña en A es R = .

AA

niaa ii 1,


4.2 Relaciones

Relaciones de Orden

N +, *

Z +, *,

Q +, *, , /

R +, *, , / ,±

C +, *, , / ,

1+2, 2*3

x + 5 = 2

2x + 3 = 4

x2 – 2 = 0

x2 + 1 = 0

A medida que se aumenta desde N hasta C se adquiere mayor capacidad para resolver ecuaciones polinomiales, aunque al pasar de R a C se pierde algo.


4.3 Relaciones de Orden

En R, dados los números r1, r2 con r1r2, siempre es

posible decir si r1 r2 o r2 r1. No obstante en C, (2+i)

(1+2i). Se ha perdido la capacidad de “ordenar” los elementos del sistema numérico.



Sea A un conjunto y R una relación en A. El par (A, R) se llama conjunto parcialmente ordenado si la relación R en A es un orden parcial, o una relación de ordenamiento parcial. Si a A se le denomina conjunto parcialmente ordenado, se sobre entiende que hay un orden parcial R en A que convierte a A en este conjunto parcialmente ordenado.





EJEMPLO Sea A el conjunto de cursos ofrecidos en una universidad. Defínase la relación R en A mediante x R y si x e y son el mismo curso o si x es un requisito previo para y. Entonces, R transforma a A en un conjunto parcialmente ordenado.

EJEMPLO Defínase R en A = {1, 2, 3, 4} por x R y, si , es decir, x divide a y. Entonces, R ={(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (1, 3), (1, 4), (2, 4)} es un orden parcial y (A, R) es un conjunto parcialmente ordenado.

EJEMPLO Para construir una casa hay ciertos trabajos, como excavar los cimientos, que deben realizarse antes de poder comenzar otras fases de la construcción . Si A es un conjunto de tareas que deben realizarse para construir una casa o completar un proceso especial de fabricación, se puede definir una relación R en A por x R y si x e y denotan la misma tarea o si la tarea x debe realizarse antes de comenzar la y. De esta manera se asigna un orden a los elementos de A, convirtiéndolo en un conjunto parcialmente ordenado.





EJEMPLO En el conjunto A = {1, 2, 3, 4, 5}, la relación R en A, definida por x R y si x y, es un orden parcial, que transforma a A en un conjunto parcialmente ordenado que se puede denotar por (A, ). Si B = {1, 2, 4} A, el conjunto ={(1, 1), (2, 2), (4, 4), (1, 2), (1, 4), (2, 4)} es un orden parcial en B.

En general si R es un orden parcial en A, entonces para cualquier subconjunto B de A, convierte a B en un conjunto parcialmente ordenado, donde el orden parcial de B se induce de R.

RBB

Definición Si (A, R) es un conjunto parcialmente ordenado, se dice que A está totalmente ordenado si para toda x, y A se cumple x R y o y R x. En este caso R se denomina orden total.





EJEMPLO En el conjunto N, la relación R definida porx R y si x y es un orden total. La relación de subconjunto aplicada a A = P(U), U = {1, 2, 3} es un orden parcial, pero no total: {1, 2}, {1, 3}A, pero ni {1, 2} {1, 3} ni {1, 3} {1, 2}.

Definición Si (A, R) es un conjunto parcialmente ordenado, un elemento x A se llama maximal de A si para toda a A, a x x R a . Un elemento y A se denomina minimal de A si cuando b A y b y, entonces b R y.





EJEMPLO Sea U = {1, 2, 3} y A = P(U).

Sea R la relación de subconjunto en A. Entonces U es maximal, mientras que es minimal para este conjunto parcialmente ordenado.

Para B, la colección de subconjuntos propios de {1, 2, 3}, sea R la relación de subconjunto en B . En el conjunto parcialmente ordenado (B, ), {1, 2}, {1, 3}, {2, 3} son elementos maximales, mientras que es el único elemento minimal.



EJEMPLO Con la relación R “es menor o igual que” en el conjunto Z, (Z, ) es un conjunto parcialmente ordenado sin elemento maximal ni minimal. No obstante el conjunto parcialmente ordenado sin elemento maximal ni minimal. No obstante, el conjunto parcialmente ordenado (N, ) tiene elemento minimal 0, pero no maximal.

Teorema Si (A, R) es un conjunto parcialmente ordenado y A finito, entonces A tiene elementos maximal y minimal.

Demostración Sea a1A. Si no hay elemento a A, a

a1 con a1 R a , entonces a1 es maximal. De no ser así, hay

un elemento a2 A , a2 a1, con a1 R a2.



Si ningún elemento a A, a a2 , cumple a2 R a,

entonces a2 es maximal. De lo contrario se puede

encontrar a3 A, a3 a2 , a3 a1 (¿por qué?) con a1 R a2

y a2 R a3. Siguiendo así, como A es finito, se alcanza un

elemento an A con an R a para cualquier a an A, de

modo que an es maximal.



Definición Si (A, R) es un conjunto parcialmente ordenado, un elemento x A se denomina elemento mínimo si x R a, para todo a A. El elemento y A se denomina máximo si a R y para toda a A.



EJEMPLO Sean U = {1, 2, 3} y R la relación de subconjunto.

a) Con A = P(U), (A, ) tiene a como elemento mínimo y a U como máximo.

b) Para B = la colección de subconjuntos no vacíos de U, (B, ) tiene a U como elemento máximo. No existe elemento mínimo, pero si tres elementos minimales.



Para un conjunto parcialmente ordenado (A, R), es posible tener varios elementos maximales y minimales. ¿Qué sucede con los elementos mínimo y máximo?





Teorema Si el conjunto parcialmente ordenado (A, R) tiene algún elemento máximo (mínimo), ese elemento es único.

Demostración Supóngase que x, y A y que ambos son elementos máximos. Como x es un elemento máximo, y R x. Así mismo, x R y, pues y es un elemento máximo. Como R es antisimétrico, x = y.

Definición Sea (A, R) un conjunto parcialmente ordenado con B A. Un elemento x A se llama cota inferior de B si x R b para toda bB. Si y A y b R y, para toda b B, y se denomina cota superior de B.





Un elemento x´A se llama máxima cota inferior (mci) de B si es una cota inferior de B y si para el resto de las cotas inferiores x´´ de B, x´´ R x´. De manera análoga, y´ A es una mínima cota superior (mcs) de B si es una cota superior de B y para el resto de las cotas superiores y´´ de B, y´ R y´´.

EJEMPLO Sea R la relación “es menor o igual que” para el conjunto parcialmente ordenado en el siguiente caso: Si A = R, y B = [0, 1], entonces B tiene mci 0 y mcs 1. Obsérvese que 0, 1 B. Para C = (0, 1], C tiene mci 0 y mcs 1, y 1 C, pero 0 C.





Teorema Si (A, R) es un conjunto parcialmente ordenado y B A, si B tiene mcs (mci), ésta es única.

Demostración. Se deja como ejercicio.

Definición El conjunto parcialmente ordenado (A, R) se denomina red si para cualquier x, y A, existen la mcs{x, y} y la mci{x, y} .

EJEMPLO. Para A=N, y x,y N, defínase xRy por x y. Entonces mcs{x, y}= max{x, y}, mci{x, y}=min{x, y} y (N, ) es una red.



Relaciones de Equivalencia


4.4 Relaciones de Equivalencia

Recordemos que R en un conjunto A es una relación de equivalencia si es reflexiva, simétrica y transitiva.

Si se considera la relación R en Z definida por x R y, si x – y es un múltiplo de 2, entonces R es una relación de equivalencia en Z, donde todos los enteros pares e impares están relacionados. Por ejemplo, aquí no se tiene 4 = 8, pero si 4 R 8, pues ya no interesa el tamaño de un número, sino sólo dos propiedades: paridad e imparidad. Esta relación descompone Z en dos subconjuntos formados por los enteros pares e impares: Z = {... , -3, -1, 1, 3, ...} {... , -4, -2, 2, 4, ...}. Esta descomposición de Z es un ejemplo de partición, concepto íntimamente ligado a la relación de equivalencia.



IiiA

Definición Dados un conjunto A y un conjunto de índices, I, sea Ai A, para cada iI. Entonces es una

partición de A si

a)

b) , para i, j I, i j.

Cada conjunto Ai se llama celda o bloque de la partición.

Ii

iAA

ji AA



EJEMPLO Si A = {1, 2, 3, ..., 10}, entonces los siguientes conjuntos son particiones de A:

a) A1 = {1, 2, 3, 4, 5}, A2 ={6, 7, 8, 9, 10};

b) A1 = {1, 3, 5, 7, 9}, A2={2, 4, 6, 8, 10};

c) A1 = {1, 2, 3}, A2 ={4, 6, 7, 9}, A3 = {5, 8, 10};

d) Ai = {i, i+5}, 1 i 5.



EJEMPLO Sea A=R y para cada iZ, sea Ai=[i, i+1).

Entonces constituye una partición de R.


Definición Sea R una relación de equivalencia en un conjunto A. Para cualquier x A, la clase de equivalencia de x, denotada por [x], se define mediante

xyAyx R][


EJEMPLO Defínase la relación R en Z, por xRy, si 4 divide a (x–y). Para esta relación se encuentra que

[0] = {..., -8, -4, 0, 4, 8, 12, ...} = {4k kZ}

[1] = {..., -7, -3, 1, 5, 9, 13, ...} = {4k + 1 kZ }

[2] = {..., -6, -2, 2, 6, 10, 14, ...} = {4k + 2 kZ }

[3] = {..., -5, -1, 3, 7, 11, 15, ...} = {4k + 3 kZ }

{[0], [1], [2], [3]} proporciona una partición de Z.



Teorema Si R es una relación de equivalencia en un conjunto A y x, y A, entonces: a) x [x]; b) x R y si y sólo si [x] = [y] y c) [x] = [y] o [x] [y] = .

Demostración

a) Este resultado se obtiene de la propiedad reflexiva de R

b) Si x R y , sea w [x]. Entonces, w R x; además como R es transitiva, w R y. Por tanto, w [y] y [x] [y]. Con R simétrica, x R y y R x. De este modo, si t [y], entonces t R y y por la propiedad transitiva, t R x. De ahí que t [x] e [y] [x]. Por tanto [x] = [y]. A la inversa sea [x] = [y]. Como por el apartado a) x [x], entonces x [y] o x R y.

c) Esta propiedad plantea que las clases de equivalencia sólo se pueden relacionar de dos maneras: son idénticas o disjuntas.

c) Continuación... Se supone que [x] [y] y se muestra cómo entonces resulta que [x] [y] = . Si [x] [y] , entonces sea v A con v [x] y v [y]. Por tanto, v R x, v R y x R y. Además por el apartado b), x R y [x] = [y]. Esto contradice la hipótesis de que [x] [y], por tanto se rechaza la hipótesis de que [x] [y] , y de ahí se obtiene el resultado.



Obsérvese que si R es una relación de equivalencia en A, entonces, de acuerdo con a) y c) del teorema anterior, las distintas clases de equivalencia determinadas por R constituyen una partición de A.

EJEMPLO Si A ={1, 2, 3, 4, 5} y R = {(1, 1), (2, 2), (2, 3), (3, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5)}, entonces R es una relación de equivalencia en A, [1] = {1}, [2] = {2,3}=[3], [4]={4,5}=[5] y A = [1] [2] [4].



EJEMPLO 3.31 En FORTRAN ANSI hay una instrucción llamada instrucción EQUIVALENCE, que permite a dos o más variables de un programa dado referirse al mismo lugar en la memoria. Por ejemplo EQUIVALENCE (A, C, P), (ARRIBA, ABAJO). Informa al compilador que las variables A, C, P compartirán un lugar en la memoria y que ARRIBA y ABAJO compartirá otro. Aquí el conjunto de todas las variables del programa se descompone por la relación de equivalencia R, donde V1 R V2 si V1 y V2 son

variables de programa que comparten una misma localidad de la memoria.



EJEMPLO Después de ver ejemplos de cómo una relación de equivalencia origina una partición de un conjunto, se volverá a ello. Si una relación de equivalencia R en A = {1, 2, 3, 4, 5, 6, 7} causa la partición A = {1, 2} {3} {4, 5, 7} {6}, ¿Cuál es el valor de R?

Considérese el subconjunto {1, 2} de la partición. Este subconjunto implica que [1] = {1, 2} = [2], y así (1, 1), (2, 2), (1, 2), (2, 1) R. (Los primeros dos pares ordenados son necesarios para la propiedad reflexiva de R, en tanto que los otros preservan la simetría). De manera análoga, el subconjunto {4, 5, 7} implica que bajo R, [4] = [5] = [7] = {4, 5, 7} y que, como relación de equivalencia, R debe contener {4, 5, 7} {4, 5, 7}. De hecho R = ({1, 2} {1, 2}) ({3} {3}) ({4, 5, 7} {4, 5, 7}) ({6} {6}), y |R| = 22 + 12 + 32 + 12 = 15.


Teorema Si A es un conjunto, entonces:

a) Cualquier relación de equivalencia R en A origina una partición de A.

b) Cualquier partición de A origina una relación de equivalencia R en A.


Demostración:

El apartado a) resulta de los apartados a) y c) del teorema anterior.

Para el apartado b), dada una partición de A, defínase la relación R en A por x R y, si x, y están en la misma celda de la partición. Se deja como ejercicio la comprobación de que R es una relación de equivalencia.



Producto Cartesiano. 4.1 Producto Cartesiano o Cruz Capítulo 4. Relaciones Definición Dados los...

Documents

Transcript of Producto Cartesiano. 4.1 Producto Cartesiano o Cruz Capítulo 4. Relaciones Definición Dados los...