Cuándo utilizar el contrapositivo para demostrar una afirmación

Question

Mi pregunta trata de abordar la intuición o las situaciones en las que utilizar el contrapositivo para demostrar un enunciado matemático es un intento adecuado.

Siempre que tengamos un enunciado matemático de la forma $A \implies B$ siempre podemos intentar demostrar el contrapositivo en su lugar, es decir $\neg B \implies \neg A$ . Sin embargo, lo que me parece interesante de pensar es, ¿cuándo debe ser prometedor este enfoque? ¿Cuándo es una buena idea, cuando se trata de demostrar algo, utilizar el contrapositivo? ¿Cuál es la intuición que $A \implies B$ puede ser más difícil de hacer directamente que si se intenta hacer el contrapositivo?

Estoy buscando más bien un conjunto de directrices o intuiciones o heurística que podría sugerir que intentar utilizar el contrapositivo para demostrar el enunciado matemático podría ser una buena idea.

Algunos problemas tienen estructuras que hacen más "obvio" intentar la inducción o la contradicción. Por ejemplo, en los casos en los que hay una recursión o algo que se itera, a veces la inducción es la forma natural de intentar el problema. O cuando algún objeto matemático tiene la propiedad X, entonces suponer que no tiene la propiedad X puede parecer prometedor porque suponer lo contrario podría llevar a una contradicción. Así que me preguntaba si había algo análogo a probar cosas usando el contrapositivo.

Me preguntaba si la comunidad tiene un buen conjunto de heurísticas para cuando enseñan que podría ser una buena idea usar el contrapositivo en una prueba.

Además, esta pregunta podría beneficiarse de algunos ejemplos simples, pero muy perspicaces, que muestren por qué la negación podría ser más fácil de demostrar. Además, sé que esta intuición puede adquirirse a partir de la experiencia, por lo que proporcionar ejemplos buenos o sólidos podría ser una gran forma de contribuir. Eso sí, ¡no olvides decir qué tipo de intuición intentas enseñar con tus ejemplos!

Tenga en cuenta que probablemente no estoy esperando un algoritmo mágico súper general de prueba real porque un algoritmo como ese probablemente podría ser utilizado para automatizar prooving, lo que podría implicar algo grande como $P=NP$ . (Obviamente una prueba de P vs NP siempre es interesante, pero creo que pedir a la comunidad que pruebe la P vs NP no es algo realista).

Answer 1

La contraposición suele ser útil cuando una implicación tiene múltiples hipótesis, o cuando la hipótesis especifica múltiples objetos (quizás infinitos).

Como ejemplo simple (y podría decirse que artificial), compare, para $x$ un número real:

1(a). Si $x^4 - x^3 + x^2 \neq 1$ entonces $x \neq 1$ . (No es fácil de ver sin una contraposición implícita )

1(b). Si $x = 1$ entonces $x^4 - x^3 + x^2 = 1$ . (Inmediatamente obvio.)

He aquí un clásico del análisis real elemental, con $x$ de nuevo por un número real:

2(a). Si $|x| \leq \frac{1}{n}$ para cada número entero positivo $n$ entonces $x = 0$ .

Esto es cierto, pero es incómodo de demostrar directamente porque hay efectivamente infinitas hipótesis (una por cada positivo $n$ ), pero ningún número finito de estas hipótesis implica la conclusión .

2(b). Si $x \neq 0$ existe un número entero positivo $n$ tal que $\frac{1}{n} < |x|$ .

La contrapositiva, que se desprende inmediatamente de la propiedad arquimediana, sólo requiere una estrategia para mostrar algunos La hipótesis se viola si la conclusión es falsa.

3(a). Si $f$ es una función continua de valor real sobre $[0, 1]$ y si $$ \int_0^1 f(x) g(x)\, dx = 0\quad\text{for every continuous $ g $,} $$ entonces $f \equiv 0$ .

