Set Proof

Y 가 X의 진부분집합이면 X $\nsim$ Y 를 보도록 하자.

만약 X 가 비어있는 집합이라면, 그런 Y 는 없다. 따라서 X 와 대등한 집합은 없다.

만약 X 가 비어있는 집합이 아니면, $\sim {\bar {n}}$ 인 어떤 n 이 있다. 수학적 귀납의 원칙을 써서 보이기로 하자.

(base) n = 1 이면 Y는 비어있어야 한다. 따라서 X $\nsim$ Y.

(step) n = k 에서 X $\nsim$ Y 이 성립한다면 반드시 n = k+1 일 때도 성립한다는 것을 보여야 한다.

n = k 에서 X $\nsim$ Y 이 성립 한다고 했으므로, Y 와 일대일 대응하는 집합 {1, 2, ..., m} 이 있고 이때, m < k 일 수 밖에 없다.

이제 우리가 보여야 할 것은 X 가 {1, 2, 3, ... , k + 1 } 와 일대일로 대응할 때, 그 진부분집합 Y 는 X 와 일대일 대응이 있을 수 없다는 사실이다.

진부분집합 Y 는 X 와 일대일 대응 g 가 있다고 해보자.

그리고 X 가 {1, 2, 3, ... , k + 1 } 와 일대일로 대응하기 때문에, 그 때의 대응을 f 라 하면, X의 모든 원소는 {f(1), f(2), ... , f(k+1)} 이 된다. 진부분 집합 Y와 본래집합 X가 g로 일대일 대응하기 때문에, 집합 Y 는 { g(f(1)), g(f(2)), ... , g(f(k+1))} 다.

그런데 Y 는 X 의 진부분집합이다. 따라서 최소한 X 의 어떤 원소 중 최소한 하나는 Y 에 있다. 그것을 f(1) 이라 하자. f(1) 은 g(f(1)), g(f(2)), ... , g(f(k+1))들 중 하나와 겹칠 것이다. 그것을 g(f(k+1)) 이라고 해보자.

이제 집합 X 와 집합 Y 에서 같은 원소 f(1) 을 빼낸 집합들을 보자. 그것들을 X' , Y' 라 하자.

다시 말해 X' := { f(2), ... , f(k+1)} 이고 Y':= { g(f(1)), g(f(2)), ... ,g(f(k)) } 다. 그런데 Y 와 X는 g 로 일대일로 대응한다고 했고, 같은 원소를 빼냈기 때문에 마찬가지로 여기서도 X'와 Y' 는 g 로 일대일 대응한다.

이것은 말이 안된다. 왜냐하면, 바로 앞 n = k 일 때, 다시 말해서 어떤 일대일 대응도 없다고 했기 때문이다.

}

그러면 $X'\sim {\bar {k}}$ 다.

집합 Y 는 비어 있거나, 아니면 f(1), f(2), ... f(k+1)중 하나라도 없어야 한다. 그 중 하나만 적게 들었다고 하고 그 하나가 f(1) 이라고 해보자. 그렇다면 Y 는 { f(2), f(3) , ... , f(k+1) } 가 된다.

이제 집합 X 에서 원소 f(1) 을 빼고 나머지를 보자. 그 집합은 { f(2), f(3) , ... , f(k+1) }다. }