3.3: Набори живлення
- Page ID
- 62460
Даним множиною\(A,\) ми називаємо множини всіх підмножин\(A\) степеневого набору\(A,\), яку ми позначимо\(\mathcal{P}(A)\).
Якщо\(A=\{1,2,3\},\) тоді
\[\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}.\]
Якщо\(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.
З\(B\), як і в попередній пропозиції, показати, що\(|B|=2^{n}\).
За аналогією з випадком, коли\(A\) є кінцевим, ми допускаємо\(2^{|A|}=|\mathcal{P}(A)|\) для будь-якого непорожнього множини\(A .\)
Припустимо\(A\) і\(B\) є множинами, для яких існує функція один-на-один\(\varphi: A \rightarrow \bar{B}\) але не існує кореспонденції один до одного\(\psi: A \rightarrow B .\) Потім пишемо\(|A|<|B| .\)
Якщо\(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\) що незліченно. Як наслідок, ми маємо наступний результат.
\(\mathbb{R}\)незліченна.
Дозвольте\(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\}|\)
Нехай\(I=\{x: x \in \mathbb{R}, 0 \leq x<1\}\) і припустимо\(b\),\(a\) і є дійсними числами з\(a<b .\) Показати, що
\[|I|=|\{x: x \in \mathbb{R}, a \leq x<b\}|.\]
Чи існує набір\(A \subset \mathbb{R}\) для якого\(\aleph_{0}<|A|<2^{\aleph_{0}} ?\) (Перш ніж працювати занадто довго над цією проблемою, ви можете прочитати про гіпотезу континуму Кантора.)