La simplificación de una prueba categórica de dilema constructivo

Question

En la axiomática del cálculo proposicional el siguiente axioma esquema de captura constructivo dilema: $\newcommand{\lif}{\supset} \renewcommand{\land}{\&}$

\begin{equation} (a \lif c) \lif ((b \lif c) \lif ((a \lor b) \lif c)) \tag{1} \end{equation}

En un bicartesian cerrado de la categoría que representa una lógica, disyunciones son co-productos, y de esta sencilla forma del dilema constructivo es capturado por el subproducto de la flecha, tal que dado flechas $f\colon A \to C$$g\colon B \to C$, no hay una única flecha $[f,g]\colon A \lor B \to C$. Ahora, desde la $(1)$ es un teorema del cálculo proposicional, esperamos que exista una flecha de la siguiente forma en el bicartesian cerrado categoría:

\begin{equation} \top \to (a \lif c) \lif ((b \lif c) \lif ((a \lor b) \lif c)) \tag{2} \end{equation}

Tengo una derivación de esta flecha, pero parece mucho más complicado de lo que debe ser. De hecho, de todos los axiomas en una de las axioma de sistemas se muestra en la Wikipedia, este es el más complicado para derivar una flecha. Me pregunto si esto se puede simplificar de alguna manera de que me estoy perdiendo. Aquí está la derivación que tengo. Empezamos con:

$$ Un \de la tierra ((A \C lif) \de la tierra (B\C lif)) \xrightarrow{\langle{\pi\pi',\pi\rangle}} (\lif C)\de la tierra A \xrightarrow{\mathrm{eval}} C $$

Alarmada, tenemos

$$ Un \xrightarrow{\lambda(\mathrm{eval}\langle{\pi\pi',\pi\rangle})} ((A \C lif) \de la tierra (B\C lif)) \lif C \etiqueta{3} $$

Asimismo, para $B$:

$$ B \de la tierra ((A \C lif) \de la tierra (B\C lif)) \xrightarrow{\langle{\pi'\pi',\pi\rangle}} (B \C lif)\de la tierra B \xrightarrow{\mathrm{eval}} C $$

Alarmada, tenemos

$$ B \xrightarrow{\lambda(\mathrm{eval}\langle{\pi'\pi',\pi\rangle})} ((A \C lif) \de la tierra (B\C lif)) \lif C \etiqueta{4} $$

Con $(3)$ $(4)$ podemos obtener un subproducto de la flecha:

$$ Un \lor B \xrightarrow{[(3),(4)]} ((Un \lif C) \de la tierra (B\C lif)) \lif C \etiqueta{5} $$

Para llevar a $\top$ en la imagen, podemos componer $(5)$, con una proyección de:

$$ \top \de la tierra (A \lor B) \xrightarrow{(5)\pi'} ((A \C lif) \de la tierra (B\C lif)) \lif C \etiqueta{6} $$

Ahora, ya que esto es una (bi)cartesiana cerrada categoría, podemos uncurry $(6)$ para obtener:

$$ (\top \de la tierra (A \lor B)) \de la tierra ((A \C lif) \de la tierra (B\C lif)) \xrightarrow{\lambda^{-1}((5)\pi')} C \etiqueta{7} $$

Ahora, los productos son conmutativas, así que no es difícil de conseguir

\begin{multline} ((\top \land (A \lif C)) \land (B\lif C)) \land (A \lor B) \to \\ (\top \land (A \lor B)) \land ((A \lif C) \land (B\lif C)) \tag{8} \end{multline}

que a través de la composición nos da:

$$ ((\top \de la tierra (A \C lif)) \de la tierra (B\C lif)) \la tierra (a \lor B) \xrightarrow{(\lambda^{-1}((5)\pi'))(8)} C \etiqueta{9} $$

Podemos curry $(9)$ tres veces para obtener la deseada teorema de la flecha:

\begin{equation} \top \xrightarrow{\lambda\lambda\lambda(9)} (a \lif c) \lif ((b \lif c) \lif ((a \lor b) \lif c)) \tag{10} \end{equation}

Ufff! Todo esto parece bastante complicada, dado lo trivial algunos de los teorema de flechas se derivan. E. g., los proyectos y las inyecciones son triviales:

\begin{gather*} \lambda\pi\colon \top \to (p \land q) \lif p \qquad \lambda\pi'\colon \top \to (p \land q) \lif q \\ \lambda\iota\colon \top \to p \lif (p \lor q) \qquad \lambda\iota'\colon \top \to q \lif (p \lor q) \end{reunir*}

Algunas de las flechas para las otras conectivas son un poco más complicado, pero este es por lejos el más complicado, y me pregunto si me he perdido alguna manera más fácil de hacerlo. Hay algunos más canónica, la manera más sencilla?

Esta es una muy simple prueba en deducción natural de los sistemas, a lo largo de las líneas de:

• 1. Suponga $a \lif c$.
  • 2. Suponga $b \lif c$.
    • 3. Suponga $a \lor b$.
    • 4. $c$ $\lor$- eliminación con 1, 2, 3.
    • 5. $(a\lor b) \lif c$ $\lif$- introducción 3-4.
  • 6. $(b\lif c) \lif ((a \lor b) \lif c)$ $\lif$ introducción 2-5.
• 7. $(a\lif c) \lif ((b\lif c) \lif ((a \lor b) \lif c))$ $\lif$ introducción 1-6.

La dificultad en el tratamiento categórico parece que no hay manera de hacer $\lor$-eliminación (es decir, para la construcción de un subproducto de flecha) en un contexto donde hay otros supuestos. De forma que la flecha de la derivación he dado anteriormente en realidad hace que el $\lor$-eliminación de uno de los últimos pasos, de forma análoga a:

• Suponga $a$
  • Suponga $a \lif c$
    • Suponga $b \lif c$
      • $c$ por modus ponens
• $\vdots$
• $a \lif ((a \lif c) \lif ((b \lif c) \lif c))$ por ...
• $\vdots$ (de manera similar para $b$)
• $b \lif ((a \lif c) \lif ((b \lif c) \lif c))$ por ...
• Suponga $a \lor b$
  • $((a \lif c) \lif ((b \lif c) \lif c))$ $\lor$- eliminación
• $(a \lor b) \lif ((a \lif c) \lif ((b \lif c) \lif c))$ yb $\lif$-introducción
• $\vdots$ reorganización de antecedentes
• $(a \lif c) \lif ((b \lif c) \lif ((a \lor b) \lif c))$

Answer 1

Después de que el traqueteo de lejos en esto, yo creo que la dificultad viene en el mantenimiento de cualquier "en el ámbito de los supuestos" disponible en cada uno de los casos. La prueba de que he descrito en la pregunta ¿que esta haciendo el codominio de la subproducto de la flecha de una exponencial. Que es, tratando de mostrar a $C$ a partir de los supuestos $A \lor B$, $A \lif C$, y $B \lif C$, que terminó derivando flechas de la forma

\begin{gather} f\colon A \to ((A \lif C) \land (B \lif C)) \lif C \\ g\colon B \to ((A \lif C) \land (B \lif C)) \lif C \end{reunir}

con el fin de obtener un subproducto de la flecha

$$ [f,g]\colon A \lor B \a ((A \C lif) \de la tierra (B \C lif)) \lif C $$

Parece que la una (?) esta alternativa es la de incorporar los supuestos en cada una de las alternativas. Es decir, recibiendo $f$ $g$ como:

\begin{gather} f\colon A \land (A \lif C) \land (B \lif C) \to C \\ g\colon B \land (A \lif C) \land (B \lif C) \to C \\ \end{reunir}

para obtener un subproducto de la flecha:

$$ [f,g]\colon (A \de la tierra (A \C lif) \de la tierra (B \C lif)) \lor (B \a la tierra (A \C lif) \de la tierra (B \C lif)) \a C $$

La disyunción tiene mucho más complicado disjuncts, pero no es del todo difícil para derivar la flecha que se distribuye conjuntamente más de la disyunción. (De hecho, me hizo una pregunta acerca de esto hace aproximadamente un año, probablemente cuando se trabaja en un problema similar, la distribución de los productos (conjunción) más de subproducto (disyunción).)

\begin{multline} \top \land (A \lif C) \land (B \lif C) \land (A \lor B) \to \\ (A \land (A \lif C) \land (B \lif C)) \lor (B \land (A \lif C) \land (B \lif C)) \tag{11} \end{multline}

y con la composición, se obtiene:

$$\top \land (A \lif C) \land (B \lif C) \land (A \lor B) \to C$$

Alarmada dos veces, obtenemos

$$\top \to (A \lif C) \lif ((B \lif C) \lif ((A\lor B) \lif C))$$

No estoy seguro de si es sencillo o no, sobre todo desde que hace algunos mano saludando con respecto a $(11)$. Si evita la necesidad de "uncurrying" de las partes más interesantes de la prueba, que me parece atractiva, aunque todavía hay un caso de que en la justificación de $(11)$.

Answer 2

Puedes probarlo en el Secuente Cálculo como se describe en el pdf se menciona en los comentarios (http://zll22.user.srcf.net/talks/2011-12-01-CategoricalLogic.pdf )

1  A                     |- A                               Identity
2  B                     |- B                               Identity
3  C                     |- C                               Identity
4  A, A -> C             |- C                               1,3 Modus ponens
5  B, B -> C             |- C                               2,3 Modus ponens
6  A v B, A -> C, B -> C |- C                               4,5 Disjunction elimination
7  A -> C, B -> C, A v B |- C                               6 reshuffeling antecedents
8  A -> C, B -> C,       |- (A v B) -> C                    7 Conditional proof
9  A -> C                |- (B->C)->((A v B) -> C)          8 Conditional proof
10                       |- (A->C)->((B->C)->((A v B)->C))  9 Conditional Proof 

Así que si usted puede reemplazar cada línea con su categórica equivalente está hecho :)

(Ps la línea 3 se usa dos veces, y yo tomo algunas libertades con la estructura de las reglas , pero estas reglas no se mencionan en el pdf)

Buena suerte

AÑADIDO posterior:

Hice un tal vez una mejor prueba:

1  A                     |- A                               Identity
2  B                     |- B                               Identity
3  C                     |- C                               Identity
4  A, A -> C             |- C                               1,3 Modus ponens
5  A                     |- (A -> C) -> C                   4  Conditional proof
6  A, B -> C             |- (A -> C) -> C                   5  weakening
7  A                     |- (B -> C) -> ((A -> C) -> C)     6  Conditional proof  
8  B, B -> C             |- C                               2,3 Modus ponens
9  B, B -> C, A -> C     |- C                               8  weakening
10 B, B -> C             |- (A -> C) -> C                   9  Conditional proof
11 B                     |- (B -> C) -> ((A -> C) -> C)     10 Conditional proof
12 A v B                 |- (B -> C) -> ((A -> C) -> C)     7,11 Disjunction elimination
13 B -> C                |- B -> C                          Identity
14 A v B, B -> C         |- (A -> C) -> C                   12,13 Modus ponens
15 A -> C                |- A -> C                          Identity
16 A v B, B -> C, A -> C |- C                               14,15 Modus ponens
17 A -> C, B -> C, A v B |- C                               16 reshuffeling antecedents
18 A -> C, B -> C        |- (A v B) -> C                    17 Conditional proof
19 A -> C                |- (B->C)->((A v B) -> C)          18 Conditional proof
20                       |- (A->C)->((B->C)->((A v B)->C))  19 Conditional Proof 

No estoy seguro si la regla de debilitamiento (línea 6 y 9) se permite nuevamente, esta es una regla estructural.

Ps si se refiere a esta prueba se refieren a ella como la prueba 2

Answer 3

Voy a poner una resolución de la prueba aquí. Es probable que no ayuda.

assumption 1 ANac
assumption 2 ANbc
assumption 3 Aab
R 1, 3     4 Abc
R 2, 4     5 c