Idempotentność


Idempotentność w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Spis treści

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: | | x | | = | x | . {\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: max ( x , x ) = x . {\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. Przykładem jest liczba 1 {\displaystyle 1} będąca idempotentem mnożenia: 1 = 1 1. {\displaystyle 1=1\cdot 1.}

Definicje | edytuj kod

Działania jednoargumentowe | edytuj kod

 Osobny artykuł: działanie jednoargumentowe.

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

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

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

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

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

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

funkcji idempotentnych, gdzie

( n k ) k n k {\displaystyle {n \choose k}k^{n-k}}

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

Działania dwuargumentowe | edytuj kod

 Osobny artykuł: działanie dwuargumentowe.

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

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

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

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

Powiązania | edytuj kod

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

  • Twierdzenie, iż działanie dwuargumentowe {\displaystyle \star } na zbiorze X {\displaystyle X} jest idempotentne jest równoważne żądaniu, by każdy element zbioru S {\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: f f = f . {\displaystyle f\circ f=f.} W ten sposób twierdzenie, że f {\displaystyle f} jest jednoargumentowym działaniem idempotentnym na S {\displaystyle S} jest równoważne stwierdzeniu, że f {\displaystyle f} jest elementem idempotentnym działania {\displaystyle \circ } na zbiorze funkcji X X . {\displaystyle X\to X.}

Przykłady | 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 {\displaystyle X} jej domknięcie jest idempotentna na zbiorze potęgowym zbioru X . {\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 | edytuj kod

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

Idempotentne elementy pierścienia | edytuj kod

 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 {\displaystyle r} jest idempotentny, gdy r 2 = r . {\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 a {\displaystyle a} i b {\displaystyle b} są idempotentami, to

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

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

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

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

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

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

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

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

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

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

Dowolny idempotent różny od 0 {\displaystyle 0} i 1 {\displaystyle 1} jest dzielnikiem zera, gdyż a ( 1 a ) = 0. {\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 0. {\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 | edytuj kod

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

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

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

Informatyka | 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 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 kod

Uwagi | edytuj kod

  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 kod

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

Bibliografia | 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 978-1-4020-0238-0
  • 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 1-4020-2690-0
Na podstawie artykułu: "Idempotentność" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy