Aljabar Heyting

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 a → b dari implikasi sedemikian rupa maka (c ∧ a) ≤ b adalah ekuivalen c ≤ (a → b). Dari sudut pandang logika, A → B adalah definisi dengan proposisi terlemah yang modus ponens, pada kaidah inferensi A → B, A ⊢ B 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 a → b didefinisikan sebagai ¬a ∨ b, seperti halnya setiap kelengkapan kekisi distributif yang memenuhi satu sisi hukum distributif tak hingga a → b diambil sebagai supremum dari himpunan semua c yang sebagai c ∧ a ≤ b. 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 ¬¬a ≤ a 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

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

a\wedge x\leq b.

Elemen ini adalah pseudo-kelengkapan relatif dari a dihubungkan dengan b, dan dilambangkan sebagai a→b. 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, $a\wedge \lnot a=0$ , dan ¬a adalah elemen terbesar yang memiliki sifat ini. Namun, secara umum tidak benar bahwa $a\vee \lnot a=1$ , 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 H₁ 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

Definisi teori-kategori

Aljabar Heyting $H$ adalah kekisi batas yang memiliki semua objek eksponensial.

Kekisi $H$ sebagai salah satu kategori dimana pertemuan $\wedge$ , adalah produk. Kondisi eksponensial berarti bahwa untuk setiap objek $Y$ dan $Z$ dalam $H$ sebuah $Z^{Y}$ eksponensial unik sebagai objek dalam $H$ .

Implikasi Heyting (ditulis juga $\Rightarrow$ atau $\multimap$ untuk menghindari kebingungan seperti penggunaan $\to$ untuk menunjukkan fungtor) sebagai eksponensial: $Y\Rightarrow Z$ adalah notasi alternatif untuk $Z^{Y}$ . Dari definisi eksponensial kita memiliki implikasi ( $\Rightarrow :H\times H\to H$ ) adalah kanan adjoin untuk pertemuan ( $\wedge :H\times H\to H$ ). Adjungsi ini dapat ditulis sebagai $(-\wedge Y)\dashv (Y\Rightarrow -)$ atau lebih lengkapnya sebagai: $(-\wedge Y):H{\stackrel {\longrightarrow }{\underset {\longleftarrow }{\top }}}H:(Y\Rightarrow -)$

Definisi teori kisi

Definisi ekuivalen dari aljabar Heyting dapat diberikan dengan mempertimbangkan pemetaan:

{\begin{cases}f_{a}\colon H\to H\\f_{a}(x)=a\wedge x\end{cases}}

untuk beberapa a dalam H. Kekisi berbatas H adalah aljabar Heyting jika dan hanya jika setiap pemetaan f_a adalah adjoint bawah monoton hubungan Galois. Dalam hal ini adjoin atas g_a diberikan oleh g_a(x) = a→x, 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 a→b.

Kekisi terikat dengan operasi implikasi

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:

$a\to a=1$
$a\wedge (a\to b)=a\wedge b$
$b\wedge (a\to b)=b$
$a\to (b\wedge c)=(a\to b)\wedge (a\to c)$

dimana 4 adalah hukum distributif untuk →.

Karakterisasi menggunakan aksioma logika intuisi

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 $\top$ 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 $\bot$ dan $\top$ , maka A adalah aljabar Heyting untuk operasi ini (dan relasinya ≤ didefinisikan oleh kondisi bahwa $a\leq b$ maka a→b = $\top$ ) jika dan hanya jika kondisi berikut berlaku untuk setiap elemen x, y dan z dari A:

${\mbox{Jika }}x\leq y{\mbox{ dan }}y\leq x{\mbox{ maka }}x=y,$
${\mbox{Jika }}\top \leq y,{\mbox{ maka }}y=\top ,$
$x\leq y\to x,$
$x\to (y\to z)\leq (x\to y)\to (x\to z),$
$x\land y\leq x,$
$x\land y\leq y,$
$x\leq y\to (x\land y),$
$x\leq x\lor y,$
$y\leq x\lor y,$
$x\to z\leq (y\to z)\to (x\lor y\to z),$
$\bot \leq x.$

Akhirnya, kita dapat mendefinisikan ¬x sebagai x→ $\bot$ .

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

Aljabar Heyting bebas melalui satu generator (alias kekisi Rieger–Nishimura)

Setiap aljabar Boolean adalah aljabar Heyting, dengan p→q diberikan oleh ¬p∨q.
Setiap himpunan terurut total yang memiliki elemen terkecil 0 dan elemen terbesar 1 adalah aljabar Heyting (jika dilihat sebagai kekisi). Dalam hal ini p→q 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:

$a\land b$
b a	12	1
0	0	0
12	12	12
1	12	1

$a\lor b$
b a	0	12	1
0	0	12	1
12	12	12	1
1	1	1	1

$a \to b$
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 \lor\neg 12 = 12 \lor(12 \to 0) = 12 \lor0 = 12$ melancungkan hukum tengah yang dikecualikan.

Setiap topologi sebagai kelengkapan aljabar Heyting dalam bentuk kisi himpunan terbuka-nya. Dalam hal ini, elemen A→B adalah interior dari gabungan A^c dan B, di mana A^c 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 (LM_n) merupakan aljabar Heyting untuk semua n^[7] (namun bukan aljabar-MV untuk n ≥ 5^[8]).

Sifat

Sifat umum

Urutan $\leq$ pada aljabar Heyting H dapat diperoleh dari operasi → sebagai berikut: untuk setiap elemen a, b dari H, $a\leq b$ jika dan hanya jika a→b = 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

Diberikan rumus $F(A_{1},A_{2},\ldots ,A_{n})$ dari kalkulus proposisional (menggunakan, variabel, penghubung $\land ,\lor ,\lnot ,\to$ , dan konstanta 0 dan 1), yang terbukti sejak awal studi aljabar Heyting, bahwa dua kondisi berikut adalah ekuivalen:

Rumus F terbukti benar dalam kalkulus proposisional intuisionis.
Identitas $F(a_{1},a_{2},\ldots ,a_{n})=1$ untuk setiap aljabar Heyting H dan elemen $a_{1},a_{2},\ldots ,a_{n}\in H$ .

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 $a\leq b$ jika dan hanya jika a→b = 1, mengikuti dari 1 ⇒ 2 bahwa setiap kali rumus F→G pembuktian dengan benar, kita memiliki $F(a_{1},a_{2},\ldots ,a_{n})\leq G(a_{1},a_{2},\ldots ,a_{n})$ untuk setiap aljabar Heyting H, dan elemen $a_{1},a_{2},\ldots ,a_{n}\in H$ . Ini mengikuti dari teorema deduksi bahwa F→G 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 $F(a_{1},a_{2},\ldots ,a_{n})=G(a_{1},a_{2},\ldots ,a_{n})$ , 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 $F(A_{1},A_{2},\ldots ,A_{n})$ tidak dapat dibuktikan, cukup dengan menunjukkan aljabar Heyting H dan elemen $a_{1},a_{2},\ldots ,a_{n}\in H$ sedemikian rupa sehingga $F(a_{1},a_{2},\ldots ,a_{n})\neq 1$ .

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 $(a\land b)\to c=a\to (b\to c)$ .

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

Distributivitas

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

$a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$
$a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$

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

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

x\wedge \bigvee Y=\bigvee \{x\wedge y\mid y\in Y\}

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

a\to b=\bigvee \{c\mid a\land c\leq b\}

sebagai operasi pseudo-kelengkapan relatif.

Elemen reguler dan kelengkapan

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

x = ¬¬x.
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 x∧y = 0 dan x∨y = 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:

H adalah aljabar Boolean;
setiap x dalam H adalah reguler;^[9]
setiap x dalam H adalah kelengkapan.^[10]

Dalam hal ini, elemen a→b adalah sama dengan ¬a ∨ b.

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

Hukum De Morgan dalam aljabar Heyting

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

\forall x,y\in H:\qquad \lnot (x\vee y)=\lnot x\wedge \lnot y.

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

\forall x,y\in H:\qquad \lnot (x\wedge y)=\lnot \lnot (\lnot x\vee \lnot y).

Pernyataan berikut ekuivalen untuk semua aljabar Heyting H:

H memenuhi kedua hukum De Morgan,
$\lnot (x\wedge y)=\lnot x\vee \lnot y{\mbox{ untuk semua }}x,y\in H,$
$\lnot (x\wedge y)=\lnot x\vee \lnot y{\mbox{ untuk semua reguler }}x,y\in H,$
$\lnot \lnot (x\vee y)=\lnot \lnot x\vee \lnot \lnot y{\mbox{ untuk semua }}x,y\in H,$
$\lnot \lnot (x\vee y)=x\vee y{\mbox{ untuk semua reguler }}x,y\in H,$
$\lnot (\lnot x\wedge \lnot y)=x\vee y{\mbox{ untuk semua reguler }}x,y\in H,$
$\lnot x\vee \lnot \lnot x=1{\mbox{ untuk semua }}x\in H.$

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

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 H_comp hanyalah pembatas ∨ ke H_komp, 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

Definisi

Diberikan dua aljabar Heyting H₁ dan H₂ dengan pemetaan f : H₁ → H₂, maka bahwa ƒ adalah morfisme dari aljabar Heyting apabila untuk setiap elemen x dan y dalam H₁, maka dari itu:

$f(0)=0,$
$f(x\land y)=f(x)\land f(y),$
$f(x\lor y)=f(x)\lor f(y),$
$f(x\to y)=f(x)\to f(y),$

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

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

Sifat

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

Contoh

Diberikan aljabar Heyting H dan setiap subaljabar H₁, pemetaan inklusi i : H₁ → H adalah morfisme.

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

Hasil bagi

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

$1\in F,$
${\mbox{Jika }}x,y\in F{\mbox{ maka }}x\land y\in F,$
${\mbox{Jika }}x\in F,\ y\in H,\ {\mbox{dan }}x\leq y{\mbox{ maka }}y\in F.$

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 y₁, y₂, ..., y_n ∈ S dengan y₁ ∧ y₂ ∧ ... ∧ y_n ≤ x.

Jika H adalah aljabar Heyting dan F adalah filter pada H, dengan mendefinisikan relasi ∼ pada H sebagai berikut: maka ditulis sebagai x ∼ y dengan x → y dan y → x 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 p_F : H → H/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 : H → H′ suatu f(y) = 1 untuk setiap y ∈ S, faktor f unik melalui surjeksi kanonik p_F : H → H/F. Artinya, morfisme unik f′ : H/F → H′ sebagai f′p_F = f. Morfisme f′ dikatakan sebagai induksi oleh f.

