1.6: Кардинальність

\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\Q}{\mathbb{Q}}\)\(\newcommand{\A}{\mathbb{A}}\)\(\newcommand{\bs}{\boldsymbol}\)

Основна теорія

Визначення

Припустимо, що\(\mathscr{S}\) це непорожня колекція множин. Ми визначаємо відношення\(\approx\)\(\mathscr{S}\) на\(A \approx B\) якщо і тільки якщо існує функція один до одного\(f\) з\(A\) onto\(B\). \(\approx\)Відношення - це відношення еквівалентності на\(\mathscr{S}\). Тобто, для всіх\( A, \, B, \, C \in \mathscr{S} \),

1. \( A \approx A \), Рефлексивне властивість
2. Якщо\( A \approx B \) тоді\( B \approx A \), симетрична властивість
3. Якщо\( A \approx B \) і\( B \approx C \ \) то\( A \approx C \), перехідне властивість

Доказ

1. Функція ідентичності\( I_A \) на\( A \), задана\( I_A(x) = x \) for\( x \in A \),\( A \) відображає один до одного на\( A \). Звідси\( A \approx A \)
2. Якщо\( A \approx B \) тоді існує функція один до одного\( f \) з\( A \) onto\( B \). Але тоді\( f^{-1} \) це функція один-на-один з\( B \) на\( A \), так\( B \approx A \)
3. Припустимо, що\( A \approx B \) і\( B \approx C \). Тоді існує функція один до одного\( f \) з\( A \) onto\( B \) і функція один до одного\( g \) з\( B \) onto\( C \). Але тоді\( g \circ f \) це функція один до одного з\( A \) на\( C \), так що\( A \approx C \).

Функція «один до одного»\( f \) від\( A \) onto іноді\( B \) називається біекцією. Таким чином, якщо\( A \approx B \) потім\( A \) і\( B \) знаходяться в листуванні один до одного і, як кажуть, мають однакову кардинальність. Класи еквівалентності за цим співвідношенням еквівалентності захоплюють поняття наявності однакової кількості елементів.

Нехай\(\N_0 = \emptyset\), і для\(k \in \N_+\), нехай\(\N_k = \{0, 1, \ldots k - 1\}\). Як завжди,\( \N = \{0, 1, 2, \ldots\} \) це множина всіх натуральних чисел.

Припустимо, що\( A \) це набір.

