Hace una prueba por contradicción siempre existen?

Question

Buen día,

Generalmente, las pruebas por las contradicciones son la más fácil, y a veces, incluso las únicas disponibles. Sin embargo, hay casos donde los más fáciles de la prueba no es prueba por contradicción. Por ejemplo, la de abajo:

A partir de la definición de los números racionales, todos ellos se puede expresar como cocientes de dos números enteros. Y a partir de esto, lógicamente, todos los coeficientes racionales así, porque:

$$ \forall\ \forall b\ \forall c\ \forall d:\{a;b;c;d\}\subconjunto\mathbb Z\setminus\{0\}\\ \left\{\frac a b;\frac c d\right\}\subconjunto\mathbb P;\ \frac{\ \frac una b\ }{\ \frac c d\ }= \frac{\frac una b\times bd}{\frac c d\times bd}= \frac{ad}{bc}\in \mathbb Q $$

o, más en general (y que de hecho hace la prueba casi superflua, puesto que la división es una multiplicación la multiplicación es conmutativa) por $m$ fracciones:

$$ \forall\ \forall b:\{a;b\}\subconjunto\mathbb Z\setminus\{0\}\\ \bigcup_ {n=1}^m\left\{\frac {a_n} {b_n}\right\}\subconjunto\mathbb P;\ \prod_{n=1}^m \frac {a_n} {b_n}= \frac {\prod_{n=1}^m a_n} {\prod_{n=1}^m b_n} \in \mathbb Q $$ (fin del ejemplo)

Cuando digo que la prueba por contradicción, me refiero a la falsa declaración, usted puede asumir con el fin de provocar la contradicción debe ser fundamental a la prueba, de tal manera que si se quita, no hay ninguna prueba. Puede una prueba siempre se puede encontrar para cualquier teorema demostrado/conjetura/fórmula?

Answer 1

Cada vez que algo es comprobable en todo, es posible disimular que la prueba como una contradicción. Pero el resultado no es necesariamente muy esclarecedor.

Supongamos que tenemos algún tipo de argumento válido a favor de la proposición $P$. A continuación, podemos también probar $P$ por contradicción:

$P$ es cierto. Es decir, asumir una contradicción que $\neg P$. Entonces (inserte el existente argumento aquí) y, por tanto,$P$. Pero ambos $\neg P$ (por supuesto) y $P$ (por el argumento que hemos dado), y que es una contradicción. Por lo tanto, $P$ es cierto, Q. E. D.

Usted puede entonces el objeto de que la suposición de $\neg P$ no fue muy utilizado para producir la contradicción. Habitual de la lógica matemática no se preocupa de eso, permite que los supuestos no van a ser utilizadas sin afectar a la validez de una conclusión. Pero hay cosas que llama la relevancia de la lógica que intenta capturar la idea de que de alguna manera es un error no hacer uso de una suposición.

Por desgracia, eso no nos ayuda aquí, incluso de acuerdo a la relevancia de la lógica, de la $\neg P$ suposición sin duda fue utilizado para producir la contradicción en la anterior prueba. Sin ella no habría habido ninguna contradicción en todo, y la prueba se desmoronaría.

---

Es mucho más interesante cuestión de si hay cosas que sólo puede probarse por contradicción. Los argumentos que nunca el uso de la prueba por contradicción se estudian en intuitionistic lógica, y resulta que hay declaraciones de cuyas pruebas depende esencialmente de pasos intermedios por contradicción. Por ejemplo, la de Peirce de la ley: $$ ((P\Rightarrow Q)\Rightarrow P)\Rightarrow P $$ no puede ser probado sin admitir prueba por contradicción, o algo que es esencialmente equivalente.

Answer 2

Hay muchas direcciones de prueba puede tomar.

Algunas pruebas de empezar con la conclusión, y cada nuevo paso es un inversa implicación hasta llegar a la "verdad".

Algunas pruebas de comenzar con la hipótesis (o "verdadero"), y cada nuevo paso es una consecuencia hasta llegar a la conclusión.

Una prueba por contradicción comienza con la negación de la asunción, y cada nuevo paso es una consecuencia hasta llegar a "false". Lógicamente hablando, usted puede siempre convertir una prueba por contradicción en una dirección de prueba del primer tipo de uso de demorgan la transforma.

La prueba por contradicción: $$ \lnot conclusion \rightarrow false $$ es equivalente a a $$ conclusion \leftarrow true $$ y pasos intermedios $$ a \rightarrow b$$ se puede convertir a $$ \lnot a \leftarrow \lnot b $$

...a menos que, por supuesto, usted está trabajando con un conjunto muy limitado de reglas de inferencias que no admiten ambos tipos de pruebas.

Answer 3

Cualquier prueba por contradicción en una constante proposicional cálculo requiere que una premisa de obtener el alta. En consecuencia, esa premisa no pertenece a el axioma/teorema de conjunto de que el cálculo proposicional. La descarga de los locales para un cálculo proposicional requiere que usted tenga una deducción metatheorem alrededor. Sin embargo, si usted no tiene ninguna deducción metatheorem alrededor, entonces la prueba por contradicción se convierte en ilegal para que el cálculo proposicional.

Supongamos que tenemos la siguiente las reglas de formación para bien formado fórmulas (wffs) siguiendo una notación polaca esquema.

1. Todas las letras en minúscula del alfabeto latino califica como un wff.
2. Si $\alpha$ califica como un wff, a continuación, N$\alpha$ califica como un wff.
3. Si $\alpha$ califica como un wff, y así no $\beta$ C$\alpha$$\beta$ califica como un wff.

Supongamos que nuestro único axioma es

1 CCpqCCqrCpr.

Y tenemos la regla de desprendimiento "De $\vdash$C$\alpha$$\beta$, así como $\vdash$$\alpha$, podemos inferir $\vdash$$\beta$" y la regla de uniforme de sustitución. Tal sistema no se clasifica como de acuerdo en que no es el caso que tenemos $\vdash$ $\alpha$ y $\vdash$ N$\alpha$.

Podemos probar

2 CCCCqrCprsCCpqs.

y

3 CCpCqrCCsqCpCsr.

Además, dado que cada teorema de este sistema se presenta como un condicional, no existe el último teorema de este sistema. Sin embargo, ninguno de los anteriores teoremas ni cualquier otro teoremas de este sistema puede llegar demostrado por la contradicción de acuerdo a la definición pertinente de una prueba de este sistema (algo así como cada teorema es el axioma CCpqCCqrCpr o puede deducirse en una secuencia finita de bien formado fórmulas que se inicia con CCpqCCqrCpr, y sólo utiliza uniforme de sustitución y de desprendimiento y termina con el teorema).

Así que, definitivamente, NO, prueba por contradicción no siempre existe.