3.3: Набори живлення

Визначення

Даним множиною$A,$ ми називаємо множини всіх підмножин$A$ степеневого набору$A,$, яку ми позначимо$\mathcal{P}(A)$.

Приклад$\PageIndex{1}$

Якщо$A=\{1,2,3\},$ тоді

$$\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}.$$

Пропозиція$\PageIndex{1}$

Якщо$A$ кінцевий з$|A|=n,$ потім$|\mathcal{P}(A)|=2^{n}$.

Доказ

Нехай

$$B=\left\{\left(b_{1}, b_{2}, \ldots, b_{n}\right): b_{i}=0 \text { or } b_{i}=1, i=1,2, \ldots, n\right\}$$

і нехай$a_{1}, a_{2}, \ldots, a_{n}$ будуть елементи$A .$ Визначити$\varphi: B \rightarrow \mathcal{P}(A)$, дозволяючи

$$\varphi\left(b_{1}, b_{2}, \ldots, b_{n}\right)=\left\{a_{i}: b_{i}=1, i=1,2, \ldots, n\right\}.$$

Потім$\varphi$ йде листування один на один. Результат тепер випливає з наступної вправи. $\quad$Q.E.D.

Вправа$\PageIndex{1}$

З$B$, як і в попередній пропозиції, показати, що$|B|=2^{n}$.

За аналогією з випадком, коли$A$ є кінцевим, ми допускаємо$2^{|A|}=|\mathcal{P}(A)|$ для будь-якого непорожнього множини$A .$

Визначення

Припустимо$A$ і$B$ є множинами, для яких існує функція один-на-один$\varphi: A \rightarrow \bar{B}$ але не існує кореспонденції один до одного$\psi: A \rightarrow B .$ Потім пишемо$|A|<|B| .$

Теорема$\PageIndex{2}$

Якщо$A$ є непорожнім набором, то$|A|<|\mathcal{P}(A)|$.

Доказ

Визначити$\varphi: A \rightarrow \mathcal{P}\left(\mathbb{Z}^{+}\right)$ по

$$\varphi\left(\left\{a_{i}\right\}_{i=1}^{\infty}\right)=\left\{i: i \in \mathbb{Z}^{+}, a_{i}=1\right\}.$$

Потім$\varphi$ йде листування один на один. $\quad$Q.E.D.

Тепер нехай$B$ буде набір всіх послідовностей$\left\{a_{i}\right\}_{i=1}^{\infty}$ в$A$ такий, що для кожного цілого$N$ існує ціле число$n>N$ таке, що$a_{n}=0 .$ Нехай$C=A \backslash B$,

$$D_{0}=\left\{\left\{a_{i}\right\}_{i=1}^{\infty}: a_{i}=1, i=1,2,3, \ldots\right\},$$

і

$$D_{j}=\left\{\left\{a_{i}\right\}_{i=1}^{\infty}: a_{j}=0, a_{k}=1 \text { for } k>j\right\}$$

для$j=1,2,3, \ldots$ Тоді$\left|D_{0}\right|=1$ і$\left|D_{j}\right|=2^{j-1}$ для$j=1,2,3, \ldots$ того,

$$C=\bigcup_{j=0}^{\infty} D_{j},$$

так$C$ підраховується. Оскільки$A=B \cup C,$ і$A$ є незліченним, то випливає,$B$ що незліченно. Тепер, якщо ми дозволимо

$$I=\{x: x \in \mathbb{R}, 0 \leq x<1\},$$

ми бачили, що функція$\varphi: B \rightarrow I$ визначається

$$\varphi\left(\left\{a_{i}\right\}_{i=1}^{\infty}\right)=a_{1} a_{2} a_{3} a_{4} \ldots$$

це листування один на один. Звідси випливає,$I$ що незліченно. Як наслідок, ми маємо наступний результат.

Теорема$\PageIndex{4}$

$\mathbb{R}$незліченна.

Вправа$\PageIndex{2}$

Дозвольте$I=\{x: x \in \mathbb{R}, 0 \leq x<1\} .$ показати, що

а.$|I|=|\{x: x \in \mathbb{R}, 0 \leq x \leq 1\}|$

б.$|I|=|\{x: x \in \mathbb{R}, 0<x<1\}|$

c.$|I|=|\{x: x \in \mathbb{R}, 0<x<2\}|$

д.$|I|=|\{x: x \in \mathbb{R},-1<x<1\}|$

Вправа$\PageIndex{3}$

Нехай$I=\{x: x \in \mathbb{R}, 0 \leq x<1\}$ і припустимо$b$,$a$ і є дійсними числами з$a<b .$ Показати, що

$$|I|=|\{x: x \in \mathbb{R}, a \leq x<b\}|.$$

Вправа$\PageIndex{4}$

Чи існує набір$A \subset \mathbb{R}$ для якого$\aleph_{0}<|A|<2^{\aleph_{0}} ?$ (Перш ніж працювати занадто довго над цією проблемою, ви можете прочитати про гіпотезу континуму Кантора.)