3(b). Si $f$ es una función continua de valor real sobre $[0, 1]$ que no es indénticamente cero, entonces $$ \int_0^1 f(x) g(x)\, dx \neq 0\quad\text{for some continuous $ g $.} $$

Aquí la contraposición no es especialmente útil porque el elección específica $f = g$ da cualquier dirección. Es decir, 3(a) tiene infinitas hipótesis, pero un de ellos es suficiente para deducir la conclusión.

Contrasta con el aspecto superficialmente similar:

4(a). Si $f$ es una función continua de valor real sobre $[0, 1]$ y si $$ \int_0^1 f(x) g(x)\, dx = 0\quad\text{for every non-negative step function $ g $,} $$ entonces $f \equiv 0$ .

4(b). Si $f$ es una función continua de valor real sobre $[0, 1]$ que no es indénticamente cero, entonces $$ \int_0^1 f(x) g(x)\, dx \neq 0\quad\text{for some non-negative step function $ g $.} $$

(Esquema de 4(b): Si $f$ no es idéntico $0$ Hay un $x_0$ en $(0, 1)$ tal que $f(x_0) \neq 0$ . Por continuidad, existe un $\delta > 0$ tal que $[x_0 - \delta, x_0 + \delta] \subset (0, 1)$ y $|f(x)| > |f(x_0)|/2$ para todos $x$ con $|x - x_0| < \delta$ . Dejemos que $g$ sea la función característica de $[x_0 - \delta, x_0 + \delta]$ .)

Al igual que en 2(a), la hipótesis de 4(a) comprende infinitas condiciones, y ningún número finito es suficiente. En este caso, el contrapositivo 4(b) surge de forma natural, ya que al intentar establecer 4(a) directamente uno se ve obligado a preguntarse cómo puede fallar la conclusión.

Answer 2

Aquí tienes algunos ejemplos, espero que te sirvan de ayuda. Primero uno fácil.

Teorema . Dejemos que $n$ sea un número entero. Si $n$ es incluso entonces $n^2$ está en paz.

Prueba (esquema). Sea $n$ sea par. Entonces $n=2k$ para algún número entero $k$ Así que $n^2=4k^2=2(2k^2)$ que es par.

Ahora intente lo contrario por el mismo método.

Teorema . Dejemos que $n$ sea un número entero. Si $n^2$ es incluso entonces $n$ está en paz.

Prueba (intento). Supongamos que $n^2$ es incluso, digamos $n^2=2k$ . Entonces $n=\sqrt{2k}$ y así... ???? Esto no parece tener solución, $\sqrt{2k}$ no parece un número entero en absoluto, ¡no importa probar que es par!

Ahora trata de demostrar lo contrario utilizando su contrapositivo.

Teorema . Dejemos que $n$ sea un número entero. Si $n^2$ es incluso entonces $n$ está en paz.

Prueba . Tenemos que demostrar que si $n$ es impar, entonces $n^2$ es impar. Entonces, dejemos que $n=2k+1$ Entonces $n^2=4k^2+4k+1=2(2k^2+2k)+1$ que es impar. ¡Listo!

Creo que el punto aquí es que para el intento de una prueba directa comenzamos con $n^2=2k$ . Esto nos da implícitamente alguna información sobre $n$ pero es bastante indirecta y difícil de conseguir. El uso del contrapositivo comienza con $n=2k+1$ que nos da una información muy clara y utilizable sobre $n$ .

Quizás se podría poner una heurística de la siguiente forma "prueba ambas formas, sólo durante un par de pasos, y mira si alguna parece notablemente más fácil que la otra".

Answer 3

PS esta respuesta es sólo un borrador, tal vez voy a añadir más tarde

En general, hay 6 formas de demostrar los teoremas condicionales.

Creo que si quieres probar $ P \to Q $ tiene las siguientes 6 opciones (se detallan más adelante)

1. Prueba condicional directa
2. Prueba contrapositiva directa
3. Prueba indirecta condicionada
4. Prueba indirecta contrapuesta
5. Prueba indirecta
6. Prueba contrapositiva indirecta

