¿Por qué la ley de Peirce implica la ley del medio excluido?

Question

Por qué si en un sistema formal la ley de Peirce $((P\rightarrow Q)\rightarrow P) \rightarrow P$ es cierto, la ley del medio excluido $P \lor \neg P$ ¿también es cierto?

Answer 1

La intuición:

La ley de Peirce es de la forma $$\big((A \to B) \to A\big) \quad \to \quad A,$$ es decir, dado $(A \to B) \to A$ podríamos deducir $A$ . Por lo tanto, trataremos de construir $$((P \lor \neg P) \to \bot) \to (P \lor \neg P).$$ El truco es que para cualquier $A \to B$ podemos fortalecer $A$ o relajarse $B$ por ejemplo:

\begin {align} P \lor \neg P & \to \bot & \text {implica}&& P & \to \bot , \\ P & \to P & \text {implica}&& P & \to P \lor \neg P. \end {align} Así que podríamos empezar con una tautología (asumo que la negación es sólo una abreviatura de $\to \bot$ ) \begin {align} \neg P & \to \neg P \\ (P \to \bot ) & \to \neg P \end {align} reforzar el lado izquierdo $$(P \lor \neg P \to \bot) \to \neg P$$ y relajar el lado derecho $$(P \lor \neg P \to \bot) \to P \lor \neg P.$$

Ahora aplicamos la ley de Peirce, y ya está ;-)

Cosas usadas:

• negación $\neg P$ es una abreviatura de $P \to \bot$ ,
• identidad: $\dfrac{\quad}{\Gamma, A \vdash A}[\alpha]$
• aplicación: $\dfrac{\Gamma \vdash A, A \to B}{\Gamma \vdash B}[\beta]$
• composición finita $\dfrac{\Gamma \vdash A_1 \to A_2, A_2 \to A_3, \ldots, A_{n-1} \to A_n}{ \Gamma \vdash A_1 \to A_n}[\gamma]$ ,
• introducción de la disyunción: $\dfrac{}{\Gamma, A \vdash A \lor B}[\delta]$ ,
• implicación: $\dfrac{\Gamma, A \vdash B}{\Gamma \vdash A \to B}[\iota]$ ,
• La ley de Peirce $\dfrac{}{\Gamma \vdash ((A\to B) \to A) \to A}[\pi]$ .

La prueba:

La premisa

$$ \dfrac{ \dfrac{ \dfrac{ \frac{}{P \to P \lor \neg P}{[\delta,\iota]}, \quad \frac{}{P \lor \neg P \to \bot \vdash P \lor \neg P \to \bot}[\alpha] }{P\lor\neg P \to \bot \vdash P \to \bot}[\gamma] }{(P\lor\neg P\to \bot) \to \neg P}[\iota], \quad \dfrac{\quad}{\neg P \to P \lor \neg P}[\delta, \iota] }{(P \lor \neg P \to \bot) \to P \lor \neg P}[\gamma] $$

y la derivación final

$$ \dfrac{ \dfrac{\text{from above} }{(P \lor \neg P \to \bot) \to P \lor \neg P}, \ \dfrac{}{((P \lor \neg P \to \bot) \to P \lor \neg P) \to P \lor \neg P}[\pi] }{P \lor \neg P}[\beta] $$

Hay varios atajos y suposiciones implícitas, sobre todo la negación $\neg P$ es una abreviatura de $P \to \bot$ Tengan cuidado. No obstante, espero que siga siendo útil $\ddot\smile$

Answer 2

Esto es probablemente lo que está buscando: La Ley de Peirce es equivalente a la Ley del Medio Excluido . Sin embargo, hay que tener en cuenta que esta prueba depende de algunas suposiciones que son no encarnada en toda lógica. Por ejemplo, en la lógica de la relevancia, el paso de $\neg p$ a $p \rightarrow q$ no es válido, ya que $p$ puede no ser relevante para $q$ .

Answer 3

¿Por qué? Porque se puede demostrar. Un sistema formal no tiene (o tiene una referencia mínima) al significado, y en consecuencia cualquier teorema lógico es válido, porque puedes demostrarlo dado el conjunto de axiomas y las reglas de inferencia del sistema. Esbozaré un sistema formal en el que se puede demostrar la ley del medio excluido ApNp y la ley de Peirce CCCpqpp. Primeras reglas de formación:

1. Todas las letras minúsculas del alfabeto latino se consideran fórmulas.
2. Si $\alpha$ se califica como una fórmula, por lo que la dosis N $\alpha$
3. Si $\alpha$ y $\beta$ se califica como una fórmula, también lo hace C $\alpha$$\beta$, and A$\alpha$$\beta$ .
4. Las reglas anteriores son suficientes para lo que sigue.

El sistema (y casi todas las pruebas que aparecen a continuación pueden acreditarse al trabajo de Jan Lukasiewicz y a los editores y traductores de la obra de Lukasiewicz Elementos de lógica matemática ) tiene tres axiomas:

