Semigelanggang

Templat:Sidebar teori gelanggang Dalam aljabar abstrak, semigelanggang adalah struktur aljabar dengan gelanggang tanpa persyaratan setiap elemen menggunakan aditif invers.

Semigelanggang tropis adalah bidang penelitian aktif, yang menghubungkan varietas aljabar dengan struktur linear sesepenggal.^[1]

Struktur aljabar
Sejenis grup Grup Semigrup / Monoid Rak dan ganjal Grup semu dan gelung Grup abelian Magma Grup Lie Teori grup
Sejenis gelanggang Gelanggang Semigelanggang Gelanggang dekat Gelanggang komutatif Ranah integral Medan Gelanggang pembagian Teori gelanggang
Sejenis kekisi Kekisi Semikekisi Kekisi dikomplemenkan Urutan total Aljabar Heyting Aljabar boolean Peta kekisi Teori kekisi
Sejenis modul Modul Grup dengan operator Ruang vektor Aljabar linear
Sejenis aljabar Aljabar Asosiatif Non-asosiatif Aljabar komposisi Aljabar Lie Bertingkat Bialjabar
l b s

Semigelanggang adalah himpunan R dengan dua operasi biner + dan ⋅, disebut sebagai penjumlahan dan perkalian, maka:^[2][3][4]

• (R, +) adalah monoid komutatif dengan elemen identitas 0:
  • (a + b) + c = a + (b + c)
  • 0 + a = a + 0 = a
  • a + b = b + a
• (R, ⋅) adalah monoid dengan elemen identitas 1:
  • (a⋅b)⋅c = a⋅(b⋅c)
  • 1⋅a = a⋅1 = a
• Perkalian kiri dan kanan mendistribusikan di atas penambahan:
  • a⋅(b + c) = (a⋅b) + (a⋅c)
  • (a + b)⋅c = (a⋅c) + (b⋅c)
• Perkalian dengan 0 menghilangkan R:
  • 0⋅a = a⋅0 = 0

Simbol ⋅ biasanya dihilangkan dari notasi; a⋅b ditulis ab. Demikian pula, urutan operasi yang diterapkan sebelum + adalah a + bc yaitu a + (bc).

Dibandingkan dengan gelanggang, semigelanggang menghilangkan persyaratan untuk invers di bawah penjumlahan; artinya, ini hanya membutuhkan monoid komutatif, bukan grup komutatif. Dalam sebuah gelanggang, syarat pembalikan aditif dengan keberadaan nol perkalian yang ditentukan secara eksplisit. Jika perkalian sebuah semigelanggang adalah komutatif, maka disebut semigelanggang komutatif.^[5]

Ada beberapa penulis yang lebih memilih untuk mengabaikan persyaratan bahwa semigelanggang memiliki 0 atau 1. Analogi antara gelanggang dan semigelanggang di satu sisi dan grup dan semigrup di sisi bekerja. Para penulis ini sering menggunakan rig untuk konsep definisi.^{[catatan 1]}

Seseorang dapat menggeneralisasi teori (asosiatif) aljabar dari gelanggang komutatif langsung ke teori aljabar melalui semigelanggang komutatif.^{[butuh rujukan]}

Semigelanggang dimana setiap elemen adalah aditif idempotent (yaitu, a + a = a untuk semua elemen a) disebut semigelanggang idempoten.^[6] Semigelanggang idempoten khusus untuk teori semigelanggang karena setiap gelanggang dimana idempoten dalam penambahan adalah trivial.^{[catatan 2]} Mendefinisikan urutan parsial ≤ pada semigelanggang idempoten dengan a ≤ b maka a + b = b (atau, dengan kata lain, jika x dengan a + x = b). Sangat mudah untuk melihat bahwa 0 adalah elemen terkecil sehubungan dengan urutan 0 ≤ a untuk semua a. Penjumlahan dan perkalian menghormati urutan dalam arti bahwa a ≤ b menyiratkan ac ≤ bc, ca ≤ cb dan (a + c) ≤ (b + c).

(max, +) dan (min, +) semigelanggang tropikal pada riil, sering digunakan dalam evaluasi kinerja pada sistem kejadian diskrit. Bilangan sebenarnya adalah "biaya" atau "waktu kedatangan"; operasi "maks" berhubungan dengan harus menunggu semua prasyarat dari sementara operasi "min" dengan kemampuan untuk memilih yang sederhana; dan + sesuai dengan akumulasi di sepanjang jalur yang sama.

Dengan demikian, algoritma Floyd–Warshall untuk jalur terpendek dapat diformulasi ulang sebagai komputasi aljabar (min, +). Demikian pula, algoritma Viterbi untuk urutan keadaan yang paling mungkin sesuai dengan urutan pengamatan dalam Model Markov tersembunyi dirumuskan sebagai komputasi melalui (maks, ×) aljabar tentang probabilitas. Algoritma pemrograman dinamis bergantung pada sifat distributif dari semigelanggang terkait untuk menghitung jumlah secara besar-besaran untuk eksponensial.^[7][8]

Menurut definisi, gelanggang juga merupakan semigelanggang. Contoh motivasi dari semigelanggang adalah himpunan bilangan asli N (termasuk nol) di bawah penjumlahan dan perkalian biasa. Demikian pula, semigelanggang bentuk non-negatif bilangan rasional dan non-negatif bilangan real. Semua semigelanggang adalah sifat komutatif.^[9][10][11]

• Himpunan untuk semua ideal dari gelanggang tertentu membentuk semigelanggang idempoten di bawah penjumlahan dan perkalian ideal.
• Setiap unital kuantel adalah semigelanggang idempoten dalam penggabungan dan perkalian.
• Kisi distributif adalah semigelanggang komutatif dan idempoten di bawah gabung dan temu.
• Secara khusus, aljabar Boolean adalah semigelanggang. Gelanggang Boolean merupakan semigelanggang, tetapi tidak idempoten di bawah penjumlahan. Semigelanggang Boolean adalah semigelanggang isomorfis ke subsemigelanggang dari aljabar Boolean.^[9]
• Kisi condong normal dalam gelanggang R adalah semigelanggang idempoten untuk operasi perkalian dan nabla, dimana operasi terakhir didefinisikan oleh ${\displaystyle a\nabla b=a+b+ba-aba-bab}$.
• Semua c-semigelanggang merupakan semigelanggang dengan penambahan idempoten dan ditentukan melalui himpunan arbitrer.
• Kelas isomorfisme objek dalam operasi kategori distributif, di bawah operasi produk bersama dan produk, semigelanggang yang dikenal sebagai gelang Burnside.^[12] Gelang Burnside adalah gelanggang jika dan hanya jika kategorinya adalah trivial.

Semigelanggang (himpunan)^[13] adalah himpunan S tidak kosong dari himpunan yang sedemikian rupa

1. ${\displaystyle \emptyset \in S}$
2. Jika ${\displaystyle E\in S}$ dan ${\displaystyle F\in S}$ maka ${\displaystyle E\cap F\in S}$.
3. Jika ${\displaystyle E\in S}$ dan ${\displaystyle F\in S}$ maka sejumlah batas himpunan disjoin ${\displaystyle C_{i}\in S}$ untuk ${\displaystyle i=1,\ldots ,n}$ sehingga ${\displaystyle E\setminus F=\bigcup _{i=1}^{n}C_{i}}$.

Semigelanggang digunakan dalam teori ukuran. Contoh semigelanggang dari himpunan adalah himpunan dari setengah terbuka, setengah tertutup riil interval ${\displaystyle [a,b)\subset \mathbb {R} }$.

Semigelanggang kompleks adalah semigelanggang yang aditif monoidnya adalah monoid kompleks, artinya memiliki operasi jumlah infiniter Σ_I untuk setiap himpunan indeks I dan hukum distributif (tak hingga) berikut:^[15][17][19]

${\displaystyle \sum _{i\in I}{\left(a\cdot a_{i}\right)}=a\cdot \left(\sum _{i\in I}{a_{i}}\right),\qquad \sum _{i\in I}{\left(a_{i}\cdot a\right)}=\left(\sum _{i\in I}{a_{i}}\right)\cdot a.}$

Contoh semigelanggang kompleks adalah himpunan pangkat dari monoid di bawah gabungan dan semigelanggang matriks di atas semigelanggang kompleks.^[20]

Semigelanggang kontinu didefinisikan sebagai penambahan monoid adalah monoid kontinu. Yaitu, diurutkan sebagian dengan sifat batas atas terkecil, dan penjumlahan dan perkalian sebagai ketertiban dan suprema. Semigelanggang N ∪ {∞} dengan penjumlahan biasa, perkalian dan urutan diperpanjang adalah semigelanggang kontinu.^[21]

Semua semigelanggang berkelanjutan selesai:^[17] sebagai bagian dari definisi.^[20]

Semigelanggang bintang (terkadang dieja Semigelangbintang) adalah semigelanggang dengan operasi uner tambahan ^∗,^{[6][15][22][23]} maka

${\displaystyle a^{*}=1+aa^{*}=1+a^{*}a.}$

Aljabar Kleene merupakan bintang semigelanggang dengan penambahan idempoten untuk teori bahasa formal dan ekspresi reguler.^[15]

Dalam semigelanggang bintang kompleks, operasi bintang sebagai contoh bintang Kleene: untuk semigelanggang kompleks menggunakan operasi jumlah tak hingga untuk definisi bintang Kleene biasa:^[15]

${\displaystyle a^{*}=\sum _{j\geq 0}{a^{j}},}$

dimana ${\displaystyle a^{j}={\begin{cases}1,&j=0,\\a\cdot a^{j-1}=a^{j-1}\cdot a,&j>0.\end{cases}}}$

Semigelanggang Conway adalah bintang semigelanggang yang menggunakan persamaan bintang-penjumlahan dan bintang-produk:^[6][24]

${\displaystyle {\begin{aligned}(a+b)^{*}&=\left(a^{*}b\right)^{*}a^{*},\\(ab)^{*}&=1+a(ba)^{*}b.\end{aligned}}}$

Setiap bintang semigelanggang kompleks sama dengan semigelanggang Conway,^[25] tapi kebalikannya tidak berlaku. Contoh semigelanggang Conway non-kompleks adalah himpunan bilangan rasional non-negatif Q_≥0 ∪ {∞} dengan penjumlahan dan perkalian biasa (ini adalah modifikasi dari contoh dengan riil non-negatif diberikan dalam bagian ini dengan menghilangkan bilangan irasional).^[15]

Semigelanggang iterasi adalah semigelanggang Conway menggunakan aksioma grup Conway,^[6] diasosiasikan oleh John Conway ke grup dalam semigelanggang bintang.^[26]

Contoh semigelanggang bintang meliputi:

• (disebutkan di atas) semigelanggang relasi biner di atas beberapa himpunan dasar U dimana ${\displaystyle R^{*}=\bigcup _{n\geq 0}R^{n}}$ untuk semua ${\displaystyle R\subseteq U\times U}$. Operasi bintang adalah refleksif dan penutupan transitif dari R (yaitu relasi biner refleksif dan transitif terkecil di atas U yang mengandung R).^[15]
• semigelanggang bahasa formal merupakan bintang semigelanggang kompleks, dengan operasi bintang dengan bintang Kleene (untuk himpunan/bahasa).^[15]
• Himpunan ekstensi riil non-negatif [0, ∞] dengan penjumlahan dan perkalian riil yang biasa adalah semigelanggang bintang kompleks dengan operasi bintang yang diberikan oleh a^∗ = 1/(1 − a) untuk 0 ≤ a < 1 (yaitu deret geometri) dan a^∗ = ∞ for a ≥ 1.^[15]
• Semigelanggang Boolean dengan 0^∗ = 1^∗ = 1.^[a][15]
• Semigelanggang aktif N ∪ {∞}, dengan penjumlahan dan perkalian ekstensi, dan 0^∗ = 1, a^∗ = ∞ untuk a ≥ 1.^[a][15]

