멱등법칙 문서 원본 보기

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

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

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

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

:<math>f(f(x))=f(x)</math>

가 성립한다는 성질이다. 멱등성을 지닌 함수를 '''멱등 함수'''({{llang|en|idempotent function}})라고 한다.

[[항등 함수]]

:<math>\operatorname{id}_S:S\to S,\ \operatorname{id}_S(x)=x</math>

와 [[상수 함수]]

:<math>K_c:S\to S,\ K_c(x)=c,\ c\in S</math>

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

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

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

:<math>\sum_{k=0}^{n}{n \choose k}k^{n-k}</math>

여기서 <math>\textstyle{n \choose k}</math>는 [[조합]]으로, ''n'' 원소 집합에서 ''k'' 개의 부동점을 고른 것이다. ''k<sup>n-k</sup>''은 ''n'' 원소 집합을 부동점들의 집합 ''A''와 아닌 원소들의 집합 ''B''로 [[집합의 분할|분할]]했을 때 ''B''에서 ''A''로 가는 함수의 총수이다.

''n'' = 0, 1, 2, ...일 때의 값은 차례대로 다음과 같다.
:1, 1, 3, 10, 41, 196, 1057, 6322, 41393, ... {{OEIS|A000248}}

멱등성의 성립 여부는 [[함수의 합성]]에 의해 보존되지 않는다.<ref>''f''와 ''g''가 교환 가능하다면, 즉 ''f'' ∘ ''g'' = ''g'' ∘ ''f''이면, ''f''와 ''g'' 멱등성은 ''f'' ∘ ''g'', ''g'' ∘ ''f''의 멱등성을 함의한다.</ref> 예를 들어서, 두 함수 ''f''(''x'') = ''x'' [[합동 산술|mod]] 3, ''g''(''x'') = max(''x'', 5)는 모두 멱등함수이지만 ''f'' ∘ ''g''는 아니다(''g'' ∘ ''f''는 멱등함수이지만 말이다<ref>이는 ''f''와 ''g''가 교환 가능한 것이 멱등성 보존의 [[필요조건]]은 아니라는 것을 보여준다</ref>). 또한, [[부정|¬]] 함수는 멱등성이 성립하지 않지만 ¬ ∘ ¬에게는 성립한다.

=== 이항연산, 멱등원 ===
{{본문|멱등원}}
★를 ''S'' 위의 [[이항연산]]이라고 할 때, ★에 대한 [[멱등원]]은

:<math>x\bigstar x=x</math>

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

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

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

:<math>x\bigstar x=x</math>

가 성립한다는 것이다.

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

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

:<math>f\circ f=f</math>

라는 것과 동치이다.

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

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

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

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

:<math>f(x_1,x_2,\ldots,x_n)=(x_1-\bar{x},x_2-\bar{x},\ldots,x_n-\bar{x})</math>

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

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

=== 환의 멱등원 ===
{{본문|멱등원}}

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

:<math>\forall x:x \wedge x=x,\ x \vee x=x</math>

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

[[멱등 반환]]은 덧셈이 멱등성을 갖는 [[반환 (수학)|반환]]이다.

== 컴퓨터 과학 ==
{{참고|참조 투명성|재진입성|정렬 알고리즘}}

== 같이 보기 ==
* [[폐포연산]]
* [[고정점]]
* [[멱영원]]
* [[반복함수]]
* [[대합 (수학)]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{SpringerEOM|제목=Idempotent|id=p/i050080}}

{{전거 통제}}

[[분류:추상대수학]]
[[분류:폐포 연산자]]
[[분류:관계 (수학)]]
[[분류:이론 컴퓨터 과학]]
[[분류:이항연산]]