멱등법칙

멱등법칙(冪等法則) 또는 멱등성(冪等性, 영어: idempotent)은 수학이나 전산학에서 연산의 한 성질을 나타내는 것으로, 연산을 여러 번 적용하더라도 결과가 달라지지 않는 성질을 의미한다. 멱등법칙의 개념은 추상대수학(특히, 사영작용소·폐포연산자 이론)과 함수형 프로그래밍(참조 투명성의 성질과 관련된)의 여러 부분에서 사용하고 있다.

멱등성의 개념은 적용되는 곳에 따라 여러 의미를 가진다.

• 어떤 단항연산(또는 함수)은 어느 값에라도 두 번 적용되었을 때, 한 번 적용했을 때와 같은 결과를 주는 경우, 즉 f(f(x)) ≡ f(x)인 경우 멱등법칙을 만족한다고 한다. 예를 들어, 절댓값 함수는 멱등법칙을 만족한다: abs(abs(x)) ≡ abs(x).
• 어떤 이항연산은 두 같은 값에 적용되었을 때 항상 그 값을 결과로 주는 경우 멱등법칙을 만족한다고 한다. 예를 들어, 두 값의 최댓값을 주는 연산은 멱등법칙을 만족한다: max(x, x) ≡ x. 단항연산에 대한 정의는 이항연산에 대한 정의의 특수화이다.
• 어떤 이항 연산이 주어지고, 두 같은 값을 피연산자로 할 때 그 값이 결과로 나오는 경우 그 값을 이 연산에 대한 멱등원이라고 한다. 예를 들어, 수 1은 곱셈의 멱등원이다: 1 × 1 = 1.

정의

단항연산

단항연산 f, 즉 어떤 집합 S에서 자신으로 가는 함수의 멱등성은 S의 모든 원소 x에 대해

$f(f(x))=f(x)$

가 성립한다는 성질이다. 멱등성을 지닌 함수를 멱등 함수(영어: idempotent function)라고 한다.

항등 함수

$\operatorname {id} _{S}:S\to S,\ \operatorname {id} _{S}(x)=x$

와 상수 함수

$K_{c}:S\to S,\ K_{c}(x)=c,\ c\in S$

는 모두 멱등성을 만족한다.

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

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

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

여기서 $\textstyle {n \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, ... (OEIS의 수열 A000248)

멱등성의 성립 여부는 함수의 합성에 의해 보존되지 않는다. 예를 들어서, 두 함수 f(x) = x mod 3, g(x) = max(x, 5)는 모두 멱등함수이지만 f ∘ g는 아니다(g ∘ f는 멱등함수이지만 말이다). 또한, ¬ 함수는 멱등성이 성립하지 않지만 ¬ ∘ ¬에게는 성립한다.

이항연산, 멱등원

 이 부분의 본문은 멱등원입니다.

★를 S 위의 이항연산이라고 할 때, ★에 대한 멱등원은

$x\bigstar x=x$

를 만족하는 S의 원소 x이다.

멱등원의 예로, ★의 항등원이 존재한다면, 그는 멱등원이다.

이항연산의 멱등성은 S의 모든 원소가 멱등원이라는 성질이다. 즉 임의의 x ∈ S에 대해

$x\bigstar x=x$

가 성립한다는 것이다.

합집합·교집합 연산, 논리곱·논리합 연산, 그리고 일반적으로 격자의 이음과 만남 연산은 모두 이항연산으로서 멱등성을 갖는다.

단항연산의 멱등성은 이항연산의 멱등성의 특례이다. X = S^S를 집합 S에서 자기 자신으로 가는 함수들의 집합으로 두고, 합성 연산 ∘을 X 위에 정의하면, 함수 f_{∈ X} : S → S가 멱등성을 갖는다는 것은 f가 이항연산 ∘에 대한 멱등원이라는 것, 즉

$f\circ f=f$

라는 것과 동치이다.

예

함수

위에서 언급한 것처럼 항등사상과 상수사상은 필연히 멱등 함수이다.

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

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

통계학에서의 분산과 비슷한 다음과 같은 함수는 멱등성을 만족한다.

$f(x_{1},x_{2},\ldots ,x_{n})=(x_{1}-{\bar {x}},x_{2}-{\bar {x}},\ldots ,x_{n}-{\bar {x}})$

여기서 ${\bar {x}}=\textstyle {\frac {x_{1}+x_{2}+\cdots +x_{n}}{n}}$은 산술 평균이다. 예를 들어 (3, 6, 8, 8, 10)에 함수를 적용하면 평균값이 7이므로 f(3, 6, 8, 8, 10) = (-4, -1, 1, 1, 3)이 된다. 이렇게 얻어진 값은 평균값이 0이므로 함수를 다시 한 번 적용해도 결과는 변하지 않는다.

형식언어

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

환의 멱등원

 이 부분의 본문은 멱등원입니다.

다른 예

불 대수에서 논리곱과 논리합 연산은 모두 멱등법칙을 만족한다, 즉 불 대수의 모든 원소는 두 연산의 멱등원이다.

$\forall x:x\wedge x=x,\ x\vee x=x$

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

멱등 반환은 덧셈이 멱등성을 갖는 반환이다.

컴퓨터 과학

 참조 투명성, 재진입성 및 정렬 알고리즘 문서를 참고하십시오.

같이 보기

• 폐포연산
• 고정점
• 멱영원
• 반복함수
• 대합 (수학)

외부 링크

• “Idempotent”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.