La forma más fácil en tu caso depende de cuál sea el teorema que quieres demostrar, creo que en general:

• empezar con lo que son las declaraciones más fáciles.

• Intentar empezar con afirmaciones positivas (la negación sólo añade un nivel extra de complejidad).

• si sólo una de las fórmulas " $ P \lor \lnot P $ " $ ( \forall x P(x) \lor \forall x \lnot P(x) ) $ o " $ Q \lor \lnot Q $ " $ ( \forall x Q(x) \lor \forall x \lnot Q (x) )$ es demostrable, prefiere la negación de esa variable sobre la negación de la otra.

• La prueba condicional directa es la mejor (es constructiva)

• A continuación, los métodos 2, 3 y 4.

• Utiliza sólo una de las pruebas indirectas si todo lo demás falla (porque añaden una capa extra de negación), si actúas así posiblemente no tendrás que volver a utilizar el método indirecto, aunque muchos argumentarán que los métodos 3 y 4 son sólo métodos de prueba indirecta disfrazados.

PS 1 los nombres de los métodos 2, 3, 4 y 6 son propios, no existe una terminología oficial. (Me los acabo de inventar mientras pensaba en la pregunta)

PS 2 Por supuesto, hay muchas combinaciones posibles de los 6 métodos que he mencionado, e incluso es cierto que una "Prueba indirecta condicional" es una combinación de una "Prueba indirecta" dentro de una "Prueba directa", pero las he organizado un poco para que se mencionen todos los métodos principales (en mi opinión).

PS 3 todos los métodos de prueba que contengan una "eliminación de negación doble" (~~Eliminación) son no constructivo (pruebas que $ P \to Q $ es un teorema, pero no han encontrado un método para transformar una P en una Q), pero de hecho todos, excepto el método de demostración directa, contienen ~~Eliminaciones.

PS 4 Pruebas para obtener $ P \to Q $ de $ \lnot Q \to \lnot P $ :

Esta prueba contiene en sí misma una eliminación de la negación doble, por lo que todas las pruebas que conducen a $ \lnot Q \to \lnot P $ son no constructivo.

1 | . . . ~Q -> ~P       proved before
2 | |____ P              Assumption
3 | | |__ ~Q             Assumption
4 | | | . ~P             1,3 -> Eliminations
5 | | | . contradiction  2,3 contradiction Introduction
. | | <----------------------- end subproof
6 | | . . ~~Q            3-5 ~ Introduction
7 | | . . Q              6   ~~Elimination
. | <------------------------- end subproof
8 | . . . P -> Q         2-7 ->Introduction

Los diferentes métodos:

1) Prueba condicional directa

• Supongamos que P
• de alguna manera llegar a Q
• introducción de la implicación

Prueba formal

1 | |____ P          Assumption
: | | : : ?????????     some aplications of inference rules
: | | : : ?????????     some aplications of inference rules
k | | . . Q             inference rule
. | <-------------------- end subproof
m | . . . P -> Q     1-k -> Introduction

2) Prueba contrapositiva directa

• Supongamos que ~Q
• de alguna manera llegar a ~P
• introducción de la implicación

Prueba formal

1 | |____ ~Q          Assumption
: | | : : ?????????      some aplications of inference rules
: | | : : ?????????      some aplications of inference rules
k | | . . ~P             inference rule
. | <--------------------- end subproof
m | . . . ~Q -> ~P    1-k ->  Introduction

3) Prueba indirecta condicional

• Supongamos que P
• Supongamos que ~Q
• alguna contradicción
• Reductio ad absurdum
• introducción de la implicación

Prueba formal

