일반성을 잃지 않고

1. 개요

일반성을 잃지 않고(Without loss of generality, WLOG)는 수학적 증명에서 사용되는 표현으로, 특정 가정을 해도 증명의 일반성이 훼손되지 않음을 나타낸다. 이는 여러 경우 중 하나의 경우에 대한 증명을 제시함으로써, 다른 모든 경우에 대해서도 동일한 논리를 적용할 수 있음을 의미하며, 증명의 간결성을 높이는 데 기여한다. 예를 들어, 세 물체의 색깔에 대한 증명에서 첫 번째 물체가 빨간색이라고 가정해도 일반성을 잃지 않는 경우에 해당한다.

2. 예시

비둘기집 원리를 예로 들어 "일반성을 잃지 않고"라는 표현이 어떻게 사용되는지 살펴본다.

예시: 세 물체가 빨간색 혹은 파란색으로 색칠되어 있다면 이 중 두 개는 같은 색이다.

이 정리는 다음과 같이 증명할 수 있다.

: 일반성을 잃지 않고, 첫 번째 물체가 빨간색이라고 가정하자. 다른 두 물체 중 하나가 빨간색이라면, 그 물체와 첫 번째 물체가 같은 빨간색이므로 증명이 끝난다. 만약 그렇지 않다면, 다른 두 물체는 같은 파란색이므로 증명이 끝난다.

이 논증은 첫 번째 물체가 빨간색이라는 가정을 하여 결론을 이끌어 내었지만, 첫 번째 물체를 파란색이라고 가정하더라도 '빨간색'과 '파란색'이라는 단어를 바꾸어 증명할 수 있다. 어떻게 가정하더라도 본질적으로 같은 논증을 통해 결론을 이끌어 낼 수 있으므로, "일반성을 잃지 않고"를 사용하여 증명을 간결하게 할 수 있다.

2.1. 비둘기집 원리

비둘기집 원리를 예시로 들어 "일반성을 잃지 않고"라는 표현이 어떻게 사용되는지 살펴보자.

세 물체가 빨간색 또는 파란색으로 칠해져 있을 때, 적어도 두 물체는 같은 색이라는 것을 증명할 수 있다. (자세한 증명 과정은 하위 섹션을 참고)

2.1.1. 증명 과정

비둘기집 원리의 한 예시인 다음 정리를 생각하자.

:세 물체가 빨간색 혹은 파란색으로 색칠되어 있다면 이 중 두 개는 같은 색이다.

이 정리를 다음과 같이 증명할 수 있다.

:일반성을 잃지 않고, 첫 번째 물체가 빨간색이라고 가정하자. 다른 두 물체 중 하나가 빨간색이라면, 그 물체와 첫 번째 물체가 같은 빨간색이므로 증명이 끝난다. 만약 그렇지 않다면, 다른 두 물체는 같은 파란색이므로 증명이 끝난다.

이 논증은 첫 번째 물체가 빨간색이라는 가정을 하여 결론을 이끌어 내었지만, 첫 번째 물체를 파란색이라고 가정하더라도 논증에서 '빨간색'과 '파란색'이라는 단어를 바꾸어 원 명제를 증명할 수 있다. 어떻게 가정하더라도 본질적으로 같은 논증을 통해 결론을 이끌어 낼 수 있으므로, 첫 번째 물체가 파란색이라는 가정으로부터 본질적으로 똑같은 논증을 한 번 더 작성하는 대신에, "일반성을 잃지 않고"를 사용하여 증명을 간단하게 바꿀 수 있다.

다음의 정리를 고려해 보자(이것은 비둘기집 원리의 한 경우이다).

:세 개의 물체가 각각 빨간색 또는 파란색으로 칠해져 있다면, 같은 색상의 물체가 적어도 두 개는 있어야 한다.

증명:
:일반성을 잃지 않고, 첫 번째 물체가 빨간색이라고 가정해 보자. 다른 두 물체 중 하나라도 빨간색이면 증명은 끝난다. 그렇지 않다면, 다른 두 물체는 모두 파란색이어야 하며, 그래도 증명은 끝난다.

위의 논증이 유효한 이유는, 첫 번째 물체가 파란색이라는 대안적인 가정을 했을 경우에도 똑같은 추론을 적용할 수 있기 때문이며, 마찬가지로 '빨간색'과 '파란색'이라는 단어를 증명의 문구에서 자유롭게 교환할 수 있기 때문이다. 결과적으로, 이 경우 "일반성을 잃지 않고"의 사용은 유효하다.