1 CCpqCCqrCpr (silogismo hipotético)

2 CCNppp

3 CpCNpq

En palabras se puede traducir el primer axioma como "si la primera (proposición) implica la segunda, si la segunda implica la tercera, entonces la primera implica la tercera". El segundo axioma puede traducirse como "si la negación de la primera implica la primera, entonces la primera". El tercer axioma puede traducirse como "si lo primero, entonces, si no lo primero, entonces lo segundo". El sistema tiene una definición

4' Apq:=CNpq

Tiene tres reglas de inferencia

S: Para cualquier letra minúscula $\lambda$ dentro de cualquier axioma podemos sustituirlo uniformemente por cualquier otra fórmula, siempre que dicha sustitución se produzca para todos Las letras minúsculas son equívocas con $\lambda$ en esa fórmula. Por ejemplo, si se diera el caso de que CpCqp fuera un axioma de nuestro sistema, podríamos sustituir p por Cpp en CpCqp (las sustituciones se abreviarán con la notación p/Cpp en adelante) y obtener C Cpp Cq Cpp, pero no C Cpp C qp. También podemos aplicar dicha sustitución uniforme a cualquier teorema que ya hayamos derivado.

R: Para cualquier fórmula en la que Xpq, o alguna instancia de sustitución de Xpq, podemos sustituir Xpq por Yrs, donde tenemos una definición tal que tenemos la definición Yrs:=Xpq, donde las variables de Yrs contienen sólo variables equiformes con Xpq. Este reemplazo no tiene que ocurrir uniformemente para la fórmula. Puede ocurrir sólo en un lugar dentro de una fórmula. En particular aquí esto significa que si tenemos algún teorema como CCNpqCqCNpq, podemos reemplazar cualquier instancia de CNpq en CCNpqCqCNpq con Apq, para producir CApqCqCNpq.

D: Si tenemos un teorema C $\alpha$$\beta$ and $\alpha$ qualifies as a theorem also, we may detach $\beta $ como un teorema también.

Así que, primero demostraremos la ley del medio excluido, en símbolos ApNp. La notación "1, p/q" indica que sustituiremos uniformemente la fórmula p en la referencia de la fórmula por el numeral 1 con q. El signo "=" se utiliza para indicar que la fórmula a la izquierda del signo "=" viene como equiforme con la fórmula a la derecha del signo "=". La notación C1-2 indica que la fórmula 1 viene como antecedente o primera fórmula que conecta la C de la izquierda de la fórmula, la 2 viene como consecuente o segunda fórmula que conecta la C de la izquierda de la fórmula, y el "-" indica que separaremos la fórmula 2 como teorema. La notación 3 R = 4 indica que sustituiremos la fórmula 3, que viene como una instancia de sustitución de CNpq, por la fórmula Apq (p y q permanecen equiformes a través de CNpq y Apq) y obtendremos el teorema 4.

1 axioma CCpqCCqrCpr

2 Axioma CCNppp

3 Axioma CpCNpq

 1 q/CNpq = 4

4 C CpCNpq CCCNpqrCpr

 4 = C 3 - 5

5 CCCNpqrCpr

 5 q/p, r/p = 6

6 C CCNppp Cpp

 6 = C 3 - 7

7 Cpp

 7 p/Np = 8

8 CNpNp

 8 R = 9

9 ApNp

A continuación probaremos CqCpq para poder demostrar dos teoremas cualesquiera de otro teorema en este sistema.

  1 p/Cpq, q/CCqrCpr, r/s = 10

10 C CCpqCCqrCpr CCCCqrCprsCCpqs

  10 = C 1 - 11

11 CCCCqrCprsCCpqs

  11 q/Cqr, r/Csr, s/CCsqCpCsr = 12

12 C CCCCqrCsrCpCsrCCsqCpCsr CCpCqrCCsqCpCsr

  11 p/s, s/CpCsr = 13

13 CCCCqrCsrCpCsrCCsqCpCsr

  12 = C 13 - 14

14 CCpCqrCCsqCpCsr

  11 s/CCCprsCCqrs = 15    

15 CCCqrCprCCCprsCCqrs CCpqCCCprsCCqrs

  1 p/Cqr, q/Cpr, r/s = 16

16 CCCqrCprCCCprsCCqrs

  15 = C 16 - 17

17 CCpqCCCprsCCqrs

  14 p/Cpq, q/CCprs, r/CCqrs, s/t = 18

18 C CCpqCCCprsCCqrs CCtCCprsCCpqCtCCqrs

  18 = C17 - 19

19 CCtCCprsCCpqCtCCqrs

  5 r/CCCNpppCCqpp = 20

20 C CCNpqCCCNpppCCqpp CpCCCNpppCCqpp

  17 p/Np, r/p, s/p = 21

21 CCNpqCCCNpppCCqpp

  20 = C 21 - 22

22 CpCCCNpppCCqpp

  22 p/CCNppp = 23