1 | |____ P              Assumption
: | | : : ?????????         some aplications of inference rules
: | | : : ?????????         some aplications of inference rules
a | | |__ ~Q             Second Assumption
: | | | : ?????????         some aplications of inference rules
: | | | : ?????????         some aplications of inference rules
i | | | . contradiction     contradiction Introduction
. | | <---------------------- end subproof
j | | . . ~~Q            a-i ~ Introduction
k | | . . Q              j   ~~Elimination
. | <------------------------ end subproof 
m | . . . P -> Q         1-k ->  Introduction

Los resultados entre la línea 1 y a pueden ser interesantes por su propio acuerdo, por eso este método es mejor que 5) Prueba indirecta

4) Prueba indirecta contrapuesta

Esta es una variación del método de prueba indirecta condicional (no 3) las suposiciones se reorganizan. elija este método si a partir de la suposición de ~Q se pueden demostrar más cosas útiles que a partir de la suposición de P.

• Supongamos que ~Q
• Supongamos que P
• alguna contradicción
• Reductio ad absurdum
• introducción de la implicación

Prueba formal

1 | |____ ~Q            Assumption
: | | : : ?????????         some aplications of inference rules
: | | : : ?????????         some aplications of inference rules
a | | |__ P             Second Assumption
: | | | : ?????????        some aplications of inference rules
: | | | : ?????????        some aplications of inference rules
i | | | . contradiction    contradiction Introduction 
. | | <---------------------- end subproof
k | | . . ~P            a-i ~ Introduction
. | <------------------------ end subproof
m | . . . ~Q -> P       1-k ->  Introduction

Los resultados entre la línea 1 y a pueden ser interesantes fuera de su propia concordancia, por eso este método es mejor que 6) Prueba contrapositiva indirecta

5) Prueba indirecta

• Supongamos que ~(P -> Q)
• alguna contradicción
• Reductio ad absurdum

Prueba formal

1 | |____ ~(P -> Q)     Assumption
2 | | : : ?????????         some aplications of inference rules
: | | : : ?????????         some aplications of inference rules
: | | : : ?????????         some aplications of inference rules
j | | : : ?????????         some aplications of inference rules
k | | . . Contradiction     contradiction Introduction
. | <------------------------ end subproof
m | . . . ~~(P -> Q)    1-k ~ Introduction
n | . . . P -> Q        m   ~~Elimination

A menudo (¿siempre?) esta prueba puede ser sustituida por una prueba indirecta condicional (3), es aconsejable utilizar ese método.

6) Prueba contrapositiva indirecta

• Supongamos que ~(~Q -> ~P)
• alguna contradicción
• Reductio ad absurdum

Prueba formal

1 | |____ ~(~Q -> ~P)    Assumption
2 | | : : ?????????          some aplications of inference rules
: | | : : ?????????          some aplications of inference rules
: | | : : ?????????          some aplications of inference rules
j | | : : ?????????          some aplications of inference rules
k | | . . Contradiction      contradiction Introduction
. | <------------------------ end subproof 
m | . . . ~~(~Q -> ~P)   1-k ~ Introduction
n | . . . ~Q -> ~P       m   ~~Elimination

A menudo (¿siempre?) esta prueba puede ser sustituida por una prueba indirecta contrapuesta (4), es aconsejable utilizar ese método.

PS esta respuesta es (todavía) sólo un borrador, tal vez voy a añadir más tarde

Answer 4

Mira otro ejemplo:

En el lenguaje de establece tiene la forma $$A\subset B\Longleftrightarrow B^c\subset A^c,$$ donde $A^c$ es el complemento de $A$ .

Answer 5

Una de las razones por las que hacer una prueba de $A\Rightarrow B$ por contradicción podría ser más fácil es lo siguiente. Para una prueba directa sólo se puede utilizar $A$ como su base de trabajo, mientras que una prueba por contradicción le da tanto $A$ y $\neg B$ para empezar, y así poder sacar más conclusiones.

En este caso, ni siquiera estamos probando $\neg B \Rightarrow \neg A$ pero $$A \wedge \neg B \Rightarrow \text{false}.$$

Al final, todos ellos son equivalentes, por supuesto.