younghwanjoo1608

ㅎㅇ

1 minute read


임의의 set $U$에 대해 $U$의 element의 수를 $\vert U \vert$로 나타닌다.

그럼 당연히, $\mathcal{V}$-structure $M$에 대해 $M$은 $\vert M_U \vert$를 의미하게 되며 $M$의 underlying set $U_M$의 원소의 수를 말한다. 이제 $\vert M \vert$을 $M$의 size라고 하자.


위 case의 경우 $\vert M \vert = 5$.


만약 $M$의 underlying set이 infinite이면 $\vert M \vert = \infty$라고 쓸 수 있다. 그게 끝일까?


Definition 1.5.1

$A$, $B$가 set이라고 하자.

$B$에서 $A$로의 one-to-one function $f$가 존재하면 우리는 이를 $\vert B \vert \leq \vert A \vert$라고 정의한다.


위 정의는 $f$가 one-to-one이고 $B$를 domain으로 가져야 한다고 요구하고 있다. 임의의 $b \in B$에 대해 이 함수는 $A$에서 원소 $f(b)$를 골라낸다. 그러한 함수가 존재한다면 비로소 $\vert B \vert \leq \vert A \vert$라고 말할 수 있다.


Example 2.5.2

$P$를 모든 prime number의 set, $E$를 모든 짝수 자연수의 set이라고 하자. 함수 $f:P \rightarrow Q$를 $f(p)=2p$로 정의하자. 이 함수는 one-to-one이므로, $\vert P \vert \leq \vert E \vert$이다. 따라서 짝수는 최소한 소수들만큼 많이 존재한다.


Example 2.5.3

$\mathbb{N} \times \mathbb{N}$은 모든 자연수들의 ordered pair의 집합이다.

모든 $n \in \mathbb{N}$에 대해 함수 $f: \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$를 $f(n) = (n,1)$로 정의하자. 이 함수는 one-to-one이다. 따라서 $\vert \mathbb{N} \vert \leq \vert \mathbb{N} \times \mathbb{N} \vert$라고 결론내릴 수 있다.

그럼 그 역은 어떨까? 함수 $g: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$를 $g(m,n) = 2^m 3^n$으로 정의하자. 이 역시 one-to-one이고 $\vert \mathbb{N} \times \mathbb{N} \vert \leq \vert \mathbb{N}\vert$가 성립한다.


Definition 2.5.4

$A$, $B$가 set이라고 하자.

$\vert B \vert \leq \vert A \vert$이고 $\vert A \vert \leq \vert B \vert$일 때 $A$와 $B$는 같은 size를 가졌다고 하며 $\vert B \vert = \vert A \vert$로 표기한다.

$\vert A \vert < \vert B \vert$는 $\vert A \vert \leq \vert B \vert$이나 $\vert A \vert = \vert B \vert$가 성립하지 않음을 의미한다.


따라서 $A$와 $B$가 같은 size라는 걸 보이기 위해서는 $A$에서 $B$로의 one-to-one function과 $B$에서 $A$로의 one-to-one function이 존재함을 보여야 한다.

이는 $A$에서 $B$로의 one-to-one이면서 onto인 함수를 보이면 충분하다. 이러한 함수를 one-to-one correspondence 또는 bijection이라고 한다.

You may also enjoy