Aljabar Heyting

kekisi berbatas, dengan operasi sambungan dan pertemuan yang tertulis ∨ dan ∧ dan dengan elemen terkecil 0 dan elemen terbesar 1

Dalam matematika, sebuah Aljabar Heyting (juga dikenal sebagai aljabar pseudo-Boolean[1]) adalah kekisi berbatas, dengan operasi sambungan dan pertemuan yang tertulis ∨ dan ∧ dan dengan elemen terkecil 0 dan elemen terbesar 1, dilengkapi dengan operasi biner ab dari implikasi sedemikian rupa maka (ca) ≤ b adalah ekuivalen c ≤ (ab). Dari sudut pandang logika, AB adalah definisi dengan proposisi terlemah yang modus ponens, pada kaidah inferensi AB, AB yang merupakan kesan. Seperti Aljabar Boolean, aljabar Heyting sebagai bentuk varietas dapat diaksiomatis dengan persamaan hingga. Aljabar Heyting diperkenalkan oleh Arend Heyting (1930) untuk memformalkan logika intuisi.

Sebagai kekisi, aljabar Heyting merupakan distributif. Setiap aljabar Boolean adalah aljabar Heyting ketika ab didefinisikan sebagai ¬ab, seperti halnya setiap kelengkapan kekisi distributif yang memenuhi satu sisi hukum distributif tak hingga ab diambil sebagai supremum dari himpunan semua c yang sebagai cab. Dalam kasus hingga, setiap kekisi distributif tak kosong, khususnya setiap tak kosong hingga kaidah, secara otomatis kelengkapan dan sepenuhnya adalah distributif, dan karenanya dinamakan sebagai aljabar Heyting.

Ini mengikuti dari definisi bahwa 1 ≤ 0 → a, sesuai dengan intuisi bahwa setiap proposisi a tersirat oleh kontradiksi 0. Meskipun operasi negasi ¬a bukan bagian dari definisi, maka hal itu didefinisikan sebagai a → 0. Konten intuitif dari ¬a adalah proposisi yang mengasumsikan a yang disebabkan terjadinya kontradiksi. Definisi tersebut menyiratkan bahwa a ∧ ¬a = 0. Selanjutnya dapat ditunjukkan bahwa a ≤ ¬¬a, sebaliknya ¬¬aa tidak semua benar secara umum, yaitu eliminasi negasi ganda yang tidak berlaku secara umum dalam aljabar Heyting.

Aljabar Heyting menggeneralisasi aljabar Boolean dalam arti bahwa aljabar Heyting memenuhi a ∨ ¬a = 1 (pengecualian tengah), ekuivalen ¬¬a = a (eliminasi negasi ganda), adalah aljabar Boolean. Elemen-elemen dari aljabar Heyting H dari bentuk ¬a terdiri dari kisi Boolean, tetapi secara umum ini bukan subaljabar dari H (lihat di bawah).

Aljabar Heyting berfungsi sebagai model aljabar proposisional logika intuisi dengan cara yang sama dengan model aljabar Boolean proposisional logika klasik. Logika internal dari topos elementer didasarkan pada aljabar Heyting dari subobjek dari objek terminal 1 yang diurutkan dengan penyertaan, ekuivalen morfisme dari 1 ke pengklasifikasi subobbjek.

Himpunan terbukasdari ruang topologi sebagai bentuk kelengkapan aljabar Heyting. Kelengkapan aljabar Heyting dengan demikian menjadi objek utama studi dalam topologi tanpa titik.

Setiap aljabar Heyting yang himpunan elemen non-terbesarnya memiliki elemen terbesar (dan sebagai bentuk aljabar Heyting lainnya) adalah irreduksi tak langsung, dimana setiap aljabar Heyting dibuat secara irreduksi secara sublangsung dengan menggabungkan elemen terbesar yang baru. Oleh karena itu, bahkan di antara aljabar Heyting hingga, yang terdiri dari tak hingga yang tidak direduksi secara sublangsung, tidak ada dua di antaranya memiliki teori persamaan yang sama. Oleh karena itu, tidak ada himpunan hingga aljabar Heyting yang dapat menyediakan semua contoh tandingan untuk non-hukum aljabar Heyting. Ini sangat kontras dengan aljabar Boolean, yang satu-satunya yang tidak direduksi secara sublangsung adalah dua elemen dengan cukup untuk semua contoh tandingan untuk non-hukum aljabar Boolean, dasar untuk metode keputusan tabel kebenaran sederhana. Namun demikian, dapat ditentukan apakah persamaan berlaku untuk semua aljabar Heyting.[2]

Aljabar Heyting terkadang menggunakan aljabar semu-Boolean,[3] atau bahkan kekisi Brouwer,[4] meskipun istilah yang terakhir mungkin menunjukkan definisi ganda,[5] atau memiliki arti yang sedikit lebih umum.[6]

Definisi formal

sunting

