Autor Tema: Duda con buen ordenamiento

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

06 Marzo, 2008, 01:00 am
Leído 3505 veces

Eleal

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 549
  • Karma: +0/-0
  • Sexo: Masculino
Tengo una duda con lo siguiente:

Si R es una relación conexa sobre un conjunto A, tal que todo subconjunto no vacío de A tiene un R-elemento mínimo, entonces R es reflexiva sobre A.  (I)

____________

Por otro lado, consideraba lo siguiente: Si \( (\exists{x})(x \in{A}\ \wedge <x,x> \, \not\in{R}) \) tendríamos que
\( \{x\} \subseteq{A}, \{x\}\neq{\emptyset} \). Pero este conjunto no tendría elemento minimal.

Quisiera saber si lo de arriba es correcto o no.

Saludos,

Nota:

-) <x,y> es un par ordenado.


Aquí algunas definiciones que uso:

-) Un conjunto R es una relación si y sólo si

\(  \forall{x \in{R}}, \)\( \exists{y,z} \) tales que \(  x=<y,z> \).

-) Una relación R es reflexiva sobre un conjunto A si y sólo si

\( (\forall{x})(x \in{A}\Longrightarrow{<x,x> \in{R}}) \)

-) Una relación R es conexa sobre un conjunto A si y sólo si

\( (\forall{x,y})(x,y \in{A} \wedge x \neq{y}\Longrightarrow{<x,y> \in{R} \ \vee{<y,x> \in{R}}) \)

-) x es un elemento minimal de A si y sólo si
\( x \in{A} \ \wedge \, (\forall{y })(y\in{A} \Longrightarrow{<y,x> \not\in{R}}) \)

06 Marzo, 2008, 01:28 am
Respuesta #1

León

  • Lathi
  • Mensajes: 903
  • Karma: +0/-0
  • Sexo: Masculino
Tengo una duda con lo siguiente:

Si R es una relación conexa sobre un conjunto A, tal que todo subconjunto no vacío de A tiene un R-elemento mínimo, entonces R es reflexiva sobre A.  (I)

____________

Por otro lado, consideraba lo siguiente: Si \( (\exists{x})(x \in{A}\ \wedge <x,x> \, \not\in{R}) \) tendríamos que
\( \{x\} \subseteq{A}, \{x\}\neq{\emptyset} \). Pero este conjunto no tendría elemento minimal.

¿Cómo que no? x mismo es el elemento minimal.

Salvo que esté mareado la afirmación esa, con las definiciones que muestras, es recontrafalsa.

Por ejemplo \( A=\{1\},R=\emptyset \) es un contraejemplo. Si ese contraejemplo no convence por ser demasiado trivial tienes también \( A=\{1,2\}, R=\{<1,2>\} \).

No sólo eso, ya que todos los elementos deben ser el minimal del subconjunto unitario que los contiene y que un elemento minimal, por definición no puede relacionarse con si mismo, \( \forall x\in A,<x,x>\not\in R \). ¡No hay relación menos reflexiva que eso!

07 Marzo, 2008, 01:27 am
Respuesta #2

Eleal

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 549
  • Karma: +0/-0
  • Sexo: Masculino
Gracias León por tu respuesta, pero todavía no tengo claro algo,

Mi duda sale de este ejercicio:

"Si R es conexa en un conjunto A y todo subconjunto no vacío de A tiene un elemento mínimo, entonces R es un buen orden para A." (II)

Pude probar que entonces R es transitiva y asimétrica (y por ser asimétrica es antisimétrica), pero no podía probar la reflexividad. ¿ Entonces (II) es completamente falso? ¿Sería posible cambiar un poco las hipótesis  para que (II) sea cierto? ¿Y si se cambiase la definición de elemento minimal para permitir que se relacione con sí mismo?

Saludos,
_____

Definición:
R es un buen orden para A si y solo si R es reflexiva, antisimétrica y transitiva sobre A y todo subconjunto no vacío de A tiene elemento mínimo.

-) Una relacion R es irreflexiva sobre un conjunto A si y sólo si
\( (\forall{x})(x \in{A}\Longrightarrow{<x,x> \not\in{}{R}}) \)

-) x es un elemento mínimo de A si y sólo si
\( x \in{A} \ \wedge \, (\forall{y })(y\in{A} \wedge \, x\neq{y} \Longrightarrow{<x,y> \in{R}}) \)



07 Marzo, 2008, 02:21 am
Respuesta #3

León

  • Lathi
  • Mensajes: 903
  • Karma: +0/-0
  • Sexo: Masculino
-) x es un elemento mínimo de A si y sólo si
\( x \in{A} \ \wedge \, (\forall{y })(y\in{A} \wedge \, x\neq{y} \Longrightarrow{<x,y> \in{R}}) \)

