¿Cuál es el razonamiento explícito detrás de la prueba por contradicción?

Parece que hay varias preocupaciones superpuestas en su problema con la prueba por contradicción.

1. Tiene una objeción a la tabla de verdad por implicación material:

Sin embargo, nunca me ha satisfecho el argumento de que dos proposiciones falsas crean una implicación verdadera. ¿Qué buenas justificaciones hay para estar de acuerdo con esto?

2. Pareces malinterpretar la prueba por contradicción:

1. Muestre que p -> q, donde "->" es el condicional. 2. Demostrar que q es falsa. 3. Deducir de una tabla de verdad que p debe ser falsa.

Comenzaré con el segundo tema. Diría que una mejor definición de prueba por contradicción es la siguiente:

1. Dado P, A
2. Dado P, no A
3. Ergo, dado P, A y no A
4. Por lo tanto, no P debido a la contradicción cuando P

Esto está algo relacionado con la implicación material, como usted observa correctamente. Pero esto no se trata realmente de probar que A es falso, sino de probar que A y no A son verdaderos simultáneamente. Pero dado que esto es imposible en la lógica estándar, debemos habernos equivocado al aceptar P, por lo tanto, no P.

Volviendo al tema de la lógica estándar, podemos abordar parcialmente sus preocupaciones sobre la implicación material. Hay tres reglas fundamentales que sigue la lógica clásica:

1. Ley de la Identidad: debemos querer decir lo mismo con lo mismo cada vez. (no podemos cambiar el significado de las variables y los términos a mitad del argumento).
2. Ley del medio excluido: cada proposición que abordamos debe ser verdadera o falsa (y solo una de las dos en este significado de o).
3. Ley de no contradicción: no podemos aceptar que A y su opuesto (no A) sean verdaderos al mismo tiempo.

También podemos expresar esto sucintamente:

1. UN = UN
2. Para cualquier A, verdadero o falso
3. no (A y no A)

La implicación material es un operador lógico que opera en dos términos y vive en este mundo. Su propósito es trabajar con condiciones, es decir, lugares donde el valor de una variable depende de otra. Dado que tenemos 2 variables que (por regla 2 pueden tener dos valores cada una), tenemos cuatro posibilidades.

Para A -> B,

1. A es verdadero y B es verdadero
2. A es verdadero y B es falso
3. A es falso y B es verdadero
4. A es falso y B es falso

Lo que hace la implicación es probar si la implicación se cumple. Por lo tanto, aceptamos que se cumple (ver toda la implicación como verdadera) cuando A es verdadera y B es verdadera. También deberíamos poder ver que la implicación es falsa cuando A es verdadera pero B es falsa.

La situación es un poco más complicada y confusa cuando A es falso (si estamos pensando "si, entonces" en lugar de simplemente aceptarlo como un operador). Más recientemente, la explicación que he estado dando en mis clases es la siguiente:

Cuando A es falsa, no tenemos la oportunidad de verificar si la implicación se cumple o no directamente. Pero dadas las tres leyes (particularmente 2), debemos declarar que esto es verdadero o falso. Dado que no hemos refutado la implicación, sigue siendo cierta para nuestros propósitos.

Pero la cuestión es que no necesitamos esto específicamente para la prueba por contradicción, porque en la prueba por contradicción lo que hemos hecho es mostrar que alguna suposición P conduce a una contradicción. Y las contradicciones son inaceptables en base a la tercera regla. Ergo, la suposición misma debe ser rechazada.

La prueba por contradicción en general, no se limita al uso de condicionales .

En lógica, la prueba por contradicción es una forma de prueba, y más específicamente una forma de prueba indirecta, que establece la verdad o validez de una proposición mostrando que el hecho de que la proposición sea falsa implicaría una contradicción .

Lo que se necesita es el concepto de implicación lógica o consecuencia lógica .

Este concepto es el núcleo de toda lógica. Aristóteles lo identificó claramente en primer lugar :

Toda la lógica de Aristóteles gira en torno a una noción: la deducción ( sullogismos ). [...] ¿Qué es entonces una deducción? Aristóteles dice:

Una deducción es un discurso ( logos ) en el que, habiéndose supuesto ciertas cosas, algo diferente de las supuestas resulta necesariamente por serlo. ( Análisis previo I.2, 24b18–20)

Cada una de las “cosas supuestas” es una premisa ( prótasis ) del argumento, y lo que “resulta de necesidad” es la conclusión ( sumperasma ).

El núcleo de esta definición es la noción de “resultado de la necesidad”. Esto corresponde a una noción moderna de consecuencia lógica : X resulta necesariamente de Y y Z si fuera imposible que X fuera falso cuando Y y Z son verdaderos. Por lo tanto, podríamos tomar esto como una definición general de "argumento válido".

Así, un argumento válido es un argumento que, a partir de premisas verdaderas , deriva una conclusión verdadera.

Si del conjunto de premisas Γ ∪ {A} derivamos algo falso , como una contradicción por medio de las reglas de la lógica, tenemos que concluir que al menos una de las premisas es falsa , porque, por la definición de consecuencia lógica :

si todas las premisas son verdaderas, entonces necesariamente también lo es la conclusión .

Por lo tanto, concluimos que el enunciado A es "responsable" de la contradicción y que el conjunto restante de premisas Γ implica la negación de A , es decir, ¬ A.

En su ejemplo, si hemos probado

P → Q ,

entonces procedemos de la siguiente manera:

1) asumir P

2) derivar ¬ Q ;

por modus ponens , derivamos de P → Q y 1) también:

3) P

Ahora tenemos la contradicción y por lo tanto tenemos que concluir que nuestra suposición inicial P es falsa , es decir

4) ¬P .

Expresado de otra forma, si P → Q y P → ¬ Q , usando la tautología : (P → Q) → ((P → ¬ Q) → ¬P) , por dos aplicaciones del modus ponens concluimos con ¬ P , que equivale a decir:

¬ P es la consecuencia lógica de P → Q y P → ¬ Q .

En símbolos:

PAG → Q, PAG → ¬ Q ⊨ ¬ PAG

El razonamiento explícito detrás de una prueba por contradicción son las dos leyes

"no (no A) = A" y "Si A => B y B falso, entonces A falso"

Estas leyes se cumplen en la lógica proposicional. El método veraz prueba la segunda ley.

Una prueba por contradicción aplica estas leyes de la siguiente manera: para probar que una proposición "A" es verdadera, se supone por el contrario que "A" es falsa. es decir, "no A" verdadero. De esta suposición se deriva en uno o más pasos una cierta afirmación "B", que se demuestra que es falsa. Ahora "no A => B" y "B" falso implica "no A" falso, por lo tanto, "A" verdadero.

El método que estás describiendo no es "demostración por contradicción", se llama "demostración del contrapositivo" - expresado simbólicamente como ¬q ⇒ ¬p . Esta declaración es lógicamente equivalente a p ⇒ q . Es importante comprender que ambos métodos se ocupan de probar la implicación material p ⇒ q , no (repito que no ) la verdad de p o q , como asume en sus comentarios.

¿Como funciona esto? El enunciado p ⇒ q es verdadero a menos que p pueda ser verdadero mientras que q es falso. [1]

En el método de probar la contrapositiva que usted describe, se procede asumiendo que q es falsa y demuestra que esto implica que p debe ser falsa. Esto significa que nunca podemos hacer que p sea verdadera y q falsa, por lo que se puede concluir que p ⇒ q según [1] .

En el método de prueba por contradicción, se supone que p ⇒ q es falsa, es decir, p verdadera y q falsa (al contrario de [1] ) y se muestra que esta suposición conduce a una contradicción, lo que nos permite concluir que nunca podemos tener p verdadera yq falso . Esto es equivalente a decir p ⇒ q ya que la única vez que una implicación material es falsa es cuando es posible que p sea verdadera y q sea falsa.

Sus comentarios sobre estas estrategias asumen que sabemos que p ⇒ q es verdadero y luego derivamos los valores de verdad de p y q . Esto no es correcto en ninguno de los métodos de prueba, por contradicción o por contraposición. El objetivo de estos métodos es probar la verdad de p ⇒ q .

EDITAR

Con respecto a sus comentarios (abajo):

1. ¿Cómo podemos probar la implicación material sin establecer primero cuáles deben ser los valores de verdad de p y q?

Ambos métodos funcionan asumiendo los valores de verdad relevantes. En el caso de probar la contrapositiva, suponemos que q es falsa y demostramos que esto nos obliga a aceptar que p también debe ser falsa. Aquí hay un ejemplo de una demostración de la contrapositiva:

