Ley de Peirce

En lógica, la ley de Peirce lleva el nombre del filósofo y lógico Charles Sanders Peirce. Fue tomado como un axioma en su primera axiomatización de la lógica proposicional. Se puede considerar como la ley del tercero excluido escrita en una forma que involucra solo un tipo de conectivo, a saber, la implicación.

En cálculo proposicional, la ley de Peirce dice que ((P → Q)→ P)→ P. Escrito, esto significa que P debe ser verdadera si hay una proposición Q tal que la verdad de P se sigue de la verdad de "si P entonces Q ". En particular, cuando se toma Q como una fórmula falsa, la ley dice que si P debe ser verdadera siempre que implique falsedad, entonces P es verdadera. De esta forma la ley de Peirce implica la ley del tercero excluido.

La ley de Peirce no se cumple en la lógica intuicionista ni en la lógica intermedia y no puede deducirse únicamente del teorema de deducción.

Bajo el isomorfismo de Curry-Howard, la ley de Peirce es el tipo de operadores de continuación, por ejemplo, call/cc en Scheme.

Historia

Aquí está la propia declaración de la ley de Peirce:Se requiere un quinto icono para el principio del tercero excluido y otras proposiciones relacionadas con él. Una de las fórmulas más simples de este tipo es:

{(x → y) → x } → x.

Esto no es axiomático. Que es verdad aparece como sigue. Solo puede ser falso si el consecuente final x es falso mientras que su antecedente (x → y) → x es verdadero. Si esto es cierto, su consecuente, x, es verdadero, cuando toda la fórmula sería verdadera, o su antecedente x → y es falso. Pero en el último caso el antecedente de x → y, es decir x, debe ser verdadero. (Peirce, The Collected Papers 3.384).

Peirce continúa señalando una aplicación inmediata de la ley:De la fórmula que acabamos de dar, obtenemos inmediatamente:

{(x → y) → un } → x,

donde la a se usa en tal sentido que (x → y) → a significa que de (x → y) se sigue toda proposición. Con ese entendimiento, la fórmula enuncia el principio de tercero excluido, que de la falsedad de la negación de x se sigue la verdad de x. (Peirce, The Collected Papers 3.384).

Advertencia: ((x → y)→ a)→ x no es una tautología. Sin embargo, [ a → x ]→[((x → y)→ a)→ x ] es una tautología.

Otras pruebas

Aquí hay una prueba simple de la ley de Peirce asumiendo la doble negación y derivando la disyunción estándar de una implicación :

Usando la ley de Peirce con el teorema de deducción

La ley de Peirce permite mejorar la técnica de usar el teorema de deducción para probar teoremas. Supongamos que se le da un conjunto de premisas Γ y se quiere deducir una proposición Z de ellas. Con la ley de Peirce, se pueden agregar (sin costo) premisas adicionales de la forma Z → P a Γ. Por ejemplo, supongamos que tenemos P → Z y (P → Q)→ Z y deseamos deducir Z para que podamos usar el teorema de deducción para concluir que (P → Z)→(((P → Q)→ Z)→ Z) es un teorema. Entonces podemos agregar otra premisa Z → Q. De eso y P → Z, obtenemos P → Q. Luego aplicamos modus ponens con (P → Q) → Z como premisa mayor para obtener Z. Aplicando el teorema de deducción, se obtiene que (Z → Q)→ Z se sigue de las premisas originales. Luego usamos la ley de Peirce en la forma ((Z → Q)→ Z)→ Z y modus ponens para derivar Zdel local original. Entonces podemos terminar de demostrar el teorema como originalmente pretendíamos.

P → Z	1. hipótesis
(P → Q) → Z	2. hipótesis
Z → Q	3. hipótesis
PAGS	4. hipótesis
Z	5. modus ponens utilizando los pasos 4 y 1
q	6. modus ponens utilizando los pasos 5 y 3
P → Q	7. deducción de 4 a 6
Z	8. modus ponens utilizando los pasos 7 y 2
(Z → Q)→ Z	9. deducción de 3 a 8
((Z → Q)→ Z)→ Z	10. Ley de Peirce
Z	11. modus ponens utilizando los pasos 9 y 10
((PAG → Q)→ Z)→ Z	12. deducción de 2 a 11
(PAG → Z)→(((PAG → Q)→ Z)→ Z)	13. deducción de 1 a 12 QED

Completitud del cálculo proposicional implicacional

Una razón por la que la ley de Peirce es importante es que puede sustituir a la ley del tercero excluido en la lógica que solo usa implicación. Las oraciones que se pueden deducir de los esquemas axiomáticos:

• PAG →(Q → PAG)
• (PAG →(Q → R))→((PAG → Q)→(PAG → R))
• ((PAG → Q)→ PAG)→ PAG
• de P y P → Q inferir Q

(donde P, Q, R contienen solo "→" como conectivo) son todas las tautologías que usan solo "→" como conectivo.