Mengapa prosedur eliminasi potongan ini berakhir (kasus kontraksi)?

Dalam survei Melliès ' Categorical Semantics of Linear Logic , prosedur penghilangan potongan untuk logika linear intuitionistic diberikan yang mencakup kasus berikut:

3.9.3 Promosi vs. kontraksi
Buktinya ditransformasikan menjadi bukti $\frac{\frac{\frac{π_{1} ⋮}{! Γ ⊢ SEBUAH}}{! Γ ⊢! SEBUAH} Promosi \frac{\frac{π_{2} ⋮}{Υ_{1},! SEBUAH,! SEBUAH, Υ_{2} ⊢ B}}{Υ_{1},! SEBUAH, Υ_{2} ⊢ B} Kontraksi}{Υ_{1},! Γ, Υ_{2} ⊢ B} Memotong$ $\displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{\displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B}}{\Upsilon_1 , !A , \Upsilon_2 \vdash B} \text{ Contraction} }{ \Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B } \text{ Cut}$ $\frac{\frac{\frac{π_{1} ⋮}{! Γ ⊢ SEBUAH}}{! Γ ⊢! SEBUAH} Promosi \frac{\frac{\frac{π_{1} ⋮}{! Γ ⊢ SEBUAH}}{! Γ ⊢! SEBUAH} Promosi \frac{π_{2} ⋮}{Υ_{1},! SEBUAH,! SEBUAH, Υ_{2} ⊢ B}}{Υ_{1},! SEBUAH,! Γ, Υ_{2} ⊢ B} Memotong}{\frac{Υ_{1},! Γ,! Γ, Υ_{2} ⊢ B}{Υ_{1},! Γ, Υ_{2} ⊢ B} Seri Kontraksi dan Pertukaran} Memotong$ $\displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B} }{ \Upsilon_1 , !A , !\Gamma , \Upsilon_2 \vdash B } \text{ Cut} }{ \displaystyle\frac{\Upsilon_1 , !\Gamma , !\Gamma , \Upsilon_2 \vdash B}{\Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B} \rlap{\;\text{ Series of Contractions and Exchanges}} } \text{ Cut}$

Mengapa ini merupakan langkah induktif yang valid? Baik ukuran formula potong maupun ukuran derivasi menurun. (Dalam bukti transformasi, cabang kanan dari potongan bawah berpotensi lebih besar setelah secara induktif menghapuskan potongan atas.) Jadi tidak jelas mengapa prosedur ini harus dihentikan.

linear-logic Sebastien Zany
sumber

Baru saja melihat sekilas dan ini adalah waktu yang lama sejak saya belum membaca formalisme seperti itu tetapi saya mendapat kesan bahwa tujuan di sini adalah untuk menghapus potongan setelah Promosi vs Kontraksi. Dalam hal ini, transformasi bekerja karena setiap kontraksi sekarang berada di bawah potongan sehingga pemotongan naik di pohon derivasi dan secara induktif dihilangkan.

Serigala

Masalahnya adalah bahwa dalam bukti transformasi, cabang kanan dari potongan bawah berpotensi lebih besar setelah secara induktif menghilangkan potongan atas. (Akan menambahkan ini dalam klarifikasi.)

Sebastien Zany

Ya, tetapi jumlah kontraksi telah berkurang satu. Sejauh yang saya tahu (sekali lagi, saya tidak terlalu banyak merinci), tidak ada transformasi lain yang menambah jumlah kontraksi. Jadi, jika Anda melihat nilainya (#kontraksi, apa pun yang Anda tulis_for_the_rest), maka nilai ini selalu menurun dalam urutan leksikografis, sehingga akan berakhir pada titik tertentu.

Serigala

Selain apa yang dikatakan holf dan Neel, bukankah variasi dari argumen (derajat, pangkat) yang biasa itu berfungsi? Maksud saya, apa perbedaan antara langkah ini dan penghapusan luka pada kontraksi di LJ? (Maksudku kalkulus sekuens intuitionistic Gentzen)

Damiano Mazza

Tapi bagaimana Anda menghilangkan potongan B? Satu-satunya hal yang tampaknya dapat Anda lakukan dalam kasing Promosi adalah menukar posisi dua potongan A dan B. Namun, Anda berakhir dalam situasi yang sama persis. Jika Anda menghilangkan B (yang sekarang di atas), Anda dapat meningkatkan jumlah kontraksi di atas A.

Jérôme Fortier

Saya menyampaikan apa yang saya tulis sebagai komentar. Karena ada banyak kasus dalam buktinya, saya hanya memberikan ide mengapa transformasi ini berakhir. Jawaban singkatnya adalah:

Dalam hal promosi vs kontraksi, setelah transformasi, jumlah kontraksi di bagian bukti yang mengandung potongan telah berkurang satu.

Untuk lebih detail, saya akan mengatakan bahwa Anda salah karena Anda berpikir bahwa jumlah potongan atau ukuran buktinya akan berkurang untuk memastikan penghentian. Namun, pemutusan hubungan kerja dapat dibuktikan dengan melihat parameter pembuktian lainnya.

Jika Anda ingin membuktikan penghentian, Anda hanya perlu menunjukkan bahwa setiap aturan akan diterapkan dalam jumlah waktu yang terbatas. Anda dapat membuktikan bahwa promosi aturan transformasi vs kontraksi akan diterapkan paling banyak m kali, di mana m adalah jumlah kontraksi dalam bukti awal Anda. Untuk membuktikan ini, Anda hanya perlu mengamati bahwa tidak ada aturan yang memperkenalkan kontraksi baru di pohon bukti. Dan ini mengurangi jumlah kontraksi per satu. Anda dapat melakukan trik ini untuk aturan "promosi vs sthg" lainnya untuk membuktikan bahwa ini hanya akan diterapkan dalam jumlah waktu terbatas.

serigala
sumber

Mengapa prosedur eliminasi potongan ini berakhir (kasus kontraksi)?

3.9.3 Promosi vs. kontraksi

Jawaban: