Prueba por inducción respecto de las inyecciones y parte del principio del palomar

Question

Demostrar la siguiente implicación por inducción en $m$:

Si existe una inyección de $N_m \rightarrow N_n$,$m \le n$.

$N_n$ $N_m$ son conjuntos con $n$ $m$ elementos, respectivamente.

Yo sé cómo hacer pruebas por inducción, estoy luchando con el paso inductivo. Hasta ahora tengo el predicado P(n) = Si existe una inyección de $N_m \rightarrow N_n$,$m \le n$.

He probado el "caso base P(1) = Si existe una inyección de $N_1 \rightarrow N_n$, $1 \le n$" descuidadamente diciendo ningún elemento en $N_n$ puede ser asignado a más de un elemento de $N_1$ porque hay un solo elemento en $N_1$. No debe, al menos, uno de los elementos en $N_n$ en orden para que sea una función, por lo $1 \le n$.

Así que yo sé que la hipótesis inductiva es P(k) = Si existe una inyección de $N_k \rightarrow N_n$,$k \le n$. Ahora tengo que demostrar que P(k+1) = Si existe una inyección de $N_{k+1} \rightarrow N_n$,$k+1 \le n$, pero estoy ni idea acerca de cómo hacer este paso.

Answer 1

Para cualquier $f: N_m \rightarrow N_n$ si $m > n$, luego por el Principio del Palomar (al menos) dos elementos de la $N_m$ debe ser enviada en el mismo elemento de $N_n$. A continuación, $f$ no es inyectiva. Ahora toma el contrapositivo.

Leyenda: (que creo que no es conocido?) el Principio del Palomar es muy similar a la del Principio de la Inducción Matemática. Véase, por ejemplo, este artículo. Sin embargo, las críticas se pueden encontrar aquí , así como en La complejidad del Principio del Palomar por M. Ajtai, en el que PHP se muestra (en algún sentido) más fuerte que el PMI.

Answer 2

La afirmación es verdadera para $m=1$: Si hay un mapa de $f:\{1\}\to N_n$, entonces necesariamente $n\geq1$.

Supongamos que el enunciado es verdadero para $m\geq1$ y que nos da una inyectiva mapa de $f:\ [m+1]\to [n]$. Tenemos que probar que $m+1\leq n$. Podemos distinguir dos casos:

(a) $\quad f(r)\ne n$ todos los $r\in[m]$.

En este caso la restricción de $f$ $[m]$proporciona una inyectiva mapa de $f':\ [m]\to[n-1]$. Por la hipótesis de inducción se sigue que $m\leq n-1$. Por lo tanto, tenemos $m+1\leq n$ en este caso.

(b) $\quad f(r)=n$ para $r\in[m]$.

En este caso,$f(m+1)<n$. Por lo tanto, la nueva función $$f'(k):=\cases{f(k) &$k\in[m], \ k\ne r$\cr f(m+1) &$(k=r)$\cr}$$ es una función inyectiva $f':\ [m]\to[n-1]$. Por la hipótesis de inducción se sigue otra vez ese $m\leq n-1$ o $m+1\leq n$.