Apa hubungan antara Logika Orde Pertama dan Teori Orde Pertama?

Saya pikir setiap FOT adalah subset dari FOL, tetapi sepertinya tidak demikian, karena FOL sudah lengkap (setiap rumus valid atau tidak valid), sementara beberapa FOT (seperti aritmatika integer linier) tidak lengkap.

Jadi, apakah FOL lebih ekspresif daripada FOT? Atau tiada tara?

Juga, pernyataan "ada pernyataan yang valid dalam LIA tetapi tidak dapat dibuktikan menggunakan aksioma LIA" aneh. Bagaimana pernyataan itu valid jika kita tidak dapat membuktikan validitasnya? Saya selalu berpikir bahwa jika Anda tidak dapat membuktikan validitas pernyataan tersebut, maka Anda tidak dapat mengklaim itu valid.

logic first-order-logic Ayrat
sumber

Saya pikir pernyataan "ada pernyataan yang valid dalam LIA tetapi tidak dapat dibuktikan menggunakan aksioma LIA" adalah salah. Teorema kelengkapan godel memastikan bahwa pernyataan yang valid pada akhirnya dapat dibuktikan dalam jumlah waktu yang terbatas. Saya pikir Anda membingungkan validitas logis dengan kebenaran logis. Itu adalah dua hal yang berbeda. Makna kelengkapan yang digunakan dalam teorema kelengkapan godel dan yang digunakan dalam teorema ketidaklengkapan tidak sama.

rotia

Jawaban:

Logika orde pertama adalah subjek matematika yang mendefinisikan banyak konsep yang berbeda, seperti rumus orde pertama , struktur orde pertama , teori orde pertama , dan masih banyak lagi. Salah satu konsep ini adalah teori orde pertama : itu adalah satu set rumus orde pertama. Seringkali kita mempertimbangkan teori orde pertama yang dihasilkan oleh sejumlah aksioma dan skema aksioma yang terbatas. Teori semacam itu ditutup sehubungan dengan derivasi logis , dan kami biasanya hanya mempertimbangkan teori yang memuaskan kondisi ini.

Teori orde pertama selesai jika untuk setiap pernyataan , ia mengandung atau negasinya. Tidak semua teori lengkap. Memang, teorema ketidaklengkapan Gödel menyoroti fakta bahwa banyak teori orde pertama yang menarik tidak lengkap. $\sigma$ $\sigma$

Sebuah Model teori orde pertama adalah interpretasi yang valid dari teori (kita meninggalkan definisi yang tepat untuk buku teks). Sebagai contoh, teori orde pertama kelompok terdiri dari semua pernyataan yang mengikuti dari aksioma kelompok. Setiap kelompok adalah model dari teori kelompok pertama.

Untuk setiap model, kalimat yang diberikan benar atau salah. Teorema kelengkapan Gödel menyatakan bahwa jika kalimat orde pertama benar dalam semua model teori orde pertama, maka itu dapat dibuktikan dari sejumlah kalimat dalam teori. Sebagai contoh, setiap pernyataan orde pertama dalam bahasa kelompok yang berlaku untuk semua kelompok dapat dibuktikan dari aksioma kelompok.

LIA (mungkin) adalah teori orde pertama yang cukup menarik untuk tidak lengkap karena teorema ketidaklengkapan Gödel. Namun, dalam model standar - bilangan bulat "benar" - setiap kalimat benar atau salah. Secara khusus, jika adalah pernyataan sedemikian rupa sehingga baik maupun milik LIA, maka atau berlaku untuk bilangan bulat sejati, tetapi fakta ini tidak dapat dibuktikan dalam LIA. $\sigma$ $\sigma$ $\lnot \sigma$ $\sigma$ $\lnot \sigma$

Yuval Filmus
sumber

apa yang spesial dari teori 'lengkap'? mengapa mereka menarik? 'tentu saja', banyak teori tidak lengkap, karena kekurangan melengkapi menanyakan apakah kalimat itu benar untuk semua model. Pada ketidaklengkapan: dalam "model integer standar", kami tidak peduli tentang semua model yang memenuhi aksioma, kami hanya memiliki satu, "model integer standar". Bukankah teorema ketidaklengkapan mengisyaratkan bahwa cara kita mendefinisikan validitas (terutama, pertimbangan kita semua model yang memenuhi aksioma) tidak tepat?

Ayrat