( nota: daré un ejemplo de un argumento informal ya que será más fácil seguir cómo funcionan los métodos ) .

EJEMPLO: Supongamos que n es un número entero positivo y que queremos probar que:

• Si n ² es par entonces n es par.

Para usar el método de probar la contrapositiva , supondremos que el enunciado q (= n es par) es falso y mostraremos que una consecuencia necesaria de este supuesto es que p (= n ² es par) también debe ser falso.

Para hacer esto, suponga que n no es par. Entonces podemos escribir n como 2k+1 , para algún entero positivo k . Por lo tanto n ² = ( 2k+1 ) ² . Expandiendo esta expresión y agrupando los términos podemos escribir esto como n ² = 4(k ² +k)+1 . Dado que 4(k ² +k)+1 no es par (dado que no es divisible por 2), hemos demostrado que la suposición de que n no es par nos obliga a concluir que n ² no es par. Por lo tanto, hemos demostrado "Si n es impar, entonces n ²es impar", o de manera equivalente "Si n ² es par, entonces n es par". Es decir, ¬ q ⇒ ¬p , que es equivalente a p ⇒ q .

Para usar el método de prueba por contradicción , supondríamos que p ⇒ q es falsa y derivaríamos una contradicción. Si p ⇒ q es falso entonces hay un entero positivo n tal que n ² es par, pero n es impar. Pero si n es impar, entonces por el mismo argumento usado en nuestro ejemplo de probar la contrapositiva, debemos tener n ² también impar. Esto contradice nuestra suposición de que p ⇒ q es falsa y, por lo tanto, podemos concluir que p ⇒ q debe ser verdadera.

2. Usando el método de probar el contrapositivo, ¿puede explicar el razonamiento detrás de cómo podemos mostrar que p es falsa asumiendo que q es falsa sin usar la tabla de verdad? ¿O es eso lo que se está utilizando para establecer esto?

Creo que mis comentarios sobre la pregunta 1 también responden a esta pregunta. El ejemplo que he dado es obviamente un argumento informal, pero que se formaliza fácilmente.

A mi entender, la prueba por contradicción consta de los siguientes pasos. 1. Muestre que p -> q, donde "->" es el condicional. 2. Demostrar que q es falsa. 3. Deducir de una tabla de verdad que p debe ser falsa.

Está describiendo modus tollens, no prueba por contradicción.

Si basamos la verdad del condicional en la verdad de p y q, ¿cómo podemos saber que el condicional es verdadero antes de saber si tanto p como q son verdaderos?

La suposición en la lógica simbólica es que sabemos/creemos que el condicional (u otra premisa) es verdadero por alguna razón fuera de la lógica simbólica. Tal vez crea que la implicación es evidente o está bien establecida por evidencia científica. Ciertamente no es porque conoces el valor de verdad de p y q.

El único escenario que produce este resultado es aquel en el que p también es falso. Sin embargo, nunca me ha satisfecho el argumento de que dos proposiciones falsas crean una implicación verdadera. ¿Qué buenas justificaciones hay para estar de acuerdo con esto?

En primer lugar, esto en realidad no cambia el razonamiento del modus tollens. Si falso -> falso fuera falso o indeterminado, aún sería el caso de que verdadero -> falso fuera falso. Dado que q es falsa, la única opción que queda es que p sea falsa.

A mi modo de ver, no deberías pensar en el condicional material como equivalente a nuestro concepto de implicación del lenguaje natural. Nuestra noción de implicación en el lenguaje natural se parece más al concepto de la lógica de predicados:

(x)(Ax -> Bx)

Esto dice que para todo x, si Ax es verdadero, Bx es verdadero. Es trivialmente verdadero cuando Ax es falso, pero si Ax es verdadero, entonces Bx también debe ser verdadero.

Considere la proposición: si yo soy el presidente, usted es el Papa. Ninguna proposición es cierta, pero parece incorrecto afirmar que la implicación es cierta porque yo siendo presidente no te convertiría en Papa. Pero lo que realmente queremos decir es algo así como, en todos los mundos posibles donde yo soy el presidente, tú eres el papa.

La lógica de primer orden es bastante ordenada en el sentido de que hay varias formas de pensar en ella que resultan todas para dar resultados idénticos.

