prueba sencilla del principio de las palomas

Question

Debo demostrar el principio de las palomas, pero las pruebas que encuentro en Internet son demasiado complejas. Esto es lo que puedo usar:

Definición $$I_n = \{p\in \mathbb{N}; p\le n\}$$

El principio de las palomas establece que si $m>n$ entonces no puede existir una función inyectiva $I_n\to I_m$ .

Ya he demostrado que si existe una biyección desde $I_n$ a $I_m$ entonces $n=m$ pero soy incapaz de probarlo sólo por una inyección. ¿Podrían ayudarme?

Answer 1

¿Quizás escriba algo mal? (Esto me parece fácil).

En primer lugar, creo que quieres decir que no puede existir una función inyectiva $f:I_m\to I_n$ ya que si $n<m$ existe en realidad un $I_n\to I_m$ (la inclusión).

Supongamos que $n<m$ y $f:I_m\to I_n$ inyectiva. Entonces $f:I_m\to f(I_m)$ es biyectiva, donde $f(I_m)=\{f(1),...,f(m)\}$ . Claramente $f(I_m)$ tiene $m$ elementos, entonces $m\le n$ porque $f(I_m)\subseteq I_n$ .

Answer 2

Aquí hay una prueba de que si $n<m$ son números naturales, entonces toda función $f : I_m \to I_n$ es no inyectiva. La prueba es por inducción en $n$ .

Consideremos primero el caso base $n=1$ y así $m \ge 2$ . Entonces $f(1)=f(2)=1$ y así $f$ no es inyectiva.

Supongamos ahora la hipótesis de inducción: la afirmación es verdadera para $n=k$ . Debemos demostrar que la afirmación es verdadera para $n=k+1$ . Considere $m > k+1$ y cualquier función $f : I_m \to I_{k+1}$ . Argumentando por contradicción, supongamos que $f$ es inyectiva. Consideremos $f(m) \in I_{k+1}$ . Desde $f$ es inyectiva, la restricción $f | I_{m-1}$ también es inyectiva, y la imagen de $f | I_{m-1}$ está contenido en el conjunto $I_{k+1}-\{f(m)\}$ . Existe una biyección $$g : I_{k+1}-\{f(m)\} \to I_k $$ dado por la fórmula $$g(i) = \begin{cases} j & \quad \text{if $1 \le j < f(m)$} \\ j-1 &\quad\text{if $f(m)<j\le k+1$} \end{cases} $$ Obtenemos así una inyección $g \circ (f | I_{m-1}) : I_{m-1} \to I_k$ contradiciendo la hipótesis de la inducción.