Aljabar Heyting H adalah kisi hingga, maka untuk semua a dan b dalam H terdapat nilai terbesar elemen x dari H sedemikian rupa sehingga

 

Elemen ini adalah pseudo-kelengkapan relatif dari a dihubungkan dengan b, dan dilambangkan sebagai ab. Kita menulis 1 dan 0 untuk elemen terbesar dan terkecil dari H.

Dalam aljabar Heyting, kita mendefinisikan pseudo-kelengkapan ¬a dari elemen a dengan menyetel ¬a = (a→0). Menurut definisi,  , dan ¬a adalah elemen terbesar yang memiliki sifat ini. Namun, secara umum tidak benar bahwa  , demikian ¬ hanya sebagai pseudo-kelengkapan, bukan kelengkapan yang sebenarnya, seperti yang terjadi pada aljabar Boolean.

Sebuah kelengkapan aljabar Heyting adalah aljabar Heyting yang merupakan kekisi lengkap.

Sebuah subaljabar dari aljabar Heyting H adalah himpunan bagian H1 dari H yang merupakan 0 dan 1 dan sebagai penutupan bawah operasi ∧, ∨ dan →. Oleh karena itu, ¬ juga sebagai penutupan bawah. Sebuah subaljabar sebagai aljabar Heyting dengan operasi induksi.

Definisi alternatif

sunting

Definisi teori-kategori

sunting

Aljabar Heyting   adalah kekisi batas yang memiliki semua objek eksponensial.

Kekisi   sebagai salah satu kategori dimana pertemuan  , adalah produk. Kondisi eksponensial berarti bahwa untuk setiap objek   dan   dalam   sebuah   eksponensial unik sebagai objek dalam  .

Implikasi Heyting (ditulis juga   atau   untuk menghindari kebingungan seperti penggunaan   untuk menunjukkan fungtor) sebagai eksponensial:   adalah notasi alternatif untuk  . Dari definisi eksponensial kita memiliki implikasi ( ) adalah kanan adjoin untuk pertemuan ( ). Adjungsi ini dapat ditulis sebagai   atau lebih lengkapnya sebagai:  

Definisi teori kisi

sunting

Definisi ekuivalen dari aljabar Heyting dapat diberikan dengan mempertimbangkan pemetaan:

 

untuk beberapa a dalam H. Kekisi berbatas H adalah aljabar Heyting jika dan hanya jika setiap pemetaan fa adalah adjoint bawah monoton hubungan Galois. Dalam hal ini adjoin atas ga diberikan oleh ga(x) = ax, dimana → sebagai definisi atas.

Namun definisi lain adalah sebagai kekisi residu dimana operasi monoidnya adalah ∧. Unit monoid kemudian menjadi sebagai elemen teratas 1. Komutatifitas monoid ini menyiratkan bahwa kedua residu bertepatan sebagai ab.

Kekisi terikat dengan operasi implikasi

sunting

Diberikan kisi terbatas A dengan elemen terbesar dan terkecil 1 dan 0, dan operasi biner →, ini sebagai bentuk aljabar Heyting jika dan hanya jika yang berikut ini berlaku:

  1.  
  2.  
  3.  
  4.  

dimana 4 adalah hukum distributif untuk →.

Karakterisasi menggunakan aksioma logika intuisi

sunting

Karakterisasi aljabar Heyting ini membuat bukti fakta dasar mengenai hubungan antara kalkulus proposisional, intuisionis, dan aljabar Heyting dekat (untuk fakta ini, lihat bagian "identitas pembuktian" dan "konstruksi universal"). Orang harus menganggap elemen   sebagai makna, secara intuitif, "terbukti benar." Bandingkan dengan aksioma di Logika intuisi#Aksiomatisasi.

Diberikan satu himpunan A dengan tiga operasi biner →, ∧ dan ∨, dan dua elemen berbeda   dan  , maka A adalah aljabar Heyting untuk operasi ini (dan relasinya ≤ didefinisikan oleh kondisi bahwa   maka ab =  ) jika dan hanya jika kondisi berikut berlaku untuk setiap elemen x, y dan z dari A:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  

Akhirnya, kita dapat mendefinisikan ¬x sebagai x .

Kondisi 1 mengatakan bahwa formula yang setara harus diidentifikasi. Ketentuan 2 menyatakan bahwa rumus yang terbukti benar ditutup di bawah modus ponens. Ketentuan 3 dan 4 adalah ketentuan lalu. Ketentuan 5, 6, dan 7 adalah ketentuan dan. Ketentuan 8, 9, dan 10 adalah ketentuan atau. Kondisi 11 adalah kondisi salah.

Tentu saja, jika serangkaian aksioma yang berbeda dipilih untuk logika, kita dapat memodifikasi aksioma.

Contoh

sunting
 
Aljabar Heyting bebas melalui satu generator (alias kekisi Rieger–Nishimura)
  • Setiap aljabar Boolean adalah aljabar Heyting, dengan pq diberikan oleh ¬pq.
  • Setiap himpunan terurut total yang memiliki elemen terkecil 0 dan elemen terbesar 1 adalah aljabar Heyting (jika dilihat sebagai kekisi). Dalam hal ini pq sama dengan 1 ketika p≤q, dan q sebaliknya.
  • Aljabar Heyting sederhana yang belum menjadi aljabar Boolean adalah himpunan terurut total {0, 12, 1} (dilihat sebagai kekisi), menghasilkan sebagai operasi:
     
    b
    a
    0 12 1
    0 0 0 0
    12 0 12 12
    1 0 12 1
     
     
    b
    a
    0 12 1
    0 0 12 1
    12 12 12 1
    1 1 1 1
     
    ab
    b
    a
    0 12 1
    0 1 1 1
    12 0 1 1
    1 0 12 1
     
    a ¬a
    0 1
    12 0
    1 0

    Dalam contoh ini, 12∨¬12 = 12∨(12 → 0) = 12∨0 = 12 melancungkan hukum tengah yang dikecualikan.

  • Setiap topologi sebagai kelengkapan aljabar Heyting dalam bentuk kisi himpunan terbuka-nya. Dalam hal ini, elemen AB adalah interior dari gabungan Ac dan B, di mana Ac menunjukkan kelengkapan dari himpunan terbuka A. Tidak semua kelengkapan aljabar Heyting sebagai bentuk seperti ini. Isu-isu ini dipelajari dalam topologi tak berarti, dimana kelengkapan aljabar Heyting juga disebut bingkai atau lokal.
  • Setiap aljabar interior sebagai aljabar Heyting dalam bentuk kekisi elemen terbukanya. Setiap aljabar Heyting sebagai bentuk ini karena aljabar Heyting diselesaikan menjadi aljabar Boolean dengan mengambil ekstensi Boolean bebas sebagai kekisi distributif hingga dan maka sebagai topologi umum dalam aljabar Boolean ini.
  • Aljabar Lindenbaum dari logika intuisi proposisional adalah aljabar Heyting.
  • Elemen global dari pengklasifikasi subobjek Ω dari topos dasar sebagai bentuk aljabar Heyting; itu adalah aljabar Heyting dari nilai kebenaran dari logika tingkat tinggi intuitif induksi oleh topos.
  • Aljabar Łukasiewicz—Moisil (LMn) merupakan aljabar Heyting untuk semua n[7] (namun bukan aljabar-MV untuk n ≥ 5[8]).

Sifat umum

sunting

Urutan   pada aljabar Heyting H dapat diperoleh dari operasi → sebagai berikut: untuk setiap elemen a, b dari H,   jika dan hanya jika ab = 1.

Berbeda dengan beberapa logika nilai banyak, aljabar Heyting terbagi sifat berikut dengan aljabar Boolean: jika negasi memiliki titik tetap (misal ¬a = a untuk beberapa a), maka aljabar Heyting adalah aljabar Heyting satu-elemen trivial.

Identitas pembuktian

sunting

Diberikan rumus   dari kalkulus proposisional (menggunakan, variabel, penghubung  , dan konstanta 0 dan 1), yang terbukti sejak awal studi aljabar Heyting, bahwa dua kondisi berikut adalah ekuivalen:

  1. Rumus F terbukti benar dalam kalkulus proposisional intuisionis.
  2. Identitas   untuk setiap aljabar Heyting H dan elemen  .

Metaimplikasi 1 ⇒ 2 merupakan metode praktis utama untuk membuktikan identitas dalam aljabar Heyting. Dalam praktiknya, dengan menggunakan teorema deduksi dalam pembuktian semacam itu.

Karena untuk setiap a dan b dalam aljabar Heyting H kita memiliki   jika dan hanya jika ab = 1, mengikuti dari 1 ⇒ 2 bahwa setiap kali rumus FG pembuktian dengan benar, kita memiliki   untuk setiap aljabar Heyting H, dan elemen  . Ini mengikuti dari teorema deduksi bahwa FG dapat dibuktikan [dari ketiadaan] jika dan hanya jika G dibuktikan dari F, yaitu jika G adalah konsekuensi pembuktian dari F. Khususnya, jika F dan G membuktikan ekuivalen, maka  , karena ≤ adalah relasi orde.

1 ⇒ 2 dibuktikan dengan aksioma logika dari sistem pembuktian dan memverifikasi bahwa nilainya adalah 1 dalam setiap aljabar Heyting, dan kemudian memverifikasi bahwa penerapan aturan inferensi ke ekspresi dengan nilai 1 dalam aljabar Heyting menghasilkan ekspresi dengan nilai 1. Sebagai contoh, memilih sistem pembuktian yang memiliki modus ponens sebagai satu-satunya aturan inferensi, dan aksiomanya adalah gaya Hilbert yang diberikan dalam aksiomatisasi. Maka memverifikasikan dengan mengikuti dari definisi aljabar Heyting seperti aksioma yang diberikan di atas.

1 ⇒ 2 sebagai metode untuk membuktikan bahwa rumus proposisi tertentu, meskipun tautologi dalam logika klasik, tidak bisa dibuktikan dalam logika proposisional intuisionis. Untuk membuktikan bahwa beberapa rumus   tidak dapat dibuktikan, cukup dengan menunjukkan aljabar Heyting H dan elemen   sedemikian rupa sehingga  .

Jika ingin penyebutan logika tidak digunakan, maka dalam praktiknya menjadi perlu untuk membuktikan sebagai lema versi teorema deduksi yang valid untuk aljabar Heyting: untuk setiap elemen a, b dan c dari aljabar Heyting H, dengan memiliki  .

Untuk lebih lanjut tentang metaimplication 2 ⇒ 1, lihat bagian "konstruksi universal" dibawah.

Distributivitas

sunting

Aljabar Heyting digunakan sebagai distributif. Secara khusus, maka kita memiliki identitas

  1.  
  2.  

Hukum distributif terkadang dinyatakan sebagai aksioma, namun kenyataannya mengikuti dari keberadaan pseudo-kelengkapan relatif. Alasannya adalah, sebagai adjoin bawah dari hubungan Galois, kekal   untuk semua suprema. Distribusi pada gilirannya hanyalah kekal suprema biner oleh  .

Dengan argumen serupa, hukum distributif tak hingga berikut berlaku dalam kelengkapan aljabar Heyting:

 

untuk setiap elemen x dalam H dan setiap himpunan bagian Y dari H. Sebaliknya, setiap kisi kelengkapan yang memenuhi hukum distributif tak hingga atas adalah kelengkapan aljabar Heyting, dengan

 

sebagai operasi pseudo-kelengkapan relatif.

Elemen reguler dan kelengkapan

sunting

Sebuah elemen x dari aljabar Heyting H disebut reguler jika salah satu dari kondisi ekuivalen berikut berlaku:

  1. x = ¬¬x.
  2. x = ¬y untuk beberapa y dalam H.

Kondisi ekuivalen ini dapat dinyatakan kembali hanya sebagai identitas ¬¬¬x = ¬x, berlaku untuk semua x dalan H.

Elemen x dan y dari aljabar Heyting H disebut kelengkapan satu sama lain jika xy = 0 dan xy = 1. Jika, "y" adalah unik dan sebenarnya harus sama dengan ¬x. Yang disebut juga dengan elemen kelengkapan x jika ia adalah komplemen. Bahwa jika kelengkapan x, maka demikian pula ¬x, kemudian x dan ¬x adalah kelengkapan sama lain. Namun, bahkan jika x kelengkapan sama lain, ¬x mungkin tetap memiliki komplemen (tidak sama dengan x). Dalam setiap aljabar Heyting, elemen 0 dan 1 saling melengkapi. Misalnya, mungkin saja ¬x adalah 0 untuk setiap x berbeda dari 0, dan 1 jika x = 0, dalam hal ini 0 dan 1 adalah satu-satunya elemen reguler.

Setiap elemen kelengkapan dari aljabar Heyting adalah reguler, meskipun sebaliknya tidak berlaku secara umum. Secara khusus, 0 dan 1 adalah reguler.

Untuk setiap aljabar Heyting H, kondisi ekuivalen berikut ini:

  1. H adalah aljabar Boolean;
  2. setiap x dalam H adalah reguler;[9]
  3. setiap x dalam H adalah kelengkapan.[10]

Dalam hal ini, elemen ab adalah sama dengan ¬ab.

Elemen reguler (resp. kelengkapan) dari setiap aljabar Heyting H membentuk aljabar Boolean Hreg (resp. Hkomp ), dimana operasi ∧, ¬ dan →, serta konstanta 0 dan 1, bertepatan dengan "H". Dalam kasus Hcomp dengan operasi ∨, maka Hcomp adalah subaljabar dari H. Namun secara umum, Hreg bukan sebagai subaljabar dari H, karena operasi gabungan ∨reg mungkin berbeda dari ∨. Untuk x, yHreg, maka kita menggunakan sebagai xreg y = ¬(¬x ∧ ¬y). Lihat di bawah untuk kondisi perlu dan cukup agar ∨reg bertepatan dengan ∨.

Hukum De Morgan dalam aljabar Heyting

sunting

Salah satu dari dua hukum De Morgan terpenuhi dalam setiap aljabar Heyting, yaitu

 

Namun, hukum De Morgan lainnya tidak berlaku. Sebagai gantinya, kita memiliki hukum de Morgan lemah:

 

Pernyataan berikut ekuivalen untuk semua aljabar Heyting H:

  1. H memenuhi kedua hukum De Morgan,
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  

