Idempotentność

właściwość funkcji, działania lub jego argumentu

Idempotentność[a] – 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:
  • 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:
  • 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[2]. Przykładem jest liczba będąca idempotentem mnożenia:

Definicje edytuj

Działania jednoargumentowe edytuj

Osobny artykuł: działanie jednoargumentowe.

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

 

W szczególności funkcja tożsamościowa   określona wzorem   jest idempotentna, podobnie jak funkcja stała   gdzie   dana wzorem  

Ważną klasą funkcji idempotentych są rzuty w przestrzeni liniowej. Przykładowo rzutem jest funkcja   dana wzorem   która rzutuje dowolny punkt przestrzeni trójwymiarowej na punkt płaszczyzny   gdyż trzecia współrzędna   jest równa  

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

 

funkcji idempotentnych, gdzie

 

jest liczbą funkcji idempotentnych o dokładnie   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,…[3]

Działania dwuargumentowe edytuj

Osobny artykuł: działanie dwuargumentowe.

Dwuargumentowe działanie   na zbiorze   nazywa się idempotentnym, jeżeli dla wszystkich   zachodzi

 

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   nazywa się idempotentnym lub idempotentem, jeżeli zachodzi dla niego równość

 

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

Powiązania edytuj

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

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

Przykłady edytuj

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   jej domknięcie jest idempotentna na zbiorze potęgowym zbioru   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

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

Idempotentne elementy pierścienia edytuj

Zobacz też: pierścień.

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

 

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

Dwa idempotenty   nazywa się ortogonalnymi i oznacza   jeżeli   Wówczas   również jest idempotentny i zachodzi   oraz  

Jeśli   jest idempotentem pierścienia   to

  • jest nim także   wówczas  
  • pierścień   również jest pierścieniem z jedynką  
  • nazywa się go centralnym, o ile tylko dla wszystkich   zachodzi   wówczas   jest pierścieniem z jedynką  

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

 

to jedynki pierścieni   są parami ortogonalnymi idempotentami centralnymi w   których suma jest równa   Odwrotnie, dla danych parami ortogonalnych idempotentów centralnych   sumujących się do   zachodzi

 

W szczególności idempotent centralny   daje więc rozkład   na sumę prostą  

Dowolny idempotent różny od   i   jest dzielnikiem zera, gdyż   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   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

Jeśli   jest idempotentem, to   jest inwolucją.

Jeśli   jest idempotentem, to   jest idempotentem i są one swoimi odwrotnościami: stąd jeśli   jest odwracalna w danym pierścieniu, to idempotenty i inwolucje są pojęciami równoważnymi.

Więcej, jeżeli   jest inwolucją, to   i   są idempotentami ortogonalnymi odpowiadającymi   i  

Informatyka edytuj

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

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

Uwagi edytuj

  1. Od łac. idempotent-: idem, „taki sam, równy” i potens, „mający moc, siłę” od potis, pote, „móc”; spokr. z gr. πόσις posis, „małżonek”, sanskr. पित pati, „mistrz, małżonek”.

Przypisy edytuj

Bibliografia edytuj

  • César Polcino Milies, Sudarshan K Sehgal, An introduction to group rings, tom 1, Springer, 2002 (Algebras and applications), ISBN 978-1-4020-0238-0.
  • Michiel Hazewinkel, Nadiya Gubareni, Vladimir V. Kirichenko, Algebras, rings and modules, Tom 1, Springer, 2004, ISBN 1-4020-2690-0.

Literatura dodatkowa edytuj

  • 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.
  • Lang, Serge (1993), Algebra (wyd. III), Reading, Mass.: Addison-Wesley Pub. Co., ISBN 978-0-201-55540-0, s. 443

Linki zewnętrzne edytuj

  • Eric W. Weisstein, Idempotent, [w:] MathWorld [online], Wolfram Research [dostęp 2009-02-09] (ang.).
  •   Idempotent (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-10-10].