Maka f : H₁ → H₂ adalah morfisme aljabar Heyting. Kernel dari f, yang ditulis sebagai "ker" f yang merupakan himpunan f⁻¹[{1}]. Ini adalah filter pada H₁. (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′ : H₁/(ker f) → H₂. Ini adalah isomorfisme H₁/(ker f) ke subaljabar f[H₁] dari H₂.

Konstruksi universal

Aljabar Heyting rumus proposisional dalam variabel n hingga dengan ekuivalen intuisi

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

Pertimbangkan himpunan L dari rumus proposisi dalam variabel A₁, A₂,..., A_n.
Diberikan L dengan preorder ≼ dengan mendefinisikan F≼G jika G adalah (intuisionis) konsekuensi logika dari F, yaitu jika G membuktikan dari F. Bahwa ≼ adalah preorder.
Pertimbangkan relasi ekuivalensi F∼G induksi dari preorder F≼G. Didefinisikan oleh F∼G jika dan hanya jika F≼G dan G≼F. Sebenarnya adalah hubungan ekuivalen logika (intuisionis).
Misalkan H₀ sebagai himpunan hasil bagi L/∼. Ini akan menjadi aljabar Heyting yang diinginkan.
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 [F→G], [F∧G], [F∨G] dan [¬F] hanya bergantung pada [F] dan [G]. Ini mendefinisikan operasi →, ∧, ∨ dan ¬ pada himpunan hasil bagi H₀=L/∼. Lebih lanjut definisikan 1 sebagai kelas pernyataan yang terbukti benar, dan himpunan 0=[⊥].
Verifikasi bahwa H₀, bersama dengan operasi ini, adalah aljabar Heyting. Dengan menggunakan definisi seperti aksioma dari aljabar Heyting. H₀ 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 F→G dan G→F 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 H₀ dengan syarat bahwa x≤y jika dan hanya jika x→y=1. Karena, dengan teorema deduksi, rumus F→G 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

Bahkan, konstruksi sebelumnya dapat dilakukan untuk setiap Himpunan variabel {A_i : i∈I} (secara khusus tak hingga). Dengan cara ini diperoleh aljabar Heyting bebas pada variabel {A_i}, yang akan dinyatakan kembali dengan H₀. Dalam arti "bebas" bahwa aljabar Heyting "H" yang diberikan bersama dengan keluarga elemen〈a_i: i∈I〉, apabila terdapat morfisme unik f:H₀→H dari suatu f([A_i])=a_i. 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(〈a_i〉)=G(〈a_i〉) untuk setiap keluarga elemen 〈a_i〉dalam H.

Aljabar Heyting rumus ekuivalen yang berhubungan dengan teori T

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

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

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

Perbandingan dengan aljabar Lindenbaum

Konstruksi yang diberikan memainkan peran memenuhi analog sehubungan dengan aljabar Heyting dengan aljabar Lindenbaum berhubungan dengan Aljabar Boolean. Faktanya, aljabar Lindenbaum B_T dalam variabel {A_i} sehubungan dengan aksioma T bersama H_T∪T₁, dimana T₁ adalah himpunan semua rumus dari formulir ¬¬F→F, karena aksioma tambahan T₁ adalah satu-satunya aksioma yang perlu ditambahkan agar semua tautologi klasik pembuktian.

Aljabar Heyting seperti yang diterapkan pada logika intuisi

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, (P∧Q)→P adalah apabila definisi kelengkapan semu dengan elemen terbesar x sehingga $P\land Q\land x\leq P$ . 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 P→Q. Namun dalam aljabar Heyting, jika P bernilai 1, dan P→Q bernilai 1, maka itu berarti $P\land 1\leq Q$ , dan maka $1\land 1\leq Q$ ; 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 ((P→Q)→ 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

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

^ https://www.encyclopediaofmath.org/index.php/Pseudo-Boolean_algebra
^ ^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.
^ Helena Rasiowa; Roman Sikorski (1963). The Mathematics of Metamathematics. Państwowe Wydawnictwo Naukowe (PWN). hlm. 54–62, 93–95, 123–130.
^ A. G. Kusraev; Samson Semenovich Kutateladze (1999). Boolean valued analysis. Springer. hlm. 12. ISBN 978-0-7923-5921-0.
^ 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
^ Thomas Scott Blyth (2005). Lattices and ordered algebraic structures. Springer. hlm. 151. ISBN 978-1-85233-905-0.
^ Georgescu, G. (2006). "N-Valued Logics and Łukasiewicz–Moisil Algebras". Axiomathes. 16: 123. doi:10.1007/s10516-005-4145-6. , Theorem 3.6
^ Iorgulescu, A.: Hubungan antara aljabar-MV_n dan n-nilai aljabar Łukasiewicz–Moisil—I. Matematika Diskrit. 181, 155–177 (1998) DOI:10.1016/S0012-365X(97)00052-6
^ Rutherford (1965), Th.26.2 p.78.
^ Rutherford (1965), Th.26.1 p.78.
^ 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  .
^ Cook, S.A. (1971). "The complexity of theorem proving procedures". hlm. 151–158. doi:10.1145/800157.805047.
^ Grzegorczyk, Andrzej (1951). "Undecidability of some topological theories" (PDF). Fundamenta Mathematicae. 38: 137–52.
^ Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See paragraph 4.11)

Lihat pula

Referensi

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

Aljabar Heyting di PlanetMath.

[1] ttps://www.encyclopediaofmath.org/index.php/Pseudo-Boolean_algebra

[Kripke63-2] 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.

[Rasiowa-Sikorski-3] Helena Rasiowa; Roman Sikorski (1963). The Mathematics of Metamathematics. Państwowe Wydawnictwo Naukowe (PWN). hlm. 54–62, 93–95, 123–130.

[KusraevKutateladze1999-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

[Blyth2005-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-MV_n 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  .

[Cook71-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)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]