Autor Tema: Si \(\{1,2,3,4,5\}\), ¿hay una relación de equivalencia con 15 pares ordenados?

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

02 Noviembre, 2018, 01:22 am
Leído 11926 veces

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,326
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola!

¿Verdadero o falso? "Puede existir una relación de equivalencia en el conjunto \(A=\{1,2,3,4,5\}\) formada exactamente por \(15\) pares ordenados".



Me parece que es falso... pero no sé cómo probarlo.

Intenté armar la siguiente relación: \[\forall a,b\in A:a\mathcal Rb\iff a\geq b\] (porque \(\mathcal R\subseteq A\times A\)) ya que \(|\mathcal R|=|\Delta_A\cup\{(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)\}|=5+10=15\), pero creo que no sea de equivalencia, ya que no es simétrica, ¿verdad?

También hice bastante lío poniendo muchas disyunciones para cubrir los \(15\) (como \(a\mathcal Sb\iff a=b\vee a+b=6\vee a+b=5\vee a\mid b\vee\cdots\)) pero claro, ¿quién demuestra luego que ese choclo es una clase relación de equivalencia? :laugh: :laugh:.

¿Entonces cómo se prueba? ¿Hay alguna propiedad conocida de cardinales que permita decir "Si el conjunto tiene cardinal impar luego los pares ordenados de la relación de equivalencia deben ser pares" o algo así?

Gracias!
Saludos

02 Noviembre, 2018, 01:32 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Si una relación de equivalencia en un conjunto de \( N \) elementos forma \( n \) clases de equivalencia de cardinales \( k_1,\ldots k_n \), entonces \( k_1+\cdots + k_n=N \) y el número de pares de la relación es \( k_1^2+\cdots +k_n^2 \).

Se trata de probar que no existen números no nulos que suman \( 5 \) cuyos cuadrados suman \( 15 \). No me he parado a pensar si hay una forma más elegante de hacerlo, pero a lo bruto no sale muy largo. Si no me equivoco, hay siete casos que descartar.

02 Noviembre, 2018, 01:50 am
Respuesta #2

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,326
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola Carlos, qué bueno que aportes en temas no específicos de lógica! :D

Si una relación de equivalencia en un conjunto de \( N \) elementos forma \( n \) clases de equivalencia de cardinales \( k_1,\ldots k_n \), entonces \( k_1+\cdots + k_n=N \) y el número de pares de la relación es \( k_1^2+\cdots +k_n^2 \).

Tiene todo el sentido. Sin embargo, esta pregunta ha sido sacada de un examen, y no creo que si yo hubiese estado ahí (o cualquiera que sabe que le dan poco tiempo para resolverlo) se ponga a deducir eso ???.

Por el momento te pido por favor que la descartemos y pensemos en una solución más "fácil".

Pregunta acerca de tu propuesta
Se trata de probar que no existen números no nulos que suman \( 5 \) cuyos cuadrados suman \( 15 \). No me he parado a pensar si hay una forma más elegante de hacerlo, pero a lo bruto no sale muy largo. Si no me equivoco, hay siete casos que descartar.

¿Siete casos de qué? ¿Cuáles son? Ahí me perdí.

¿O sea sería ver que el sistema formado por \[\begin{cases}x+y=5\\x^2+y^2=15\end{cases}\] no tiene soluciones naturales? Si es así, sería muy fácil de probarlo, es re común ver estos tipos de sistemas.
[cerrar]

Ahora pensé en el siguiente digrafo que puede ser de equivalencia:


Es claro que es relación pues \(\mathcal T\subseteq A\times A\) y además \(|\mathcal T|=|\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(2,3),(3,2),(4,5),(5,4),(3,4),(4,3),(3,5),(5,3)\}|=15\).

La matriz de la relación \( \mathcal T \) es \[M_{\mathcal T}=\begin{pmatrix}1&1&1&1&1\\1&1&1&0&0\\1&1&1&0&1\\1&0&0&1&1\\1&0&1&1&1\end{pmatrix},\] donde claramente es reflexiva (hay todos \( 1 \) en la diagonal principal) y simétrica (las triangulares coinciden), pero.......... ¿será transitiva? ???.