Hola, Eleal.

Lo que quieres probar es cierto si defines "x es un elemento mínimo de A" así:
\( x \in{A} \ \wedge \, (\forall{y })(y\in{A}\Longrightarrow{<x,y> \in{R}}) \)

Observa que he copiado tu última definición eliminando la condición \( x\neq y \). .. sino no hay cómo deducir la reflexividad (y de hecho podrías usar los mismos contraejemplos de mi mensaje anterior para probarlo).

Saludos.

11 Marzo, 2008, 02:22 am
Respuesta #4

Eleal

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 549
  • Karma: +0/-0
  • Sexo: Masculino
Estaba revisando las pruebas que he intentado hacer, pero veo que no están bien.

Lo que sucede es que trato de hacer ejercicios de dos libros diferentes, y cada uno tiene una definición distinta para elemento minimal, mínimo, buen orden.

A ver si puedo poner más organizadas las definiciones de cada uno de los libros:


Definiciones "A":

-) x es un elemento mínimo de un conjunto A si y sólo si
\( x \in{A} \ \wedge \, (\forall{y })(y\in{A}\Longrightarrow{<x,y> \in{R}}) \)

-) Una relación R es reflexiva sobre un conjunto A si y sólo si
\( (\forall{x})(x \in{A}\Longrightarrow{<x,x> \in{R}}) \)

-) x es un elemento minimal de A si y sólo si
\( x \in{A} \ \wedge \, (\forall{y })(y\in{A} \ \wedge \ x\neq{y} \Longrightarrow{<y,x> \not\in{R}}) \)

-) Una relación R es un buen orden para A si y sólo si cada subconjunto no vacío de A tiene un elemento minimal y  es reflexiva, antisimétrica y transitiva sobre A.
___________

Todavía me quedan algunas dudas respecto a esto. Quería probar entonces (II) del mensaje anterior usando sólo definiciones "A". A ver qué tal:

Prueba de II)
-) Reflexividad: Supongamos \( A\neq{\emptyset} \) (Si \( A=\emptyset} \), sería reflexiva). Supongamos, por reducción al absurdo, que R no es reflexiva sobre A. Por lo tanto,


 \( (\exists{x})(x\in{A} \wedge <x,x>\not\in{R}) \)  (i).
Aquí quisiera una Contradicción. Pero no la veo.

-) Antisimetría: Quería proceder de forma similar a la reflexividad. Pero no logro nada.


Saludos,



11 Marzo, 2008, 03:25 am
Respuesta #5

León

  • Lathi
  • Mensajes: 903
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Prueba de II)
-) Reflexividad: Supongamos \( A\neq{\emptyset} \) (Si \( A=\emptyset} \), sería reflexiva). Supongamos, por reducción al absurdo, que R no es reflexiva sobre A. Por lo tanto,

 \( (\exists{x})(x\in{A} \wedge <x,x>\not\in{R}) \)  (i).
Aquí quisiera una Contradicción. Pero no la veo.

Como {x} es un subconjunto no vacío de A, tiene un mínimo que no puede ser otro que x, el único elemento de ese conjunto. Por lo tanto, por las hipótesis de II, \( (\forall{y })(y\in{A}\Longrightarrow{<x,y> \in{R}}) \) y en particular \( <x,x>\in R \). (Ahí tienes la contradicción, si quieres decirlo así, o la prueba directa, si no supones nada).

Citar
-) Antisimetría: Quería proceder de forma similar a la reflexividad. Pero no logro nada.

Mmm... con esta definición de elemento mínimo la antisimetría no es cierta (por ejemplo la relación universal, que relaciona cualquier elemento con cualquier otro, en un conjunto con mas de un elemento es un contraejemplo, con la última definición de mínimo). Pero si supones la antisimetría puedes probar que entonces sí R resulta un buen orden...

Es decir, puedes probar:

III) "Si R es una relación antisimétrica, conexa en A, y tal que todo subconjunto de A tiene un elemento mínimo entonces R es un buen orden".

15 Marzo, 2008, 01:35 am
Respuesta #6

Eleal

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 549
  • Karma: +0/-0
  • Sexo: Masculino
¿Y si se agregase a (II) como hipótesis que el mínimo de cada subconjunto no vacío es único, bastaría para probar (II) con las Definiciones "A"?

Saludos,

15 Marzo, 2008, 01:56 am
Respuesta #7

León

  • Lathi
  • Mensajes: 903
  • Karma: +0/-0
  • Sexo: Masculino

Hola. Sí, en ese caso sí se puede demostrar -espero no estar mareado con respecto a qué nos estamos refiriendo.

Saludos.

16 Marzo, 2008, 12:57 am
Respuesta #8

Eleal

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 549
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias León por tu ayuda.

Saludos