23 C CCNppp CCCNCCNpppCCNpppCCNpppqCCNpppCCNppp

  23 = C 2 -24

24 C CCNCCNpppCCNpppCCNppp CCqCCNppp

  2 p/CCNppp = 25

25 CCNCCNpppCCNpppCCNppp

  24 = C 25 - 26

26 CCqCCNpppCCNppp

  5 p/t, q/CCNppp, r/CCNppp = 27

27 C CCNtCCNpppCCNppp CtCCNppp

  26 q/Nt = 28

28 CCNtCCNpppCCNppp

  27 = C 28 - 29

29 CtCCNppp

  19 p/Np, r/p, s/p = 30 

30 C CtCCNppp CCNpqCtCCqpp

  30 = C 29 - 31

31 CCNpqCtCCqpp

  1 p/CNpq, q/CtCCqpp = 32

32 C CCNpqCtCCqpp CCCtCCpprCCNpqr

  32 = C 31 - 33

33 CCCtCCpprCCNpqr

  33 t/NCCqpp, r/CCqpp = 34

34 C CCNCCqppCCqppCCqpp CCNpqCCqpp

  2 p/CCNqpp = 35

35 CCNCCNqppCCNqppCCNqpp

  35 = C 34 - 36

36 CCNpqCCqpp

  5 r/CCqpp = 37

37 C CCNpqCCqpp CpCCqpp

  37 = C 36 - 38

38 CpCCqpp

  38 p/q, q/Np = 39

39 CqCCNpqq

  14 p/q, q/CNpq, r/q, s/p = 40

40 C CqCCNpqq CCpCNpqCqCpq

  40 = C 39 - 41

41 C CpCNpq CqCpq

  41 = C 3 - 42

42 CqCpq

En palabras el teorema 42 se puede traducir como "La primera proposición implica que la segunda proposición implica la primera proposición". O equivalentemente, "La primera proposición implica que si la segunda proposición, entonces la primera proposición". En base a esto se puede demostrar cualquier proposición sobre la base de cualquier otra proposición en este sistema (tal vez quiera anotar exactamente lo que dice la regla de sustitución S y lo que no dice). Ahora demostraremos la ley de Peirce CCCpqpp.

  1 p/q, q/Cpq = 43

43 C CqCpq CCCpqrCqr

  43 = C 42 - 44 

44 CCCpqrCqr

  44 p/Nq, q/p, r/CCpqq = 45

45 C CCNqpCCpqq CpCCpqq

  36 p/q, q/p = 46

46 CCNqpCCpqq

  45 = C 45 - 47

47 CpCCpqq

  14 p/q, q/Cqr, s/p = 48

48 C CqCCqrr CCpCqrCqCpr

  47 p/q, q/r = 49

49 CqCCqrr

  48 = C 49 - 50

50 CCpCqrCqCpr

  1 p/CpCqr, q/CqCpr, r/s = 51

51 C CCpCqrCqCpr CCCqCprsCCpCqrs

  51 = C 50 - 52

52 CCCqCprsCCpCqrs

  52 q/Np, r/q, s/CCCpqpp = 53

53 C CCNpCpqCCCpqpp CCpCNpqCCCpqpp

  36 q/Cpq = 54 

54 CCNpCpqCCCpqpp

  53 = C 54 - 55

55 CCpCNpqCCCpqpp

  55 = C 3 - 56

56 CCCpqpp

Entonces, ahora demostraremos la ley del medio excluido ApNp a partir de la ley de Peirce CCCpqpp en este sistema.

  42 q/ApNp, p/CCCpqpp

57 C ApNp CCCCpqppApNp

  57 = C 9 - 58

58 CCCCpqppApNp

  58 = C 56 - 59

59 ApNp

Pero, incluso aquí, existe una trampa...

¿Y si sólo tuviéramos la ley de Perice con las reglas de inferencia S, D y R anteriores? ¿Podríamos demostrar la ley del medio excluido? Prover9 me dio la siguiente matriz (con el desprendimiento condensado como regla de inferencia, pero eso no importará aquí):

 A|  0  1|C| 0 1|N 
------------------
 0*| 1  0|0| 0 1|0
 1|| 0  0|1| 0 0|0

He marcado el 0 para indicarlo como el elemento designado aquí. Si escribes las tablas de verdad para CCCpqpp y ApNp aquí, puedes ver que CCCpqpp siempre evalúa al elemento designado 0. Sin embargo, cuando p=0, ApNp=A0N0=A00=1. También, y viene como importante para comprobar esto también, si Cpq=0, y p=0, entonces q=0, por lo que la regla D viene como válida para este sistema. Las reglas R y D son válidas para este sistema, ya que la matriz anterior implica A, C y N como verdad-funcional. Por lo tanto, a partir de la ley de Peirce "sola" (las reglas mencionadas anteriormente se entenderán preferentemente como implícitas en esta afirmación), simplemente no se puede derivar la ley del medio excluido.