모두의 행복한 결혼을 위한 수학적 조건.

A를 어떤 (유한 집합들의 모임)이라고 하고, A에는 서로 같은 유한 집합들이 여러 개 있을 수 있다.

(A가 모든 유한집합들의 모임이라는 의미가 아니다. 사실 그냥 A를 모든 원소가 유한 집합인 집합이라고 소개하면 되지 않느냐고 생각할 수 있겠지만, A를 집합이라고 하기에는 좀 애매하다. 만약, A의 원소 중에 같은 것이 있다고 해도 이것을 서로 구분해 줄 수 있기 때문이다. 예를 들어, A={ {1}, {1}, {2} } 이라고 쓰고, A의 원소의 개수를 3개라고 하는 것이다. 마치 중근을 갖는 이차방정식의 근의 개수를 2개라고 하는 것과 비슷하다.)

그러면, A의 결혼 조건은 다음과 같다.

결혼 조건 : 모든 A의 부분 모임 B에 대해, (B의 원소의 개수) ≤ ((B의 원소들의 합집합)의 원소의 개수)) 가 성립한다.

(여기서의 B도 마찬가지로 집합적으로 같은 원소들을 서로 구분해 줄 수 있는 모임이다. 다만, B의 원소 혹은 A의 원소는 우리가 아는 그 집합 개념을 쓴다.)

이게 왜 결혼 조건이라고 불리는지 의아할 수 있는데, 다음의 비유와 결과를 보자.

n명의 여자와 n명의 남자가 있다. 그리고 각각의 여자는 남자들을 결혼하면 만족할 남자와 그렇지 않은 남자로 분류한다. 그리고 남자는 본인을 결혼하기에 괜찮다고 생각되는 여자와 결혼하면 만족한다. 그리고 결혼은 남자와 여자끼리 해야 하며, 중혼은 안 된다.

그러면, 과연 모든 남자와 모든 여자가 만족하게 결혼하는 상황이 가능할까?

이제, k번째 여자 w_k에 대해, W_k={ x | x는 w_k가 결혼하기에 괜찮다고 생각하는 남자}라고 하고, A={W_1, W_2, ... , W_n}이라고 하자.

그러면, A가 결혼 조건을 만족하면, 모든 남자와 모든 여자가 만족하게 결혼하는 상황이 가능하다고 한다.

(사실, W_1과 W_2는 집합으로서 같을 수 있는데, 서로 구분되는 것으로 본다. 정 집합론적으로 찝찝하다면, (W_1, 1)과 (W_2, 2)로 해서 구분해줘도 된다.)

문제)

C={ X | n은 1 이상의 정수, X={ y | y는 n 이하의 양의 정수} } 라고 하자.

그러면, C가 결혼 조건을 만족함을 설명해라.