Autor Tema: Dada una relación definida sobre un conjunto finito probar orden total y hallar

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

13 Noviembre, 2019, 08:38 am
Respuesta #10

Luis Fuentes

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

\begin{align*}
((x\leq y\wedge\text{\(x+y\) es par})\wedge(y\leq z\wedge\text{\(y+z\) es par}))&\vee((x\leq y\wedge\text{\(x+y\) es par})\wedge(\text{\(y\) es impar e \(z\) es par}))\\
&\vee((\text{\(x\) es impar e \(y\) es par})\wedge(y\leq z\wedge\text{\(y+z\) es par}))\\
&\vee((\text{\(x\) es impar e \(y\) es par})\wedge(\text{\(y\) es impar e \(z\) es par}))
\end{align*}

La primera disyunción es claramente \( xRz \), pero no sé cómo descartar (o convertirlas en contradicción) las otras tres disyunciones ???. ¿Alguna ayuda?

En la segunda: si \( y \) es impar y \( x+y \) es par, entonces \( x \) es impar. Pero como \( z \) es par, \( xRz \).

En la tercera: si \( y \) es par y \( z+y \) es par, entonces z es par y como \( x \) es impar, \( xRz \).

En la cuarta: si \( x  \)es impar y \( z \) es par directamente \( xRz \).



Ahora vienen mis problemas que "no me dejan dormir"...:

Citar
Sea \( A \) de \( n \) elementos, con una relación de orden total.

Hasta aquí te sigo.

Hago una observación; he dicho que \( A \) tiene una relación de orden total y la estoy denotando por \( \leq \). También cuando en la demostración aparecen números uso \( \leq \) con el significado usual (la relación de orden usual en los naturales). Espero que eso no te cause confusión. Si no se podría denotar la relación de orden  en \( A \) como \( R \).

Citar
Para cada \( a\in A \) definimos:

\(  f(a)=cardinal\{b\in A|b\leq a\} \)

Acá ya me perdí. ¿Quién te da el derecho a elegir esa "función" y por qué?

Esa pregunta me hace gracia. La elijo "porque me da la gana" o "porque el espíritu de Gauss me la susurró una noche".  :D A donde voy es que no te hace falta saber porque se me ocurrió elegir esa función para entender la demostración y comprobar que funciona. De todas forma en el Spoiler te lo cuento.

Spoiler
Fíjate que el resultado que queremos probar es muy intuitivo, diría obvio. Una relación de orden total nos permite "ordenar" en fila los elementos. Si tenemos un número finito, esa fila tiene un extremo a la derecha que es el máximo.

A la hora de demostrar esto le estuve dando algunas vueltas; primero se me ocurrió un argumento inductivo; algo así como: tomo un elemento cualquiera, si no es máximo es porque hay otro mayor; luego para ese otro digo lo mismo sino es máximo es que hay otro mayor; y así sucesivamente. Y como son un número finito termino. Pero me era algo farragoso de escribir.

Entonces pensé esta otra idea. Para cada elemento "cuento" cuantos elementos hay menores o iguales que él con nuestra relación de orden; el máximo que busco cumplirá que TODOS son menores o iguales que él. Luego se trata de localizar el elemento que tiene el mayor número posible de elementos menores o iguales que él y ver que son todos. Esa es la idea de lo que estoy haciendo.
[cerrar]

Citar
¿No deberías probar que \( f \) es primero función para luego seguir con la demostración (por más trivial que parezca aunque no lo veo tan trivial con ojos de novato)?


Si quieres detallarlo hazlo. Pero es evidente. Cada elemento tiene de manera inequívoca definida su imagen: el número de elementos menores o iguales que él. ¿Dónde esta el problema o la posible ambigüedad?.

Citar
¿Por qué no puedo elegir otro objeto matemático?

 :D Podrías elegir infinidad de objetos matemáticos; yo he elegido esa función porque es la que formaliza la idea que coloquialmente expuse en el spoiler.

Citar
"De acuerdo". ¿Por qué decís "El conjunto \( \{f(a)|a\in A\} \)" en vez de "El conjunto \( \{b\in A|a\in A\} \)"?

Por que me interesa localizar el elemento que tiene el mayor número de elementos menores o iguales que él. Eso corresponde al mayor valor de la función \( f \).

