Idempoten

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 $x$ dari sebuah himpunan $S$ yang dilengkapi dengan operator biner $\cdot$ dikatakan idempoten jika berlaku $x\cdot x=x$ .^[2]^[3] Operator biner $\cdot$ dikatakan idempoten jika $x\cdot x=x$ untuk semua elemen di $S$ .^[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 $(\mathbb {N} ,\times )$ hanyalah 0 dan 1.
Pada magma $(M,\,\cdot )$ , elemen identitas $e$ atau absorbing element $a$ , jika elemen tersebut ada, akan bersifat idempoten karena $e\cdot e=e$ dan $a\cdot a=a.$
Pada grup $(G,\,\cdot )$ , elemen identitas $e$ adalah satu-satunya elemen idempoten. Hal ini terlihat karena untuk sembarang elemen $x$ di $G$ yang memenuhi $x\cdot x=x$ , juga akan memenuhi $x\cdot x=x\cdot e$ . Selanjutnya mengalikan kedua ruas dari kiri dengan elemen invers dari $x$ akan menghasilkan $x=e.$
Pada monoid $({\mathcal {P}}(E),\,\cup )$ dan $({\mathcal {P}}(E),\,\cap )$ dari himpunan kuasa ${\mathcal {P}}(E)$ himpunan $E$ , yang masing-masing dilengkapi dengan operator gabungan $\cup$ dan operator irisan $\cap$ , semua elemennya bersifat idempoten karena $x\cup u=x$ untuk setiap $x\in {\mathcal {P}}(E)$ dan $x\cap x=x$ untuk setiap $x\in {\mathcal {P}}(E)$ . Oleh karena itu, $\cup$ dan $\cap$ adalah operasi yang idempoten pada ${\mathcal {P}}(E)$ .
Semua elemen pada monoid $(\{0,1\},\,\vee )$ dan $(\{0,1\},\,\wedge )$ , dari domain Boole yang dilengkapi dengan logika disjungsi ∨ dan logika konjungsi ∧, bersifat idempoten. Akibatnya, kedua operator logika tersebut idempoten pada himpunan $\{0,\,1\}$ .
Dalam gelanggang Boole, operator perkalian bersifat idempoten.
Dalam semi-gelanggang tropikal, operator penjumlahan bersifat idempoten.

Fungsi idempoten

Dalam monoid $(E^{E},\,\circ )$ dari fungsi-fungsi yang memetakan himpunan $E$ ke dirinya sendiri dan dilengkapi dengan komposisi fungsi $\circ$ , elemen-elemen idempotennya adalah fungsi $f:E\to E$ yang memenuhi $f\circ f=f$ .^[6] Dengan kata lain, fungsi idempoten dalam monoid ini akan memenuhi $f(f(x))=f(x)$ untuk semua $x\in E$ (citra dari setiap elemen di E adalah fixed point dari f ). Sebagai contoh, fungsi nilai mutlak $\operatorname {abs} (x)$ ^[7] pada himpunan bilangan bulat adalah fungsi idempoten karena ${\text{abs}}({\text{abs}}(x))={\text{abs}}(x)$ berlaku untuk setiap bilangan bulat $x$ .^[8] Hal Ini mengartikan fungsi nilai mutlak adalah elemen yang idempoten terhadap komposisi fungsi, pada himpunan semua fungsi yang memetakan bilangan bulat ke bilangan bulat. Contoh lainnya dari fungsi idempoten adalahː

fungsi identitas dan fungsi konstan;
fungsi floor, ceil, dan fractional part;

Jika himpunan $E$ memiliki $n$ elemen, himpunan tersebut dapat dipartisi menjadi $k$ titik tetap (fixed point) dan $n-k$ titik tak-tetap dibawah pemetaan oleh f. Hal ini menghasilkan $k^{n-k}$ sebagai banyaknya fungsi idempoten yang berbeda. Oleh karena itu, dengan mempertimbangkan semua kemungkinan partisi,

\sum _{k=0}^{n}{n \choose k}k^{n-k}

menyatakan 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 ke-idempoten-an fungsi tidak terawetkan dalam operasi komposisi.^[9] Sebagai contoh, $f(x)=x{\text{ mod }}3$ (dengan ${\text{mod}}$ menyakan operasi modulo) dan $g(x)=\max(x,5)$ adalah dua fungsi yang idempoten, namun fungsi komposisi $f\circ g$ tidak.^[10] Walaupun pada kasus ini, $g\circ f$ secara kebetulan bersifat idempoten.^[11] Contoh lain adalah fungsi negasi ¬ pada domain Boole yang tidak idempoten, namun komposisi fungsi ¬ ∘ ¬ bersifat idempoten.

Arti dalam ilmu komputer

Dalam ilmu komputer, istilah idempoten dapat memiliki arti yang berbeda tergantung pada konteks penerapannya:

dalam pemrograman imperatif, sebuah subrutin dengan efek samping (side effect) dikatakan idempoten jika status sistem tetap sama beberapapun banyak panggilan dilakukan. Secara matematika, subrutin idempoten ini adalah sebuah fungsi dari ruang system state ke dirinya sendiri yang memenuhi definisi pada pembahasan bagian di atas.
dalam pemrograman fungsional, pure function bersifat idempoten jika dia idempoten dalam pengertian matematika yang diberikan dalam bagian definisi.

Idempoten adalah sifat yang sangat berguna dalam banyak situasi, karena operasi dengan sifat ini 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 data XYZ dikirim. 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.^[12] Aktivasi tombol pertama kali akan mengubah sistem ke status meminta, sampai hingga permintaan dipenuhi. Aktivasi secara berulang tombol diantara waktu aktivasi awal dan waktu permintaan dipenuhi tidak memiliki pengaruh, kecuali sistem dirancang untuk dapat menyesuaikan waktu memenuhi permintaan berdasarkan jumlah aktivasi yang dilakukan.

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 a² = 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.
^ 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.
^ Notasi yang lebih umum adalah $|x|$ , namun lebih sulit dibaca untuk ekpresi yang bertingkat.
^ Faktanya, persamaan ini berlaku untuk semua bilangan rasional, real, bahkan juga kompleks.
^ 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

[1] Polcino & Sehgal (2002), p. 127.

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

[3] 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 a² = a.

[4] George Grätzer (2003). General Lattice Theory . Basel: Birkhäuser. Here: Sect.1.2, p.5.

[5] Garrett Birkhoff (1967). Lattice Theory. Colloquium Publications. 25. Providence: Am. Math. Soc. . Here: Sect.I.5, p.8.

[6] 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.

[7] Notasi yang lebih umum adalah $|x|$ , namun lebih sulit dibaca untuk ekpresi yang bertingkat.

[8] Faktanya, persamaan ini berlaku untuk semua bilangan rasional, real, bahkan juga kompleks.

[9] 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.

[10] Sebagai contoh, f(g(7)) = f(7) = 1, namun f(g(1)) = f(5) = 2 ≠ 1

[11] uga menunjukkan sifat komutatif f dan g bukan sebuah syarat perlu agar sifat idempoten tetap berlaku.

[12] ttps://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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]