의예과 3번

(3-1) (a) 주어진 집합이 독립적인 집합이 아니라고 가정하자. 그러면 약수 배수 관계인 서로 다른 두 원소 $\displaystyle x,y$가 존재한다. 일반성을 잃지 않고 $\displaystyle x$가 $\displaystyle y$의 약수라 하면 $\displaystyle 2^n\ge y\ge2x\ge2(2^{n-1}+1)=2^n+2$가 되어 모순이 생긴다. 따라서 독립적인 집합이다.

(b) $\displaystyle \{\{1\},\{2\},A_2,\cdots,A_n\}$은 $\displaystyle \{1,2,\ldots,2^n\}$의 분할이고 $\displaystyle \{1\},\{2\},A_2,\ldots,A_n$은 서로 다른 독립적인 집합이다. 따라서 $\displaystyle \{1,2,\ldots,2^n\}$은 $\displaystyle n+1$개의 독립적인 집합으로 분할 가능하다.

(3-2) (a) $\displaystyle m=0$이면 $\displaystyle X_0=\{1\}$이므로 정의에 따라 $\displaystyle X_0$는 독립적인 집합이다. $\displaystyle m\ge1$이라 하자. $\displaystyle X_m$이 독립적인 집합이 아니라고 가정하면, $\displaystyle X_m$의 서로 다른 두 원소 $\displaystyle x=2^{a_1}\cdot3^{b_1}$, $\displaystyle y=2^{a_2}\cdot3^{b_2}$이 존재하여 $\displaystyle x$가 $\displaystyle y$의 약수이거나 $\displaystyle y$가 $\displaystyle x$의 약수이어야 한다. 일반성을 잃지 않고 $\displaystyle x$가 $\displaystyle y$의 약수라 하자. 이때 $\displaystyle a_1\le a_2,b_1\le b_2$가 성립하는데 $\displaystyle a_1+b_1=a_2+b_2=m$이므로 $\displaystyle a_1=a_2,b_1=b_2$가 되어 $\displaystyle x\neq y$에 모순이다. 따라서 $\displaystyle X_m$은 독립적인 집합이다.

(b) $\displaystyle \{X_0,X_1,\ldots,X_{a+b}\}$는 $\displaystyle D(2^a\cdot3^b)$의 분할이고 각 $\displaystyle X_i$는 독립적인 집합이므로 $\displaystyle D(2^a\cdot3^b)$은 $\displaystyle a+b+1$개의 독립적인 집합으로 분할 가능하다.Comment. (3-2)(b)의 분할은 $\displaystyle X_i$가 아니라 $\displaystyle X_i\cap D(2^a3^b)$, $\displaystyle i=0,1,\ldots,a+b$로 구성해야 한다. 예를 들어 $\displaystyle a=b=1$이면 $\displaystyle X_2=\{4,6,9\}$에는 $\displaystyle D(6)$의 원소가 아닌 $\displaystyle 4,9$가 포함된다. 교집합을 취하면 원하는 분할을 얻는다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.

(3-3) $\displaystyle a+b$에 대한 수학적 귀납법을 사용하자.$\displaystyle a+b=1$이면 $\displaystyle D(2^a\cdot3^b)$은 $\displaystyle \{1,2\}$ 또는 $\displaystyle \{1,3\}$이다. 두 집합 모두 독립적인 집합이 아니므로 하나의 독립적인 집합으로 분할 가능하지 않다.수학적 귀납법을 사용하기 위하여 $\displaystyle a+b>1$인 경우를 보자. 일반성을 잃지 않고, $\displaystyle a>1$이라 할 수 있다.Comment. (3-3)의 ‘$\displaystyle a>1$이라 할 수 있다’는 ‘$\displaystyle a>0$이라 할 수 있다’로 써야 한다. $\displaystyle a=b=1$인 경우도 포함해야 하며, 다음 단계에서 필요한 조건은 $\displaystyle a\ge1$이다. $\displaystyle a=0$인 경우에는 $\displaystyle b$를 하나 줄여 같은 논증을 적용한다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.$\displaystyle D(2^a\cdot3^b)$을 $\displaystyle a+b$개의 독립적인 집합으로 분할 가능하다고 가정하고, $\displaystyle \{Y_1,Y_2,\ldots,Y_{a+b}\}$를 독립적인 집합으로의 분할이라 하자. 일반성을 잃지 않고 $\displaystyle 2^a\cdot3^b\in Y_{a+b}$라 하자.$\displaystyle 2^a\cdot3^b$은 $\displaystyle D(2^a\cdot3^b)$의 모든 원소의 배수이므로 $\displaystyle Y_{a+b}=\{2^a\cdot3^b\}$이다. 따라서 $\displaystyle \{Y_1,Y_2,\ldots,Y_{a+b-1}\}$은 $\displaystyle D(2^a\cdot3^b)-\{2^a\cdot3^b\}$의 분할이 된다. 각각의 $\displaystyle i=1,2,\ldots,a+b-1$에 대하여 $\displaystyle Z_i=Y_i\cap D(2^{a-1}\cdot3^b)$라 하고 $\displaystyle Z_1,Z_2,\ldots,Z_{a+b-1}$ 중 정확히 $\displaystyle d\ (\le a+b-1)$개가 공집합이 아니라고 하자. 일반성을 잃지 않고, $\displaystyle Z_1,Z_2,\ldots,Z_d$는 공집합이 아니고, $\displaystyle Z_{d+1}=Z_{d+2}=\cdots=Z_{a+b-1}=\varnothing$이라 하자. $\displaystyle D(2^{a-1}\cdot3^b)\subseteq D(2^a\cdot3^b)-\{2^a\cdot3^b\}$이므로, $\displaystyle \{Z_1,Z_2,\ldots,Z_d\}$는 $\displaystyle D(2^{a-1}\cdot3^b)$의 분할인데, $\displaystyle d\le a+b-1$이므로 $\displaystyle D(2^{a-1}\cdot3^b)$이 $\displaystyle a+b-1$개의 독립적인 집합으로 분할 가능하지 않다는 귀납 가정에 모순이다. 따라서 $\displaystyle D(2^a\cdot3^b)$은 $\displaystyle a+b$개의 독립적인 집합으로 분할 가능하지 않다.