Kondisi 2 adalah hukum De Morgan lainnya. Kondisi 6 menyatakan bahwa operasi gabungan ∨reg pada aljabar Boolean Hreg elemen reguler H bertepatan dengan operasi ∨ dari H. Kondisi 7 menyatakan bahwa setiap elemen kelengkapan reguler, yaitu Hreg = Hkomp.

Dengan membuktikan ekuivalen, jelas metaimplikasi 1 ⇒ 2, 2 ⇒ 3 dan 4 ⇒ 5 adalah trivial. Selanjutnya, 3 ⇔ 4 dan 5 ⇔ 6 hasil sederhana dari hukum De Morgan pertama dan definisi elemen reguler. Dengan menunjukkan bahwa 6 ⇒ 7 dengan mengambil ¬x dan ¬¬x menggantikan x dan y di 6 dan menggunakan identitas a ∧ ¬a = 0. Perhatikan bahwa 2 ⇒ 1 mengikuti dari hukum De Morgan pertama, dan 7 ⇒ 6 hasil dari fakta bahwa operasi gabungan ∨ pada subaljabar Hcomp hanyalah pembatas ∨ ke Hkomp, dengan mempertimbangkan karakterisasi yang telah kami berikan untuk kondisi 6 dan 7. Metaimplikasi 5 ⇒ 2 adalah konsekuensi trivial dari hukum De Morgan lemah, dengan ¬x dan ¬y menggantikan x dan y di 5.

Aljabar Heyting yang memenuhi sifat- di atas terkait dengan logika De Morgan dengan cara yang sama seperti aljabar Heyting pada umumnya terkait dengan logika intuisionis.

Morfisme aljabar Heyting

sunting

Definisi

sunting

Diberikan dua aljabar Heyting H1 dan H2 dengan pemetaan f : H1H2, maka bahwa ƒ adalah morfisme dari aljabar Heyting apabila untuk setiap elemen x dan y dalam H1 , maka dari itu:

  1.  
  2.  
  3.  
  4.  

Ini mengikuti dari salah satu dari tiga kondisi terakhir (2, 3, atau 4) bahwa f adalah fungsi tingkatan, yaitu f(x) ≤ f(y) dengan xy.

Asumsi H1 dan H2 adalah struktur dengan operasi →, ∧, ∨ (kemungkinan ¬) dan konstanta 0 dan 1, dan f adalah pemetaan surjektif dari H1 ke H2 dengan sifat 1 sampai 4 atas. Maka jika H1 adalah aljabar Heyting, demikian pula H2. Ini mengikuti dari karakterisasi aljabar Heyting sebagai kekisi batas (sebagai struktur aljabar dari himpunan terurut sebagian) dengan operasi → yang memenuhi identitas tertentu.

Peta identitas f(x) = x dari aljabar Heyting ke sendiri adalah morfisme, dan gabungan gf dari setiap dua morfisme f dan g adalah morfisme. Oleh karena itu aljabar Heyting sebagai bentuk kategori.

Contoh

sunting

Diberikan aljabar Heyting H dan setiap subaljabar H1, pemetaan inklusi i : H1H adalah morfisme.

Untuk setiap aljabar Heyting H, peta x ↦ ¬¬x didefinisikan morfisme dari H ke aljabar Boolean dari elemen reguler Hreg. Ini adalah secara umum bukan sebuah morfisme dari H ke sendiri, karena operasi gabungan dari Hreg mungkin berbeda dari H.

Hasil bagi

sunting

Maka H sebagai aljabar Heyting, dan FH. Dengan menyebutnya F sebagai filter pada H jika memenuhi sifat berikut:

  1.  
  2.  
  3.  

Perpotongan himpunan filter pada H adalah filter. Oleh karena itu, jika diberikan himpunan bagian S dari H, maka filter terkecil-nya adalah S. Dengan menyebutnya filter yang dihasilkan oleh S. Jika S kosong, F = {1}. Jika tidak, F sama dengan himpunan x dalam H sehingga terdapat y1, y2, ..., ynS dengan y1y2 ∧ ... ∧ ynx.

Jika H adalah aljabar Heyting dan F adalah filter pada H, dengan mendefinisikan relasi ∼ pada H sebagai berikut: maka ditulis sebagai xy dengan xy dan yx keduanya milik F. Maka ∼ adalah relasi ekuivalen; apabila ditulis H/F untuk himpunan hasil bagi. Terdapat struktur aljabar Heyting unik pada H/F sehingga surjeksi kanonik-nya adalah pF : HH/F yang sebagai morfisme aljabar Heyting. Dengan menyebutnya aljabar Heyting H/F sebagai hasil bagi dari H dengan F.

Maka S sebagai himpunan bagian dari aljabar Heyting H dan maka F sebagai filter yang dihasilkan oleh S. Maka H/F memenuhi sifat universal berikut:

Mengingat morfisme dari aljabar Heyting f : HH′ suatu f(y) = 1 untuk setiap yS, faktor f unik melalui surjeksi kanonik pF : HH/F. Artinya, morfisme unik f′ : H/FH′ sebagai f′pF = f. Morfisme f′ dikatakan sebagai induksi oleh f.

