Idempoten

Idempoten adalah sifat beberapa operasi tertentu di matematika dan ilmu komputer yang dapat diterapkan beberapa kali tanpa memberikan hasil berbeda dengan ketika diterapkan 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] dalam konteks unsur-unsur di aljabar yang tidak berubah ketika dipangkatkan dengan sebauh bilangan bulat positif, dan secara harfiah berarti "(kemampuan memiliki) pangkat yang sama", dari idem + potence ("sama" + "pangkat").

Definisi

Elemen x dari sebuah magma (M, •) dikatakan idempoten jika berlaku x • x = x.^[2]^[3] Jika semua elemen idempoten menurut operasi •, maka • disebut idempoten. Rumus ∀ x, x • x = x disebut hukum idempoten untuk •.^[4]^[5]

Contoh

Beriut beberapa contoh objek dan sifat idempoten mereka:

Bilangan asli 0 dan 1 adalah elemen yang idempoten dengan perkalian (karena 0 × 0 = 0 dan 1 × 1 = 1), dan tidak ada bilangan asli lainnya yang memenuhi (misalnya tidak berlaku bahwa 2 × 2 = 2). Untuk alasan yang terakhir, perkalian bilangan asli bukanlah operasi idempoten. Secara formal, dalam monoid (ℕ, ×), elemen idempoten hanya 0 dan 1.

Dalam magma (M, •), elemen identitas e atau absorbing element a, jika ada, bersifat idempoten karena e • e = e dan a • a = a .
Dalam sebuah grup (G, •), elemen identitas e adalah satu-satunya elemen idempoten. Hal ini terlihat karena untuk sebarang x elemen dari G sehingga x • x = x, berlaku x • x = x • e dan x = e (dengan mengalikan kedua ruas dari kiri dengan elemen invers dari x).
Mengambil irisan x ∩ y dari dua himpunan x dan y adalah operasi idempoten, karena x ∩ x selalu sama dengan x . Dengan kata lain, hukum idempotensi ∀ x, x ∩ x = x berlku untuk operasi irisan. Demikian pula, mengambil gabungan dua himpunan adalah operasi idempoten. Secara formal, 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 kⁿ^-k fungsi idempoten yang berbeda. Oleh karena itu, dengan mempertimbangkan semua kemungkinan partisi,

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

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 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 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.
^ A more common notation for this is $|x|$ , but it is harder to read when expressions are nested.
^ In fact, this equation holds for all rational, real and even complex numbers, too.
^ This is an equation between functions. Two functions are equal if their domains and ranges agree, and their output values agree on their whole 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.
^ e.g. f(g(7)) = f(7) = 1, but f(g(1)) = f(5) = 2 ≠ 1
^ also showing that commutation of f and g is not a necessary condition for idempotency preservation
^ 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] A more common notation for this is $|x|$ , but it is harder to read when expressions are nested.

[7] In fact, this equation holds for all rational, real and even complex numbers, too.

[8] This is an equation between functions. Two functions are equal if their domains and ranges agree, and their output values agree on their whole domain.

[9] This set of functions is formally denoted as ℤ^ℤ.

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

[11] .g. f(g(7)) = f(7) = 1, but f(g(1)) = f(5) = 2 ≠ 1

[12] so showing that commutation of f and g is not a necessary condition for idempotency preservation

[13] 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]

[13]