Hay rigurosa formulación y prueba de que el principio del palomar?

Question

El conocido e intuitiva principio del palomar indica que si $n$ elementos se colocan en $m$ contenedores, y $n>m$, entonces hay al menos un contenedor que tiene más de un objeto.

Siempre he invocado este principio a la hora de resolver problemas de combinatoria para las olimpiadas de matemática, donde un alto nivel de formalización no es necesario, pero recientemente he visto en un grupo de teoría de la prueba, así que me pregunto: ¿hay un matemático formal y rigurosa formulación de este principio y, si es así, ¿cuál es la prueba?

Answer 1

Sí y no. Una forma bastante precisa de la declaración del principio del palomar sería:

Si $A$ $B$ son conjuntos, y $A$ tiene más elementos de los que $B$, e $f$ es una función de $A\to B$, a continuación, $f$ no es inyectiva.

Puede probarse? De que depende. En particular, ¿qué significa "$A$ tiene más elementos de los que $B$" significa? En el normal desarrollo de la teoría de conjuntos usamos esta frase para significar lo mismo que "$A$ tiene mayor cardinalidad de a $B$", que a su vez significa

Existe una función inyectiva $B\to A$, pero no es inyectiva función de $A\to B$.

Por lo que si utilizamos esto como nuestra definición, el principio del palomar no es una cuestión de prueba, sino que es parte de la definición de lo que significa para un conjunto para ser más grande que el otro.

Por supuesto, una vez que definir los números naturales, que puede ser que desee probar un "finito principio del palomar":

Si $m$ $n$ son naturales, y $m>n$, e $A$ $m$ elementos y $B$ $n$ elementos, y $f$ es una función de $A\to B$, a continuación, $f$ no es inyectiva.

Entonces todo lo que tienes que hacer es probar esto de las definiciones de "ha $m$" y "$m<n$".

El primero de estos es bastante fácil de hacer, porque en el normal desarrollo, el número natural $m$ está representado por el conjunto de $\{0,1,2,\ldots,m-1\}$ y "ha $m$ elementos", que significa estar en bijective correspondencia precisamente por ese conjunto. Así que cuando nos tira a la basura todas esas bijections, lo que hemos de probar es que si $m>n$$f:m\to n$, $f$ no es inyectiva.

Este sería trivial (y sin sentido) si se está utilizando la cardinalidad de la definición de lo $m>n$ significa, así que a pesar de que es la opción más común, supongamos que queremos definir $m>n$ a significar "no es un "natural" $a$ tal que $m+a+1=n$.

El contenido real de la prueba que ahora es mostrar que estas dos definiciones antagónicas de $>$ de acuerdo! Por supuesto, primero tenemos que definir la adición, pero una vez que hemos hecho esto, es bastante sencillo de inducción.

Primero vamos a comprobar que $|m+1|>|m|$ (cardenales) para todos los $m$. El caso base $m=0$ es fácil. $0$ es el conjunto vacío, por lo que no hay ninguna función para$1\to 0$, así que en el imposible caso de que tenemos uno, nos puede asegurar que no va a ser inyectiva.

Para la inducción caso, suponga que $|m+1|>|m|$ y tenemos que mostrar que $|m+1+1|>|m+1|$. Deje $f: (m+1+1)\to(m+1)$, y deje $b=f(m+1)$

$$g:(m+1)\to m : x \mapsto\begin{cases}f(x) & \text{when }f(x)\ne m \\ b & \text{when }f(x)=m \end{cases}$$

Entonces, por la hipótesis de inducción $g$ no es inyectiva, por lo que no es$p$$q$$g(p)=g(q)$. Si $f(p)=f(q)$ $f$ no es inyectiva, y hemos terminado. De lo contrario,$f(p)\ne f(q)$, pero esto sólo puede ser el caso si uno de ellos es $m$ y la otra es $b$. Pero, a continuación, cualquiera de las $f(p)$ o $f(q)$ es igual a $f(m+1)$, e $f$ es de nuevo no inyectiva.

Ahora para completar la prueba, sólo tenemos que considerar el caso en que $a\ne 0$$|m+a+1|>|m+1|$. Por este tiempo, esperamos saber que la suma es conmutativa y asociativa, por lo $m+a+1=m+1+a$. Así que, si tenemos $f:(m+a+1)\to (m+1)$, entonces también es $((m+1)+a)\to(m+1)$, y su restricción a $(m+1)$ no es inyectiva. Una restricción de una función inyectiva mismo ser inyectiva, por lo $f$ no es inyectiva. (¡Uf!).

(... excepto que también nosotros debemos demostrar a lo largo de la manera en que $p+a\subseteq p$ con el estándar de representación de los números naturales; de lo contrario la restricción de los últimos $f$ $(m+a)$no tiene sentido).

---

Una tercera opción, nosotros podría también haber dicho que $m>n$ significa que $n\in m$ para el conjunto de la representación de los números. Que necesitaría una diferente de la prueba de la inducción de arriba.

Pero a pesar de todo, estas pruebas no son muy esclarecedores sobre el principio del palomar. Intuitivamente diría que el principio del palomar es al menos tan obvio como es que $m+a+1=n$ es una buena definición de $m>n$. Por lo tanto, la prueba de realidad demuestra podría ser argumenta a que el $m+a+1$ definición es razonable. Y este también sería el caso de la $n\in m$ alternativa.

Answer 2

Deje $X$ ser finito () conjunto de orden $n$, y deje $S_1, \dots, S_m\subset X$$\bigcup S_i = X$. El principio del palomar, a continuación, afirma que si $m < n$, a continuación, algunos de los $\#S_i > 1$. Por si todo lo $\#S_i \leq 1$,$n = \#X \leq \#S_1 + \cdots + \#S_m \leq m$.

Answer 3

Una prueba por inducción sobre $m$ es bastante flexible en términos de cómo se ha formalizado, es decir, "básicamente la misma prueba" funciona en distintos sistemas. Esquema:

Caso Base $m = 1$, si más de un elemento se coloca en exactamente un cuadro, luego de que la caja contiene todos los artículos. Así que en menos de una caja que tiene más de un elemento.

Supongamos que para el paso inductivo que cada vez más de $k$ elementos que se colocan en exactamente $k$ cajas, a continuación, en menos de una caja que contiene más de un elemento.

Ahora, más de $k+1$ artículos en exactamente $k+1$ cajas. Considere dos casos de lo que es en el primer cuadro:

• Más de un elemento. Entonces uno de los cuadros (es decir la primera) contiene más de un elemento.
• 1 o 0 artículos. A continuación, el resto de los elementos (de los cuales hay más de $k + 1 - 1 = k$) fueron colocados en los otros cuadros (de los que hay exactamente $k$) y, por tanto, por la hipótesis inductiva de una de las cajas contiene más de un elemento.

Así que de cualquier manera, en menos de una caja que contiene más de un elemento y la inducción es completa.

---

Nota: si se siente valiente, tomar el caso base como $m = 0$, y el estado/mostrar que no es posible poner más de $0$ elementos en $0$ cajas en todo. Pruebas por inducción donde el caso base es vacuously verdadero es más divertido ;-)

---

Ahora, ¿cómo rigurosamente la formalización de esta prueba depende, en primer lugar, en cómo se formalice "poner las cosas en cajas", y en segundo lugar sobre cómo formalizar los números naturales. Usted podría hacer esto último, ya sea por axiomatizing un sistema de Peano o utilizando el conjunto común-construcción teórica. Usted podría hacer el anterior, ya sea mediante la definición de una partición de un conjunto con $n$ elementos, donde hay $m$ define en la partición, por lo $x \in y$ significa "elemento $x$ es en el cuadro de $y$". O (equivalente) por una función de un conjunto de tamaño $n$ a un conjunto de tamaño $m$ donde $f(x) = y$ significa "elemento $x$ es en el cuadro de $y$". O de alguna otra manera. Pero en el fin de hablar sobre el tamaño de un conjunto, necesitamos que la formalización de "tamaño". Desarrollando y mostrando las propiedades necesarias es, potencialmente, el primero de dos o más clases de un "fundamentos de matemáticas" del curso, y si alguien puede encajar en un tamaño razonable respuesta a esta pregunta, a continuación, me quito el sombrero ante ellos! Me recuerda de Russell y Whitehead del Principia Mathematica, donde la página 379 contiene la proposición 54.43, junto con la observación "De esta proposición se sigue cuando aritmética además se ha definido, que $1 + 1 = 2$". Totalmente declaración formal, y la prueba de que incluso el más simple de lo que puede ser una empresa de gran envergadura, es todo una cuestión de donde se empieza.

Yo creo que usted puede llenar los detalles en mi prueba por inducción en cualquier formalismo usted está inclinado a elegir, porque todo lo que necesito es el principio de la inducción, la capacidad de considerar el primer cuadro, la capacidad de considerar "el resto de los elementos" después de descontar el 0 o el 1 de ellos, y un lexema me metí pasado sin el cual, si ha $n$ elementos y establecer uno a un lado, entonces hay $n-1$ otros. Que puede ser demostrado por inducción y se utiliza, junto con la aritmética, para probar que los dos reclamaciones en el paso inductivo acerca de los números de los elementos restantes y el resto de las casillas.

Probablemente hay algunos realmente buena manera para la formalización de estas características (además de cualquier otra cosa que he usado sin darse cuenta) y, a continuación, mostrar que la lógica del sistema que tiene esas cosas demuestra su propia versión de el Principio del Palomar, pero no tengo la teoría de que hacer, que a mí mismo. Del mismo modo, cada una de las otras respuestas aquí utiliza ciertas propiedades del sistema que se trabaja, y donde esas propiedades pueden ser asumido o se demostró, que la prueba de la obra de Principio.

Answer 4

Una manera agradable de este estado que no se basa en el hecho de contar (y funciona con cardinalidad en lugar de sólo el tamaño finito de un conjunto) sería la frase de la siguiente manera:

Deje $P$ a un y $S$ ser una partición de $P$$|S|<|P|$. Hay algunos $s\in S$, con al menos dos elementos.

que, intuitivamente dice que, en el caso finito, si $P$ $n$ elementos, entonces cualquier partición de a $n-1$ o menos series tendrá un elemento de la partición con varios miembros. La prueba de esto es fácil. Si definimos $f:P\rightarrow S$ a ser la función tal que $p\in f(p)$ - que es, $f(p)$ es el elemento de la partición que contiene a $p$ - a continuación, se sigue que la preimagen $f^{-1}[S]=S$. Si cada $S$ tenía más de un elemento, esto sería equivalente a decir que el $f$ es inyectiva y, por tanto, que el $|S|\geq|P|$. Pues, por el contrario, $|S|<|P|$ debe ser ese $f$ no es inyectiva y, por tanto, que algunos $S$ tiene más de un elemento.

Esto es suficiente para mostrar una declaración como, "no puedes particionar $\mathbb R$ en countably tantas papeleras sin una bandeja de disponer de varios elementos", al mismo tiempo, como "Si usted tiene un conjunto de $n$ palomas, no se puede dividirlos en $n-1$ agujeros sin tener un agujero con al menos $2$ palomas"

---

Aviso de que esta prueba no requiere de saber que la cardinalidad de a $A=\{1,2,\ldots,i\}$ es mayor que la de $B=\{1,2,\ldots,j\}$$i>j$. Podemos demostrarlo por inducción en $j$. Se sostiene claramente por $j=0$, ya que no hay ninguna función para el conjunto vacío a partir de un conjunto no vacío. Para el paso inductivo, aviso que si $f:A\rightarrow B$ es una inyección, entonces $$g(a)=\begin{cases}f(a) &&\text{if }f(a)<f(i)\\f(a)-1 &&\text{if }f(a)>f(i)\end{cases}$$ es una inyección de $\{1,2,\ldots,i-1\}\rightarrow\{1,2,\ldots,j-1\}$, que no puede existir por la hipótesis inductiva.

Answer 5

Para cualquier clase de $S$ natural y número de $n$, definir $\#(S) = n$ significa que $n$ es el mínimo número natural tal que hay una inyección de $f$ $S$ a $\mathbb{N}_{< n}$. Tenga en cuenta que si hay una inyección de $S$ a $\mathbb{N}_{<k}$ algunos $k \in \mathbb{N}$, la existencia de la mínima tales $k$ sigue por el buen orden que es equivalente a la inducción. Si decimos que $S$ es finito si dicha inyección existe, entonces tenemos casilleros para cualquier finito de conjuntos de $S$ $T$ tal que $\#(S) > \#(T)$, simplemente, por definición, de la siguiente manera. Si hay una inyección de $f$$S$$T$, vamos a $g$ ser una inyección de $T$ a $\mathbb{N}_{< \#(T)}$, y, a continuación, $g \circ f$ es una inyección de $S$ a $\mathbb{N}_{< \#(T)}$, lo que implica que $\#(T) \le \#(S)$, lo cual es una contradicción.

Tenga en cuenta que la anterior es una prueba sólo para el caso finito, pero sólo utiliza la aritmética de Peano, y está más en línea con la intuición. La intuición es que si usted tiene $n$ distintos objetos, necesita al menos $n$ números naturales a la etiqueta de todos los tales que cada uno tiene una etiqueta diferente, por lo que cualquier inyección (etiquetas diferentes para diferentes objetos) no se puede utilizar sólo números naturales de $0$ a estrictamente menor que $n-1$. Y queremos usar el mínimo posible de etiquetas, lo que podemos por el principio de orden. Esta aplicación del principio de buena ordenación en sí mismo puede ser probado por medio de la inducción de una forma intuitiva. Comienza por preguntar, ¿se puede utilizar sólo las etiquetas de menos de $0$? Si es así, $0$ es el mínimo posible. Si no, podemos utilizar sólo las etiquetas de menos de $1$? Si es así, $1$ es el mínimo posible. Si no, podemos utilizar sólo las etiquetas de menos de $2$? ... Si no hay un mínimo, no habrá ninguna etiqueta que utiliza delimitada etiquetas, que intuitivamente ocurre cuando tenemos una infinidad de objetos distintos, y por lo que utilizar esta etiqueta criterio para definir la finitud.