4.9: Набори різних розмірів та теорема Кантора

Template:MathJaxZach

Ми запропонували точне твердження ідеї, що два набори мають однаковий розмір. Ми також можемо запропонувати точне твердження ідеї про те, що один набір менше іншого. Наше визначення «менше (або рівноцінне)» зажадає замість біекції між множинами ін'єкції від першого набору до другого. Якщо така функція існує, розмір першого множини менше або дорівнює розміру другого. Інтуїтивно, ін'єкція з одного набору в інший гарантує, що діапазон функції має як мінімум стільки елементів, скільки домен, оскільки жодні два елементи домену не відображаються на один і той же елемент діапазону.

Визначення\(\PageIndex{1}\)

\(A\)не більше\(B\), ніж\(\cardle{A}{B}\), написано, якщо є укол\(f \colon A \to B\).

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

Визначення\(\PageIndex{2}\)

\(A\)менше\(B\), ніж, написано\(\cardless{A}{B}\), якщо є ін'єкція,\(f\colon A \to B\) але немає біекції\(g\colon A \to B\), т\(\cardneq{A}{B}\).\(\cardle{A}{B}\) Е.

Зрозуміло, що це відношення є антирефлексивним і перехідним. (Це залишається як вправа.) Використовуючи це позначення, ми можемо сказати, що\(A\) множина є перелічуваною iff\(\cardle{A}{\Nat}\), і\(A\) що не перелічується iff\(\cardless{\Nat}{A}\). Це дозволяє нам відновити теорему 4.6.2 як спостереження, що\(\cardless{\Nat}{\Pow{\Nat}}\). Насправді Кантор (1892) довів, що цей останній пункт абсолютно загальний:

Теорема\(\PageIndex{1}\) (Cantor)

\(\cardless{A}{\Pow{A}}\), для будь-якого набору\(A\).

Доказ. Карта\(f(x) = \{x\}\) - це ін'єкція\(f \colon A \to \Pow{A}\), так як якщо\(x \neq y\), то ще й\(\{x\} \neq \{y\}\) по розширеності, і так\(f(x) \neq f(y)\). Таким чином, ми маємо це\(\cardle{A}{\Pow{A}}\).

Ми показуємо, що не може бути суб'єктивної функції\(g\colon A \to \Pow{A}\), let alone a bijective one, and hence that \(\cardneq{A}{\Pow{A}}\). For suppose that \(g\colon A \to \Pow{A}\). Since \(g\) is total, every \(x \in A\) is mapped to a subset \(g(x) \subseteq A\). We show that \(g\) cannot be surjective. To do this, we define a subset \(\overline{A} \subseteq A\) which by definition cannot be in the range of \(g\). Let \[\overline{A} = \Setabs{x \in A}{x \notin g(x)}.\nonumber\] Since \(g(x)\) is defined for all \(x \in A\), \(\overline{A}\) is clearly a well-defined subset of \(A\). But, it cannot be in the range of \(g\). Let \(x \in A\) be arbitrary, we show that \(\overline{A} \neq g(x)\). If \(x \in g(x)\), then it does not satisfy \(x \notin g(x)\), and so by the definition of \(\overline{A}\), we have \(x \notin \overline{A}\). If \(x \in \overline{A}\), it must satisfy the defining property of \(\overline{A}\), i.e., \(x \in A\) and \(x \notin g(x)\). Since \(x\) was arbitrary, this shows that for each \(x \in \overline{A}\), \(x \in g(x)\) iff \(x \notin \overline{A}\), and so \(g(x) \neq \overline{A}\). In other words, \(\overline{A}\) cannot be in the range of \(g\), contradicting the assumption that \(g\) is surjective. ◻

Повчально порівнювати доказ теореми\(\PageIndex{1}\) з теоремою 4.6.2. Там ми показали, що для будь-якого списку\(Z_1\), \(Z_2\), …, of subsets of \(\PosInt\) one can construct a set \(\overline{Z}\) of numbers guaranteed not to be on the list. It was guaranteed not to be on the list because, for every \(n \in \PosInt\), \(n \in Z_n\) iff \(n \notin \overline{Z}\). This way, there is always some number that is an element of one of \(Z_n\) or \(\overline{Z}\) but not the other. We follow the same idea here, except the indices \(n\) are now elements of \(A\) instead of \(\PosInt\). The set \(\overline{B}\) is defined so that it is different from \(g(x)\) for each \(x \in A\), because \(x \in g(x)\) iff \(x \notin \overline{B}\). Again, there is always an element of \(A\) which is an element of one of \(g(x)\) and \(\overline{B}\) but not the other. And just as \(\overline{Z}\) therefore cannot be on the list \(Z_1\), \(Z_2\), …, \(\overline{B}\) cannot be in the range of \(g\).

Доказ також варто порівняти з доказом Парадоксу Рассела, теорема 1.6.1. Дійсно, теорема Кантора була натхненням для власного парадоксу Рассела.

Проблема\(\PageIndex{1}\)

Показати, що не може бути ін'єкції\(g\colon \Pow{A} \to A\), для будь-якого набору\(A\). Підказка: Припустимо\(g\colon \Pow{A} \to A\), є ін'єкційним. Розглянемо\(D = \Setabs{g(B)}{B \subseteq A \text{ and } g(B) \notin B}\). Нехай\(x = g(D)\). Використовуйте той факт, що\(g\) є ін'єкційним, щоб вивести протиріччя.