Gracias y saludos

P.D. ¿Alguien sabe cómo probar si, dada la matriz asociada a una relación, es transitiva? Si se puede en primer lugar, ¿es necesario conocer el conjunto de elementos? ¿Cómo se visualiza en la matriz? En los libros no lo dicen y no entiendo por qué >:(.

02 Noviembre, 2018, 01:55 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Por el momento te pido por favor que la descartemos y pensemos en una solución más "fácil".

Pero estás tratando de encontrar una relación que cumpla lo pedido, cuando en realidad no existen. Ese camino no tiene nada de fácil.

¿O sea sería ver que el sistema formado por \[\begin{cases}x+y=5\\x^2+y^2=15\end{cases}\] no tiene soluciones naturales? Si es así, sería muy fácil de probarlo, es re común ver estos tipos de sistemas.

No tiene por qué haber sólo dos clases de equivalencia. Las posibilidades son

\( 1+1+1+1+1= 2+1+1+1= 2+2+1=3+2+1=4+1=3+2=5 \)

En ninguno de esos siete casos los cuadrados suman 15.

02 Noviembre, 2018, 02:01 am
Respuesta #4

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,326
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

No tiene por qué haber sólo dos clases de equivalencia. Las posibilidades son

\( 1+1+1+1+1= 2+1+1+1= 2+2+1=3+2+1=4+1=3+2=5 \)

En ninguno de esos siete casos los cuadrados suman 15.

Ahhh, a eso apuntabas cuando ponías los \( \ldots \) en

Si una relación de equivalencia en un conjunto de \( N \) elementos forma \( n \) clases de equivalencia de cardinales \( k_1,\ldots k_n \), entonces \( k_1+\cdots + k_n=N \) y el número de pares de la relación es \( k_1^2+\cdots +k_n^2 \).

¿Podrías poner un ejemplo donde puedan haber más de dos clases de equivalencia? Creo que nunca las traté.

¿Por qué no considerás los casos donde podamos conmutar términos (por ejemplo estaría faltando \( 1+2+1+1 \))? ¿Porque la suma y la potenciación son conmutativas?

Saludos

P.D. Si es posible, me gustaría recibir ayuda en

Ahora pensé en el siguiente digrafo que puede ser de equivalencia:

Imagen
[cerrar]

Es claro que es relación pues \(\mathcal T\subseteq A\times A\) y además \(|\mathcal T|=|\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(2,3),(3,2),(4,5),(5,4),(3,4),(4,3),(3,5),(5,3)\}|=15\).

La matriz de la relación \( \mathcal T \) es \[M_{\mathcal T}=\begin{pmatrix}1&1&1&1&1\\1&1&1&0&0\\1&1&1&0&1\\1&0&0&1&1\\1&0&1&1&1\end{pmatrix},\] donde claramente es reflexiva (hay todos \( 1 \) en la diagonal principal) y simétrica (las triangulares coinciden), pero.......... ¿será transitiva? ???.

y

