¿Igualdad de pruebas decidibles?

Quiero saber si la capacidad de decisión de igualdad de dos pruebas decidibles de la misma proposición puede demostrarse sin ningún axioma adicional en el cálculo de construcciones inductivas.

Específicamente, quiero saber si esto es cierto sin ningún axioma adicional en Coq.

\forall P : Prop, P \lor \neg P \Rightarrow (\forall p_{1} : P, \forall p_{2} : P, {p_{1} = p_{2}} \lor {p_{1} \neq p_{2}})

$\forall P: \texttt{Prop}, P \vee \neg P \Rightarrow (\forall p_1 : P, \forall p_2: P, \{p_1 = p_2\} \vee \{p_1 \neq p_2\})$

¡Gracias!

Editado para corregir el error: Editar 2 para hacer Propmás explícito

coq constructive-mathematics calculus-of-constructions Adam Barak
fuente

Lo que escribiste no tiene sentido. Si

es una proposición, entonces

es una prueba, y no puede formar

. ¿Quiso decir que su hipótesis era

lugar de

, es decir, "

es decidible"?

P

$P$

p : P

$p : P$

p \lor \neg p

$p \lor \lnot p$

P \lor \neg P

$P \lor \lnot P$

p \lor \neg p

$p \lor \lnot p$

P

$P$

Andrej Bauer

Lo siento, quise decir la hipótesis "

es decidible", es decir,

P

$P$

P \lor \neg P

$P \vee \neg P$

Adam Barak

Tome

como

, y la afirmación es falsa, ya que puede habitar fácilmente

con

P

$P$

N \to N

$\mathbb{N} \to \mathbb{N}$

(N \to N) \lor \neg (N \to N)

$(\mathbb{N} \to \mathbb{N}) \vee \lnot(\mathbb{N} \to \mathbb{N})$

, y la equivalencia de funciones es obviamente indecidible. ¿Hay otras condiciones sobre

que tenga en mente?

i n l (λ x . x)

$\mathsf{inl}(\lambda x.\;x)$

P

$P$

Neel Krishnaswami

P debería ser una propuesta. (En realidad, en mi desarrollo, ya utilizo la extensionalidad funcional, por lo que la declaración aún puede ser válida para mí, pero ignoremos la extensionalidad funcional / proposicional por ahora).

Adam Barak

La extensionalidad de la función no implica que la equivalencia de la función sea decidible ... Y la respuesta de Neel resuelve el caso general: si P es un tipo infinito (habitado) (que incluye algunos tipos de proposiciones si no se incluyen axiomas adicionales), entonces la implicación falla para el asimiento para

P \to P

$P\rightarrow P$

cody

Como señala Neel si trabajas bajo "las proposiciones son tipos", entonces puedes encontrar fácilmente un tipo cuya igualdad no se puede mostrar como decidible (pero, por supuesto, es consistente asumir que todos los tipos tienen igualdad decidible), como . $\mathbb{N} \to \mathbb{N}$

Si entendemos "proposición" como un tipo de tipo más restringido, entonces la respuesta depende de lo que queremos decir exactamente. Si está trabajando en el cálculo de construcciones con un Proptipo, entonces todavía no puede demostrar que las proposiciones decidibles tienen igualdad decidible. Esto es así porque es consistente en el cálculo de las construcciones de equiparar Propcon un universo de tipo de prueba relevante, por lo que para todo lo que sabe Propfuerzas contiene algo así como . Esto también implica que no puede probar su teorema para la noción de Coq . $\mathbb{N} \to \mathbb{N}$ Prop

Pero, en cualquier caso, la mejor respuesta proviene de la teoría del tipo de homotopía. Hay una proposición de tipo que satisface $P$ Es decir, una proposición tiene como máximo un elemento (como debería ser si se entiende como un valor de verdad irrelevante para la prueba). En este caso, la respuesta es, por supuesto, positiva porque la definición de proposición implica inmediatamente que su igualdad es decidible.

\forall x, y : P . x = y .

$\forall x, y : P \,.\, x = y.$

Tengo curiosidad por saber qué quieres decir con "proposición".

Andrej Bauer
fuente

¿Cómo tendrías

adentro ? ¡Gracias!

N \to N

$\mathbb{N} \rightarrow \mathbb{N}$ Prop

Adam Barak

No hay nada en el cálculo de la construcción que impida

, ¿verdad?

P r o p = T y p e

$\mathtt{Prop} = \mathtt{Type}$

Andrej Bauer

La confusión aquí es sobre lo que se entiende por "el sistema coq". Si es "el cálculo de las construcciones", entonces

. Si el "Cálculo de construcciones inductivas con 1 universo impredecible" más preciso, entonces

tiene sentido sin anotaciones a nivel de universo. Hasta donde yo sé,

es un axioma consistente (aunque inconsistente con EM por razones sutiles).

P r o p = S e t = T y p e

$\mathtt{Prop=Set=Type}$

T y p e

$\mathtt{Type}$

T y p e_{1} = P r o p

$\mathtt{Type_1=Prop}$

cody

Claro, tenemos que agregar un índice en

. El punto que debe entender @AdamBarak es el siguiente: debido a que

no genera ninguna contradicción en Coq, podemos demostrar que no se puede hacer algo en Coq al mostrar que conduciría a una contradicción si también tuvimos

T y p e

$\mathtt{Type}$

P r o p = {T y p e}_{1}

$\mathtt{Prop} = \mathtt{Type}_1$

P r o p = {T y p e}_{1}

$\mathtt{Prop} = \mathtt{Type}_1$

Andrej Bauer

Todavía no está del todo bien, porque en Coq no podemos mostrar que la equivalencia funcional sea indecidible. La afirmación "la igualdad en

es decidible" es lo que Martin Escardo llama un tabú constructivo: no se puede probar ni refutar en Coq. Entonces el argumento correcto es: si

entonces

es una proposición, y la afirmación "la igualdad en

es decidible" no es demostrable. (Mientras que usted dijo: y la afirmación "la igualdad en

es decidible" es falsa).

N \to N

$\mathbb{N} \to \mathbb{N}$

P r o p = {T y p e}_{1}

$\mathtt{Prop} = \mathtt{Type}_1$

N \to N

$\mathbb{N} \to \mathbb{N}$

N \to N

$\mathbb{N} \to \mathbb{N}$

N \to N

$\mathbb{N} \to \mathbb{N}$

Andrej Bauer

¿Igualdad de pruebas decidibles?

Respuestas: