Idempoten: Perbedaan antara revisi
k v2.04b - Fixed using Wikipedia:ProyekWiki Cek Wikipedia (DEFAULTSORT dengan huruf kecil) |
memperbaiki terjemahan |
||
Baris 1: | Baris 1: | ||
[[Berkas:HK IFC FV 曉薈 High Place 18B showflat lift button panel Dec-2013.JPG|jmpl|Tombol{{Pranala mati|date=Juni 2021 |bot=InternetArchiveBot |fix-attempted=yes }} pada [[lift]][[Tanda tujuan|.]] Menekan salah tombol sebuah lantai adalah operasi idempoten, karena memiliki efek yang sama baik dilakukan sekali atau beberapa kali.]] |
[[Berkas:HK IFC FV 曉薈 High Place 18B showflat lift button panel Dec-2013.JPG|jmpl|Tombol{{Pranala mati|date=Juni 2021 |bot=InternetArchiveBot |fix-attempted=yes }} pada [[lift]][[Tanda tujuan|.]] Menekan salah tombol sebuah lantai adalah operasi idempoten, karena memiliki efek yang sama baik dilakukan sekali atau beberapa kali.]] |
||
'''Idempoten''' adalah sifat beberapa [[Operasi (matematika)|operasi]] tertentu di [[matematika]] dan [[ilmu komputer]] yang dapat diterapkan beberapa kali tanpa memberikan hasil berbeda dengan |
'''Idempoten''' adalah sifat beberapa [[Operasi (matematika)|operasi]] tertentu di [[matematika]] dan [[ilmu komputer]]. Operasi yang memiliki sifat ini dapat diterapkan (dilakukan) beberapa kali tanpa memberikan hasil berbeda dengan hasil penerapan pertama kali. Konsep idempoten muncul dalam beberapa hal di [[aljabar abstrak]] (khususnya, dalam teori proyektor dan ''closure operators'') dan pada [[pemrograman fungsional]] (yang berhubungan dengan sifat ''referential transparency''). |
||
Istilah ini diperkenalkan oleh [[Benjamin Peirce]],<ref>Polcino & Sehgal (2002), p. 127.</ref> ketika membahas unsur aljabar yang tidak berubah ketika dipangkatkan dengan sebuah bilangan bulat positif. Idempoten berasal dari gabungan kata ''idem'' dan ''potence'' ("sama" dan "pangkat"), dan secara harfiah berarti "(kemampuan memiliki) hasil pangkat yang sama". |
|||
== Definisi == |
== Definisi == |
||
Suatu elemen <math>x</math> dari sebuah himpunan <math>S</math> yang dilengkapi dengan operator biner <math>\cdot</math> dikatakan idempoten jika berlaku <math>x\cdot x = x</math>.<ref>{{Cite book|last=Valenza|first=Robert|date=2012|url=https://books.google.com/books?id=7x8MCAAAQBAJ|title=Linear Algebra: An Introduction to Abstract Mathematics|location=Berlin|publisher=Springer Science & Business Media|isbn=9781461209010|page=22|quote=An element ''s'' of a magma such that ''ss'' = ''s'' is called ''idempotent''.}}</ref><ref>{{Cite book|last=Doneddu|first=Alfred|date=1976|url=https://books.google.com/books?id=5Ry7AAAAIAAJ|title=Polynômes et algèbre linéaire|location=Paris|publisher=Vuibert|page=180|language=fr|quote=Soit ''M'' un magma, noté multiplicativement. On nomme idempotent de ''M'' tout élément ''a'' de ''M'' tel que ''a''<sup>2</sup> = ''a''.}}</ref> Operator biner <math>\cdot</math> dikatakan idempoten jika <math>x\cdot x = x</math> untuk semua elemen di <math>S</math>.<ref>{{Cite book|last=George Grätzer|year=2003|url=https://archive.org/details/generallatticeth0000grat|title=General Lattice Theory|location=Basel|publisher=Birkhäuser|url-access=registration}} Here: Sect.1.2, p.5.</ref><ref>{{Cite book|last=Garrett Birkhoff|year=1967|title=Lattice Theory|location=Providence|publisher=Am. Math. Soc.|series=Colloquium Publications|volume=25}}. Here: Sect.I.5, p.8.</ref> |
|||
== Contoh == |
== Contoh == |
||
Berikut beberapa contoh objek matematika dan sifat idempoten mereka: |
|||
* Bilangan asli 0 dan 1 adalah elemen yang idempoten |
* Bilangan asli 0 dan 1 adalah elemen yang idempoten terhadap [[perkalian]] (karena 0 × 0 = 0 dan 1 × 1 = 1). Karena tidak ada bilangan asli lainnya yang memenuhi sifat ini (misalnya tidak berlaku bahwa 2 × 2 = 2), operasi perkalian pada bilangan asli bukanlah operasi yang idempoten. Secara formal, elemen idempoten dalam [[monoid]] <math>(\N, \times)</math> hanyalah 0 dan 1. |
||
* Dalam [[Magma (aljabar)|magma]] ( |
* Dalam [[Magma (aljabar)|magma]] <math>(M,\,\cdot)</math>, [[elemen identitas]] <math>e</math> atau ''absorbing element'' <math>a</math>, jika elemen tersebut ada, akan bersifat idempoten karena <math>e\cdot e = e</math> dan <math>a\cdot a = a.</math> |
||
* Dalam |
* Dalam [[Grup (matematika)|grup]] <math>(G,\,\cdot)</math>, elemen identitas <math>e</math> adalah satu-satunya elemen idempoten. Hal ini terlihat karena untuk sembarang elemen <math>x</math> di <math>G</math> yang memenuhi <math>x\cdot x = x</math>, juga akan memenuhi <math>x\cdot x = x\cdot e</math>. Dengan mengalikan kedua ruas dari kiri dengan [[elemen invers]] dari <math>x</math>, didapatkan <math>x = e.</math> |
||
* |
* Untuk sebarang monoid (𝒫 ''(E),'' ∪) dan (𝒫 ''(E),'' ∩) dari ''powerset'' himpunan ''E,'' yang masing-masing dilengkapi [[Gabungan (teori himpunan)|operator gabungan]] ∪ dan [[Irisan (teori himpunan)|operator irisan persimpangan]] ∩, semua elemennya idempoten; Oleh karena itu, ∪ dan ∩ adalah operasi idempoten pada 𝒫 ( ''E'' ). |
||
* Dalam monoid ({0, 1}, ∨) dan ({0, 1}, ∧) dari ''Boolean domain'' dengan [[logika disjungsi]] ∨ dan [[logika konjungsi]] |
* Dalam monoid ({0, 1}, ∨) dan ({0, 1}, ∧) dari ''Boolean domain'' dengan [[logika disjungsi]] ∨ dan [[logika konjungsi]] ∧, semua elemennya idempoten. |
||
* Dalam [[gelanggang Boolean]], operator perkalian bersifat idempoten. |
* Dalam [[gelanggang Boolean]], operator perkalian bersifat idempoten. |
||
* Dalam ''tropical semiring'', operator penjumlahan bersifat idempoten. |
* Dalam ''tropical semiring'', operator penjumlahan bersifat idempoten. |
||
Baris 28: | Baris 30: | ||
: <math>\sum_{k=0}^n {n \choose k} k^{n-k}</math> |
: <math>\sum_{k=0}^n {n \choose k} k^{n-k}</math> |
||
adalah banyaknya fungsi idempoten yang mungkin di himpunan ''E''. barisan dari rumus banyaknya fungsi idempoten di atas untuk ''n'' = 0, 1, 2, 3, 4, 5, 6, 7, 8,… adalah |
adalah banyaknya fungsi idempoten yang mungkin di himpunan ''E''. barisan dari rumus banyaknya fungsi idempoten di atas untuk ''n'' = 0, 1, 2, 3, 4, 5, 6, 7, 8,… adalah 1, 1, 3, 10, 41, 196, 1057, 6322, 41393,… {{OEIS|A000248}}. |
||
Sifat keidempotenan tidak terawetkan <!--bukan alih bahasa yang baik, bukan?-->dalam komposisi fungsi.<ref>If ''f'' and ''g'' commute, i.e. if {{Nowrap|1=''f'' ∘ ''g'' = ''g'' ∘ ''f''}}, then idempotency of both ''f'' and ''g'' implies that of {{Nowrap|''f'' ∘ ''g''}}, since {{Nowrap|1=(''f'' ∘ ''g'') ∘ (''f'' ∘ ''g'') = (''f'' ∘ ''f'') ∘ (''g'' ∘ ''g'') = ''f'' ∘ ''g''}}, using the associativity of composition.</ref> Sebagai contoh, {{Nowrap|1=''f''(''x'') = ''x''}} [[Aritmetika modular|mod]] 3 dan ''g'' (''x'') = max(''x'', 5) adalah dua fungsi idempoten, tetapi {{Nowrap|''f'' ∘ ''g''}} tidak,<ref>Sebagai contoh, ''f''(''g''(7)) = ''f''(7) = 1, namun ''f''(''g''(1)) = ''f''(5) = 2 ≠ 1</ref> meskipun {{Nowrap|''g'' ∘ ''f''}} secara kebetulan idempoten.<ref>juga menunjukkan sifat komutatif ''f'' dan ''g'' bukan sebuah [[Syarat perlu (matematika)|syarat perlu]] agar sifat idempoten tetap berlaku.</ref> Contoh lain adalah fungsi negasi {{Nowrap|¬}} pada domain Boolean yang tidak idempoten, namun {{Nowrap|¬ ∘ ¬}} idempoten. |
Sifat keidempotenan tidak terawetkan <!--bukan alih bahasa yang baik, bukan?-->dalam komposisi fungsi.<ref>If ''f'' and ''g'' commute, i.e. if {{Nowrap|1=''f'' ∘ ''g'' = ''g'' ∘ ''f''}}, then idempotency of both ''f'' and ''g'' implies that of {{Nowrap|''f'' ∘ ''g''}}, since {{Nowrap|1=(''f'' ∘ ''g'') ∘ (''f'' ∘ ''g'') = (''f'' ∘ ''f'') ∘ (''g'' ∘ ''g'') = ''f'' ∘ ''g''}}, using the associativity of composition.</ref> Sebagai contoh, {{Nowrap|1=''f''(''x'') = ''x''}} [[Aritmetika modular|mod]] 3 dan ''g'' (''x'') = max(''x'', 5) adalah dua fungsi idempoten, tetapi {{Nowrap|''f'' ∘ ''g''}} tidak,<ref>Sebagai contoh, ''f''(''g''(7)) = ''f''(7) = 1, namun ''f''(''g''(1)) = ''f''(5) = 2 ≠ 1</ref> meskipun {{Nowrap|''g'' ∘ ''f''}} secara kebetulan idempoten.<ref>juga menunjukkan sifat komutatif ''f'' dan ''g'' bukan sebuah [[Syarat perlu (matematika)|syarat perlu]] agar sifat idempoten tetap berlaku.</ref> Contoh lain adalah fungsi negasi {{Nowrap|¬}} pada domain Boolean yang tidak idempoten, namun {{Nowrap|¬ ∘ ¬}} idempoten. |
||
Baris 57: | Baris 59: | ||
* {{Citation|last=Hazewinkel, Michiel|author-link=Hazewinkel, Michiel|last2=Gubareni, Nadiya|last3=Kirichenko, V. V.|title=Algebras, rings and modules. vol. 1|series=Mathematics and its Applications|volume=575|publisher=Kluwer Academic Publishers|place=Dordrecht|year=2004|pages=xii+380|isbn=978-1-4020-2690-4|mr=2106764}} |
* {{Citation|last=Hazewinkel, Michiel|author-link=Hazewinkel, Michiel|last2=Gubareni, Nadiya|last3=Kirichenko, V. V.|title=Algebras, rings and modules. vol. 1|series=Mathematics and its Applications|volume=575|publisher=Kluwer Academic Publishers|place=Dordrecht|year=2004|pages=xii+380|isbn=978-1-4020-2690-4|mr=2106764}} |
||
* {{Citation|last=Lam, T. Y.|title=A first course in noncommutative rings|series=Graduate Texts in Mathematics|volume=131|edition=2|publisher=Springer-Verlag|place=New York|year=2001|pages=xx+385|isbn=978-0-387-95183-6|mr=1838439|doi=10.1007/978-1-4419-8616-0}} |
* {{Citation|last=Lam, T. Y.|title=A first course in noncommutative rings|series=Graduate Texts in Mathematics|volume=131|edition=2|publisher=Springer-Verlag|place=New York|year=2001|pages=xx+385|isbn=978-0-387-95183-6|mr=1838439|doi=10.1007/978-1-4419-8616-0}} |
||
* |
* hal. 443 |
||
* Peirce, Benjamin. [http://legacy-www.math.harvard.edu/history/peirce_algebra/ ''Aljabar Asosiatif Linier''] 1870. |
* Peirce, Benjamin. [http://legacy-www.math.harvard.edu/history/peirce_algebra/ ''Aljabar Asosiatif Linier''] 1870. |
||
* {{Citation|last=Polcino Milies, César|last2=Sehgal, Sudarshan K.|title=An introduction to group rings|series=Algebras and Applications|volume=1|publisher=Kluwer Academic Publishers|place=Dordrecht|year=2002|pages=xii+371|isbn=978-1-4020-0238-0|mr=1896125|doi=10.1007/978-94-010-0405-3}} |
* {{Citation|last=Polcino Milies, César|last2=Sehgal, Sudarshan K.|title=An introduction to group rings|series=Algebras and Applications|volume=1|publisher=Kluwer Academic Publishers|place=Dordrecht|year=2002|pages=xii+371|isbn=978-1-4020-0238-0|mr=1896125|doi=10.1007/978-94-010-0405-3}} |
Revisi per 27 Maret 2022 00.44
Idempoten adalah sifat beberapa operasi tertentu di matematika dan ilmu komputer. Operasi yang memiliki sifat ini dapat diterapkan (dilakukan) beberapa kali tanpa memberikan hasil berbeda dengan hasil penerapan pertama kali. Konsep idempoten muncul dalam beberapa hal di aljabar abstrak (khususnya, dalam teori proyektor dan closure operators) dan pada pemrograman fungsional (yang berhubungan dengan sifat referential transparency).
Istilah ini diperkenalkan oleh Benjamin Peirce,[1] ketika membahas unsur aljabar yang tidak berubah ketika dipangkatkan dengan sebuah bilangan bulat positif. Idempoten berasal dari gabungan kata idem dan potence ("sama" dan "pangkat"), dan secara harfiah berarti "(kemampuan memiliki) hasil pangkat yang sama".
Definisi
Suatu elemen dari sebuah himpunan yang dilengkapi dengan operator biner dikatakan idempoten jika berlaku .[2][3] Operator biner dikatakan idempoten jika untuk semua elemen di .[4][5]
Contoh
Berikut beberapa contoh objek matematika dan sifat idempoten mereka:
- Bilangan asli 0 dan 1 adalah elemen yang idempoten terhadap perkalian (karena 0 × 0 = 0 dan 1 × 1 = 1). Karena tidak ada bilangan asli lainnya yang memenuhi sifat ini (misalnya tidak berlaku bahwa 2 × 2 = 2), operasi perkalian pada bilangan asli bukanlah operasi yang idempoten. Secara formal, elemen idempoten dalam monoid hanyalah 0 dan 1.
- Dalam magma , elemen identitas atau absorbing element , jika elemen tersebut ada, akan bersifat idempoten karena dan
- Dalam grup , elemen identitas adalah satu-satunya elemen idempoten. Hal ini terlihat karena untuk sembarang elemen di yang memenuhi , juga akan memenuhi . Dengan mengalikan kedua ruas dari kiri dengan elemen invers dari , didapatkan
- Untuk sebarang monoid (𝒫 (E), ∪) dan (𝒫 (E), ∩) dari powerset himpunan E, yang masing-masing dilengkapi operator gabungan ∪ dan operator irisan persimpangan ∩, semua elemennya idempoten; Oleh karena itu, ∪ dan ∩ adalah operasi idempoten pada 𝒫 ( E ).
- Dalam monoid ({0, 1}, ∨) dan ({0, 1}, ∧) dari Boolean domain dengan logika disjungsi ∨ dan logika konjungsi ∧, semua elemennya idempoten.
- Dalam gelanggang Boolean, operator perkalian bersifat idempoten.
- Dalam tropical semiring, operator penjumlahan bersifat idempoten.
Fungsi idempoten
Dalam monoid (E E, ∘) fungsi dari himpunan E ke dirinya sendiri dengan komposisi fungsi ∘, elemen idempoten adalah fungsi f: E → E yang bersifat f ∘ f = f, dengan kata lain untuk semua x di E, f(f(x)) = f(x) (citra dari setiap elemen di E adalah fixed point dari f ). Sebagai contoh, mengambil nilai absolut abs(x) [6] dari bilangan bulat x adalah fungsi idempoten karena abs( abs(x)) = abs(x) benar untuk setiap bilangan bulat x.[7] Hal Ini mengartikan abs ∘ abs = abs[8] terpenuhi, yakni fungsi abs adalah elemen idempoten di himpunan semua fungsi [dari bilangan bulat ke bilangan bulat][9] menurut komposisi fungsi. Oleh karena itu, abs memenuhi definisi fungsi idempoten di atas. Contoh lainnya termasuk:
- fungsi identitas bersifat idempoten;
- fungsi konstan bersifat idempoten;
- fungsi floor, ceil, dan fractional part bersifat idempoten;
Jika himpunan E memiliki n elemen, kita dapat mempartisi himpunan tersebut menjadi k fixed point dan n − k non-fixed point dibawah pemetaan f. Hal ini menghasilkan kn-k fungsi idempoten yang berbeda. Oleh karena itu, dengan mempertimbangkan semua kemungkinan partisi,
adalah banyaknya fungsi idempoten yang mungkin di himpunan E. barisan dari rumus banyaknya fungsi idempoten di atas untuk n = 0, 1, 2, 3, 4, 5, 6, 7, 8,… adalah 1, 1, 3, 10, 41, 196, 1057, 6322, 41393,… (barisan A000248 pada OEIS).
Sifat keidempotenan tidak terawetkan dalam komposisi fungsi.[10] Sebagai contoh, f(x) = x mod 3 dan g (x) = max(x, 5) adalah dua fungsi idempoten, tetapi f ∘ g tidak,[11] meskipun g ∘ f secara kebetulan idempoten.[12] Contoh lain adalah fungsi negasi ¬ pada domain Boolean yang tidak idempoten, namun ¬ ∘ ¬ idempoten.
Arti dalam ilmu komputer
Dalam ilmu komputer, istilah idempoten mungkin memiliki arti yang berbeda tergantung pada konteks penerapannya:
- dalam pemrograman imperatif, subrutin dengan side effect bersifat idempoten jika status sistem tetap sama setelah baik sekali maupun beberapa kali panggilan. Dengan kata lain, fungsi dari state space sistem ke dirinya sendiri pada konteks subrutin tersebut bersifat idempoten dalam pengertian matematika yang diberikan dalam definisi;
- dalam pemrograman fungsional, pure function bersifat idempoten jika dia idempoten dalam pengertian matematika yang diberikan dalam bagian definisi.
Ini adalah sifat yang sangat berguna dalam banyak situasi, karena ini berarti bahwa operasi dapat diulangi atau dicoba ulang sesering yang diperlukan tanpa menimbulkan efek yang tidak diinginkan. Pada operasi yang tidak idempoten, algoritme mungkin perlu melacak apakah operasi sudah dilakukan atau belum.
Contoh dalam ilmu komputer
Sebuah fungsi yang mencari nama dan alamat pelanggan di sebuah database umumnya idempoten, karena operasi ini tidak membuat isi database berubah. Demikian pula dengan mengganti alamat pengguna menjadi XYZ umumnya idempoten, karena data alamat terakhir akan tetap sama tidak peduli berapa kali XYZ dilakukan. Namun, menempatkan barang dalam daftar belanjaan toko daring umumnya tidak idempoten, karena penempatan barang beberapa kali akan menambah banyak pesanan. Membatalkan pesanan bersifat idempoten, karena pesanan tetap dibatalkan tidak peduli berapa kali permintaan [pembatalan] dilakukan.
Contoh aplikasi
Contoh terapan yang dapat ditemui banyak orang dalam kehidupan sehari-hari mereka termasuk tombol pada lift dan tombol penyeberangan.[13] Aktivasi tombol pertama kali akan mengubah sistem ke status meminta, sampai hingga permintaan dipenuhi. Aktivasi tombol berulang diantara waktu aktivasi awal dan waktu permintaan yang dipenuhi tidak memiliki pengaruh, kecuali sistem dirancang untuk dapat menyesuaikan waktu memenuhi permintaan berdasarkan jumlah aktivasi.
Referensi
- ^ Polcino & Sehgal (2002), p. 127.
- ^ Valenza, Robert (2012). Linear Algebra: An Introduction to Abstract Mathematics. Berlin: Springer Science & Business Media. hlm. 22. ISBN 9781461209010.
An element s of a magma such that ss = s is called idempotent.
- ^ Doneddu, Alfred (1976). Polynômes et algèbre linéaire (dalam bahasa Prancis). Paris: Vuibert. hlm. 180.
Soit M un magma, noté multiplicativement. On nomme idempotent de M tout élément a de M tel que a2 = a.
- ^ George Grätzer (2003). General Lattice Theory
. Basel: Birkhäuser. Here: Sect.1.2, p.5.
- ^ Garrett Birkhoff (1967). Lattice Theory. Colloquium Publications. 25. Providence: Am. Math. Soc.. Here: Sect.I.5, p.8.
- ^ Notasi yang lebih umum adalah , namun lebih sulit dibaca untuk ekpresi yang bertingkat.
- ^ Faktanya, persamaan ini berlaku untuk semua bilangan rasional, real, bahkan juga kompleks.
- ^ Ini adalah persamaan antar fungsi. Dua fungsi dikatakan sama jika mereka memiliki domain dan citra yang sama, dan nilai fungsi mereka sama untuk semua elemen di domain.
- ^ This set of functions is formally denoted as ℤℤ.
- ^ If f and g commute, i.e. if f ∘ g = g ∘ f, then idempotency of both f and g implies that of f ∘ g, since (f ∘ g) ∘ (f ∘ g) = (f ∘ f) ∘ (g ∘ g) = f ∘ g, using the associativity of composition.
- ^ Sebagai contoh, f(g(7)) = f(7) = 1, namun f(g(1)) = f(5) = 2 ≠ 1
- ^ juga menunjukkan sifat komutatif f dan g bukan sebuah syarat perlu agar sifat idempoten tetap berlaku.
- ^ https://web.archive.org/web/20110523081716/http://www.nclabor.com/elevator/geartrac.pdf For example, this design specification includes detailed algorithm for when elevator cars will respond to subsequent calls for service
Daftar pustaka
- “ Idempoten ” di FOLDOC
- Goodearl, K. R. (1991), von Neumann regular rings (edisi ke-2), Malabar, FL: Robert E. Krieger Publishing Co. Inc., hlm. xviii+412, ISBN 978-0-89464-632-4, MR 1150975
- Gunawardena, Jeremy (1998), "An introduction to idempotency" (PDF), dalam Gunawardena, Jeremy, Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994, Cambridge: Cambridge University Press, hlm. 1–49, Zbl 0898.16032
- Hazewinkel, Michiel, ed. (2001) [1994], "Idempotent", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
- Hazewinkel, Michiel; Gubareni, Nadiya; Kirichenko, V. V. (2004), Algebras, rings and modules. vol. 1, Mathematics and its Applications, 575, Dordrecht: Kluwer Academic Publishers, hlm. xii+380, ISBN 978-1-4020-2690-4, MR 2106764
- Lam, T. Y. (2001), A first course in noncommutative rings, Graduate Texts in Mathematics, 131 (edisi ke-2), New York: Springer-Verlag, hlm. xx+385, doi:10.1007/978-1-4419-8616-0, ISBN 978-0-387-95183-6, MR 1838439
- hal. 443
- Peirce, Benjamin. Aljabar Asosiatif Linier 1870.
- Polcino Milies, César; Sehgal, Sudarshan K. (2002), An introduction to group rings, Algebras and Applications, 1, Dordrecht: Kluwer Academic Publishers, hlm. xii+371, doi:10.1007/978-94-010-0405-3, ISBN 978-1-4020-0238-0, MR 1896125