13.3: Детальніше про відносні розміри наборів
- Page ID
- 64912
Що таке «розмір»\(\mathbb{R}\text{?}\)
Ми знаємо\(\mathbb{N}\text{,}\)\(\mathbb{Z}\text{,}\) і\(\mathbb{Q}\) всі мають однаковий розмір (незліченно нескінченний). Але\(\mathbb{R}\) настільки великий, що він не підраховується, тому здається, що\(\mathbb{R}\) повинен бути «більше», ніж\(\mathbb{N}\text{,}\)\(\mathbb{Z}\text{,}\) і\(\mathbb{Q}\text{.}\)
set\(B\) більше, ніж встановлено,\(A\) якщо
- \(B\)має підмножину такого ж розміру, як\(A\text{,}\) і
- кожна підмножина\(B\) якого має такий же розмір, як і\(A\) належний
\(B\)якщо більше, ніж\(A\text{,}\)\(A\) то менше\(B\)
- Показати, чи існує ін'єкція\(A \hookrightarrow B\text{.}\)
- Покажіть, що кожна ін'єкція також\(A \hookrightarrow B\) не може бути surjection.
Однак, якщо один або\(A,B\) обидва з кінцевих, можна замість цього просто перевірити, що\(\vert B \vert > \vert A \vert \text{.}\)
- Зіставлення частин тесту з частинами визначення більшого набору:
- Існування ін'єкції\(f: A \hookrightarrow B\) демонструє, що\(B\) має підмножину, яка має такий же розмір,\(A\text{,}\) як обмеження кодомена для\(f: A \rightarrow f(A)\) створення біекції.
- За визначенням, підмножина\(C \subseteq B\) має такий же розмір, як\(A\) коли існує біекція\(A \to C\text{.}\) Збільшення кодомену, така біекція може розглядатися як ін'єкція, зображення\(A \hookrightarrow B\) якої є\(C \subseteq B\text{.}\) Якщо така ін'єкція також не може бути суб'єктивною, то\(C \subsetneqq B\text{,}\)\(C\) тобто є належна підмножина\(B\text{.}\)
- У другій частині тесту можна просто показати, що кожна функція\(A \to B\) не може бути відривом, і в цьому випадку, безумовно, кожна ін'єкція\(A \hookrightarrow B\) не може бути відривом. Може здатися, що це повинно бути складніше довести це більш загальне твердження, але якщо ви виявите, що ваш аргумент про те, що кожна ін'єкція не може бути відривом, насправді не покладатися на ін'єкційне припущення, то немає необхідності в цьому припущенні.
Набір\(\mathbb{R}\) більше, ніж кожен з наборів\(\mathbb{N}\text{,}\)\(\mathbb{Z}\text{,}\) і\(\mathbb{Q}\text{.}\)
Тут слід важливе порівняння встановлених розмірів.
Кожен набір менший, ніж власний набір потужності.
- Доказ
-
\(A\)Дозволяти представляти довільну множину. Ми застосуємо тест більшого набору, щоб продемонструвати, що\(\scr{P}(A)\) це більше\(A\text{.}\)
- Існує природна ін'єкція
\ begin {align*} A &\\ гачка-стрілка\ mathscr {P} (A),\\ x &\ mapsto\ {x\}. \ end {align*}
(Якщо\(A\) порожній, то це просто порожня функція, яка завжди є ін'єкційною Заявою 1 Пропозиції 12.1.1.)- Припустимо,\(f: A \rightarrow \scr{P}(A)\) це довільна функція. Використовуючи Surctive Function Test, ми продемонструємо, що він не може бути суб'єктивним, виставляючи елемент,\(X \in \scr{P}(A)\) для якого жоден елемент не\(a \in A\) задовольняє\(f(a) = X\text{.}\) (нам не потрібно буде робити припущення, яке\(f\) є ін'єкційним - див. Заява 2 Зауваження\(\PageIndex{1}\).)
Зверніть увагу, що для кожного\(a \in A\text{,}\)\(f(a) \in \scr{P} (A)\text{,}\) елемента зображення, який є елементом набору потужності, є підмножиною\(A\text{.}\) Отже, для кожного\(a \in A\) ми можемо запитати, чи\(a\) міститься в підмножині\(f(a)\) чи ні. Збираючи разом відповіді «чи ні», набір
\ begin {рівняння*} X =\ {a\ in A: a\ notin f (a)\}. \ end {equation*}
Зауважте, що\(X\) є підмножиною\(A\text{,}\) так знову це означає, що вона також є елементом\(\scr{P}(A)\text{.}\)Може\(f(a) = X\) бути можливим для деяких\(a \in A\text{?}\) Оскільки\(X \subseteq A\text{,}\) для кожного у\(a \in A\) нас є\(a \in X\) або\(a \notin X\text{.}\)
Кейс\(a \in X\).
Тоді за визначенням\(X\) вище, ми маємо\(a \notin f(a)\text{.}\) Since\(X\) містить елемент,\(a\) але\(f(a)\) не має, встановлює\(X\) і\(f(a)\) не може бути рівним.Кейс\(a \notin X\).
Тоді за визначенням\(X\) вище, ми повинні мати,\(a \in f(a)\text{,}\) оскільки інакше\(a\) б задовольнити умову бути в\(X\text{.}\) Але тепер\(f(a)\) містить елемент,\(a\) але не\(X\) робить, тому знову встановлює\(X\) і не\(f(a)\) може бути рівним.Оскільки\(f(a) = X\) це не можливо у всіх випадках, ми знайшли елемент,\(\scr{P}(A)\) який відсутній на зображенні,\(f(A)\text{,}\) як потрібно, щоб продемонструвати, що\(f\) це не є суб'єктивним.
Теорема Кантора має на увазі, що існує нескінченна кількість «рівнів» нескінченності! Бо, якщо\(A\) це нескінченний набір, то\(\scr{P}(A)\) є більшим нескінченним набором, і\(\scr{P}(\scr{P}(A))\) є ще більшим нескінченним набором, і\(\scr{P} (\scr{P}(\scr{P}(A )))\) є ще більшим нескінченним набором,...
Розмір множини натуральних чисел\(\mathbb{N}\) здається найнижчим можливим рівнем нескінченності, оскільки кожна підмножина\(\mathbb{N}\) є або скінченною, або має такий же розмір, як\(\mathbb{N}\text{.}\) (Див. Заява 1 Пропозиції 13.2.1.) Набір дійсних чисел\(\mathbb{R}\) більший, ніж\(\mathbb{N}\text{,}\) оскільки він містить\(\mathbb{N}\) як належну підмножину, але сам по собі не такий же розмір, як\(\mathbb{N}\text{.}\) Тому написання не те\(\vert \mathbb{N} \vert = \infty\) саме, що написання,\(\vert \mathbb{R} \vert = \infty\text{,}\) оскільки вони, очевидно, різні рівні нескінченності. Чи існує якийсь рівень нескінченності між цими двома?
Там не існує набір більше, ніж,\(\mathbb{N}\) але менший\(\mathbb{R}\text{.}\)
Невідомо, чи вірна гіпотеза континууму! Насправді доведено, що гіпотеза континууму не може бути ні доведена, ні спростована в певних загальних аксіоматичних системах теорії множин!
Ми бачили, що смішні речі можуть відбуватися з розмірами нескінченних множин - наприклад,\(\mathbb{N}\) це правильна підмножина,\(\mathbb{Z}\text{,}\) але вони мають однаковий розмір! Це не дефект у наших визначеннях, це просто демонструє, що для нескінченних множин відношення підмножин не є гарною мірою розміру. Але це також демонструє, що ми повинні бути пильними щодо інших можливих неінтуїтивних наслідків наших визначень, оскільки вони можуть виявити дефекти в наших визначеннях. Наприклад, з наших визначень менших і великих наборів немає очевидної причини, чому не може бути якогось дивного прикладу пари наборів\(A\) і\(B\) з\(B\) більшими, ніж\(A\) і\(A\) більшими, ніж\(B\text{.}\) На щастя, це не може статися завдяки наступному теорема.
Припустимо\(A\) і\(B\) є нескінченні множини. Якщо існує як ін'єкція, так\(A \hookrightarrow B\) і ін'єкція,\(B \hookrightarrow A\text{,}\) то\(A\) і\(B\) мають однаковий розмір.
- Доказ
-
Припустимо\(f: A \hookrightarrow B\) і\(g: B \hookrightarrow A\) є ін'єкції. Нам потрібно виставляти біекцію від\(A\) до\(B\) (або навпаки, але ми будемо будувати один від\(A\) до\(B\)).
Для кожного елемента\(a \in A\text{,}\) ми можемо побудувати ланцюжок змінних елементів з\(A\) і\(B\) наступним чином. Працюючи вперед від\(a\text{,}\) ін'єкційних\(f\) карт\(a\) до якогось елемента\(B\text{,}\) і ін'єкції\(g\) карти того елемента\(B\) до якогось елемента,\(A\text{,}\) який\(f\) відображається на якийсь елемент\(B\text{,}\) і так далі.
\ begin {align*} a_0 & = a,\\ b_0 & = f (a_0),\\ a_1 & = g (b_0),\\ b_1 & = f (a_1),\\ a_2 & = g (b_1),\\ &\ vdots\ end {align*}
Ланцюжок буде продовжуватися нескінченно, тому що функції\(f\)\(g\) завжди надають наступний елемент.Ми також можемо спробувати простежити ланцюжок назад: починаючи з нашого оригінального елемента,\(a \in A\text{,}\) ми можемо шукати якийсь елемент цієї\(g\) карти\(B\),\(a\text{,}\) хоча на перший погляд можливо, що жоден не існує. Якщо ми знайдемо такий елемент\(B\text{,}\) ми можемо потім шукати якийсь елемент,\(A\) що\(f\) карти до нього, і так далі. Хоча ланцюг поширюється нескінченно в прямому напрямку, ми не можемо бути впевнені в цьому місці, що вона буде поширюватися нескінченно в зворотному напрямку.
Тепер кожен елемент\(A\) може бути поміщений в такий ланцюжок,\(f\) і тому що і\(g\) є ін'єкційні ланцюг, в якому ми знаходимо елемент\(a\) завжди однаковий: наступний елемент ланцюга завжди\(f(a)\text{,}\) і елемент перед\(a\) завжди унікальний\(b\) в \(B\)так що\(g(b) = a\) (якщо такий елемент існує). А елементи після\(f(a)\) і до також однозначно\(b\) визначаються інжективністю\(f\)\(g\text{.}\) і так далі.
Таким чином, ми в кінцевому підсумку знаходимо кожен елемент\(A\) в унікальному ланцюжку, що чергується, і кожен ланцюг має один з чотирьох моделей:
- ланцюг з деяким елементом повторюється, і в цьому випадку ми могли б змусити ланцюг петля назад на себе при повторенні, щоб утворити кінцевий, кругової ланцюг;
- ланцюжок без повторення і без кінця або початку;
- ланцюг без повторення і без кінця, але процес простежити його назад не вдалося в якийсь момент, і останній елемент у напрямку «назад» (який ми могли б розглядати як перший елемент у всьому ланцюжку) є елементом\(A\text{;}\) і
- ланцюг без повторення і без кінця, але починається з елемента\(B\text{.}\)
Тепер, коли ми вирізали можливе повторення шляхом створення кругових ланцюгів, кожен елемент\(A\) з'являється рівно один раз в унікальному ланцюжку, і за симетрією те ж саме можна сказати про\(B\text{.}\) Ми можемо потім створити біекцію від\(A\) до\(B\) шляхом відображення кожного елемента\(A\) до елемент\(B\), який слідує за ним у ланцюжку, в якому він з'являється. За винятком елементів\(A\), які з'являються в ланцюжку, який має початок з початкового елемента з\(B\) — замість цього кожен з цих елементів\(A\) повинен бути зіставлений з елементом\(B\), який передує йому в його ланцюжку. Це створить двооб'єктивну відповідність між елементами\(A\) і\(B\text{.}\)