Idempotentność

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: ${\displaystyle {\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: ${\displaystyle \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^[2]. Przykładem jest liczba ${\displaystyle 1}$ będąca idempotentem mnożenia: ${\displaystyle 1=1\cdot 1.}$

Definicje

Działania jednoargumentowe

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

${\displaystyle f{\Big (}f(x){\Big )}=f(x).}$

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

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

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

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

funkcji idempotentnych, gdzie

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

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

Działania dwuargumentowe

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

${\displaystyle 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 ${\displaystyle x\in X}$ nazywa się idempotentnym lub idempotentem, jeżeli zachodzi dla niego równość

${\displaystyle x\star x=x.}$

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

Powiązania

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

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

Przykłady

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 ${\displaystyle X}$ jej domknięcie jest idempotentna na zbiorze potęgowym zbioru ${\displaystyle 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

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

Idempotentne elementy pierścienia

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

${\displaystyle a\leqslant b\Leftrightarrow ab=ba=a.}$

W porządku tym ${\displaystyle 0}$ jest najmniejszym, a ${\displaystyle 1}$ – największym idempotentem.

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

Jeśli ${\displaystyle a}$ jest idempotentem pierścienia ${\displaystyle R,}$ to

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

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

${\displaystyle R=R_{1}\oplus \dots \oplus R_{n},}$

to jedynki pierścieni ${\displaystyle R_{i}}$ są parami ortogonalnymi idempotentami centralnymi w ${\displaystyle R,}$ których suma jest równa ${\displaystyle 1.}$ Odwrotnie, dla danych parami ortogonalnych idempotentów centralnych ${\displaystyle a_{1},\dots ,a_{n}\in R}$ sumujących się do ${\displaystyle 1}$ zachodzi

${\displaystyle R=Ra_{1}\oplus \dots \oplus Ra_{n}.}$

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

Dowolny idempotent różny od ${\displaystyle 0}$ i ${\displaystyle 1}$ jest dzielnikiem zera, gdyż ${\displaystyle 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 ${\displaystyle 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

Jeśli ${\displaystyle a}$ jest idempotentem, to ${\displaystyle 1-2a}$ jest inwolucją.

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

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

Informatyka

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

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ż

• macierz idempotentna
• element nilpotentny

Uwagi

Przypisy

Bibliografia

• 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 .
• MichielM. Hazewinkel MichielM., NadiyaN. Gubareni NadiyaN., Vladimir V.V.V. Kirichenko Vladimir V.V.V., Algebras, rings and modules, Tom 1, Springer, 2004, ISBN 1-4020-2690-0 .

Literatura dodatkowa

• 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

• Eric W.E.W. Weisstein Eric W.E.W., Idempotent, [w:] MathWorld [online], Wolfram Research [dostęp 2009-02-09]  (ang.).