Autor Tema: Particiones, relaciones de equivalencia

0 Usuarios y 1 Visitante están viendo este tema.

23 Marzo, 2008, 02:09 pm
Leído 3160 veces

Eleal

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 549
  • Karma: +0/-0
  • Sexo: Masculino
Si \( \pi \) es una partición de un conjunto A y R es una relación de equivalencia sobre A entonces \( \pi=\pi(R)\Longleftrightarrow{R(\pi)=R} \).
(el teorema que dice que hay una biyección entre el conjunto de las particiones de un conjunto A y el conjunto de las relaciones de equivalencia sobre A)

Mi duda en concreto está en probar que \( \pi=\pi(R)\Longrightarrow{{R(\pi)=R}} \).

___________
Definiciones:

-)
\( \pi(R)=\{B:(\exists{x})(B=[x], \ B\neq{\emptyset})\} \)
Ésta sería la partición de A que induce la relación R.

(la letra mayúscula se refiere a un conjunto)

-)
\( R(\pi)=\{<x,y>: (\exists{B})(B\in{\pi}, \, x\in{B}, \, y \in{B})\} \)
Ésta sería la relación sobre A que induce la partición R.

-)
\( <x,y> \) denota un par ordenado.
-)
\( [x] \) es la R-clase de equivalencia representada por el elemento x.

23 Marzo, 2008, 03:44 pm
Respuesta #1

Fernando Revilla

  • "Há tantos burros mandando em homens de inteligência, que, às vezes, fico pensando que a burrice é uma ciência." -Antonio Aleixo.
  • Administrador
  • Mensajes: 12,575
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • "Las matemáticas son demasiado humanas."- Brouwer
    • Fernando Revilla
No me gustan nada de nada esas notaciones. Para un conjunto A no vacío, toda relación de equivalencia R en A determina una partición que es la parte para la que dices que no tienes problemas.

Si tienes una partición \( \left\{{A_i\;:i\in{I}}\right\} \) de A, entonces esta partición define una relación de equivalencia R cuyas clases de equivalencia son exactamente los \( A_i \). Efectivamente, definimos la relación en A:

\( xRy\Leftrightarrow{\exists{A_i}\;:x\in{A_i},y\in{A_i}} \)

Es sencillo a partir de la definición de partición demostrar que \( R \) es relación de equivalencia cuyo conjunto cociente es precisamente:

\( A/R=\left\{{A_i\;:i\in{I}}\right\} \)

Saludos.

24 Marzo, 2008, 01:06 am
Respuesta #2

Eleal

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 549
  • Karma: +0/-0
  • Sexo: Masculino
Si tienes una partición \( \left\{{A_i\;:i\in{I}}\right\} \) de A, entonces esta partición define una relación de equivalencia R cuyas clases de equivalencia son exactamente los \( A_i \). Efectivamente, definimos la relación en A:

\( xRy\Leftrightarrow{\exists{A_i}\;:x\in{A_i},y\in{A_i}} \) 

Es sencillo a partir de la definición de partición demostrar que \( R \) es relación de equivalencia cuyo conjunto cociente es precisamente:

\( A/R=\left\{{A_i\;:i\in{I}}\right\} \)

A ver qué tal sale:

Sea A un conjunto no vacío. Sea \( \left\{{A_i\;:i\in{I}}\right\} \) una partición de A.

Definimos la siguiente relación en A:

\( xRy\Leftrightarrow{\exists{A_i}\;:x\in{A_i},y\in{A_i}} \)    (1)

Queremos ver que:

1) R es una relación de equivalencia sobre A

2) El conjunto cociente de R respecto a A es
\( A/R=\left\{{A_i\;:i\in{I}}\right\} \)
___________________

1)

a) Reflexividad:

\( x\in{A}\Longrightarrow{\exists{A_i}\;:x\in{A_i}} \) (porque la unión de la partición es A, por definición)
Así que \( xRx \) por (1).

b) Simetría:

\( x,\ y \in{A} \wedge \ xRy \Longrightarrow{\exists{A_i}\;:x\in{A_i},y\in{A_i}} \)

De donde sale que \( xRy \) por (1).

c) Transitividad:

\( x,\ y , \ z \in{A} \ \wedge \ xRy \ \wedge\ \ yRz \Longrightarrow{(\exists{A_i}\;:x\in{A_i},y\in{A_i}) \wedge \ (\exists{A_i}\;:y\in{A_i},z\in{A_i}}) \)

Estos \( A_i \) que se garantiza existen, tienen que ser iguales porque "y" pertenece a ambos, y dos clases de equivalencia son disjuntas o son iguales.

Por lo tanto,

\( \exists{A_i}\;:x\in{A_i},y\in{A_i},z\in{A_i} \), lo que implica que
\( xRz \) por (1).

Así, R es una relación de equivalencia sobre A.


24 Marzo, 2008, 01:16 am
Respuesta #3

Eleal

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 549
  • Karma: +0/-0
  • Sexo: Masculino
Quisiera, por favor, un poquito de ayuda para ver 2).

Saludos,

24 Marzo, 2008, 10:33 am
Respuesta #4

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Para probar dos simplemente tienes que tener en cuenta que con la relación que has definido y si \( [x] \) denota la clase de equivalencia del \( x \), se tiene que:

 \( [x]=A_i  \) tal que \( x\in A_i \)

Saludos.

24 Marzo, 2008, 10:54 am
Respuesta #5

Fernando Revilla

  • "Há tantos burros mandando em homens de inteligência, que, às vezes, fico pensando que a burrice é uma ciência." -Antonio Aleixo.
  • Administrador
  • Mensajes: 12,575
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • "Las matemáticas son demasiado humanas."- Brouwer
    • Fernando Revilla

c) Transitividad:

\( x,\ y , \ z \in{A} \ \wedge \ xRy \ \wedge\ \ yRz \Longrightarrow{(\exists{A_i}\;:x\in{A_i},y\in{A_i}) \wedge \ (\exists{A_i}\;:y\in{A_i},z\in{A_i}}) \)

Estos \( A_i \) que se garantiza existen, tienen que ser iguales porque "y" pertenece a ambos, y dos clases de equivalencia son disjuntas o son iguales.

Por lo tanto,

\( \exists{A_i}\;:x\in{A_i},y\in{A_i},z\in{A_i} \), lo que implica que
\( xRz \) por (1).

Así, R es una relación de equivalencia sobre A.


Bueno, está claro que entiendes lo que es una partición y lo que es una relación de equivalencia. Ahora bien, observa que a priori de la primera hipótesis no puedes asumir que x,y,z pertenecen al mismo \( A_i \). Debes usar dos subíndices distintos. Por ejemplo:

\( (x,\ y , \ z \in{A}) \ \wedge (xRy) \ \wedge\ \ (yRz) \Rightarrow{(\exists{A_j}\;:x\in{A_j},y\in{A_j}) \wedge \ (\exists{A_k}\;:y\in{A_k},z\in{A_k}})\Rightarrow{y\in{A_j\cap{A_k}}}\Rightarrow{A_j=A_k}\Rightarrow({x\in{Aj})\wedge (z\in{A_j}})\Rightarrow{xRz} \)

Saludos.


08 Abril, 2008, 12:17 am
Respuesta #6

gonz

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 9
  • Karma: +0/-0
  • Sexo: Masculino
Hola!

A partir de una relación de equivalencia sobre un conjunto A se obtine una partición de A y a partir de una partición de A se obtiene una relación de equivalencia sobre A.
Supongamos que ya sabemos como definir la partición de A a partir de una relación de equivalencia R y como definir una relación de equivalencia a partir de una partición, la demostración es sencilla.

Debemos probar que \( \pi(R)=R \). Estos es, debemos probar que
\( a\pi(R)b\Longleftrightarrow{{aRb}} \)
Esto sale por definición de \( R(\pi) \) y de \( \pi(R) \)
Espero que te ayude en algo. Aunque esto es muy similar a lo que ya escribieron.
 :)