Равенство разрешимых доказательств?

Я хочу знать, может ли быть доказана разрешимость равенства двух разрешимых доказательств одного и того же предложения без каких-либо дополнительных аксиом в исчислении индуктивных построений.

В частности, я хочу знать, правда ли это, без каких-либо дополнительных аксиом в 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\})$

Спасибо!

Отредактировано, чтобы исправить ошибку: Изменить 2, чтобы сделать Propболее явным

coq constructive-mathematics calculus-of-constructions Адам Барак
источник

То, что вы написали, не имеет смысла. Если

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$ решаемо "?

Андрей Бауэр

Извините, я имел в виду гипотезу

P

$P$ разрешима ", то есть

P \lor \neg P

$P \vee \neg P$

Адам Барак

принимать

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})$ с

i n l (λ x . x)

$\mathsf{inl}(\lambda x.\;x)$ и эквивалентность функций, очевидно, неразрешима. Есть ли другие условия на

P

$P$ ты имеешь в виду?

Нил Кришнасвами

P должен быть предложением. (На самом деле, в своей разработке я уже использовал функциональную экстенсиональность, поэтому утверждение все еще может быть для меня верным, но давайте пока проигнорируем функциональную / пропозициональную экстенсиональность).

Адам Барак

Расширение функций не подразумевает, что эквивалентность функций разрешима ... И ответ Нила решает общий случай: если P - (обитаемый) бесконечный тип (который включает в себя некоторые типы предложений, если не включены дополнительные аксиомы), то импликация не выполняется держать для

P \to P

$P\rightarrow P$ ,

Коди

Как указывает Нил, если вы работаете в «предложениях - это типы», вы можете легко придумать тип, равенство которого не может быть показано разрешимым (но, конечно, непротиворечиво полагать, что все типы имеют разрешимое равенство), например $\mathbb{N} \to \mathbb{N}$ ,

Если мы понимаем «предложение» как более ограниченный тип, то ответ зависит от того, что именно мы имеем в виду. Если вы работаете в исчислении конструкций с Propвидом, вы все равно не сможете показать, что разрешимые предложения имеют разрешимое равенство. Это так, потому что в исчислении конструкций непротиворечиво отождествлять Propвселенную с релевантным для доказательства типом, поэтому все, что вы знаете, Propможет содержать что-то вроде $\mathbb{N} \to \mathbb{N}$ , Это также означает, что вы не можете доказать свою теорему для понятия Кока о Prop.

Но в любом случае лучший ответ приходит из теории гомотопического типа. Там предложение является типом $P$ который удовлетворяет

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

$\forall x, y : P \,.\, x = y.$ То есть предложение имеет не более одного элемента (как и должно быть, если его следует понимать как значение истины, не относящееся к доказательству). В этом случае ответ, конечно, положительный, поскольку определение суждения сразу подразумевает, что его равенство разрешимо.

Мне любопытно узнать, что вы подразумеваете под «предложением».

Андрей Бауэр
источник

Как бы вы

N \to N

$\mathbb{N} \rightarrow \mathbb{N}$ внутри Prop? Спасибо!

Адам Барак

В исчислении конструкции нет ничего, что мешало бы

P r o p = T y p e

$\mathtt{Prop} = \mathtt{Type}$ , есть?

Андрей Бауэр

Путаница здесь связана с тем, что подразумевается под «системой coq». Если это «исчисление конструкций», то

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

$\mathtt{Prop=Set=Type}$ , Если более точное «Исчисление индуктивных конструкций с 1 импредикативной вселенной», то

T y p e

$\mathtt{Type}$ бессмысленно без аннотаций уровня вселенной. Насколько я знаю,

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

$\mathtt{Type_1=Prop}$ является последовательной аксиомой (хотя несовместимой с EM по тонким причинам).

Коди

Конечно, мы должны прикрепить индекс на

T y p e

$\mathtt{Type}$ , Смысл для @AdamBarak понять это: потому что

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

$\mathtt{Prop} = \mathtt{Type}_1$ не приводит к противоречию в Coq, мы можем показать, что что-то не может быть сделано в Coq, показав, что это приведет к противоречию, если бы мы также имели

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

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

Андрей Бауэр

Все еще не совсем верно, потому что в Coq мы не можем показать, что функциональная эквивалентность неразрешима. Утверждение "равенство на

N \to N

$\mathbb{N} \to \mathbb{N}$ является решаемым ", это то, что Мартин Эскардо называет конструктивным табу: это нельзя ни доказать, ни опровергнуть в Coq. Поэтому правильный аргумент таков: если

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}$ является разрешимым "является ложным).

Андрей Бауэр

Равенство разрешимых доказательств?

Ответы: