Autor Tema: Problema de Relaciones (Retículo, Cadenas)

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

02 Junio, 2016, 06:27 am
Leído 3728 veces

andres_z

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 84
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Citar
Sea R un retículo con cinco elementos con exactamente una anticadena con 2 elementos. ¿Cuántas cadenas con 3 elementos tiene?

Estoy intentando dibujar el diagrama de Hasse, como es retículo tiene un supremo y un ínfimo, digamos \( s \) e \( i \).
La letra me dice que hay una anticadena con exactamente 2 elementos, digamos \( a \) y \( b \). Entonces dibujo \( i \) abajo de todo, luego arriba de \( i \) dibujo a \( a \) y \( b \) y los relaciono \( iRa, iRb \), y luego relaciono estos 2 con \( s \), de manera que \( aRs, bRs \).

Como son 5 elementos me queda uno por ubicar, pero no se como hacerlo sin romper lo de Retículo o lo de una sola anticadena de 2 elementos.

Gracias

02 Junio, 2016, 10:58 am
Respuesta #1

Luis Fuentes

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

 Mira el dibujo:



Saludos.

02 Junio, 2016, 01:20 pm
Respuesta #2

andres_z

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 84
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 Mira el dibujo:



Saludos.

Hola, gracias por responder.

Tengo una preguna, las cadenas no van desde el ínfimo al supremo? pues en ese caso no hay cadenas con 3 elementos no? de no ser así tengo mal la definición de Cadena :(

Saludos

02 Junio, 2016, 02:03 pm
Respuesta #3

Luis Fuentes

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

Tengo una preguna, las cadenas no van desde el ínfimo al supremo? pues en ese caso no hay cadenas con 3 elementos no? de no ser así tengo mal la definición de Cadena :(

Pues no sé que definición de cadena tienes; en principio la que yo conozco es que una cadena es un subconjunto del retículo sobre el cuál la relación es de orden total.

En ese caso habría cuatro cadenas de longitud 3 en cualquiera de los dos diagramas de Hasse del dibujo.

Esto se corrige en los mensajes posteriores


Saludos.

CORREGIDO

02 Junio, 2016, 09:06 pm
Respuesta #4

andres_z

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 84
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Tengo una preguna, las cadenas no van desde el ínfimo al supremo? pues en ese caso no hay cadenas con 3 elementos no? de no ser así tengo mal la definición de Cadena :(

Pues no sé que definición de cadena tienes; en principio la que yo conozco es que una cadena es un subconjunto del retículo sobre el cuál la relación es de orden total.

En ese caso habría cuatro cadenas de longitud 3 en cualquiera de los dos diagramas de Hasse del dibujo.

Saludos.

Hola,

Citar
Cadena de largo \( n \): Sea \( (A,R) \) un conjunto parcialmente ordenado y \( \emptyset \neq{} B \subset{} A \)  tal que \( R' \) =\(  (B \times{} B) \cap{} R \). Si \( (B, R') \) es un conjunto totalmente ordenado, decimos que \( (B, R') \) es una cadena en \( (A,R) \). Si \( B \) es finito, podemos ordenar los elementos de \( B \) como \( b_1R'b_2R'b_3R' . . . R'b_n \) y decir que la cadena tiene longitud \( n \).

Citar
Cadena Maximal: Si no existe un elemento \( a \in{} A \) tal que \( a \not\in{} \{b_1 , b_2 , . . . , b_n \} \) y \( aRb_1 \) o \( b_nRa \) o \( b_iRaRb_{i+1} \) .

Quizas me este confundiendo con la Cadena Maximal, me cuesta entender estas definiciones. La respuesta al problema es "hay 7 cadenas con 3 elementos", pero no se como llegar a eso...

Gracias

03 Junio, 2016, 10:37 am
Respuesta #5

Luis Fuentes

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

Citar
Cadena de largo \( n \): Sea \( (A,R) \) un conjunto parcialmente ordenado y \( \emptyset \neq{} B \subset{} A \)  tal que \( R' \) =\(  (B \times{} B) \cap{} R \). Si \( (B, R') \) es un conjunto totalmente ordenado, decimos que \( (B, R') \) es una cadena en \( (A,R) \). Si \( B \) es finito, podemos ordenar los elementos de \( B \) como \( b_1R'b_2R'b_3R' . . . R'b_n \) y decir que la cadena tiene longitud \( n \).

Citar
Cadena Maximal: Si no existe un elemento \( a \in{} A \) tal que \( a \not\in{} \{b_1 , b_2 , . . . , b_n \} \) y \( aRb_1 \) o \( b_nRa \) o \( b_iRaRb_{i+1} \) .

Quizas me este confundiendo con la Cadena Maximal, me cuesta entender estas definiciones.

Si, las cadenas que necesariamente contienen al ínfimo y supremo son las maximales.

Citar
La respuesta al problema es "hay 7 cadenas con 3 elementos", pero no se como llegar a eso...

Me equivoqué en mi anterior mensaje; efectivamente hay 7 cadenas. Si lo piensas visualmente una cadena es un trocito de diagrama de Hasse en el cual el diagrama es simplemente una línea sin bifurcaciones. Mi error en el conteo es que uno puede "saltarse" elementos.

En el siguiente gráfico puedes ver las 7 cadenas:



Saludos

03 Junio, 2016, 11:42 am
Respuesta #6

andres_z

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 84
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Citar
Cadena de largo \( n \): Sea \( (A,R) \) un conjunto parcialmente ordenado y \( \emptyset \neq{} B \subset{} A \)  tal que \( R' \) =\(  (B \times{} B) \cap{} R \). Si \( (B, R') \) es un conjunto totalmente ordenado, decimos que \( (B, R') \) es una cadena en \( (A,R) \). Si \( B \) es finito, podemos ordenar los elementos de \( B \) como \( b_1R'b_2R'b_3R' . . . R'b_n \) y decir que la cadena tiene longitud \( n \).

Citar
Cadena Maximal: Si no existe un elemento \( a \in{} A \) tal que \( a \not\in{} \{b_1 , b_2 , . . . , b_n \} \) y \( aRb_1 \) o \( b_nRa \) o \( b_iRaRb_{i+1} \) .

Quizas me este confundiendo con la Cadena Maximal, me cuesta entender estas definiciones.

Si, las cadenas que necesariamente contienen al ínfimo y supremo son las maximales.

Citar
La respuesta al problema es "hay 7 cadenas con 3 elementos", pero no se como llegar a eso...

Me equivoqué en mi anterior mensaje; efectivamente hay 7 cadenas. Si lo piensas visualmente una cadena es un trocito de diagrama de Hasse en el cual el diagrama es simplemente una línea sin bifurcaciones. Mi error en el conteo es que uno puede "saltarse" elementos.

En el siguiente gráfico puedes ver las 7 cadenas:



Saludos

¡Muchas gracias! muy detallada imagen, no sabia que se podian "saltar" elementos.

Tengo una duda mas... sobre cadenas maximales, ¿los 3 últimos diagramas de la figura son cadenas maximales? no entiendo bien la parte de la definición que dice "\( aRb_1 \) o \( b_nRa \) o \( b_iRaRb_{i+1} \)"

Gracias!

03 Junio, 2016, 12:00 pm
Respuesta #7

Luis Fuentes

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

¡Muchas gracias! muy detallada imagen, no sabia que se podian "saltar" elementos.

Fíjate que una cadena es un subconjunto de elementos en los cuales la relación es completa; visualmente "lineal". Entonces nada obliga a que entre dos elementos haya que coger todos los intermedios.

Citar
Tengo una duda mas... sobre cadenas maximales, ¿los 3 últimos diagramas de la figura son cadenas maximales?


No, en mi dibujo no está marcada ninguna cadena maximal.

Citar
no entiendo bien la parte de la definición que dice "\( aRb_1 \) o \( b_nRa \) o \( b_iRaRb_{i+1} \)"

Pues \( aRb_1 \) se refiere a que no puedes añadir ningún elemento "anterior" a todos.
\( b_nRa \)  a que no puedes añadir ninguno posterior.
\( b_iRaRb_{i+1} \)  a que no puedes añadir ninguno por el medio.

Pero hay una forma más cómoda de definir y entender lo que es una cadena maximal, es aquella que no está contenida en una cadena más grande.

Ahora he marcado las cadenas maximales:



Saludos.

03 Junio, 2016, 12:40 pm
Respuesta #8

andres_z

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 84
  • Karma: +0/-0
  • Sexo: Masculino
Hola

¡Muchas gracias! muy detallada imagen, no sabia que se podian "saltar" elementos.

Fíjate que una cadena es un subconjunto de elementos en los cuales la relación es completa; visualmente "lineal". Entonces nada obliga a que entre dos elementos haya que coger todos los intermedios.

Citar
Tengo una duda mas... sobre cadenas maximales, ¿los 3 últimos diagramas de la figura son cadenas maximales?


No, en mi dibujo no está marcada ninguna cadena maximal.

Citar
no entiendo bien la parte de la definición que dice "\( aRb_1 \) o \( b_nRa \) o \( b_iRaRb_{i+1} \)"

Pues \( aRb_1 \) se refiere a que no puedes añadir ningún elemento "anterior" a todos.
\( b_nRa \)  a que no puedes añadir ninguno posterior.
\( b_iRaRb_{i+1} \)  a que no puedes añadir ninguno por el medio.

Pero hay una forma más cómoda de definir y entender lo que es una cadena maximal, es aquella que no está contenida en una cadena más grande.

Ahora he marcado las cadenas maximales:



Saludos.

¡Genial! ¡Muchisimas gracias! Quedo todo muy claro.

Saludos