¿Alguien sabe cómo probar si, dada la matriz asociada a una relación, es transitiva? Si se puede en primer lugar, ¿es necesario conocer el conjunto de elementos? ¿Cómo se visualiza en la matriz? En los libros no lo dicen y no entiendo por qué >:(.

EDITADO

02 Noviembre, 2018, 02:12 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Podrías poner un ejemplo donde puedan haber más de dos clases de equivalencia? Creo que nunca las traté.

En el conjunto \( \{1,2, 3, 11,12\} \) considerar la relación de equivalencia "terminar en la misma cifra". Hay tres clases de equivalencia, \( \{1, 11\} \), \( \{2,12\} \) y \( \{3\} \).

¿Por qué no considerás los casos donde podamos conmutar términos (por ejemplo estaría faltando \( 2+1+1+1 \))? ¿Porque la suma y la potenciación son conmutativas?

¿Por qué dices que falta ese caso? Es el segundo de los siete.

Respecto a lo que preguntas, sólo tienes que dibujar el grafo de la relación. Si no quedan los elementos divididos en grupos disjuntos donde todos estén relacionados con todos es que la relación no es de equivalencia. Si es reflexiva y simétrica, es que falla la transitividad. Por ejemplo, en tu matriz, dibujando el grafo se ve enseguida que 2 está relacionado con 3 y 3 con 5, pero 2 no está relacionado con 5.

02 Noviembre, 2018, 02:23 am
Respuesta #6

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,326
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

¿Por qué dices que falta ese caso? Es el segundo de los siete.

Perdón, quise decir \( 1+2+1+1 \) (o \( 1+1+2+1 \), ...). Edité correctamente el mensaje.

Respecto a lo que preguntas, sólo tienes que dibujar el grafo de la relación. Si no quedan los elementos divididos en grupos disjuntos donde todos estén relacionados con todos es que la relación no es de equivalencia. Si es reflexiva y simétrica, es que falla la transitividad. Por ejemplo, en tu matriz, dibujando el grafo se ve enseguida que 2 está relacionado con 3 y 3 con 5, pero 2 no está relacionado con 5.

No entiendo lo anterior a lo que está en negrita.

De lo que está en negrita, :o :o, pero una relación de equivalencia debe cumplir que sea reflexiva, simétrica y transitiva, ¿no? ¿O te referís a que si la matriz cumple que sea reflexiva y simétrica luego no es transitiva? ¡Pero si es así para qué nos sirve la matriz asociada sino para determinar si la relación es de equivalencia!

Lo que está luego de lo negrita lo entiendo muy bien :).

Saludos

02 Noviembre, 2018, 02:35 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Perdón, quise decir \( 1+2+1+1 \) (o \( 1+1+2+1 \), ...). Edité correctamente el mensaje.

Lo que digo es que una relación de equivalencia divide al conjunto en clases de equivalencia disjuntas. Si hay cuatro clases de equivalencia, la única posibilidad es que una tenga 2 elementos y las otras tres tengan 1, y en tal caso la relación tiene \( 2^2+1^2+1^2+1^2=7 \) pares ordenados, y no hay más posibilidades con cuatro clases de equivalencia. Con tres clases de equivalencia puede haber una con 3 elementos y otras dos con 1 cada una, o bien dos con 2 y una con 1, y no hay más opciones, etc.

Respecto a lo que preguntas, sólo tienes que dibujar el grafo de la relación. Si no quedan los elementos divididos en grupos disjuntos donde todos estén relacionados con todos es que la relación no es de equivalencia. Si es reflexiva y simétrica, es que falla la transitividad. Por ejemplo, en tu matriz, dibujando el grafo se ve enseguida que 2 está relacionado con 3 y 3 con 5, pero 2 no está relacionado con 5.

No entiendo lo anterior a lo que está en negrita.

Digo que si miras el grafo y no ves los elementos del conjunto divididos en subconjuntos disjuntos dos a dos en los que todos estén relacionados con todos, entonces puedes asegurar que la relación no es de equivalencia, y sabiendo que no es de equivalencia, sin el grafo ves que sí que es reflexiva y simétrica (todos los elementos tienen una flecha bucle y todas las flechas van en los dos sentidos, como ocurre en tu relación, porque te has preocupado de que sea reflexiva y simétrica) entonces, para que la relación no sea de equivalencia, lo que tiene que fallar es la transitividad.

02 Noviembre, 2018, 02:42 am
Respuesta #8

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,326
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Perdón, quise decir \( 1+2+1+1 \) (o \( 1+1+2+1 \), ...). Edité correctamente el mensaje.

Lo que digo es que una relación de equivalencia divide al conjunto en clases de equivalencia disjuntas. Si hay cuatro clases de equivalencia, la única posibilidad es que una tenga 2 elementos y las otras tres tengan 1, y en tal caso la relación tiene \( 2^2+1^2+1^2+1^2=7 \) pares ordenados, y no hay más posibilidades con cuatro clases de equivalencia. Con tres clases de equivalencia puede haber una con 3 elementos y otras dos con 1 cada una, o bien dos con 2 y una con 1, y no hay más opciones, etc.

Bien, pero no me refiero a eso. Me refiero a que si tenemos \( 2+1+1+1 \), ¿por qué es equivalente a \( 1+2+1+1 \)? ¿Porque la suma de clases es conmutativa (y de paso asociativa)?

