Teori Pembuktian
Teori pembuktian mempelajari pembuktian formal sebagai objek matematika tersendiri, menganalisis struktur, transformasi, dan kekuatan teori yang menghasilkannya.
Definition
Teori pembuktian adalah cabang logika matematika yang memperlakukan pembuktian dalam sistem formal sebagai objek kombinatorial terbatas, mempelajari bagaimana pembuktian tersebut dapat ditransformasi dan dinormalisasi serta apa yang diungkapkan oleh keberadaannya tentang konsistensi dan kekuatan teori yang mendasarinya.
Scope
Area ini mencakup kalkulus formal seperti deduksi natural dan kalkulus sekuen, teorema eliminasi-potongan dan normalisasi, teorema ketidaklengkapan Goedel, pengukuran kekuatan teori melalui analisis ordinal, serta konten konstruktif dan komputasional dari pembuktian yang diungkapkan oleh korespondensi antara pembuktian dan program.
Sub-topics
Core questions
- Bagaimana pembuktian formal dapat direpresentasikan dan dimanipulasi sebagai objek kombinatorial?
- Jalan memutar mana dalam pembuktian yang dapat dihilangkan secara sistematis, dan apa yang diungkapkannya?
- Apa batasan inheren pada apa yang dapat dibuktikan oleh teori formal tentang dirinya sendiri?
- Bagaimana kekuatan suatu teori dapat diukur secara tepat?
Key theories
- Teorema eliminasi-potongan
- Gentzen menunjukkan bahwa setiap pembuktian dalam kalkulus sekuen dapat ditransformasi menjadi pembuktian tanpa aturan potongan, menghasilkan pembuktian dengan properti subformula dan hasil konsistensi langsung.
- Teorema ketidaklengkapan Goedel
- Setiap teori formal yang konsisten dan cukup kuat untuk menyatakan aritmetika mengandung kalimat benar yang tidak dapat dibuktikan dan tidak dapat membuktikan konsistensinya sendiri, menetapkan batasan fundamental pada formalisasi.
- Korespondensi Curry-Howard
- Pembuktian dalam deduksi natural sesuai dengan istilah kalkulus lambda bertipe dan normalisasi pembuktian sesuai dengan komputasi, menghubungkan teori pembuktian dengan teori bahasa pemrograman.
Clinical relevance
Teori pembuktian mendasari analisis konsistensi dan konten konstruktif dalam matematika dan menyediakan dasar teoretis untuk teori tipe, pemrograman fungsional, dan asisten pembuktian otomatis, di mana pembuktian berfungsi ganda sebagai program yang dapat diverifikasi.
History
Teori pembuktian didirikan oleh Hilbert sebagai bagian dari programnya untuk mengamankan matematika dengan pembuktian konsistensi finitari. Teorema ketidaklengkapan Goedel tahun 1931 menunjukkan bahwa program asli tidak dapat sepenuhnya berhasil, dan eliminasi-potongan Gentzen serta pembuktian konsistensi untuk aritmetika melalui induksi transfinit mengarahkan bidang ini menuju analisis ordinal dan, kemudian, paradigma pembuktian-sebagai-program.
Key figures
- David Hilbert
- Gerhard Gentzen
- Kurt Goedel
- Jean-Yves Girard
Related topics
Seminal works
- troelstra2000
- takeuti1987
- girard1989
Frequently asked questions
- Bagaimana teori pembuktian berbeda dari teori model?
- Teori model mempelajari struktur dan kebenaran kalimat di dalamnya, sebuah perspektif semantik, sedangkan teori pembuktian mempelajari derivasi formal dan transformasi sintaksisnya. Teorema kelengkapan Goedel menghubungkan keduanya, tetapi metode dan pertanyaan mereka berbeda.
- Apa itu program Hilbert?
- Itu adalah proposal untuk membuktikan konsistensi seluruh matematika hanya dengan menggunakan penalaran finitari yang tidak kontroversial. Teorema ketidaklengkapan kedua Goedel menunjukkan bahwa tidak ada teori yang cukup kuat yang dapat membuktikan konsistensinya sendiri, sehingga program tersebut tidak dapat dilaksanakan dalam bentuk aslinya, meskipun versi modifikasinya tetap berpengaruh.