멱등법칙

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

  • 어떤 단항연산(또는 함수)은, 어느 값에라도 두 번 적용되었을 때, 한 번 적용했을 때와 같은 결과를 주는 경우, 즉 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-평면으로 투영시키는 함수 \pi_{xy}(x,y,z)=(x,y,0)이 그 예이다.

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

\sum_{k=0}^{n}{n \choose k}k^{n-k}

여기서 {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)

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

이항연산, 멱등원[편집]

\bigstarS 위의 이항연산이라고 할 때, \bigstar에 대한 멱등원

x\bigstar x=x

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

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

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

x\bigstar x=x

가 성립한다는 것이다.

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

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

f\circ f=f

라는 것과 동치이다.

[편집]

함수[편집]

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

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

위상 공간 X의 부분집합 UU폐포로 대응시키는 함수는 X멱집합 \mathcal{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}=\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

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

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

컴퓨터 과학[편집]

같이 보기[편집]

각주[편집]

  1. fg가 교환 가능하다면, 즉 fg = gf이면, fg 멱등성은 fg, gf의 멱등성을 함의한다.
  2. 이는 fg가 교환 가능한 것이 멱등성 보존의 필요조건은 아니라는 것을 보여준다

바깥 고리[편집]