Kesetaraan bukti yang dapat diputuskan?

Saya ingin tahu apakah decidability of equality dari dua bukti decidable dari proposisi yang sama dapat dibuktikan tanpa aksioma tambahan dalam Calculus of Inductive Constructions.

Secara khusus, saya ingin tahu apakah ini benar tanpa ada aksioma tambahan dalam 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\})$

Terima kasih!

Diedit untuk memperbaiki kesalahan: Edit 2 untuk membuat Proplebih eksplisit

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

Apa yang Anda tulis tidak masuk akal. Jika

adalah proposisi maka

adalah bukti, dan Anda tidak dapat membentuk

. Apakah maksud Anda hipotesis Anda adalah

bukannya

, yaitu, "

dapat dipilih"?

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

Maaf, maksud saya hipotesis "

adalah decidable", yaitu

P

$P$

P \lor \neg P

$P \vee \neg P$

Adam Barak

Ambil

menjadi

, dan pernyataan itu salah, karena Anda dapat dengan mudah menghuni

dengan

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

, dan kesetaraan fungsi jelas tidak dapat ditentukan. Apakah ada kondisi lain pada

Anda pikirkan?

i n l (λ x . x)

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

P

$P$

Neel Krishnaswami

P harus menjadi proposisi. (Sebenarnya, dalam perkembangan saya, saya sudah menggunakan ekstensionalitas fungsional, jadi pernyataan itu masih bisa berlaku untuk saya, tetapi mari kita abaikan ekstensionalitas fungsional / proposisional untuk saat ini).

Adam Barak

Fungsi ekstensionalitas tidak menyiratkan bahwa kesetaraan fungsi dapat dipilih ... Dan jawaban Neel menyelesaikan kasus umum: jika P adalah tipe tak terbatas (dihuni) (yang mencakup beberapa jenis Proposisi jika tidak ada aksioma tambahan yang dimasukkan), maka implikasinya gagal untuk ditahan untuk

P \to P

$P\rightarrow P$

cody

Jawaban:

Seperti yang Neel tunjukkan jika Anda bekerja di bawah "proposisi adalah tipe" maka Anda dapat dengan mudah menghasilkan jenis yang kesetaraannya tidak dapat diperlihatkan dapat dipilih (tetapi tentu saja konsisten untuk menganggap bahwa semua jenis memiliki kesetaraan yang dapat ditentukan), seperti . $\mathbb{N} \to \mathbb{N}$

Jika kita memahami "proposisi" sebagai jenis yang lebih terbatas, maka jawabannya tergantung pada apa yang sebenarnya kita maksudkan. Jika Anda bekerja dalam kalkulus konstruksi dengan Propjenis maka Anda masih tidak dapat menunjukkan bahwa proposisi yang dapat dideklarasikan memiliki kesetaraan yang dapat ditentukan. Hal ini karena itu adalah konsisten dalam kalkulus konstruksi untuk menyamakan Propdengan jenis alam semesta bukti yang relevan, sehingga untuk semua yang Anda tahu Propkekuatan berisi sesuatu seperti . Ini juga menyiratkan Anda tidak dapat membuktikan teorema Anda untuk pengertian Coq tentang . $\mathbb{N} \to \mathbb{N}$ Prop

Tetapi bagaimanapun juga, jawaban terbaik datang dari teori tipe homotopy. Ada proposisi adalah tipe yang memenuhi $P$ Yaitu, proposisi memiliki paling banyak satu elemen (sebagaimana mestinya jika itu dipahami sebagai nilai kebenaran yang tidak relevan dengan bukti). Dalam kasus ini jawabannya tentu saja positif karena definisi proposisi segera menyiratkan bahwa kesetaraannya dapat ditentukan.

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

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

Saya ingin tahu apa yang Anda maksud dengan "proposisi".

Andrej Bauer
sumber

Bagaimana Anda akan memiliki

di dalam ? Terima kasih!

N \to N

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

Adam Barak

P r o p = T y p e

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

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

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$

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