Autor Tema: Principio del palomar

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

14 Diciembre, 2020, 03:07 am
Leído 242 veces

lina.galvism

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 32
  • País: co
  • Karma: +0/-0
Hola a todos, espero se encuentren bien.

Me piden demostrar el principio del palomar como se sigue:

"Sean \( A\equiv n \) y \( B\equiv m \) con \( n, m\in\omega \) y \( m<n \). Suponga que \( f:A\longrightarrow B \) es una función. Muestre  que \( f \) no puede ser inyectiva. (donde \( \omega \))"

He escrito la siguiente demostración, agradecería sus comentarios puesto que no sé si está bien planteada la demostración.

Sean \( n, m\in\omega \) tal que \( m<n \). Sean \( g:n\longrightarrow A \) una función biyectiva, tal que para todo \( i\in n \) se tiene que \( g(i)=x_i\in A \), así que \( A=\{x_o, x_1,\cdots, x_{n-1}\} \) con \( n \) elementos y \( h:m\longrightarrow B \), una función biyectiva donde para todo \( j\in m \) le asigna  \( h(j)=y_j \), luego \( B=\{y_o,y_1,\cdots, y_{m-1}\} \) con \( m \) elementos. 

Razonando por reducción al absurdo, supongamos que la función \( f \) es inyectiva. Definamos la función \( f \) tal que para \( x_i \in A \) su imagen esta dada por \( f(x_i)=y_i \)

Claramente es una función inyectiva, puesto que para \( f(x_i)=y_i \) y \( f(x_j)=y_j \), si \( y_i=y_j \) por la inyectividad de \( h \), se sigue que \( i=j \) por tanto \( x_i=x_j \).

De lo anterior se sigue que \( B \) tiene \( n \) elementos, así que \( n=m \)\( (\rightarrow\leftarrow) \). Puesto que por hipótesis \( m<n \); el absurdo viene de suponer que \( f \) es inyectiva, por tanto \( f:A\longrightarrow B \) no puede ser inyectiva.

14 Diciembre, 2020, 11:19 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,669
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Razonando por reducción al absurdo, supongamos que la función \( f \) es inyectiva. Definamos la función \( f \) tal que para \( x_i \in A \) su imagen esta dada por \( f(x_i)=y_i \)

¿Te han dado una función \( f \) y tú defines otra función \( f \)? A partir de ahí ya no está claro dónde interviene la función que te han dado y cuál es la función que defines tú. No tienes que usar el mismo nombre para dos cosas distintas. Además, no vas a llegar muy lejos definiendo otra función inyectiva de \( A \) en \( B \), cuando ya tienes una.

Tendrías que usar las tres funciones que tienes para definir una función inyectiva de \( n \) en \( m \). Eso sí que te daría una contradicción. A cada elemento de \( n \) le asignas uno de \( A \), con \( f \) pasas a uno de \( B \) y de ahí pasas a uno de \( m \).

¿Con los resultados previos que ya tienes demostrados te basta eso para llegar a una contradicción? ¿Está claro que no puede haber una aplicación inyectiva de \( n \) en \( m \)?

16 Diciembre, 2020, 01:09 pm
Respuesta #2

lina.galvism

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 32
  • País: co
  • Karma: +0/-0
He redactado nuevamente la demostración:


Sean \( n, m\in\omega \) tal que \( m<n \). Como \( A\equiv n \) entonces existe una función \( g:n\longrightarrow A \) biyectiva y como \( B\equiv m \) entonces hay una función  \( h:m\longrightarrow B \) biyectiva.

Razonando por reducción al absurdo, supongamos que existe una función \( C:A\longrightarrow B \) inyectiva. Ahora, la función \( S=h^{-1}\circ C\circ g \), va de \( n \) en \( m \) y sabemos que la composición de funciones inyectivas es inyectiva, por tanto \( S \) es inyectiva. Luego, la función \( S_*:n\longrightarrow S_{[n]} \) es biyectiva con \( S_{[n]}\subsetneq m \)(1)

Por hipótesis tenemos que \( m<n \) así que \( m\subsetneq n \), más aun, de (1) se sigue que  \( S_{[n]}\subsetneq n \); por tanto, \( n \) es equipotente con un subconjunto propio de si mismo \( (\rightarrow\leftarrow) \). Pues \( n\in\omega \) y no existe número natural que sea equipotente con su subconjunto propio de si mismo. De lo anterior se concluye que no existe una función inyectiva \( C:A\longrightarrow B \), donde \( A\equiv n \) y \( B\equiv m \) para \( m<n \)

16 Diciembre, 2020, 03:49 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 9,669
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No puedes asegurar que \( S[n]\subsetneq m \). Sólo puedes asegurar que \( S[n]\subset m\subsetneq n \), y con eso te basta para concluir.