Digo que si miras el grafo y no ves los elementos del conjunto divididos en subconjuntos disjuntos dos a dos en los que todos estén relacionados con todos, entonces puedes asegurar que la relación no es de equivalencia, y sabiendo que no es de equivalencia, sin el grafo ves que sí que es reflexiva y simétrica (todos los elementos tienen una flecha bucle y todas las flechas van en los dos sentidos, como ocurre en tu relación, porque te has preocupado de que sea reflexiva y simétrica) entonces, para que la relación no sea de equivalencia, lo que tiene que fallar es la transitividad.

Creo que te entiendo :laugh:. Parece como si estuviésemos hablando sobre componentes conexas.

Entonces sólo hay una única manera de probarlo:

Si una relación de equivalencia en un conjunto de \( N \) elementos forma \( n \) clases de equivalencia de cardinales \( k_1,\ldots k_n \), entonces \( k_1+\cdots + k_n=N \) y el número de pares de la relación es \( k_1^2+\cdots +k_n^2 \).

¿Alguna prueba de esto, por favor? Supongo que sale por inducción.

Saludos

02 Noviembre, 2018, 10:04 am
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Bien, pero no me refiero a eso. Me refiero a que si tenemos \( 2+1+1+1 \), ¿por qué es equivalente a \( 1+2+1+1 \)? ¿Porque la suma de clases es conmutativa (y de paso asociativa)?

Sí te refieres a eso. De hecho, no sé a qué llamas suma de clases. Lo que yo digo es que hay siete casos:

1) Hay cinco clases de 1 elemento cada una.
2) Hay cuatro clases de 1 elemento y una de 2.
3) Hay dos clases de 2 elementos y una de 1.
4) Hay una clase de 3 elementos y dos de 1.
5) Hay una clase de 3 elementos y una de 2.
6) Hay una clase de 4 elementos y otra de 1.
7) Hay una clase de 5 elementos.

¿Estás de acuerdo en que estos siete casos (donde no hay sumas ni nada) cubren todas las posibilidades o falta alguno?

Si estás de acuerdo en que se da necesariamente uno y sólo uno de los casos anteriores, entonces, en el caso 2 tendríamos \( 2^2+1^2+1^2+1^2=7 \) pares en la relación. La cuenta \( 1^2+2^2+1^2+1^2=7 \) sería considerar de nuevo el caso 2, en el que hay una clase (la que sea) con dos elementos y el resto con 1. El orden no importa porque no hay ningún orden establecido en las clases. No tiene sentido hablar de "la primera clase", "la segunda clase", etc. a menos que introduzcas tú un orden para luego concluir que no importa el orden. Si, directamente, no consideramos ningún orden en las clases, no viene al caso plantearse si importa o no un orden inexistente.

¿Alguna prueba de esto, por favor? Supongo que sale por inducción.

Sea \( A \) un conjunto en el que hay una relación de equivalencia \( R \) y sean \( \{C_i\}_{i\in I} \) las clases de equivalencia determinadas por \( R \). Un hecho básico sobre relaciones de equivalencia es que dos elementos \( x, y\in A \) están relacionados si y sólo si están en la misma clase \( C_i \). En otros términos:

\( (x, y)\in R \) si y sólo si existe un \( i\in I \) tal que \( (x, y)\in C_i\times C_i \), si y sólo si \( (x, y)\in \bigcup_{i\in I}(C_i\times C_i) \).

Esto prueba que \( R=\bigcup_{i\in I}(C_i\times C_i) \). Además todo elemento de \( A \) está en una clase de equivalencia, luego \( A=\bigcup_{i\in I}C_i \), y las clases \( C_i \) son disjuntas dos a dos, luego también lo son los productos \( C_i\times C_i \). Por lo tanto, podemos tomar cardinales y resulta:

\( |A|=\sum_{i\in I}|C_i| \), \( |R|=\sum_{i\in I}|C_i\times C_i| = \sum_{i\in I}|C_i|^2 \).

Si llamas \( k_i=|C_i| \), \( n=|I| \) y \( N=|A| \) te queda expresado en los términos en que lo había expresado antes.