El conjunto \( \{b\in A|a\in A\} \) es \( A \) y yo no se si tiene máximo. Es precisamente lo que quiero probar.

Citar
Veamos que \( f(a_0)=n \).

¿Eso es porque querés demostrar que \( f(a_0) \) es efectivamente la menor de las cotas superiores i.e. es el máximo?

No. Eso es porque quiero probar que el elemento \( a_0 \) tienes \( n \) elementos menores o iguales que él. Como he comenzado diciendo que \( A \) tiene \( n \) elementos, eso querrá decir que todos los elementos de \( a \) son menores o iguales que \( a_0 \) y por tanto \( a_0 \) es el máximo.

Citar
Entiendo que en otro caso sea \( cardinal\{b\in A|b\leq a\}<n \) pues nunca puede ser \( >n \), pero no entiendo de dónde sale ese \( n=card(A)=|A| \).

Pues porque he comenzado diciendo que \( A \) es un conjunto de \( n \) elementos, es decir, que \( card(A)=n \).

Citar
Como la relación es de orden total, necesariamente \( a_0<a_1 \) (...)

¿Por qué \( a_0<a_1 \) y no \( a_1<a_0 \)? Yo lo interpretaría así: "necesariamente \( f(a_0)<f(a_1) \)".

Porque \( a_1 \) es un elemento (está dicho antes) que cumple \( a_1\not\leq a_0 \) y por eso no puede ocurrir que \( a_1<a_0 \).

Y efectivamente de ahí se deduce que \( a_1 \) tiene más elementos menores o iguales que el que \( a_0 \): todos los que tenía \( a_0 \) y además \( a_1 \) y por eso \( f(a_0)<f(a_1) \), lo cual contradice que \( f(a_0) \) fuese el máximo.

Hago hincapié en lo que dije al principio. Cuando trabajo con elementos de \( A \) la relación de orden la denoto por \( \leq \), pero no sabemos todavía si todo conjunto finito tiene máximo: es lo que queremos probar. Cuando trabajo con elementos \( f(a) \) son ya números naturales y ahí la relación de orden es la usual para esos números y sabemos que todo conjunto acotado superiormente tiene máximo.

Saludos.

P.D. Por cierto que la función \( f \) que he definido sirve de hecho para mostrar que toda relación de orden total en un conjunto finito de \( n \) elementos es isomorfa a la relación de orden usual en los primer \( n \) números naturales.

13 Noviembre, 2019, 01:17 pm
Respuesta #11

manooooh

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

Luego lo miro con más detalle, pero tengo una duda:

Decís que denotaste la relación \( R \) por \( \leq \) cuando hablamos de los elementos de la forma \( a_i,b \). Cuando se le aplica la función \( f \) pasan a ser naturales y ahí se usa el orden usual de los naturales.

Pero mi duda es: ¿Qué significa entonces \( a_1<a_0 \)? ¿Significa \( a_1\!\!\!\not Ra_0\equiv(a_1,a_0)\notin R \)?

Saludos

13 Noviembre, 2019, 02:05 pm
Respuesta #12

Luis Fuentes

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

Pero mi duda es: ¿Qué significa entonces \( a_1<a_0 \)? ¿Significa \( a_1\!\!\!\not Ra_0\equiv(a_1,a_0)\notin R \)?

\( a_1<a_0 \) significa \( a_1Ra_0 \) y \( a_1\neq a_0 \).

Y por completar:

\( a\leq b \) significa \( aRb \)
\( a>b \) significa \( a\not R b \)
\( a\geq b \) significa \( a\not R b \) ó \( a=b \).

Saludos.

15 Noviembre, 2019, 01:44 am
Respuesta #13

manooooh

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

En la segunda: si \( y \) es impar y \( x+y \) es par, entonces \( x \) es impar. Pero como \( z \) es par, \( xRz \).

En la tercera: si \( y \) es par y \( z+y \) es par, entonces z es par y como \( x \) es impar, \( xRz \).

En la cuarta: si \( x  \)es impar y \( z \) es par directamente \( xRz \).

De acuerdo. Gracias.

Hago una observación; he dicho que \( A \) tiene una relación de orden total y la estoy denotando por \( \leq \). También cuando en la demostración aparecen números uso \( \leq \) con el significado usual (la relación de orden usual en los naturales). Espero que eso no te cause confusión. Si no se podría denotar la relación de orden  en \( A \) como \( R \).

Luis quiero estar en tu cabeza: ¿Por qué se te ocurrió definir a una misma cosa (el \( \leq \)) con dos significados distintos?

¿No era más fácil escribir \(  f(a)=cardinal\{b\in A|b\leq a\} \), ... como \(  f(a)=|b\in A|bRa| \), ...?

Esa pregunta me hace gracia. La elijo "porque me da la gana" o "porque el espíritu de Gauss me la susurró una noche".  :D A donde voy es que no te hace falta saber porque se me ocurrió elegir esa función para entender la demostración y comprobar que funciona. De todas forma en el Spoiler te lo cuento.

Spoiler
Fíjate que el resultado que queremos probar es muy intuitivo, diría obvio. Una relación de orden total nos permite "ordenar" en fila los elementos. Si tenemos un número finito, esa fila tiene un extremo a la derecha que es el máximo.

A la hora de demostrar esto le estuve dando algunas vueltas; primero se me ocurrió un argumento inductivo; algo así como: tomo un elemento cualquiera, si no es máximo es porque hay otro mayor; luego para ese otro digo lo mismo sino es máximo es que hay otro mayor; y así sucesivamente. Y como son un número finito termino. Pero me era algo farragoso de escribir.

Entonces pensé esta otra idea. Para cada elemento "cuento" cuantos elementos hay menores o iguales que él con nuestra relación de orden; el máximo que busco cumplirá que TODOS son menores o iguales que él. Luego se trata de localizar el elemento que tiene el mayor número posible de elementos menores o iguales que él y ver que son todos. Esa es la idea de lo que estoy haciendo.
[cerrar]

Muy interesante.

:D Podrías elegir infinidad de objetos matemáticos; yo he elegido esa función porque es la que formaliza la idea que coloquialmente expuse en el spoiler.

Eso no es cierto. Decís que el objeto que formaliza tu idea es \( f \) pero si quiero usar una transformación lineal entre espacios vectoriales (uno de infinitos objetos matemáticos), ¿también sirve? O usar una función multivariable de números complejos. O sea comparto que escogiste correctamente a la función, pero no es cierto que haya más alternativas además de hacerlo por "fuera bruta".

Por cierto, ¿\( f \) es una función que va de \( A \) en \( \Bbb{N} \)?

Creo que el resto de tu explicación me quedó claro.

P.D. Por cierto que la función \( f \) que he definido sirve de hecho para mostrar que toda relación de orden total en un conjunto finito de \( n \) elementos es isomorfa a la relación de orden usual en los primer \( n \) números naturales.

:o.

Saludos

15 Noviembre, 2019, 08:04 am
Respuesta #14

Luis Fuentes

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

Luis quiero estar en tu cabeza: ¿Por qué se te ocurrió definir a una misma cosa (el \( \leq \)) con dos significados distintos?

¿No era más fácil escribir \(  f(a)=cardinal\{b\in A|b\leq a\} \), ... como \(  f(a)=|b\in A|bRa| \), ...?

Pues porque es usual denotar a cualquier relación de orden  y más aun si es de orden total por \( \leq \), que es el símbolo que evoca un orden.

Citar
Eso no es cierto. Decís que el objeto que formaliza tu idea es \( f \) pero si quiero usar una transformación lineal entre espacios vectoriales (uno de infinitos objetos matemáticos), ¿también sirve? O usar una función multivariable de números complejos. O sea comparto que escogiste correctamente a la función, pero no es cierto que haya más alternativas además de hacerlo por "fuera bruta".

No me expliqué bien. Escogí la \( f \) porque me sirve para probar lo que quiero. Evidentemente "cualquier cosa" no me serviría. Entonces es eso lo que quise decir, que entre las muchas cosas que puedo usar, escojo las útiles en ese momento.

Por ora parte si hay alguna otra alternativa, como la demostración por inducción que esbocé en el Spoiler.

Citar
Por cierto, ¿\( f \) es una función que va de \( A \) en \( \Bbb{N} \)?

Si.

Saludos.

16 Noviembre, 2019, 10:36 pm
Respuesta #15

manooooh

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

Sí, yo también me expresé mal cuando dije de que "no hay nada más además de lo que mostraste" porque está el argumento inductivo de tu spoiler. Me quería referir a que no cualquier concepto matemático responde al apartado (b).

Gracias.

Saludos