Teori yang lengkap adalah istimewa karena memberikan nilai kebenaran yang pasti untuk setiap pernyataan. Ini adalah sesuatu yang ingin Anda miliki. Sisa pertanyaan Anda adalah milik bidang filsafat. Yang mengatakan, teorema kelengkapan Gödel menyamakan validitas di semua model dengan provabilitas.

Yuval Filmus

masih tidak melihat manfaatnya - pertimbangkan FOL, yang lengkap: misalkan Anda ingin memeriksa apakah F valid atau tidak: 'kelengkapan' tidak banyak membantu jika F tidak valid, karena validitas FOL semi-decidable. Apakah saya melewatkan sesuatu?

Ayrat

Pernyataan "logika orde pertama selesai" tidak berarti atau salah.

Yuval Filmus

Tidak benar bahwa teori orde pertama adalah serangkaian kalimat orde pertama yang konsisten . Yang benar untuk dikatakan adalah: teori orde pertama adalah seperangkat rumus orde pertama yang ditutup dengan deduksi. Saya bisa dengan sempurna merumuskan teori yang tidak konsisten. Mungkin perlu bertahun-tahun sebelum kita mengetahui bahwa itu tidak konsisten. Dan sebuah teori mungkin mengandung formula, bukan hanya kalimat (yang merupakan formula tertutup).

Andrej Bauer

Frasa "logika tingkat pertama" memiliki dua arti:

Ini adalah bab dari logika matematika di mana kita mempelajari beberapa jenis sistem formal dan segala sesuatu yang berkaitan dengannya.
Ini adalah jenis khusus teori orde pertama, yaitu teori yang dihasilkan oleh tanda tangan kosong dan set aksioma kosong.

Pertanyaan Anda mengacu pada makna kedua, tetapi untuk memahami ini, kita perlu membangun:

Ada bahasa formal tertentu yang disebut bahasa logika tingkat pertama . Berbicara secara tidak resmi, itu adalah hal-hal yang dapat Anda bangun dari variabel, persamaan, , , , , and . Barang ini dikenal sebagai formula orde pertama . $\land$ $\lor$ $\lnot$ $\Rightarrow$ $\forall$ $\exists$
Ada sistem formal tertentu yang disebut logika tingkat pertama yang memberi tahu kita apa artinya bahwa kita membuktikan formula tingkat pertama. Sistem diberikan sebagai seperangkat aturan inferensi.
Sebuah teori orde pertama $\mathcal{T}$ diberikan oleh:
- sebuah tanda tangan $\Sigma_{\mathcal{T}}$ yang terdiri dari satu set konstanta, simbol fungsi, dan simbol hubungan. Anggap ini sebagai ekstensi dari bahasa dasar logika tingkat pertama. Kami menyebutnya bahasa $\mathcal{T}$ .
- seperangkat formula urutan pertama yang tertutup secara deduktif yang ditulis dalam bahasa yang diperpanjang oleh tanda tangan.

Satu set formula dikatakan deduktif ditutup jika aplikasi aturan inferensi dari orde pertama logika untuk formula di memberikan formula yang lagi di . Dengan kata lain, mengandung semua konsekuensi logisnya. Cara yang umum untuk membuat himpunan adalah: mulailah dengan beberapa rangkaian formula , dan tambahkan padanya semua konsekuensi logisnya, dan konsekuensi dari konsekuensi itu, dan seterusnya. Ini disebut penutupan deduktif dari . Sering kita sebut rumus dalam aksioma . $S$ $S$ $S$ $S$ $S$ $A$ $A$ $A$

Sebuah teori mungkin lengkap atau tidak lengkap. Tidak penting untuk mengetahui apa yang dimaksud "lengkap" di sini, tetapi penting untuk mengetahui bahwa hal berikut dapat terjadi: kita dapat memiliki dua set rumus dan , sehingga , penutupan deduktif dari adalah teori lengkap, dan penutupan deduktif adalah tidak sebuah teori yang lengkap. $A$ $B$ $A \subseteq B$ $A$ $B$

Kami sekarang siap untuk menjawab pertanyaan Anda. Misalkan adalah teori yang tanda tangannya kosong dan rumus siapa yang merupakan penutupan deduktif set kosong. Misalkan adalah teori yang tanda tangannya adalah aritmetika Peano (konstanta , operasi unary , operasi biner dan ) dan rumusnya adalah penutupan deduktif aksioma Peano. Itu adalah fakta bahwa $T$ $P$ $0$ $S$ $+$ $\times$

$T$ terkandung dalam (sebenarnya terkandung dalam setiap teori), $P$ $T$
$T$ selesai,
$P$ tidak lengkap.

