¿es esencial la prueba por contradicción para demostrar el Principio del Casillero?

Question

La forma estándar de demostrar el Principio de Colocación que, poniendo $n+1$ palomas en $n$ casilleros necesita la existencia de al menos un casillero con al menos 2 palomas es por contradicción. Es decir, que si es falso que haya al menos un palomar en el que haya al menos dos palomas, entonces todo palomar tiene como máximo una paloma, por lo que hay como máximo $n$ palomas.

¿Se puede evitar la prueba por contradicción?

Answer 1

Sí, puede utilizar la prueba por contrapositivo en su lugar, lo que se parece pero no requiere una contradicción. También podríamos demostrar la forma general: si al menos $mn + 1$ las palomas se clasifican en $n$ agujeros, entonces al menos un agujero contiene al menos $m + 1$ palomas.

La contraposición es: si todos los $n$ agujeros contienen como máximo $m$ palomas entonces hay como máximo $mn$ palomas. Pero esto está claro, simplemente sumamos el número de palomas en los agujeros. (Obsérvese que hay que decir "al menos $mn + 1$ palomas" y no " $mn + 1$ palomas" para que esto funcione).

Es frustrantemente común que la gente utilice la prueba por contradicción cuando una prueba por contrapositiva sería suficiente y vale la pena saber cómo detectar la diferencia. Hay una diferencia real: en cada punto de una prueba por contraposición estás escribiendo un enunciado verdadero. En una prueba por contradicción sabes que al final vas a escribir una afirmación falsa y estás esperando a ver cuándo ocurre. Es mucho más fácil cometer un error de esta manera porque los pasos intermedios de una prueba por contradicción no pueden ser inspeccionados para comprobar su validez. Si te equivocas en una prueba por contradicción, piensas que has terminado. Esta es una de las razones por las que los locos siguen presentando pruebas de una página del último teorema de Fermat, etc.

Answer 2

A continuación se presentan dos pruebas formalizadas (en Agda) de una versión del principio de casillero. La forma en que he enunciado el principio es así:

Suponga que tiene una lista de números naturales. Entonces, si la suma de los números (número de palomas) es mayor que la longitud de la lista (número de agujeros), la lista tiene un elemento mayor que 1 (el agujero tiene más de 1 paloma).

Primero tengo un par de pruebas sencillas comunes a ambos:

lift : {m : } {ms}
      [ n   ] (n  ms) × (1 < n)
      [ n   ] (n  m  ms) × (1 < n)
lift (n , nms , 1<n) = (n , there nms , 1<n)

test : (n : )  (n  1)  (1 < n)
test 0 = inj zn
test 1 = inj -refl
test (suc (suc n)) = inj (mm+n 2 n)

Aquí hay una prueba que primero demuestra la versión "negativa" del teorema:

down : {m ms}
      ( n  n  (m  ms)  n  1)
       n  n  ms  n  1
down all n nms = all n (there nms)

negative : (l : List )
          ( n  n  l  n  1)
          sum l  length l
negative [] all = -refl
negative (n  ns) all with test n
... | inj n1 = +-mono- n1 (negative ns (down all))
... | inj 1<n = -elim (< 1<n (all n (here refl)))

up : {m ms}
    m  1
    ( n  n  ms  n  1)
     n  n  m  ms  n  1
up m1 all n (here refl) = m1
up m1 all n (there nms) = all n nms

search : (l : List )
        ¬ ( n  n  l  n  1)
        [ n   ] (n  l) × (1 < n)
search [] ¬all = -elim (¬all  _ ())
search (n  ns) ¬all with test n
... | inj n1 = lift (search ns (¬all  up n1))
... | inj 1<n = n , here refl , 1<n

positive : (l : List )
          length l < sum l
          [ n   ] (n  l) × (1 < n)
positive l l<s = search l  all  < l<s (negative l all)

Intenté usar un principio clásico real en lugar de search pero en realidad terminó siendo más largo.

Aquí está la versión directa (nota, hay un caso omitido para la lista vacía en la prueba, porque el ordenador puede decir que $\mathsf{length}\ l < \mathsf{sum}\ l$ es imposible para la lista vacía):

cancel : {i j k l}  k  i  i + j < k + l  j < l
cancel {i} ki i+j<k+l =
  +-cancel-< i (<-trans i+j<k+l (+-mono- _ ki))

positive : (l : List )
          length l < sum l
          [ n   ] (n  l) × 1 < n
positive (n  ns) l<s with test n
... | inj 1<n = (n , here refl , 1<n)
... | inj n1 = lift (positive ns (cancel n1 l<s))

Como puedes ver, la prueba de la afirmación negativa es estructuralmente casi la misma que la prueba directa de la afirmación positiva, porque ambas se limitan a hacer inducción sobre la lista. Probar la versión negativa primero sólo llevó a un trabajo extra derivando la declaración deseada real después (que en sí mismo es casi tan largo como la prueba directa).

En casos como éste -proposiciones decidibles sobre números finitos-, procedimientos como $\mathsf{search}$ permiten utilizar la prueba por contradicción de forma constructiva. Puedes ver esto como que la lógica clásica está justificada, o que no añade ningún poder esencial en esos casos.

Sin embargo, tampoco es necesariamente el caso de que la prueba por contradicción haga que tus pruebas sean más fáciles/cortas. A menudo, los matemáticos utilizan este tipo de pruebas por costumbre, más que porque sean necesarias o (por cualquier medida) beneficiosas. Podrías suponer que ya has demostrado la afirmación negativa, supongo, pero también podrías haber demostrado el principio de encasillamiento y derivar de él la afirmación negativa.

Aquí es el archivo completo que contiene las pruebas.

Hay versiones del principio de encasillamiento en las que la prueba directa es mucho más difícil que la de aquí. Sin embargo, la razón por la que son difíciles tiene que ver con la manipulación de funciones entre tipos finitos, que es el análogo de $\mathsf{cancel}$ . Es posible que la prueba indirecta sea más fácil en ese caso, pero los análogos de hechos sobre el ordenamiento en él también van a ser más difíciles de probar.

Answer 3

El principio es fácil de demostrar mediante inducción .

La afirmación es válida para $n = 1$ En ese caso, usted tiene $2$ palomas en el palomar único. Supongamos que la afirmación es válida para $n$ y considerar $n+2$ palomas en $n+1$ casilleros. Entonces, o bien hay al menos $2$ número de palomas en el palomar $n+1$ o hay como máximo $1$ número de paloma en el casillero $n+1$ . En este último caso, hay menos $n+1$ palomas en los casilleros con números $1$ a $n$ . Por la hipótesis inductiva, uno de estos casilleros debe contener al menos $2$ palomas.