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.

Definisi

Semigelanggang adalah himpunan R dengan dua operasi biner + dan ⋅, disebut sebagai penjumlahan dan perkalian, maka:

• (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.

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.

Teori

Seseorang dapat menggeneralisasi teori (asosiatif) aljabar dari gelanggang komutatif langsung ke teori aljabar melalui semigelanggang komutatif.

Semigelanggang dimana setiap elemen adalah aditif idempotent (yaitu, a + a = a untuk semua elemen a) disebut semigelanggang idempoten. Semigelanggang idempoten khusus untuk teori semigelanggang karena setiap gelanggang dimana idempoten dalam penambahan adalah trivial. 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).

Aplikasi

(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.

Contoh

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.

Secara umum

• 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.
• Kisi condong normal dalam gelanggang R adalah semigelanggang idempoten untuk operasi perkalian dan nabla, dimana operasi terakhir didefinisikan oleh $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. Gelang Burnside adalah gelanggang jika dan hanya jika kategorinya adalah trivial.

Himpunan semigelanggang

Semigelanggang (himpunan) adalah himpunan S tidak kosong dari himpunan yang sedemikian rupa

1. $\emptyset \in S$
2. Jika $E\in S$ dan $F\in S$ maka $E\cap F\in S$.
3. Jika $E\in S$ dan $F\in S$ maka sejumlah batas himpunan disjoin $C_{i}\in S$ untuk $i=1,\ldots ,n$ sehingga $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 $[a,b)\subset \mathbb {R}$.

Contoh spesifik

• Akhir pecahan (non-negatif) ${\frac {\mathbb {N} _{0}}{b^{\mathbb {N} _{0}}}}:=\left\{mb^{-n}\mid m,n\in \mathbb {N} _{0}\right\}$ dalam sistem bilangan posisi ke basis tertentu $b\in \mathbb {N}$. Maka ${\frac {\mathbb {N} _{0}}{b^{\mathbb {N} _{0}}}}\subseteq {\frac {\mathbb {N} _{0}}{c^{\mathbb {N} _{0}}}}$‍ jika $b$ bagi $c$. Selanjutnya, ${\frac {\mathbb {Z} _{0}}{b^{\mathbb {Z} _{0}}}}:={\frac {\mathbb {N} _{0}}{b^{\mathbb {N} _{0}}}}\cup \left(-{\frac {\mathbb {N} _{0}}{b^{\mathbb {N} _{0}}}}\right)$ adalah gelanggang dari semua pecahan ke basis $b$, dan padat dalam $\mathbb {Q}$ untuk $|b|>1$.
• Bilangan alami ekstensi N ∪ {∞} dengan penjumlahan dan perkalian ekstensi (dan 0⋅∞ = 0).
• Diberikan semigelanggang S, maka matriks semigelanggang $M_{n}(S)$ dari persegi-n dengan -n matriks membentuk semiring di bawah matriks biasa penjumlahan dan perkalian, dan semigelanggang matriks ini umumnya non-komutatif meskipun S komutatif. Misalnya, matriks dengan entri non-negatif, $M_{n}(\mathbb {N} )$ bentuk matriks semigelanggang.
• Jika A adalah monoid komutatif, himpunan End(A) dari endomorfisme f : A → A bentuk sebuah semigelanggang, dimana penjumlahan adalah penjumlahan dan perkalian secara runcing komposisi fungsi. Morfisme nol dan identitas adalah elemen netral. Semigelanggang komposisi tidak terdistribusi pada penambahan searah yang tersisa: a · (b+c) ≠ (a·b) + (a·c). Jika A adalah monoid aditif dari bilangan asli kita memperoleh semigelanggang dari bilangan asli sebagai End(A), dan jika A = Sⁿ dengan S semigelanggang (setiap morfisme ke matriks) semigelanggang matriks persegi n-oleh-n dengan koefisien dalam S.
• Semigelanggang Boolean adalah semigelanggang komutatif B dari bentuk oleh aljabar Boolean dua elemen dan ditentukan oleh 1 + 1 = 1. Idempoten dan merupakan contoh paling sederhana dari semigelanggang yang bukan gelanggang. Diberikan dua himpunan X dan Y, relasi biner antara X dan Y dengan matriks indeks oleh X dan Y dengan entri dalam semigelanggang Boolean, penjumlahan matriks terkait dengan penyatuan relasi, dan perkalian matriks terkait dengan komposisi relasi.
• Diketahui himpunan U, himpunan relasi biner di atas U adalah semigelanggang dengan penambahan union (dari relasi sebagai himpunan) dan perkalian komposisi relasi. Nol semigelanggang adalah relasi kosong dan unitnya adalah relasi identitas. Relasi ini sesuai dengan semiring matriks (memang, semialjabar matriks) dari matriks persegi indeks U dengan entri dalam semigelanggang Boolean, dan kemudian penjumlahan dan perkalian adalah operasi matriks biasa, sedangkan nol dan unit adalah matriks nol dan matriks identitas biasa.
• Himpunan polinomial dengan koefisien bilangan asli, dilambangkan N[x], membentuk semiring komutatif. Sebenarnya, ini adalah semigelanggang komutatif bebas pada generator tunggal {x}.
• Semigelanggang tropis ditentukan dengan berbagai cara. Maks-plus semigelanggang R ∪ {−∞} adalah komutatif, semiring idempoten dengan max(a, b) sebagai penjumlahan semigelanggang (identitas −∞) dan penjumlahan biasa (identitas 0) berfungsi sebagai perkalian semigelanggang. Dalam rumus alternatif, semigelanggang tropis adalah R ∪ {∞}, dan min menggantikan max sebagai operasi penjumlahan. Versi terkait menggunakan R ∪ {±∞} sebagai himpunan dasar.
• Himpunan bilangan pokok lebih kecil dari tak hingga mana pun dari bentuk kardinal apa pun yang diberikan dalam penjumlahan dan perkalian kardinal. Kelas semua kardinal dari model dalam membentuk semiring (kelas) di bawah penjumlahan dan perkalian kardinal (model dalam).
• Probabilitas semigelanggang dari bilangan riil non-negatif dengan penjumlahan dan perkalian biasa.
• Log semigelanggang di atas R ∪ {±∞} dengan tambahan yang diberikan oleh

  $x\oplus y=-\log(e^{-x}+e^{-y})\ ,$

  dengan perkalian +, elemen nol + ∞, dan elemen satuan 0.
• Keluarga (kelas kesetaraan isomorfisme) kelas kombinatorial (himpunan banyak objek dengan ukuran bilangan bulat non-negatif maka banyak objek tak hingga dari setiap ukuran) dengan kelas kosong sebagai objek nol, kelas yang hanya terdiri dari himpunan kosong sebagai unit, disjoint union kelas sebagai penjumlahan, dan produk Kartesius kelas sebagai perkalian.
• Semigelanggang Łukasiewicz: interval tertutup [0, 1] dengan tambahan yang diberikan dengan maksimal argumen (a + b = maks(a,b)) dan perkalian ab diberikan oleh max(0, a + b − 1) dalam logika multi-nilai.
• Semigelanggang Viterbi ditentukan melalui himpunan dasar [0, 1] dan maksimum sebagai penjumlahan, maka perkaliannya adalah perkalian biasa dari bilangan real. Ini sebagai penguraian probabilistik.
• Diberikan alfabet (himpunan hingga) Σ, himpunan bahasa formal di atas Σ (himpunan bagian dari Σ^∗) adalah semiring dengan produk induksi oleh pita penggabungan $L_{1}\cdot L_{2}=\left\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\right\}$ dan penambahan sebagai penyatuan bahasa (yaitu, penyatuan sebagai kumpulan). Nol dari semigelanggang adalah himpunan kosong (bahasa kosong) dan unit semiring adalah bahasa yang hanya berisi pita kosong.
• Menggeneralisasi contoh sebelumnya (dengan melihat Σ^∗ sebagai monoid bebas di atas Σ), ambil M menjadi monoid; himpunan daya P(M) dari semua himpunan bagian M bentuk semigelanggang di bawah satuan teori himpunan sebagai penjumlahan dan perkalian himpunan: $U\cdot V=\{u\cdot v:u\in U,\ v\in V\}$.
• Begitu pula jika $(M,e,\cdot )$ adalah monoid, maka himpunan multihimpunan hingga dalam $M$ bentuk sebuah semigelanggang. Artinya, elemen adalah fungsi $f:M\to \mathbb {N}$; diberikan elemen $M$, fungsi tersebut memberi tahu berapa kali elemen muncul dalam multihimpunan yang diwakilinya. Satuan aditif adalah fungsi nol konstan. Unit perkalian adalah fungsi memetakan $e$ ke 1, dan semua elemen lain dari $M$ ke 0. Jumlah diberikan oleh $(f+g)(x)=f(x)+g(x)$ dan produk diberikan oleh $(fg)(x)=\sum \{f(y)g(z)\mid y\cdot z=x\}$.