Teori secara populer disebut "logika tingkat pertama", tetapi ini benar-benar keliru. Beberapa orang sedikit lebih tepat dan menyebutnya "teori murni logika tingkat pertama". $T$

Singkatnya, pertanyaan Anda mengungkapkan hal berikut:

Anda tidak tahu bahwa "logika tingkat pertama" mungkin merujuk pada teori dengan tanda tangan kosong yang dihasilkan oleh aksioma kosong.
Teori yang lengkap mungkin menjadi tidak lengkap ketika kita mengembangkannya.
Anda menggunakan definisi kelengkapan yang salah. Definisi yang benar adalah: sebuah teori lengkap jika, setiap kalimat atau negasinya adalah teorema teori.

NB: kalimat adalah rumus tertutup ( kalimat yang tidak mengandung variabel bebas).

Terakhir, izinkan saya menjawab pertanyaan Anda tentang validitas:

sebuah formula dapat dibuktikan jika ada buktinya
sebuah rumus valid jika itu benar di setiap model

Sebuah meta-teorema dasar tentang logika tingkat pertama adalah bahwa setiap rumus yang dapat dibuktikan valid. Kebalikannya berlaku juga dan dikenal sebagai teorema kelengkapan Gödel .

Namun, sering terjadi bahwa dalam situasi tertentu seseorang dengan sengaja membuat ketidakcocokan antara validitas dan provabilitas untuk alasan yang baik. Sebagai contoh, jika kita membatasi perhatian hanya pada model yang terbatas , maka dapat dengan mudah terjadi bahwa akan ada pernyataan yang valid yang tidak memiliki bukti. Mengapa orang melakukan itu? Dalam ilmu komputer bisa jadi karena alasan algoritmik, atau karena seseorang hanya tertarik pada kelas model tertentu.

ANDA berkata "satu-satunya cara untuk mengetahui bahwa suatu kalimat itu valid adalah dengan membuktikannya". Ini mungkin terjadi pada tingkat informal (saya pikir Tuhan tidak setuju dengan Anda), tetapi perhatikan bahwa bukti validitas semacam itu terjadi di luar teori, pada tingkat meta. Memang, karena membangun validitas memerlukan seseorang untuk berbicara tentang semua model ini tentu bukan sesuatu yang kita harapkan untuk dilakukan di dalam teori.

Andrej Bauer
sumber

Anda sepertinya bingung tentang teorema kelengkapan Godel dan teorema ketidaklengkapan Godel. Apa yang Anda sebut "teorema ketidaklengkapan Godel" tampaknya merupakan negasi langsung dari teorema kelengkapan Godel. Teorema ketidaklengkapan pertama Godel adalah tentang kalimat yang tidak dapat dibuktikan atau dibantah, bukan kalimat yang valid tetapi tidak terbukti.

user2357112 mendukung Monica

Terima kasih, saya hanya menghapus sedikit itu karena tidak menambahkan apa pun pada penjelasan.

Andrej Bauer

@AndrejBauer dapatkah Anda mengklarifikasi 'paradoks' berikut ini dengan "1. dimuat dalam "? : Sejak tidak lengkap maka ada sehingga dan . Sekarang tanyakan " "? Karena (penutupan deduktif dari aksioma mereka), maka harus ada atau , tetapi keduanya melanggar asumsi keberadaan seperti !

T

$T$

P

$P$

P

$P$

s

$s$

s \notin P

$s \not\in P$

\neg s \notin P

$\neg s \not\in P$

s \in T

$s \in T$

T \subset P

$T \subset P$

s \in T

$s \in T$

\neg s \in T

$\neg s \in T$

s

$s$

Ayrat

pertanyaan lain: apakah Anda memiliki contoh pernyataan yang valid yang tidak memiliki bukti?

Ayrat

Klarifikasi kecil:

Anda mungkin berpikir bahwa teori dengan tanda tangan kosong adalah teori kosong, yaitu tidak mengandung rumus tertutup. Itu tidak benar. Logika orde pertama memungkinkan seseorang untuk membuktikan - tanpa menarik aksioma - formula tertutup tertentu yang dikenal sebagai tautologi. Ini 'benar' hanya karena bentuknya; mereka tidak memiliki konten yang berarti. Teorema Kelengkapan Godel kemudian mengatakan bahwa koleksi tautologi lengkap - yaitu, semua rumus tertutup yang valid (yaitu 'benar dalam semua model') sebenarnya diturunkan dalam logika orde pertama. [Buktinya menarik dan jelas tidak trivial.]

PMar
sumber