Idempotentność

Z testwiki
Przejdź do nawigacji Przejdź do wyszukiwania

Szablon:Spis treści Idempotentność[uwaga 1] – 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 PeirceSzablon:Odn 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|.
  • 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[1]. Przykładem jest liczba 1 będąca idempotentem mnożenia: 1=1⋅1.

Definicje

Działania jednoargumentowe

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

f(f(x))=f(x).

W szczególności funkcja tożsamościowa idX określona wzorem idX(x)=x jest idempotentna, podobnie jak funkcja stała Kc, gdzie c∈X, dana wzorem Kc(x)=c.

Ważną klasą funkcji idempotentych są rzuty w przestrzeni liniowej. Przykładowo rzutem jest funkcja πxy dana wzorem π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:X→X jest idempotentne wtedy i tylko wtedy, gdy odwzorowuje wszystkie elementy zbioru X na punkty stałe. Dla zbioru n-elementowego istnieje

∑k=0n(nk)kn−k

funkcji idempotentnych, gdzie

(nk)kn−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

Szablon:Osobny artykuł Dwuargumentowe działanie ⋆ na zbiorze X nazywa się idempotentnym, jeżeli dla wszystkich x∈X zachodzi

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

x⋆x=x.

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

Powiązania

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

  • Twierdzenie, iż działanie dwuargumentowe ⋆ na zbiorze X jest idempotentne jest równoważne żądaniu, by każdy element zbioru S 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: f∘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 ∘ na zbiorze funkcji X→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 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

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

Idempotentne elementy pierścienia

Szablon:Zobacz też Element idempotentny pierścienia to, z definicji, element idempotentny względem mnożenia w pierścieniuSzablon:Odn. Innymi słowy element r jest idempotentny, gdy r2=r. W zbiorze idempotentów pierścienia można zadać porządek częściowy w następujący sposób: jeśli a i b są idempotentami, to

a⩽b⇔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⊥b, jeżeli ab=ba=0. Wówczas a+b również jest idempotentny i zachodzi a⩽a+b oraz b⩽a+b.

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

  • jest nim także b=1−a; wówczas a⊥b;
  • pierścień aRa również jest pierścieniem z jedynką a;
  • nazywa się go centralnym, o ile tylko dla wszystkich x∈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=R1⊕…⊕Rn,

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

R=Ra1⊕…⊕Ran.

W szczególności idempotent centralny a∈R daje więc rozkład R na sumę prostą Ra⊕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

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

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

Więcej, jeżeli b jest inwolucją, to 1−b2 i 1+b2 są idempotentami ortogonalnymi odpowiadającymi a i 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ż

Uwagi

Szablon:Uwagi

Przypisy

Szablon:Przypisy

Bibliografia

Literatura dodatkowa

Linki zewnętrzne

Szablon:Działania dwuargumentowe Szablon:Funkcje matematyczne

Szablon:Kontrola autorytatywna


Błąd rozszerzenia cite: Istnieje znacznik <ref> dla grupy o nazwie „uwaga”, ale nie odnaleziono odpowiedniego znacznika <references group="uwaga"/>

  1. ↑ Szablon:Encyklopedia PWN
  2. ↑ Szablon:OEIS
Źródło: „https://pl.wiki.beta.math.wmflabs.org/w/index.php?title=Idempotentność&oldid=5479”