Maka f : H1H2 adalah morfisme aljabar Heyting. Kernel dari f, yang ditulis sebagai "ker" f yang merupakan himpunan f−1[{1}]. Ini adalah filter pada H1. (Catatan: Harus diperhatikan karena definisi ini, jika diterapkan pada morfisme aljabar Boolean, adalah ganda dengan apa yang disebut inti morfisme yang dipandang sebagai morfisme gelanggang.) Dengan hal diatas, induksi f adalah morfisme f′ : H1/(ker f) → H2. Ini adalah isomorfisme H1/(ker f) ke subaljabar f[H1] dari H2.

Konstruksi universal

sunting

Aljabar Heyting rumus proposisional dalam variabel n hingga dengan ekuivalen intuisi

sunting

Metaimplikasi 2 ⇒ 1 pada bagian "identitas pembuktian" dibuktikan dengan menunjukkan bahwa hasil konstruksi berikut yang merupakan aljabar Heyting:

  1. Pertimbangkan himpunan L dari rumus proposisi dalam variabel A1, A2,..., An.
  2. Diberikan L dengan preorder ≼ dengan mendefinisikan FG jika G adalah (intuisionis) konsekuensi logika dari F, yaitu jika G membuktikan dari F. Bahwa ≼ adalah preorder.
  3. Pertimbangkan relasi ekuivalensi FG induksi dari preorder F≼G. Didefinisikan oleh FG jika dan hanya jika FG dan GF. Sebenarnya adalah hubungan ekuivalen logika (intuisionis).
  4. Misalkan H0 sebagai himpunan hasil bagi L/∼. Ini akan menjadi aljabar Heyting yang diinginkan.
  5. Dengan menulis [F] untuk kelas ekuivalensi dari rumus F. Operasi →, ∧, ∨ dan ¬ yang didefinisikan oleh L. Verifikasi bahwa rumus yang diberikan F dan G, kelas ekuivalensi [FG], [FG], [FG] dan [¬F] hanya bergantung pada [F] dan [G]. Ini mendefinisikan operasi →, ∧, ∨ dan ¬ pada himpunan hasil bagi H0=L/∼. Lebih lanjut definisikan 1 sebagai kelas pernyataan yang terbukti benar, dan himpunan 0=[⊥].
  6. Verifikasi bahwa H0, bersama dengan operasi ini, adalah aljabar Heyting. Dengan menggunakan definisi seperti aksioma dari aljabar Heyting. H0 memenuhi kondisi MAKA-1 sampai SALAH karena semua rumus dari bentuk yang diberikan adalah aksioma logika intuisionis. MODUS-PONENS mengikuti dari fakta bahwa jika rumus ⊤→F, dimana pembuktian benar, maka F adalah pembuktian benar (dengan penerapan kaidah modus ponens inferensi). Akhirnya, hasil EKUIV dari fakta bahwa jika FG dan GF keduanya terbukti benar, maka F dan G dapat dibuktikan satu sama lain (dengan penerapan kaidah modus ponens inferensi) dengan [F]=[G].

Seperti biasa di bawah definisi aljabar Heyting seperti aksioma, kita mendefinisikan ≤ pada H0 dengan syarat bahwa xy jika dan hanya jika xy=1. Karena, dengan teorema deduksi, rumus FG dengan pembuktian benar jika dan hanya jika G dapat dibuktikan dari F, maka [F]≤[G] jika dan hanya jika F≼G. Dengan kata lain, adalah relasi order pada L/∼ yang diinduksi oleh preorder ≼ pada L.

Aljabar Heyting bebas pada himpunan generator sebarang

sunting

Bahkan, konstruksi sebelumnya dapat dilakukan untuk setiap Himpunan variabel {Ai : iI} (secara khusus tak hingga). Dengan cara ini diperoleh aljabar Heyting bebas pada variabel {Ai}, yang akan dinyatakan kembali dengan H0. Dalam arti "bebas" bahwa aljabar Heyting "H" yang diberikan bersama dengan keluarga elemen〈ai: iI〉, apabila terdapat morfisme unik f:H0H dari suatu f([Ai])=ai. Keunikan f tidak sulit untuk dilihat, dan keberadaannya pada dasarnya berasal dari metaimplikasi 1 ⇒ 2 dari bagian "Identitas pembuktian" di atas, dalam bentuk akibat wajarnya bahwa setiap kali F dan G adalah rumus pembuktian ekuivalen, F(〈ai〉)=G(〈ai〉) untuk setiap keluarga elemen 〈ai〉dalam H.

Aljabar Heyting rumus ekuivalen yang berhubungan dengan teori T

sunting

