멱등법칙

1. 개요

멱등법칙은 수학 및 컴퓨터 과학에서 연산을 여러 번 수행해도 결과가 처음 한 번 수행한 것과 동일한 속성을 의미한다. 함수 f에 대해 f(f(x)) = f(x)가 성립하는 경우 함수 f는 멱등 함수이며, 이항 연산 ★에 대해 x ★ x = x가 성립하면 멱등 연산이다. 멱등성은 함수, 이항 연산, 그리고 프로그래밍 및 정보 공학 전반에 걸쳐 적용되며, 특히 정보 공학에서는 연산의 반복이나 재시도를 안전하게 수행할 수 있게 해주는 중요한 속성으로 사용된다. 멱등성을 만족하는 연산의 예시로는 절댓값 함수, 합집합, 교집합 연산, HTTP의 GET, PUT, DELETE 요청 등이 있다.

2. 정의

멱등성은 연산의 종류에 따라 단항 연산과 이항 연산에서의 멱등성으로 구분된다.

단항 연산의 멱등성은 해당 연산을 두 번 적용한 결과가 한 번 적용한 결과와 같음을 의미한다. 항등 함수와 상수 함수는 멱등성을 만족하는 대표적인 예시이다.

이항 연산의 멱등성은 집합의 모든 원소가 해당 연산에 대해 멱등원이라는 성질이다. 합집합·교집합, 논리곱·논리합 연산 등이 이에 해당한다.

2.1. 단항 연산

단항 연산 f, 즉 어떤 집합 S에서 자신으로 가는 함수의 멱등성은 S의 모든 원소 x에 대해 :$f(f(x))=f(x)$ 가 성립한다는 성질이다. 멱등성을 지닌 함수를 멱등 함수(idempotent function^영어)라고 한다.

항등 함수
:$\backslash operatorname\{id\}\_S:S\backslash to\; S,\backslash \; \backslash operatorname\{id\}\_S(x)=x$
와 상수 함수
:$K\_c:S\backslash to\; S,\backslash \; K\_c(x)=c,\backslash \; c\backslash in\; S$
는 모두 멱등성을 만족한다.

벡터 공간 위의 사영작용소는 멱등 함수의 중요한 부류이다. 3차원 공간의 점을 xy-평면으로 투영시키는 함수 π_xy(x, y, z) = (x, y, 0)이 그 예이다.

함수 f : S → S의 멱등성과 동치인 서술은 S의 모든 원소의 함수값이 f의 부동점이라는 것이다. 이로써, n 원소 집합에 정의된 멱등 함수의 개수는 다음과 같다는 걸 알 수 있다.

:$\backslash sum\_\{k=0\}^\{n\}\{n\; \backslash choose\; k\}k^\{n-k\}$

여기서 $\backslash textstyle\{n\; \backslash choose\; k\}$는 조합으로, n 원소 집합에서 k 개의 부동점을 고른 것이다. k^n-k은 n 원소 집합을 부동점들의 집합 A와 아닌 원소들의 집합 B로 분할했을 때 B에서 A로 가는 함수의 총수이다.

n = 0, 1, 2, ...일 때의 값은 차례대로 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, ... 이다.

멱등성의 성립 여부는 함수의 합성에 의해 보존되지 않는다. 예를 들어서, 두 함수 f(x) = x mod 3, g(x) = max(x, 5)는 모두 멱등함수이지만 f ∘ g는 아니다(g ∘ f는 멱등함수이지만 말이다). 또한, ¬ 함수는 멱등성이 성립하지 않지만 ¬ ∘ ¬에게는 성립한다.
위에서 언급한 것처럼 항등사상과 상수사상은 필연히 멱등 함수이다.

실수 또는 복소수 변수의 절댓값 함수, 실변수의 바닥 함수는 모두 멱등 함수이다.

위상 공간 X의 부분집합 U를 U의 폐포로 대응시키는 함수는 X의 멱집합 P(X)에 정의된 함수로 멱등성을 가진다. 이러한 함수는 폐포연산의 한 예이며, 모든 폐포연산은 멱등성을 만족한다.

2.2. 이항 연산

집합 S 위의 이항 연산 *에 대해, S의 모든 원소 x에 대해 x * x = x 가 성립하면 이항 연산 *는 멱등 연산이다. 멱등 연산에 대한 항등원은 항상 멱등원이다. 예를 들어, 집합의 합집합과 교집합은 모두 멱등 연산이다.

3. 주요 예시

수학 및 컴퓨터 과학 분야에서 멱등법칙의 주요 예시는 다음과 같다.

수학

* 집합 연산에서 합집합(∪)과 교집합(∩)은 멱등 연산이다.
* 논리 연산에서 논리곱(∧)과 논리합(∨)은 멱등 연산이다.
* 불 대수에서 논리곱과 논리합 연산은 모두 멱등 법칙을 만족한다.
* 선형대수학에서 사영작용소는 멱등 법칙을 만족한다. 벡터 공간의 사영작용소들은 벡터 공간 위의 선형변환이 이루는 환의 멱등원이다.
* 실수 및 복소수의 절댓값 함수, 실수의 바닥 함수는 멱등 함수이다.
* 위상 공간에서 부분집합의 폐포를 구하는 함수는 멱등 함수이다.
* 멱등 반환은 덧셈이 멱등성을 갖는 반환이다. 트로피컬 반환에서 덧셈은 멱등원이다.
* 최대공약수 도메인에서 최대공약수와 최소공배수 연산은 멱등원이다.
* 멱등 행렬의 행렬식은 0 또는 1이다.

컴퓨터 과학

* 클레이니 스타와 클레이니 플러스는 형식언어에서 반복을 표현하는 연산자로, 멱등법칙을 만족한다.
* C 언어의 헤더 파일은 멱등성을 가지도록 include guard^영어를 사용하여 설계된다. 즉, 특정 헤더 파일이 여러 번 포함되어도 한 번 포함한 것과 동일한 효과를 가진다.
* HTTP에서 GET, PUT, DELETE 메서드는 멱등성을 가지도록 구현되어야 하지만, POST는 그럴 필요가 없다.
* 사용자 인터페이스 설계에서, 버튼이 멱등하다는 것은 한 번 누르나 여러 번 누르나 같은 효과를 얻을 수 있다는 것을 의미한다.
* 이벤트 스트림 처리에서 멱등성은 동일한 파일, 이벤트 또는 메시지를 여러 번 수신해도 시스템이 동일한 결과를 생성할 수 있는 능력을 의미한다.
* 로드-저장 아키텍처에서 페이지 폴트를 발생시킬 수 있는 명령은 멱등적이다.
* 데이터베이스에서 고객의 이름과 주소를 조회하는 함수는 일반적으로 멱등적이다. 고객의 주소를 변경하는 요청 또한 멱등적이다.

3.1. 수학

집합 연산에서 합집합(∪)과 교집합(∩)은 멱등 연산이다. 논리 연산에서 논리곱(∧)과 논리합(∨)은 멱등 연산이다. 불 대수에서 논리곱과 논리합 연산은 모두 멱등 법칙을 만족한다.

선형대수학에서 사영작용소는 멱등 법칙을 만족한다. 벡터 공간의 사영작용소들은 벡터 공간 위의 선형변환이 이루는 환의 멱등원이다.

실수 및 복소수의 절댓값 함수, 실수의 바닥 함수는 멱등 함수이다.

위상 공간에서 부분집합의 폐포를 구하는 함수는 멱등 함수이다.

멱등 반환은 덧셈이 멱등성을 갖는 반환이다. 트로피컬 반환에서 덧셈은 멱등원이다. 최대공약수 도메인에서 최대공약수와 최소공배수 연산은 멱등원이다.

멱등 행렬의 행렬식은 0 또는 1이다.

3.2. 컴퓨터 과학

클레이니 스타와 클레이니 플러스는 형식언어에서 반복을 표현하는 연산자로, 멱등법칙을 만족한다.

C 언어의 헤더 파일은 멱등성을 가지도록 설계된다. 즉, 특정 헤더 파일이 여러 번 포함되어도(#include의 중첩으로 쉽게 발생) 한 번 포함한 것과 동일한 효과를 가지도록 include guard^영어를 사용한다.

HTTP에서 GET, PUT, DELETE 메서드는 멱등성을 가지도록 구현되어야 하지만, POST는 그럴 필요가 없다. 웹은 기본적으로 GET 요청 결과를 캐시에 보관하지만, POST 요청은 캐시하지 않는다. DELETE 요청은 지정된 URI의 리소스를 삭제하며, 멱등성을 가진다. 멱등성은 단순히 처리 중인 요청을 다시 받았을 때 아무것도 하지 않는 것만을 의미하지 않으며, 그러한 조작은 안전(safe)하다고 한다.

사용자 인터페이스 설계에서, 버튼이 멱등하다는 것은 한 번 누르나 여러 번 누르나 같은 효과를 얻을 수 있다는 것을 의미한다. 예를 들어, "일시 정지" 버튼은 여러 번 눌러도 일시 정지 상태를 유지하며, "재생" 버튼으로 실행을 재개할 수 있다. 적외선 원격 조작이나 터치 패널과 같이 사용자가 버튼을 한 번만 제대로 누르기 어려운 환경에서는 멱등한 사용자 인터페이스가 선호된다. 엘리베이터 호출 버튼도 멱등하다 (엘리베이터가 도착할 때까지 여러 번 눌러도 효과는 변하지 않는다).

이벤트 스트림 처리에서 멱등성은 동일한 파일, 이벤트 또는 메시지를 여러 번 수신해도 시스템이 동일한 결과를 생성할 수 있는 능력을 의미한다.

로드-저장 아키텍처에서 페이지 폴트를 발생시킬 수 있는 명령은 멱등적이다.

데이터베이스에서 고객의 이름과 주소를 조회하는 함수는 일반적으로 멱등적이다. 고객의 주소를 변경하는 요청 또한 멱등적이다. 하지만 고객의 주문 요청은 여러 번 요청하면 여러 주문으로 이어지므로 멱등적이지 않다.

4. 정보 공학에서의 멱등성

정보 공학에서의 멱등성이란, 어떤 연산을 한 번 수행하든 여러 번 수행하든 동일한 결과를 나타내는 것을 말한다. 특히, 몇 번을 수행하더라도 오류나 불일치 상태가 변하지 않는 연산을 지칭한다.

예를 들어, 데이터베이스에서 고객의 이름과 주소를 조회하는 함수는 일반적으로 멱등적이다. 데이터베이스 내용이 변경되지 않기 때문이다. 마찬가지로, 고객의 주소를 특정 값으로 변경하는 요청도 보통 멱등적이다. 요청을 몇 번 하든 최종 주소는 같기 때문이다. 그러나 고객의 주문 요청은 여러 번 요청하면 여러 주문으로 이어지므로, 대개 멱등적이지 않다. 반면 특정 주문을 취소하는 요청은 멱등적이다. 아무리 많은 요청을 하더라도 주문은 취소된 상태로 유지되기 때문이다.

하지만 멱등적 서브루틴의 시퀀스(연속된 명령)라고 해도, 나중 서브루틴이 앞선 서브루틴이 의존하는 값을 바꾸는 경우에는 멱등적이지 않을 수 있다. 즉, 멱등성은 순차적 구성에 대해 닫혀있지 않다.

예쁘게 인쇄의 경우, 출력이 이미 "예쁘다면" 다시 예쁘게 인쇄해도 할 일이 없어야 하므로, 멱등적일 것으로 예상된다.

4.1. 멱등성과 관련된 개념

컴퓨터 과학에서 멱등성은 적용되는 맥락에 따라 다른 의미를 가질 수 있다.

* 명령형 프로그래밍에서, 부작용이 있는 서브루틴은 여러 번 호출해도 단일 호출과 동일한 시스템 상태 변화를 가져오면 멱등성이 있다.
* 함수형 프로그래밍에서, 순수 함수는 정의에서 주어진 수학적 의미에서 멱등성이 있으면 멱등성이 있다.

이는 많은 상황에서 매우 유용한 속성이다. 필요에 따라 의도하지 않은 효과를 일으키지 않고 작업을 반복하거나 재시도할 수 있기 때문이다.

멱등성은 참조 투명성, 재진입성, 안정 정렬, 명령-쿼리 분리와 관련이 있다.

하이퍼텍스트 전송 프로토콜(HTTP)에서 멱등성과 안전성은 HTTP 메서드를 구분하는 주요 속성이다. 주요 HTTP 메서드 중에서 GET, PUT, DELETE는 표준에 따라 멱등적인 방식으로 구현되어야 하지만, POST는 그럴 필요가 없다.

이벤트 스트림 처리에서 멱등성은 동일한 파일, 이벤트 또는 메시지를 두 번 이상 수신하더라도 시스템이 동일한 결과를 생성할 수 있는 능력을 의미한다.

로드-저장 아키텍처에서 페이지 폴트를 발생시킬 수 있는 명령어는 멱등적이다.

서비스 지향 아키텍처(SOA)에서 멱등적 단계로만 구성된 다단계 오케스트레이션 프로세스는 프로세스의 일부가 실패하더라도 부작용 없이 다시 재생할 수 있다.

멱등적인 많은 작업은 종종 중단된 경우 프로세스를 "재개"하는 방법을 가지고 있다.