Variasi

Semigelanggang kompleks dan kontinu

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:

$\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.

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.

Semua semigelanggang berkelanjutan selesai: sebagai bagian dari definisi.

Semigelanggang bintang

Semigelanggang bintang (terkadang dieja Semigelangbintang) adalah semigelanggang dengan operasi uner tambahan ^∗, maka

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

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

Semigelanggang bintang kompleks

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

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

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

Semigelanggang Conway

Semigelanggang Conway adalah bintang semigelanggang yang menggunakan persamaan bintang-penjumlahan dan bintang-produk:

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

Setiap bintang semigelanggang kompleks sama dengan semigelanggang Conway, 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).

Semigelanggang iterasi adalah semigelanggang Conway menggunakan aksioma grup Conway, diasosiasikan oleh John Conway ke grup dalam semigelanggang bintang.

Contoh

Contoh semigelanggang bintang meliputi:

• (disebutkan di atas) semigelanggang relasi biner di atas beberapa himpunan dasar U dimana $R^{*}=\bigcup _{n\geq 0}R^{n}$ untuk semua $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).
• semigelanggang bahasa formal merupakan bintang semigelanggang kompleks, dengan operasi bintang dengan bintang Kleene (untuk himpunan/bahasa).
• 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.
• Semigelanggang Boolean dengan 0^∗ = 1^∗ = 1.
• Semigelanggang aktif N ∪ {∞}, dengan penjumlahan dan perkalian ekstensi, dan 0^∗ = 1, a^∗ = ∞ untuk a ≥ 1.

Mogand

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

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

Generalisasi

Generalisasi semigelanggang tidak membutuhkan keberadaan identitas perkalian, sehingga perkalian adalah semigrup dari monoid. Struktur seperti itu disebut gelanggang hemi atau pra-semigelanggang. Generalisasi lebih lanjut adalah pra-semigelanggang-kiri, 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.

Lihat pula

• Himpunan gelanggang
• Aljabar penilaian

Sumber

• 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. 

Bacaan lebih lanjut

• 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