Cuando Γ es un conjunto de fórmulas y P es una fórmula, la notación

Γ ⊢ P

llamada vinculación sintáctica , es la afirmación de que existe una prueba deductiva de P usando las fórmulas en Γ como hipótesis. por ejemplo, la introducción de la conjunción es el axioma

P, Q ⊢ P ∧ Q

Una formulación de prueba por contradicción es

Γ, P ⊢ Q
Γ, P ⊢ ¬Q
therefore
Γ ⊢ ¬P

Algunas versiones de la lógica tienen un símbolo ⊥ que significa "contradicción", en cuyo caso probablemente lo formularíamos como

Γ, P ⊢ ⊥
therefore
Γ ⊢ ¬P

tales formas de prueba a menudo pueden usar de

P, ¬P ⊢ ⊥

Se puede pensar en el condicional como un medio para convertir la noción de implicación en forma proposicional; específicamente

Γ, P ⊢ Q      if and only if      Γ ⊢ P → Q

Entonces, en lugar de trabajar con la noción de implicación, se manipulan las proposiciones. por ejemplo modus ponens

P, P → Q ⊢ Q

pero en cambio podríamos verlo dado como la tautología

⊢ (P ∧ (P → Q)) → Q

Del mismo modo, podemos reformular la prueba por contradicción como

(P → Q), (P → ¬Q) ⊢ ¬P

o como la tautología

⊢ ((P → Q) ∧ (P → ¬Q)) → ¬P

Usando el símbolo de contradicción, también podríamos poner esto como

⊢ (P → ⊥) → ¬P

Hay otra notación

Γ ⊨ P

llamado vinculación semántica . Dado que estamos hablando de lógica proposicional, una forma de definir esto es que es la afirmación de que toda valoración de verdad que hace que cada afirmación en Γ sea verdadera también hace que P sea verdadera.

(una valoración de verdad es simplemente una elección de valor de verdad para cada proposición atómica y calcular la verdad de proposiciones más complejas usando los operadores booleanos correspondientes en valores de verdad)

Por ejemplo, podemos demostrar

P ⊨ P ∨ Q

por tablas de verdad, es decir, comprobando que cada fila de la tabla de verdad P = truetambién tiene P ∨ Q = true.

Queremos que la implicación se comporte de la misma manera: por ejemplo,

Γ, P ⊨ Q      if and only if      Γ ⊨ P → Q

Observe que la afirmación P⊨Q es idéntica a

es imposible asignar valores de verdad de una manera que haga que P sea verdadero y Q sea falso

En consecuencia, las filas en la tabla de verdad que son falsas P→Qdeben ser exactamente las filas donde Pes verdadero y Qes falso, ni más ni menos.

Entonces, lo mágico de la lógica proposicional (y de la lógica de primer orden) son el teorema de completitud y el teorema de solidez, que juntos dicen

Γ ⊢ P      if and only if      Γ ⊨ P

Así que eso es lo que estamos haciendo cuando observamos los valores de verdad : estamos haciendo cálculos y tabulaciones de valores de verdad para resolver la vinculación semántica y usar este teorema para determinar la vinculación sintáctica.

La prueba por contradicción es un método de prueba INDIRECTO: agregas la negación de lo que quieres probar condicionalmente a tus premisas en una subdemostración y demuestras que conduce a una contradicción con un paso previo de tu prueba. Entonces, clásicamente, puede concluir que lo que quería probar debe ser cierto. No todas las lógicas admiten esta forma de razonamiento; por ejemplo, las lógicas intuicionistas no lo hacen, ya que no aceptan la equivalencia lógica incondicional entre que un enunciado sea verdadero y la negación de ese enunciado sea falso.

Si chocara a gran velocidad contra un poste de luz, me sangraría la nariz. Mi nariz no está sangrando. Por lo tanto, no me encontré con un poste de luz.

Usted preguntó: "Si basamos la verdad del condicional en la verdad de p y q, ¿cómo podemos saber que el condicional es verdadero antes de saber si tanto p como q son verdaderos?"

En el ejemplo, p y q son ambos falsos. No choqué contra el poste de luz, no me sangra la nariz. Pero el condicional es verdadero . p -> q es verdadero en tres de cuatro casos: si p y q son ambos falsos, si ambos son verdaderos, y si p es falso pero q es verdadero. Solo es falso si p es verdadero y q es falso.