Idempotentność

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Idempotentność (łac. idempotent-: idem, „taki sam, równy” i potens, „mieć moc, siłę”, od potis, pote, „móc”; spokr. z gr. πόσις posis, „małżonek”, sanskr. पित pati, „mistrz, małżonek”) – w matematyce i informatyce właściwość pewnych operacji, która pozwala na ich wielokrotne stosowanie bez zmiany wyniku.

Pojęcie idempotentności pojawia się wielokrotnie w algebrze (w szczególności w teorii rzutów i operatorów domknięcia) oraz programowaniu funkcyjnym (w którym ma ono związek z przejrzystością referencyjną).

Termin wprowadził Benjamin Peirce[1] w kontekście elementów algebry, które są niezmiennicze ze względu na potęgowanie.

Istnieje kilka znaczeń idempotentności w zależności od pojęcia, do którego się odnoszą:

  • Działanie jednoargumentowe (lub funkcja) jest idempotentne, jeżeli zastosowana dwukrotnie daje ten sam wynik, co zastosowana jednokrotnie. Przykładowo funkcja wartości bezwzględnej jest idempotentna jako funkcja zbioru liczb rzeczywistych w siebie: \Big||x|\Big| = |x|.
  • Działanie dwuargumentowe jest idempotentne, gdy zastosowane do dwóch równych wartości daje ją w wyniku. Przykładem może być działanie brania maksimum dwóch wartości, które jest idempotentne: \max(x, x) = x.
  • Dla danego działania dwuargumentowego elementem idempotentnym, lub krótko idempotentem, względem tego działania jest wartość, dla której dana na obu argumentach zostaje zwrócona jako wynik. Przykładem jest liczba 1 będąca idempotentem mnożenia: 1 = 1 \cdot 1.

Definicje[edytuj | edytuj kod]

Działania jednoargumentowe[edytuj | edytuj kod]

 Osobny artykuł: działanie jednoargumentowe.

Działanie jednoargumentowe f, tzn. funkcję danego zbioru X w siebie, nazywa się idempotentną, jeśli dla każdego x \in X zachodzi

f\Big(f(x)\Big) = f(x).

W szczególności funkcja tożsamościowa \operatorname{id}_X określona wzorem \operatorname{id}_X(x) = x jest idempotentna, podobnie jak funkcja stała K_c, gdzie c \in X, dana wzorem K_c(x) = c.

Ważną klasą funkcji idempotentych są rzuty w przestrzeni liniowej. Przykładowo rzutem jest funkcja \pi_{xy} dana wzorem \pi_{xy}(x, y, z) = (x, y, 0), która rzutuje dowolny punkt przestrzeni trójwymiarowej na punkt płaszczyzny XY, gdyż trzecia współrzędna z jest równa 0.

Działanie jednoargumentowe f\colon X \to X jest idempotentne wtedy i tylko wtedy, gdy odwzorowuje wszystkie elementy zbioru X na punkty stałe. Dla zbioru n-elementowego istnieje

\sum_{k=0}^n {n \choose k} k^{n-k}

funkcji idempotentnych, gdzie

{n \choose k} k^{n-k}

jest liczbą funkcji idempotentnych o dokładnie k punktach stałych. Początkowymi wyrazami ciągu liczby funkcji idempotentnych danego przez powyższą sumę są: 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, …[2]

Działania dwuargumentowe[edytuj | edytuj kod]

 Osobny artykuł: działanie dwuargumentowe.

Dwuargumentowe działanie \star na zbiorze X nazywa się idempotentnym, jeżeli dla wszystkich x \in X zachodzi

x \star x = x.

Przykładami działań idempotentnych mogą być działania sumy zbiorów i iloczynu zbiorów, a także działania koniunkcji logicznej i dysjunkcji logicznej oraz, w ogólności, działania kresu dolnego i górnego w kratach.

Element x \in X nazywa się idempotentnym lub idempotentem, jeżeli zachodzi dla niego równość

x \star x = x.

W szczególności idempotentem działania \star jest jego element neutralny.

Powiązania[edytuj | edytuj kod]

Powyższe trzy pojęcia można przedstawić następująco:

  • Twierdzenie, iż działanie dwuargumentowe \star na zbiorze X jest idempotentne jest równoważne żądaniu, by każdy element zbioru S był idempotenty względem \star.
  • Własność definiująca idempotentności jednoargumentowej można zapisać za pomocą operacji złożenia funkcji \circ w następujący sposób: f \circ f = f. W ten sposób twierdzenie, że f jest jednoargumentowym działaniem idempotentnym na S jest równoważne stwierdzeniu, że f jest elementem idempotentnym działania \circ na zbiorze funkcji X \to X.

Przykłady[edytuj | edytuj kod]

Jak wspomniano wyżej, przekształcenia tożsamościowe i stałe są idempotentne. Idempotentne są również funkcje wartości bezwzględnej zmiennej rzeczywistej i zespolonej oraz funkcja podłogi i sufitu zmiennej rzeczywistej.

Funkcja przypisująca każdemu podzbiorowi przestrzeni topologicznej X jej domknięcie jest idempotentna na zbiorze potęgowym zbioru X. Jest to przykład operatora domknięcia; własność idempotentności cechuje wszystkie operatory domknięcia. Idempotentne są również działania wnętrza oraz k-rozszerzenia.

Języki formalne[edytuj | edytuj kod]

Operatory gwiazdka i plus Kleene'ego wykorzystywane w językach formalnych do wyrażania powtórzeń są idempotente.

Idempotentne elementy pierścienia[edytuj | edytuj kod]

Information icon.svg Zobacz też: pierścień.

Element idempotentny pierścienia to, z definicji, element idempotentny względem mnożenia w pierścieniu[3]. Innymi słowy element r jest idempotentny, gdy r^2 = r. W zbiorze idempotentów pierścienia można zdać porządek częściowy w następujący sposób: jeśli a i b są idempotentami, to

a \leqslant b \Leftrightarrow ab = ba = a.

W porządku tym 0 jest najmniejszym, a 1 – największym idempotentem.

Dwa idempotenty a, b nazywa się ortogonalnymi i oznacza a \perp b, jeżeli ab = ba = 0. Wówczas a + b również jest idempotentny i zachodzi a \leqslant a + b oraz b \leqslant a + b.

Jeśli a jest idempotentem pierścienia R, to

  • jest nim także b = 1 - a; wówczas a \perp b;
  • pierścień aRa również jest pierścieniem z jedynką a;
  • nazywa się go centralnym, o ile tylko dla wszystkich x \in R zachodzi ax = xa; wówczas Ra jest pierścieniem z jedynką a.

Idempotenty centralne są blisko związane z rozkładami R na sumy proste pierścieni. Jeśli

R = R_1 \oplus \dots \oplus R_n,

to jedynki pierścieni R_i są parami ortogonalnymi idempotentami centralnymi w R, których suma jest równa 1. Odwrotnie, dla danych parami ortogonalnych idempotentów centralnych a_1, \dots, a_n \in R sumujących się do 1 zachodzi

R = Ra_1 \oplus \dots \oplus Ra_n.

W szczególności idempotent centralny a \in R daje więc rozkład R na sumę prostą Ra \oplus R(1 - a).

Dowolny idempotent różny od 0 i 1 jest dzielnikiem zera, gdyż a(1 - a) = 0. W związku z tym dziedziny całkowitości i pierścienie z dzieleniem nie mają takich idempotentów. Pierścienie lokalne również nie mają tego rodzaju idempotentów, ale z innego powodu: jedynym idempotentem zawartym w radykale Jacobsona pierścienia jest 0. Istnieje katenoida idempotentów w pierścieniu kokwaternionów.

Pierścienie, których wszystkie elementy są idempotentne nazywa się pierścieniami Boole'a. Można pokazać, że w każdym takim pierścieniu mnożenie jest przemienne, a każdy element swoim elementem przeciwnym.

Związek z inwolucjami[edytuj | edytuj kod]

Jeśli a jest idempotentem, to 1 - 2a jest inwolucją.

Jeśli b jest idempotentem, to \tfrac{1 - b}{2} jest idempotentem i są one swoimi odwrotnościami: stąd jeśli 2 jest odwracalna w danym pierścieniu, to idempotentny i inwolucje są pojęciami równoważnymi.

Więcej, jeżeli b jest inwolucją, to \tfrac{1 - b}{2} i \tfrac{1 + b}{2} są idempotentami ortogonalnymi odpowiadającymi a i 1-a.

Informatyka[edytuj | edytuj kod]

W informatyce idempotentność jest własnością operacji pozwalającą na jej wielokrotne powtarzanie bez zmiany wyniku lub powodowania błędu. Taką cechę ma np. operacja czytania.

Przykłady[edytuj | edytuj kod]

Programista aplikacji internetowych powinien zadbać o idempotentność wykonywanych przez serwer operacji, nie dopuszczając np. do kolejnego zakupu identycznego wyrobu w sklepie internetowym po odświeżeniu strony. Jedną z metod jest wprowadzenie tokenu synchronizującego, który jest inkrementowany przy każdym zapytaniu od klienta i np. jako ciasteczko przesyłany wraz z odpowiedzią do klienta. Jeśli token otrzymany od klienta jest różny od tokena zapamiętanego na serwerze, oznacza to że nastąpiło rozsynchronizowanie, np. klient odświeżył stronę.

Standardowo uważa się metody GET i HEAD protokołu HTTP za idempotentne, więc przeglądarki internetowe nie wyświetlają żadnego ostrzeżenia w przypadku odświeżania strony za pomocą metody GET. Stąd poleca się implementację operacji zmieniających stan sesji klienta za pomocą metody POST.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Idempotent - Wolfram Mathworld (ang.). [dostęp 9 lutego 2009].
  • Bryan Basham, Kathy Sierra, Bert Bates: Head First Servlets & JSP. Helion, 2005. ISBN 83-7361-810-4.
  • Deepak Alur, John Crupi, Dan Malks: Core J2EE Wzorce projektowe. Wyd. 2. Helion, 2004. ISBN 83-7361-344-7.
  • Peirce, B.. Linear Associative Algebra. 1870.
  • Milies, César Polcino; Sehgal, Sudarshan K. An introduction to group rings. Algebras and applications, Tom 1. Springer, 2002. ISBN 9781402002380
  • Lang, Serge (1993), Algebra (wyd. III), Reading, Mass.: Addison-Wesley Pub. Co., ISBN 978-0-201-55540-0, s. 443
  • Michiel Hazewinkel, Nadiya Gubareni, Nadezhda Mikhaĭlovna Gubareni, Vladimir V. Kirichenko. Algebras, rings and modules. Tom 1. 2004. Springer, 2004. ISBN 1402026900

Przypisy

  1. Polcino & Sehgal (2002), s. 127.
  2. (ciąg A000248 w OEIS)
  3. Zob. Hazewinkel i in. (2004), s. 2.