Istilah mogand (untuk "monoid ganda") telah digunakan untuk berbagai jenis semigelanggang:

• Digunakan oleh Kuntzman pada tahun 1972 untuk menunjukkan apa yang sekarang disebut semigelanggang.^[27]
• Penggunaan yang berarti subgrup idempoten diperkenalkan oleh Baccelli et al. pada tahun 1992.^[28]
• Nama "mogand" kadang digunakan untuk menunjukkan semigelanggang tatanan alami.

Generalisasi semigelanggang tidak membutuhkan keberadaan identitas perkalian, sehingga perkalian adalah semigrup dari monoid. Struktur seperti itu disebut gelanggang hemi^[29] atau pra-semigelanggang.^[30] Generalisasi lebih lanjut adalah pra-semigelanggang-kiri,^[31] yang tidak menggunakan distribusi-kanan (atau pra-semigelanggang-kanan, yang tidak menggunakan distribusi-kiri).

Dalam teori kategori, gelang-2 adalah kategori dengan fungtor operasi ial analog dengan gelang. Bahwa bilangan kardinal membentuk gelang dapat dikategorikan untuk kategori himpunan (atau lebih umum, topos) adalah gelang-2.

• Himpunan gelanggang
• Aljabar penilaian

• Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs), Dunod (Paris) 
• François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Synchronization and Linearity (online version) Diarsipkan 2016-11-04 di Wayback Machine., Wiley, 1992, ISBN 0-471-93609-X
• Golan, Jonathan S., Semirings and their applications. Updated and expanded version of The theory of semirings, with applications to mathematics and theoretical computer science (Longman Sci. Tech., Harlow, 1992, MR1163371. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923-5786-8 MR1746739
• Berstel, Jean; Perrin, Dominique (1985). Theory of codes. Pure and applied mathematics. 117. Academic Press. ISBN 978-0-12-093420-1. Zbl 0587.68066. 
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067. 
• Głazek, Kazimierz (2002). A guide to the literature on semirings and their applications in mathematics and information sciences. With complete bibliography. Dordrecht: Kluwer Academic. ISBN 1-4020-0717-5. Zbl 1072.16040. 
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177. 
• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007. 

• Golan, Jonathan S. (2003). Semirings and Affine Equations over Them. Springer Science & Business Media. ISBN 978-1-4020-1358-4. Zbl 1042.16038. 
• Gondran, Michel; Minoux, Michel (2008). Graphs, Dioids and Semirings: New Models and Algorithms. Operations Research/Computer Science Interfaces Series. 41. Dordrecht: Springer Science & Business Media. ISBN 978-0-387-75450-5. Zbl 1201.16038. 
• Grillet, Mireille P. (1970). "Green's relations in a semiring". Port. Math. 29: 181–195. Zbl 0227.16029. 
• Gunawardena, Jeremy (1998). "An introduction to idempotency". Dalam Gunawardena, Jeremy. Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994 (PDF). Cambridge: Cambridge University Press. hlm. 1–49. Zbl 0898.16032. 
• Jipsen, P. (2004). "From semirings to residuated Kleene lattices". Studia Logica. 76 (2): 291–303. doi:10.1023/B:STUD.0000032089.54776.63. Zbl 1045.03049. 
• Steven Dolan (2013) Fun with Semirings Diarsipkan 2018-07-13 di Wayback Machine., DOI:10.1145/2500365.2500613