Diberikan satu himpunan rumus T dalam variabel {Ai}, dilihat sebagai aksioma, konstruksi yang sama dapat dilakukan terhadap suatu relasi FG mendefinisikan pada L berarti bahwa G adalah konsekuensi pembuktian dari F dan himpunan aksioma T. Maka dengan menunjukkan HT sebagai aljabar Heyting yang diperoleh. Maka HT memenuhi sifat universal yang sama dengan H0 di atas, namun apabila aljabar Heyting H dan keluarga elemen 〈ai〉 memenuhi sifat J(〈ai〉)=1 untuk setiap aksioma J(〈Ai〉) dalam T. Maka dengan memperhatikan bahwa HT, diambil dengan keluarga elemen 〈[Ai]〉sendiri yang memenuhi sifat ini. Keberadaan dan keunikan morfisme pembuktian dengan cara yang sama untuk H0, kecuali bahwa apabila memodifikasi metaimplikasi 1 ⇒ 2 di "Identitas pembuktian" sehingga 1 terbaca "pembuktian benar" dari T," dan 2 terbaca "setiap elemen a1, a2,..., an dalam H pernyataan rumus T."

Aljabar Heyting HT yang baru saja didefinisikan apabila dilihat sebagai hasil bagi dari aljabar Heyting bebas H0 pada himpunan variabel yang sama, dengan sifat universal H0 sehubungan dengan HT, dan keluarga elemen 〈[Ai]〉.

Setiap aljabar Heyting isomorfik ke salah satu bentuk HT. Untuk melihat ini, misalkan H berupa aljabar Heyting, dan maka 〈ai: i∈I〉 sebagai keluarga elemen dengan hasil H (misalnya, keluarga surjektif). Dengan memperhatikan himpunan T dari rumus J(〈Ai〉) dalam variabel 〈Ai: i∈I〉 seperti J(〈ai〉)=1. Maka, memperoleh morfisme f:HTH dengan sifat universal HT , yang jelas-jelas surjektif. Tidak sulit untuk menunjukkan bahwa f adalah injektif.

Perbandingan dengan aljabar Lindenbaum

sunting

Konstruksi yang diberikan memainkan peran memenuhi analog sehubungan dengan aljabar Heyting dengan aljabar Lindenbaum berhubungan dengan Aljabar Boolean. Faktanya, aljabar Lindenbaum BT dalam variabel {Ai} sehubungan dengan aksioma T bersama HTT1, dimana T1 adalah himpunan semua rumus dari formulir ¬¬FF, karena aksioma tambahan T1 adalah satu-satunya aksioma yang perlu ditambahkan agar semua tautologi klasik pembuktian.

Aljabar Heyting seperti yang diterapkan pada logika intuisi

sunting

Jika menafsirkan aksioma logika proposisional intuisionistik sebagai istilah dari aljabar Heyting, apabila mengevaluasi ke elemen terbesar 1, dalam aljabar Heyting hanya di bawah penetapan nilai ke variabel rumus. Misalnya, (PQ)→P adalah apabila definisi kelengkapan semu dengan elemen terbesar x sehingga  . Pertidaksamaan ini dipenuhi untuk setiap x, sebagai x yang terbesar adalah 1.

Selanjutnya, kaidah modus ponens memungkinkan kita untuk menurunkan rumus Q dari rumus P dan PQ. Namun dalam aljabar Heyting, jika P bernilai 1, dan PQ bernilai 1, maka itu berarti  , dan maka  ; hanya mungkin Q memiliki nilai 1.

Ini berarti bahwa jika suatu rumus dapat diturunkan dari hukum logika intuisionistik, yang diturunkan dari aksiomanya melalui kaidah modus ponens, maka apabila nilai 1 di semua aljabar Heyting di bawah penetapan nilai hanya ke variabel rumus. Namun apabila membangun aljabar Heyting di mana nilai hukum Peirce tidak selalu 1. Pertimbangkan aljabar 3-elemen {0,12,1} seperti yang diberikan di atas. Jika menetapkan 12 ke P dan 0 ke Q, maka nilai hukum Peirce ((PQ)→ P)→P adalah 12. Oleh karena itu, hukum Peirce tidak dapat diturunkan secara intuitif. Lihat isomorfisme Curry–Howard untuk konteks umum tentang apa yang menjelaskan dalam teori tipe.

Kebalikannya juga dapat dibuktikan: jika suatu rumus selalu bernilai 1, maka rumus tersebut dapat dikurangkan dari hukum logika intuisionistik, jadi rumus "valid secara intuitif" adalah rumus yang selalu memiliki nilai 1. Ini mirip dengan gagasan bahwa rumus yang "valid secara klasik" adalah rumus yang memiliki nilai 1 di aljabar Boolean dua elemen di bawah kemungkinan penetapan nilai benar dan salah ke variabel rumus—yaitu, yaitu rumus yang merupakan tautologi dalam pengertian tabel kebenaran yang biasa. Aljabar Heyting, dari sudut pandang logika, merupakan generalisasi dari sistem nilai kebenaran yang biasa, dan elemen terbesarnya 1 dianalogikan dengan 'benar'. Sistem logika dua nilai yang biasa adalah kasus khusus dari aljabar Heyting, dan yang terkecil non-trivial, dimana satu-satunya elemen aljabar adalah 1 (benar) dan 0 (salah).

Masalah keputusan

sunting

Masalah apakah persamaan yang diberikan berlaku di setiap aljabar Heyting pembuktian apabila ditentukan oleh S. Kripke pada tahun 1965.[2] Kompleksitas komputasi yang tepat dari masalah ini dibuat oleh R. Statman pada tahun 1979, yang menunjukkan kelengkapan-RUANGP[11] dan karenanya setidaknya memutuskan persamaan aljabar Boolean (ditunjukkan oleh coNP-complete pada tahun 1971 oleh S. Cook)[12] dan diperkirakan akan jauh lebih sulit. Teori dasar atau urutan pertama dari aljabar Heyting tidak dapat diputuskan.[13] Masih terbuka apakah teori universal Horn dari aljabar Heyting, atau masalah kata, apabila ditentukan.[14] Sebuah propos dari masalah kata diketahui bahwa aljabar Heyting tak hingga secara lokal (tidak ada aljabar Heyting yang dihasilkan oleh himpunan tak kosong hingga), berbeda dengan aljabar Boolean hingga secara lokal dan masalah kata yang dapat ditentukan. Tidak diketahui apakah aljabar Heyting lengkap gratis ada kecuali dalam kasus generator tunggal dimana aljabar Heyting bebas pada satu generator yang diselesaikan secara sederhana dengan menghubungkan puncak baru.

Catatan

sunting
  1. ^ https://www.encyclopediaofmath.org/index.php/Pseudo-Boolean_algebra
  2. ^ a b Kripke, S. A.: 1965, 'Analisis semantik logika intuisionistik I'. Dalam: J. N. Crossley dan M. A. E. Dummett (eds.): Sistem Formal dan Fungsi Rekursif. Amsterdam: Belanda Utara, hlm. 92–130.
  3. ^ Helena Rasiowa; Roman Sikorski (1963). The Mathematics of Metamathematics. Państwowe Wydawnictwo Naukowe (PWN). hlm. 54–62, 93–95, 123–130. 
  4. ^ A. G. Kusraev; Samson Semenovich Kutateladze (1999). Boolean valued analysis. Springer. hlm. 12. ISBN 978-0-7923-5921-0. 
  5. ^ Yankov, V.A. (2001) [1994], "Brouwer lattice", dalam Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
  6. ^ Thomas Scott Blyth (2005). Lattices and ordered algebraic structures. Springer. hlm. 151. ISBN 978-1-85233-905-0. 
  7. ^ Georgescu, G. (2006). "N-Valued Logics and Łukasiewicz–Moisil Algebras". Axiomathes. 16: 123. doi:10.1007/s10516-005-4145-6. , Theorem 3.6
  8. ^ Iorgulescu, A.: Hubungan antara aljabar-MVn dan n-nilai aljabar Łukasiewicz–Moisil—I. Matematika Diskrit. 181, 155–177 (1998) DOI:10.1016/S0012-365X(97)00052-6
  9. ^ Rutherford (1965), Th.26.2 p.78.
  10. ^ Rutherford (1965), Th.26.1 p.78.
  11. ^ Statman, R. (1979). "Intuitionistic propositional logic is polynomial-space complete". Theoretical Comput. Sci. 9: 67–72. doi:10.1016/0304-3975(79)90006-9. hdl:2027.42/23534 . 
  12. ^ Cook, S.A. (1971). "The complexity of theorem proving procedures". hlm. 151–158. doi:10.1145/800157.805047. 
  13. ^ Grzegorczyk, Andrzej (1951). "Undecidability of some topological theories" (PDF). Fundamenta Mathematicae. 38: 137–52. 
  14. ^ Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See paragraph 4.11)

Lihat pula

sunting

Referensi

sunting
  • Rutherford, Daniel Edwin (1965). Introduction to Lattice Theory. Oliver and Boyd. OCLC 224572. 
  • F. Borceux, Handbook of Categorical Algebra 3, In Encyclopedia of Mathematics and its Applications, Vol. 53, Cambridge University Press, 1994. ISBN 0-521-44180-3 OCLC 52238554
  • G. Gierz, K.H. Hoffmann, K. Keimel, J. D. Lawson, M. Mislove and D. S. Scott, Continuous Lattices and Domains, In Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003.
  • S. Ghilardi. Free Heyting algebras as bi-Heyting algebras, Math. Rep. Acad. Sci. Canada XVI., 6:240–244, 1992.
  • Heyting, A. (1930), "Die formalen Regeln der intuitionistischen Logik. I, II, III", Sitzungsberichte Akad. Berlin: 42–56, 57–71, 158–169, JFM 56.0823.01 

Pranala luar

sunting