¿Cuáles son algunos ejemplos interesantes de prueba por contrapositivo?

El contrapositivo de la declaración

[matemáticas] p \ rightarrow q [/ matemáticas]

es la declaración

[matemáticas] \ neg \, q \ rightarrow \ neg \, p [/ matemáticas].

Las dos declaraciones son lógicamente equivalentes , lo que significa que ambas son verdaderas o ambas falsas. A veces es más fácil demostrar una implicación demostrando su contrapositivo .


Ejemplo. Deje [math] a, b, n \ in \ mathbb Z [/ math]. Pruebalo

Si [math] n \ nmid ab [/ math], entonces [math] n \ nmid a [/ math] y [math] n \ nmid b \ ldots (1) [/ math]

Prueba . Probamos el enunciado [math] (1) [/ math] al probar su enunciado contrapositivo

Si [math] n \ mid a [/ math] o [math] n \ mid b [/ math], entonces [math] n \ mid ab \ ldots (2) [/ math]

El resto de la prueba es una aplicación directa de la definición de divisibilidad.

Si [math] n \ mid a [/ math], entonces [math] a = nc [/ math] para algunos [math] c \ in \ mathbb Z [/ math]. Por lo tanto, [math] ab = n (cb) [/ math], de modo que [math] n \ mid ab [/ math]. La prueba del caso [matemática] n \ mid b [/ matemática] es idéntica. [matemáticas] \ blacksquare [/ matemáticas]


Observación. ¿Cómo probarías la declaración [matemática] (1) [/ matemática] directamente? ¿Eso sería más fácil?

Una de las pruebas más famosas de todos los tiempos, irónicamente, una que se cita incorrectamente como un ejemplo de prueba por contradicción [1], es una prueba por contraposición.

En 1891, Georg Cantor asumió que hay un conjunto T que contiene cada cadena de longitud infinita [2] que mezcla solo dos caracteres. Usó ‘m’ y ‘w’, pero seguiré el ejemplo de Wikipedia y usaré ‘0’ y ‘1’ (así como sus nombres para conjuntos).

Luego asumió que hay un subconjunto infinito de T , llamado S , que puede estar en una lista ordenada [3]. Que esto sea posible es trivial para demostrar:

  • s (1) = 1000000 …
  • s (2) = 0100000 …
  • s (3) = 0010000 …
  • etc.

Tenga en cuenta que esto es solo un ejemplo, la prueba no especifica el conjunto S. Tenga en cuenta también que cada cadena tiene infinitos ‘0’ después de ‘…’, y que hay infinitas cadenas de este tipo en la lista.

Al hacer una nueva cadena d cuyo enésimo carácter es el carácter opuesto del Enésimo carácter en s (n), Cantor demostró que d no puede estar en S , pero por definición debe estar en T. De este modo se demuestra que “si S se puede poner en una lista ordenada, entonces S no contiene todos los elementos de T “.

El contrapositivo de esta afirmación probada es “Si S contiene todos los elementos de T , entonces S no se puede poner en una lista ordenada”.

Quizás esto se llama prueba por contradicción porque Cantor usó términos que, cuando se traducen del alemán al inglés, pueden significar “contradicción”. Pero lo que quiso decir fue que la contradicción entre ” S contiene todos los elementos de T ” y “Hay un elemento de T que no es S ”mostró que estas declaraciones eran negaciones entre sí; es decir, P2 y ¬P2 utilizados en contraposición.

+++++

[1] Para probar la afirmación P por contradicción, primero asume ¬P. Luego muestra que otra afirmación Q se deduce de ¬P, donde Q se sabe que es falso (o equivalentemente, ¬Q se sabe que es verdadero). Esta contradicción demuestra que su suposición es incorrecta, por lo que P debe ser cierto.

Se afirma que la prueba en cuestión supone tanto ¬P1 como ¬P2. Pero lo que muestra es que P2 se deduce de asumir ¬P1 solo. La afirmación es que la suposición de ¬P2 hace la contradicción, por lo que P1 y P2 no pueden ser ciertos. De hecho, es una prueba, pero no por contradicción. Probar “Si ¬P1 entonces P2” prueba “Si ¬P2 entonces P1”.

[2] La prueba no era sobre números reales, como se suele afirmar. De hecho, en la introducción, Cantor dice específicamente que no se trata de números reales.

[3] Esta es la declaración que llamé ¬P1 arriba. ¬P2 es ” S es todo de T “, pero nunca se supone en la prueba.