1. \(A\)є кінцевим, якщо\(A \approx \N_k\) для деяких\(k \in \N\), в цьому випадку\(k\) є кардинальність\(A\), і ми пишемо\(\#(A) = k\).
2. \( A \)нескінченна\( A \), якщо не скінченна.
3. \( A \)є незліченно нескінченним, якщо\( A \approx \N \).
4. \( A \)підраховується, якщо\( A \) є кінцевим або незліченно нескінченним.
5. \( A \)є незліченним, якщо\( A \) не підраховується.

У частині (а) розглядайте\(\N_k\) як еталонний набір з\(k\) елементами; будь-який інший набір з\(k\) елементами повинен бути еквівалентним цьому. Ми вивчимо кардинальність скінченних множин у наступних двох розділах, присвячених лічильній мірі та комбінаторним структурам. У цьому розділі ми зосередимося насамперед на нескінченні множини. У частині (d) лічильний набір - це той, який можна перерахувати або порахувати, поставивши елементи в один до одного відповідність з\( \N_k \) деякими\( k \in \N \) або з усіма\( \N \). Незліченний набір - це той, який не можна так порахувати. Підрахувальні множини відіграють особливу роль в теорії ймовірностей, як і в багатьох інших галузях математики. Апріорі, незрозуміло, що є незліченні набори, але незабаром ми побачимо приклади.

попередні приклади

Якщо\( S \) є множиною, нагадаємо, що\(\mathscr{P}(S)\) позначає потужність\(S\) множини (множина всіх підмножин\(S\)). Якщо\( A \) і\( B \) є множинами, то\( A^B \) це набір всіх функцій з\( B \) в\( A \). Зокрема,\(\{0, 1\}^S\) позначає набір функцій з\(S\) в\(\{0, 1\}\).

Якщо\(S\) це набір, то\(\mathscr{P}(S) \approx \{0, 1\}^S\).

Доказ

Відображення, яке приймає набір\(A \in \mathscr{P}(S)\) у свою індикаторну функцію\(\boldsymbol{1}_A \in \{0, 1\}^S\), є один до одного і на. Зокрема, якщо\( A, \, B \in \mathscr{P}(S) \) і\( \bs{1}_A = \bs{1}_B \), то\( A = B \), таким чином, відображення один до одного. З іншого боку, якщо\( f \in \{0, 1\}^S \) тоді\( f = \bs{1}_A \) де\( A = \{x \in S: f(x) = 1\} \). Отже, відображення відбувається на.

Далі наведено кілька прикладів незліченно нескінченних множин.

Наступні множини незліченно нескінченні:

1. Безліч парних натуральних чисел\(E = \{0, 2, 4, \ldots\}\)
2. Безліч цілих чисел\(\Z\)

Доказ

1. Функція,\(f: \N \to E\) задана\(f(n) = 2 n\) одним до одного і on-to.
2. Функція,\(g: \N \to \Z\) задана\(g(n) = \frac{n}{2}\) якщо\( n \) парна, а\(g(n) = -\frac{n + 1}{2}\) якщо\( n \) непарна, є один до одного і на.

На одному рівні може здатися, що\( E \) має лише вдвічі менше елементів, скільки\( \Z \) у\( \N \) той час як має вдвічі більше елементів, ніж\( \N \). Як показує попередній результат, ця точка зору неправильна:\( \N \)\( E \), і\( \Z \) всі мають однакову кардинальність (і незліченно нескінченна ). Наступний приклад показує, що дійсно є незліченні набори.

Якщо\(A\) множина з принаймні двома елементами\(S = A^\N\), то набір усіх функцій з\(\N\) into\(A\) є незліченним.

Доказ

Доказ є протиріччям і використовує приємний трюк, відомий як метод діагоналізації. Припустимо,\(S\) що незліченно нескінченно (це явно не скінченно), так що елементи\(S\) можуть бути перераховані:\(S = \{f_0, f_1, f_2, \ldots\}\). \(b\)Дозволяти\(a\) і позначити окремі елементи\(A\) і визначити\(g: \N \to A\),\(g(n) = b\) якщо\(f_n(n) = a\) і\(g(n) = a\) якщо\(f_n(n) \ne a\). Зверніть увагу, що\(g \ne f_n\) для кожного\(n \in \N\), так\(g \notin S\). Це суперечить тому, що\(S\) є сукупністю всіх функцій з\(\N\) в\(A\).

Підмножини нескінченних множин

Звичайно, набір повинен бути настільки ж великим, як і будь-яка його підмножина, з точки зору кардинальності. З іншого боку, у прикладі (4) множина натуральних чисел\( \N \), набір парних натуральних чисел\( E \) та набір цілих чисел мають\( \Z \) однакову кардинальність, хоча\( E \subset \N \subset \Z \). У цьому підрозділі ми розглянемо деякі цікаві та дещо парадоксальні результати, які стосуються підмножин нескінченних множин. По дорозі ми побачимо, що лічильна нескінченність - це найменша з нескінченностей.

Якщо\(S\) є нескінченним набором, то\(S\) має лічильну нескінченну підмножину.

Доказ

Виберіть\(a_0 \in S\). Це можливо зробити, оскільки\(S\) є нескінченним і, отже, непорожнім. Індуктивно, вибравши\(\{a_0, a_1, \ldots, a_{k-1}\} \subseteq S\), вибирайте\(a_k \in S \setminus \{a_0, a_1, \ldots, a_{k-1}\}\). Знову ж таки, це можливо зробити, оскільки не\(S\) є кінцевим. Очевидно,\(\{a_0, a_1, \ldots \}\) є незліченно нескінченною підмножиною\(S\).

Множина\(S\) нескінченна тоді і лише тоді\(S\), коли еквівалентна належній підмножині\(S\).

Доказ

Якщо\(S\) є кінцевим, то не\(S\) є еквівалентним належному підмножині за принципом pigeonhole. Якщо\(S\) нескінченно, то\(S\) має незліченно нескінченну\(\{a_0, a_1, a_2, \ldots\}\) підмножину за попереднім результатом. Визначте функцію\( f: S \to S \) по\( f \left(a_n\right) = a_{2 n} \) for\(n \in \N\) і\( f(x) = x \) for\(x \in S \setminus \{a_0, a_1, a_2, \ldots\}\). Потім\( f \)\(S\) відображає один до одного на\(S \setminus \{a_1, a_3, a_5, \ldots\}\).

Коли\(S\) був нескінченним у доказі попереднього результату, ми не тільки зіставляли\(S\) один до одного на належну підмножину, ми насправді викинули незліченно нескінченну підмножину і все ще підтримували еквівалентність. Аналогічно, ми можемо додати незліченно нескінченний набір до нескінченного набору,\(S\) не змінюючи кардинальності.

Якщо\(S\) є нескінченною\(B\) множиною і є лічильним набором, то\(S \approx S \cup B\).

Доказ

Розглянемо самий крайній випадок, коли\(B\) зліченно нескінченно і нероз'єднаний від\(S\). Тоді\(S\) має незліченно нескінченну\(A = \{a_0, a_1, a_2, \ldots\}\) підмножину за результатом вище, і\(B\) може бути перелічено, так\(B = \{b_0, b_1, b_2, \ldots\}\). Визначте функцію\( f: S \to S \cup B \),\(f\left(a_n\right) = a_{n/2}\) якщо\( n \) парне,\( f\left(a_n\right) = b_{(n-1)/2} \) якщо\( n \) непарне, і\( f(x) = x \) якщо\( x \in S \setminus \{a_0, a_1, a_2, \ldots\} \). Потім\( f \)\( S \) відображає один до одного на\( S \cup B \).

Зокрема, якщо\(S\) є\(B\) незліченним і підраховується тоді\(S \cup B\) і\(S \setminus B\) мають таку ж кардинальність\(S\), як і, зокрема, незліченні. З точки зору дихотомій скінченно-нескінченний і злічено-незліченний, набір дійсно принаймні такий же великий, як підмножина. Для початку нам потрібен попередній результат.

Якщо\(S\) нескінченно нескінченно, а\(A \subseteq S\) потім\(A\) підраховується.

Доказ

Досить показати, що якщо\( A \) є нескінченною підмножиною,\( S \) то\( A \) є незліченно нескінченним. Оскільки\(S\) є незліченно нескінченним, його можна перерахувати:\(S = \{x_0, x_1, x_2, \ldots\}\). \(n_i\)Дозволяти\(i\) найменший індекс такий, що\(x_{n_i} \in A\). Тоді\(A = \{x_{n_0}, x_{n_1}, x_{n_2}, \ldots\}\) і, отже, незліченно нескінченно.

Припустимо, що\(A \subseteq B\).

1. Якщо\(B\) скінченний\(A\), то кінцевий.
2. Якщо\(A\) нескінченно, то\(B\) нескінченно.
3. Якщо\(B\) підраховується, то\(A\) підраховується.
4. Якщо\(A\) незліченна,\(B\) то незліченна.

Доказ

1. Це зрозуміло з визначення кінцевої множини.
2. Це контрапозитив (а).
3. Якщо\( A\) скінченна, то\( A \) піддається зліченню. Якщо\( A \) нескінченно, то\( B \) нескінченно по (b) і, отже, незліченно нескінченно. Але тоді\( A \) незліченно нескінченна по (9).
4. Це контрапозитив (с).

Порівняння за допомогою функцій один до одного та на

Ми розглянемо глибше загальне питання про те, коли один набір хоча б такий же великий, як інший, в сенсі кардинальності. Не дивно, що це врешті-решт призведе до часткового порядку на класах еквівалентності кардинальності.

Спочатку зауважте, що якщо існує функція, яка\(A\) відображає набір один до одного в набір\(B\), то в певному сенсі є копія\(A\) міститься в\(B\). Значить,\(B\) повинен бути як мінімум такий же великий, як\(A\).

Припустимо, що\(f: A \to B\) це один-на-один.

1. Якщо\(B\) скінченний\(A\), то кінцевий.
2. Якщо\(A\) нескінченно, то\(B\) нескінченно.
3. Якщо\(B\) підраховується, то\(A\) підраховується.
4. Якщо\(A\) незліченна,\(B\) то незліченна.

Доказ

Зверніть увагу, що\(f\) карти\(A\) один до одного на\(f(A)\). Звідси\( A \approx f(A) \) і\(f(A) \subseteq B\). Результати тепер випливають з (10):

1. Якщо\( B \) кінцевий, то\( f(A) \) кінцевий і, отже\( A \), кінцевий.
2. Якщо\( A \) нескінченно, то\( f(A) \) нескінченно і, отже\( B \), нескінченно.
3. Якщо\( B \) підраховується, то\( f(A) \) підраховується і, отже\( A \), підраховується.
4. Якщо\( A \) є незліченним, то\( f(A) \) є незліченним і, отже\( B \), незліченним.

З іншого боку, якщо існує функція, яка відображає набір\(A\) на набір\(B\), то в певному сенсі є копія\(B\) міститься в\(A\). Значить,\(A\) повинен бути як мінімум такий же великий, як\(B\).

Припустимо, що\(f: A \to B\) це на.

1. Якщо\(A\) скінченний\(B\), то кінцевий.
2. Якщо\(B\) нескінченно, то\(A\) нескінченно.
3. Якщо\(A\) підраховується, то\(B\) підраховується.
4. Якщо\(B\) незліченна,\(A\) то незліченна.

Доказ

Для кожного\(y \in B\) виберіть конкретний\(x \in A\) з\(f(x) = y\) (якщо ви зухвалий, вам може знадобитися викликати аксіому вибору). \(C\)Дозволяти бути безліччю обраних очок. Потім\(f\) карти\(C\) один до одного на\(B\), так\( C \approx B \) і\(C \subseteq A\). Результати тепер випливають з (11):

1. Якщо\( A \) кінцевий, то\( C \) кінцевий і, отже\( B \), кінцевий.
2. Якщо\( B \) нескінченно, то\( C \) нескінченно і, отже\( A \), нескінченно.
3. Якщо\( A \) підраховується, то\( C \) підраховується і, отже\( B \), підраховується.
4. Якщо\( B \) є незліченним, то\( C \) є незліченним і, отже\( A \), незліченним.

Попередня вправа також може бути доведена з попереднього, оскільки якщо існує\(f\) відображення функції\(A\) на\(B\), то існує функція\(g\) відображення\(B\) один до одного в\(A\). Така подвійність доведена в обговоренні аксіоми вибору. Простим і корисним наслідком попередніх двох теорем є те, що якщо\(B\) це задана незліченно нескінченна множина, то множина\(A\) підраховується тоді і тільки тоді, коли існує функція один до одного\(f\) з\(A\) into\(B\), якщо і тільки якщо існує функція\(g\) з \(B\)на\(A\).

Якщо\(A_i\) є обчислювальним набором для кожного\(i\) в обчислювальному наборі\(I\) індексів, то\(\bigcup_{i \in I} A_i\) підраховується.

Доказ

Розглянемо самий крайній випадок, коли набір індексів\(I\) є незліченно нескінченним. Оскільки\( A_i \) підраховується, існує функція\(f_i\), яка\(\N\) відображає\(A_i\) для кожного\(i \in \N\). Нехай\(M = \left\{2^i 3^j: (i, j) \in \N \times \N\right\}\). Зверніть увагу, що точки в\( M \) різні, тобто\( 2^i 3^j \ne 2^m 3^n \) якщо\( (i, j), \, (m, n) \in \N \times \N \) і\( (i, j) \ne (m, n) \). Отже,\(M\) нескінченно, а з тих пір\( M \subset \N \),\( M \) незліченно нескінченно. Функція,\(f\) задана\(f\left(2^i 3^j\right) = f_i(j)\) для\((i, j) \in \N \times \N\) карт\( M \) на\( \bigcup_{i \in I} A_i \), і, отже, цей останній набір підраховується.

Якщо\(A\) і\(B\) підраховуються, то\(A \times B\) підраховується.

Доказ

Існує функція\(f\), яка відображає\(\N\) на\(A\), і існує функція,\(g\) яка відображає\(\N\) на\(B\). Знову ж таки, нехай\(M = \left\{2^i 3^j: (i, j) \in \N \times \N \right\}\) і нагадаємо,\(M\) що незліченно нескінченно. Визначте\(h: M \to A \times B\) по\(h\left(2^i 3^j\right) = \left(f(i), g(j)\right)\). Потім\(h\) карти\( M \) на\( A \times B \) і, отже, цей останній набір підраховується.

Останній результат також може бути доведений з попереднього, зазначивши, що

\[ A \times B = \bigcup_{a \in A} \{a\} \times B \]

Обидва докази працюють тому, що набір по суті\(M\) є копією\(\N \times \N\), вбудованою всередині\(\N\). Остання теорема узагальнює твердження про те, що кінцевий добуток обчислюваних множин все ще піддається зчисленню. Але, з (5), твір нескінченно багатьох наборів (з принаймні 2 елементами кожен) буде незліченним.

Множина раціональних чисел\(\Q\) зліченно нескінченна.

Доказ

Множини\(\Z\) і\(\N_+\) є незліченно нескінченними і, отже, безліч\(\Z \times \N_+\) незліченно нескінченна. Функція,\(f: \Z \times \N_+ \to \Q\) задана\(f(m, n) = \frac{m}{n}\) є onto.

Дійсне число є алгебраїчним, якщо воно є коренем поліноміальної функції (ступеня 1 або більше) з цілими коефіцієнтами. Раціональні числа є алгебраїчними, як і раціональні корені раціональних чисел (коли вони визначені). Більш того, алгебраїчні числа замикаються при додаванні, множенні і діленні. Реальне число трансцендентне, якщо воно не алгебраїчне. Цифри\(e\) і\(\pi\) трансцендентні, але ми не знаємо багато інших трансцендентних чисел за іменем. Однак, як ми побачимо, більшість (у сенсі кардинальності) реальних чисел трансцендентні.

Множина алгебраїчних чисел\(\A\) зліченно нескінченна.

Доказ

Нехай\(\Z_0 = \Z \setminus \{0\}\) і нехай\(\Z_n = \Z^{n-1} \times \Z_0\) для\(n \in \N_+\). Набір\(\Z_n\) незліченно нескінченний для кожного\(n\). Нехай\(C = \bigcup_{n=1}^\infty \Z_n\). Подумайте про набір коефіцієнтів і зверніть увагу, що\(C\) незліченно нескінченно.\(C\) Нехай\(P\) позначають множину поліномів ступеня 1 або більше, з цілими коефіцієнтами. Функція\((a_0, a_1, \ldots, a_n) \mapsto a_0 + a_1\,x + \cdots + a_n\,x^n\) відображає\(C\) на\(P\), і, отже,\( P \) підраховується. Для\( p \in P \), давайте\( A_p \) позначимо набір коренів\( p \). Поліном ступеня\(n\) in\(P\) має більшість\(n\) коренів, за фундаментальною теоремою алгебри, тому, зокрема,\( A_p \) є кінцевим для кожного\( p \in P \). Нарешті, зверніть увагу, що\( \A = \bigcup_{p \in P} A_p \) і так\( \A \) підраховується. Звичайно\( \N \subset \A \), так\( \A \) незліченно нескінченно.

Тепер давайте розглянемо деякі незліченні набори.

Інтервал\([0, 1)\) незліченний.

Доказ

Нагадаємо, що\( \{0, 1\}^{\N_+} \) це набір всіх функцій from\( \N_+ \) into\(\{0, 1\}\), який в даному випадку може розглядатися як нескінченні послідовності або бітові рядки:\[ \{0, 1\}^{\N_+} = \left\{\bs{x} = (x_1, x_2, \ldots): x_n \in \{0, 1\} \text{ for all } n \in \N_+\right\} \] За (5) цей набір є незліченним. Нехай\( N = \left\{\bs{x} \in \{0, 1\}^{\N_+}: x_n = 1 \text{ for all but finitely many } n\right\}\), набір бітових рядків, які в кінцевому підсумку закінчуються у всіх 1s. Зверніть увагу, що\( N = \bigcup_{n=1}^\infty N_n \) де\( N_n = \left\{\bs{x} \in \{0, 1\}^{\N_+}: x_k = 1 \text{ for all } k \ge n\right\} \). \( N_n \)Зрозуміло, що є кінцевим для всіх\( n \in \N_+ \), так\( N \) і піддається зліченню, і\( S = \{0, 1\}^{\N_+} \setminus N \) тому незліченна. Насправді,\( S \approx \{0, 1\}^{\N_+} \). Функція\[\bs{x} \mapsto \sum_{n = 1}^\infty \frac{x_n}{2^n} \]\( S \) відображає один до одного на\( [0, 1) \). У словах кожне число в\( [0, 1) \) має унікальне двійкове розширення у вигляді послідовності в\( S \). Звідси\( [0, 1) \approx S \) і зокрема, незліченна. Причина усунення бітових рядків, які закінчуються в 1s, полягає в забезпеченні унікальності, щоб відображення було один до одного. Рядок бітів\( x_1 x_2 \cdots x_k 0 1 1 1\cdots \) відповідає тому ж числу в\( [0, 1) \), що і бітовий рядок\( x_1 x_2 \cdots x_k 1 0 0 0\cdots \).

Наступні набори мають однакову кардинальність, і зокрема всі незліченні:

1. \(\R\), множина дійсних чисел.
2. Будь-який інтервал\(I\)\(\R\), до тих пір, поки інтервал не є порожнім або єдиною точкою.
3. \(\R \setminus \Q\), Набір ірраціональних чисел.
4. \(\R \setminus \A\), сукупність трансцендентних чисел.
5. \(\mathscr{P}(\N)\), потужність набору\(\N\).

Доказ

1. \( x \mapsto \frac{2 x - 1}{x (1 - x)} \)Картографування\( (0, 1) \) відображає один до одного на\( \R \) так\( (0, 1) \approx \R \). Але\( (0, 1) = [0, 1) \setminus \{0\} \), так\( (0, 1] \approx (0, 1) \approx \R \), і всі ці набори незліченні за попереднім результатом.
2. Припустимо\( a, \, b \in \R \), і\( a \lt b \). \( x \mapsto a + (b - a) x \)Картографування\( (0, 1) \) відображає один до одного на\( (a, b) \) і, отже,\( (a, b) \approx (0, 1) \approx \R \). Крім того\( [a, b) = (a, b) \cup \{a\} \),\( (a, b] = (a, b) \cup\{b\} \),, і\( [a, b] = (a, b) \cup \{a, b\} \), так\( (a, b) \approx [a, b) \approx (a, b] \approx [a, b]\approx \R \). Функція\( x \mapsto e^x \) відображає\( \R \) один до одного на\( (0, \infty) \), так що\( (0, \infty) \approx \R \). Для\( a \in \R \), функція\( x \mapsto a + x \)\( (0, \infty) \) відображає один на один\( (a, \infty) \) і відображення\(x \mapsto a - x \) карти\( (0, \infty) \) один до одного на\( (-\infty, a) \) так\( (a, \infty) \approx (-\infty, a) \approx (0, \infty) \approx \R \). Далі,\( [a, \infty) = (a, \infty) \cup \{a\} \) і\( (-\infty, a] = (-\infty, a) \cup \{a\} \), так\( [a, \infty) \approx (-\infty, a] \approx \R \).
3. \( \Q \)є незліченно нескінченним, так\( \R \setminus \Q \approx \R \).
4. Аналогічно,\( \A \) є незліченно нескінченним, так\( \R \setminus \A \approx \R \).
5. Якщо\( S \) нескінченно нескінченно, то за попереднім результатом і (а),\( \mathscr{P}(S) \approx \mathscr{P}(\N_+) \approx \{0, 1\}^{\N_+} \approx [0, 1) \).

Частковий порядок кардинальності

Припустимо, що\(\mathscr{S}\) це непорожня колекція множин. Ми визначаємо відношення\(\preceq\)\(\mathscr{S}\) на\(A \preceq B\) якщо і тільки якщо існує функція один-до-одному\(f\) з\(A\) into\(B\), якщо і тільки якщо існує функція\(g\) from\(B\) onto\(A\). У світлі попереднього підрозділу,\(A \preceq B\) слід охопити поняття, яке\(B\) є принаймні таким же великим\(A\), як, у сенсі кардинальності.

Відношення\(\preceq\) буває рефлексивним і перехідним.

Доказ

Для\( A \in \mathscr{S} \), функція ідентичності,\( I_A: A \to A \) задана\( I_A(x) = x \) одним до одного (а також на), так що\( A \preceq A \). Припустимо, що\( A, \, B, \, C \in \mathscr{S} \) і те\( A \preceq B \) і\( B \preceq C \). Тоді існують функції один-на-один\( f: A \to B \) і\( g: B \to C \). Але потім\( g \circ f: A \to C \) один на один, так що\( A \preceq C \).

Таким чином, ми можемо використовувати конструкцію в розділі про відносини еквівалентності, щоб спочатку визначити відношення еквівалентності на\(\mathscr{S}\), а потім продовжити\(\preceq\) до істинного часткового порядку на колекції класів еквівалентності. Єдине питання, яке залишається, полягає в тому, чи співвідношення еквівалентності, яке ми отримуємо таким чином, таке ж, яке ми використовували при вивченні кардинальності. Перефразирований, питання полягає в наступному: Якщо існує функція один до одного з\(A\) into\(B\) і функція один до одного з\(B\) в\(A\), чи обов'язково існує функція один до одного від\(A\) onto\(B\)? На щастя, відповідь так; результат відомий як теорема Шредера-Бернштейна, названа на честь Ернста Шредера та Фелікса Бернштейна.

Якщо\(A \preceq B\) і\(B \preceq A\) тоді\(A \approx B\).

Доказ

Включення множини\(\subseteq\) - це частковий порядок на\(\mathscr{P}(A)\) (множина потужності\(A\)) з властивістю, що кожна підколекція\(\mathscr{P}(A)\) має супремум (а саме об'єднання підколекції). Припустимо, що\(f\)\(A\) карти один на один в\(B\) і\(g\) карти\(B\) один до одного в\(A\). Визначте функцію\(h: \mathscr{P}(A) \to \mathscr{P}(A)\) за допомогою\(h(U) = A \setminus g[B \setminus f(U)]\) for\(U \subseteq A\). Потім\(h\) збільшується:\ begin {align} U\ підмножина V &\ має на увазі f (U)\ підмножина f (V)\ означає B\ setminus f (V)\ підмножина B\ setminus f (U)\\ &\ має на увазі g [B\ setminus f (V)]\ підрозділ g [B\ setminus f (U)\ означає, що г [B\ setminus g] [B\ setminus f (U)]\ підмножина A\ setminus g [B\ setminus f (V)]\ кінець {вирівнювання} З теореми фіксованої точки для частково впорядкованих множин існує\(U \subseteq A\) таке, що\(h(U) = U\). Звідси\(U = A \setminus g[B \setminus f(U)]\) і тому\(A \setminus U = g[B \setminus f(U)]\). Тепер визначте\(F: A \to B\),\(F(x) = f(x)\) якщо\(x \in U\) і\(F(x) = g^{-1}(x)\) якщо\(x \in A \setminus U\).

\( f \)карти\( U \) один до одного на\( f(U) \);\( g \) карти\( B \setminus f(U) \) один до одного на\( A \setminus U \)

Далі ми покажемо, що\( F \) є один-на-один. Припустимо, що\( x_1, \, x_2 \in A \) і\( F(x_1) = F(x_2) \). Якщо\( x_1, \, x_2 \in U \) тоді\( f(x_1) = f(x_2) \) так,\( x_1 = x_2 \)\( f \) так як один до одного. Якщо\( x_1, \, x_2 \in A \setminus U \) тоді\( g^{-1}(x_1) = g^{-1}(x_2) \) так,\( x_1 = x_2 \)\( g^{-1} \) так як один до одного. Якщо\( x_1 \in U \) і\( x_2 \in A \setminus U \). Тоді\( F(x_1) = f(x_1) \in f(U) \) поки\( F(x_2) = g^{-1}(x_2) \in B \setminus f(U) \), так\( F(x_1) = F(x_2) \) не можна.

Нарешті ми покажемо, що\( F \) знаходиться на. Нехай\( y \in B \). Якщо\( y \in f(U) \) то\( y = f(x) \) для деяких\( x \in U \) так\( F(x) = y \). Якщо\( y \in B \setminus f(U) \) тоді\( x = g(y) \in A \setminus U \) так\( F(x) = g^{-1}(x) = y \).

Ми напишемо\(A \prec B\) якщо\(A \preceq B\)\(A \not \approx B\), але, Тобто існує функція один до одного з\(A\) в\(B\), але там не існує функція від\(A\) onto\(B\). Зверніть увагу,\(\prec\) що це матиме своє звичайне значення, якщо застосовується до класів еквівалентності. Тобто,\([A] \prec [B]\) якщо і тільки якщо\([A] \preceq [B]\) але\([A] \ne [B]\). Інтуїтивно, звичайно,\(A \prec B\) означає,\(B\) що строго більше\(A\), ніж, в сенсі кардинальності.

\(A \prec B\)в кожному з наступних випадків:

1. \(A\)і\(B\) є кінцевими і\(\#(A) \lt \#(B)\).
2. \(A\)є кінцевим і незліченно\(B\) нескінченним.
3. \(A\)є незліченно\(B\) нескінченним і незліченним.

Закриваємо нашу дискусію спостереженням, що для будь-якого набору завжди є більший набір.

Якщо\(S\) це набір, то\(S \prec \mathscr{P}(S)\).

Доказ

По-перше, це тривіально, щоб\(S\) зіставити один до одного в\(\mathscr{P}(S)\); просто карта\(x\) до\(\{x\}\). Припустимо, тепер, що\(f\) карти\(S\) на\(\mathscr{P}(S)\) і нехай\(R = \{x \in S: x \notin f(x)\}\). Оскільки\(f\) є на, існує\(t \in S\) таке, що\(f(t) = R\). Зверніть увагу, що\(t \in f(t)\) якщо і тільки якщо\(t \notin f(t)\).

Доказ того, що набір не може бути відображений на його потужності, схожий на парадокс Рассела, названий на честь Бертрана Рассела.

Гіпотеза континууму - це твердження про те, що немає безлічі, чия кардинальність знаходиться строго між\(\N\) і\(\R\). Гіпотеза континууму фактично починалася як континуумна гіпотеза, поки не було показано, що вона відповідає звичайним аксіомам реальної системи числення (Курт Гедель у 1940 році) та незалежна від цих аксіом (Пол Коен у 1963 році).

Припускаючи гіпотезу континууму, якщо\( S \) є незліченним, то існує\( A \subseteq S \) таке, що\( A \) і\( A^c \) є незліченними.

Доказ

За гіпотезою континууму,\( S \) якщо незліченна тоді\( [0, 1) \preceq S \). Звідси існує функція один-на-один\( f: [0, 1) \to S \). Нехай\( A = f\left[0, \frac{1}{2}\right) \). Тоді\( A \) незліченна, а з тих пір\( f\left[\frac{1}{2}, 1\right) \subseteq A^c \)\( A^c \), незліченна.

Є більш складне доказ останнього результату, без гіпотези континууму і просто використовуючи аксіому вибору.