Теорема Кантора – Бернштейна

[GlobalMiwka]

Здравствуйте!

Пусть $A$ равномощно подмножеству $B_1$ множества $B$, а $B$ равномощно подмножеству $A_1$ множества $A$. При взаимно однозначном соответствии между $B$ и $A_1$ подмножество $B_1 \subset B$ переходит в некоторое подмножество $A_2\subset A_1$. При этом все три множества $A$, $B_1$ и $A_2$ равномощны, — и нужно доказать, что они равномощны множеству $B$, или, что то же самое, $A_1$.

Пусть $f$ — функция, осуществляющая взаимно однозначное соответствие $A_0\mapsto A_2$ (элемент $x\in A_0$ соответствует элементу $f(x)\in A_2$). Когда $A_0$ переходит в $A_2$, меньшее множество $A_1$ переходит в какое-то множество $A_3\subset A_2$. Аналогичным образом само $A_2$ переходит в некоторое множество $A_4\subset A_2$. При этом $A_4\subset A_3$, так как $A_1\subset A_2$. Продолжая эту конструкцию, мы получаем убывающую последовательность множеств $A_0\supset A_1\supset A_2\supset A_3 ...$ и взаимно однозначное соответствие $f\colon A_0\mapsto A_2$, при котором $A_i$ соответствует $A_{i + 2}$. Формально можно описать $A_{2n}$ как множество тех элементов, которые получаются из какого-то элемента множества $A_0$ после $n$-кратного применения функции $f$. Аналогичным образом $A_{2n+1}$ состоит из тех и только тех элементов, которые получаются из какого-то элемента множества $A_1$ после $n$-кратного применения функции $f$. Заметим, что пересечение всех множеств $A_i$ вполне может быть непусто: оно состоит из тех элементов, у которых можно сколько угодно раз брать $f$-прообраз. Теперь можно сказать так: множество $A_0$ мы разбили на непересекающиеся слои $C_i=A_i\setminus A_i+1$ и на сердцевину $C=\bigcap_i A_i$.

Часть доказательства до места, где мне становится непонятно, а именно последние 2 предложения:
1) "можно сколько угодно раз брать $f$-прообраз". Что во что отображается ?
2) $C=\bigcap_i A_i$, не ясно как можно его получить, если $A_i$ не кончаются ?

[mihaild]

1. Не очень понимаю, в чем вопрос. Мы взяли какой-то элемент $x$ и смотрим все его прообразы. Потом прообразы прообразов. И т.д. Возможно, что на очередном шаге мы получим пустое множество (и дальше будет только оно). Возможно что на каждом шаге множество будет непустым - тогда у $x$ можно брать $f$-прообраз сколько угодно раз.
2. Что значит "как получить"? Пересечение бесконечного семейства множеств определяется так же как и конечного: элемент принадлежит пересечению тогда и только тогда, когда он принадлежит всем множествам семейства.

Попробуйте взять какой-нибудь конкретный пример. Например множество целых чисел, и отображение $f(n) = n^2$. Какими будут $A_2$, $A_4$ и т.д.? Каким получится $C$?

[GlobalMiwka]

Я не могу вычислить $C$ для вашего примера, так как элементы упорядочены, то можно ассоциировать множества $A_i$ c наименьшим элементом этого множества, но так как процесс бесконечен не ясно какой элемента в $C$ содержиться, какой бы я не выбрал, найдется подмножество, которое не начинается с этого наименьшего элемента множества $A_i$.

[Connector]

(Оффтоп)

Не знаю, по какой именно книге Вы изучаете вопрос, но неплохое объяснение (с диаграммой для наглядности) есть у Лузина, с. 37 и последующие. Может быть, что-то станет яснее.

[mihaild]

GlobalMiwka в сообщении #1422674 писал(а):

то можно ассоциировать множества $A_i$ c наименьшим элементом этого множества

Вообще непонятно, что это значит. Зачем множества ассоциировать с какими-то элементами?
Если $C$ не получается - можете хотя бы $A_0$, $A_2$, $A_4$ явно выписать?

[GlobalMiwka]

Connector у Лузина, оно обозначается $D$, но как его вычислить он не объясняет.

mihaild допустим, наше множество $A_0$ начинается с 1 и до бесконечности, тогда $A_n=\left\{ f_n(f_{n-1}(...f_1(x)...)),\forall x\in A_0\right\}$, тогда наименьший элемент множества $A_n$ начинается $2^{2n}$, но в $C$ он не содержится потому, что всегда есть множество $A_{n+1}$, которое начинается с $2^{2n+1}$, т.е. я не могу определить ни один элемент множества $C$.

Кстати, пусть $A_0$ состоит из всех квадратов $n$.

Я так понимаю, что $C$ постулируется, потому что технически его вычислить нельзя.

[mihaild]

Вы кажется совсем запутались. По какому источнику учите теорию множеств?

GlobalMiwka в сообщении #1422678 писал(а):

допустим, наше множество $A_0$ начинается с 2 и до бесконечности

$A_0$ в этом рассуждении - это то же, что и $A$, никакого произвола в его выборе нет.

GlobalMiwka в сообщении #1422678 писал(а):

тогда $A_n=\left\{ f_n(f_{n-1}(...f_1(x)...)),\forall x\in A_0\right\}$,

Так не пишут. И никаких $f_1, f_2, \ldots, f_n$ нет - у нас только одно отображение $f$. Правильно так: $A_n = \{f(f(\ldots(f(x)))) | x \in A\}$.

GlobalMiwka в сообщении #1422678 писал(а):

тогда наименьший элемент множества $A_n$

Зачем вам тут вообще порядок? Нам интересны только элементы.

GlobalMiwka в сообщении #1422678 писал(а):

Я так понимаю, что $C$ постулируется, потому что технически его вычислить нельзя.

Непонятно, что это вообще значит, но понимаете почти наверняка неправильно. Никакая вычислимость тут вообще не важна, а существование пересечения бесконечного семейства множеств выводится из аксиом (но вам пока это не нужно).

Рассмотрим $A = \mathbb{Z}$, и $f: \mathbb{Z} \to \mahbb{Z}$, $f(n) = n^2$. Найдите $A_2$.
Если непонятно, как его выписать, то проверьте, какие из чисел от $-10$ до $10$ принадлежат $A_2$, а какие нет.

[arseniiv]

Хотел найти для ТС более удобную иллюстрацию, где множества изображены овалами и прямоугольниками и закраской областей — вроде на форуме была когда-то — и не нашёл пока.

[GlobalMiwka]

Вы и ответили на мой вопрос тем, что сказали, существование определяется аксиомой, т.е. возможно, что ни один элемент этого множества возможно нельзя определить. Вроде, говорят, что множество определяется своими элементами, а если эти элементы никак нельзя найти, кроме утверждения, что они есть, существует ли такое множество на самом деле?

[arseniiv]

GlobalMiwka
Неформальный язык смешивает некоторые вещи. Одно дело, можем ли мы записать на языке теории множеств предикат, не включающий в себя определяемое множество; второе дело, существует ли доказательство из аксиом теории множеств, что существует множество ровно тех элементов, которые удовлетворяют данному предикату — но совсем третье, можем ли мы определить какие-то другие вещи, пусть и связанные с элементами этого множества. А то вот мы не можем назвать все вещественные числа по именам — ну и что?

-- Вс окт 27, 2019 23:29:19 --

GlobalMiwka в сообщении #1422688 писал(а):

говорят, что множество определяется своими элементами

Точнее здесь говорить, что множество определяется предикатом принадлежности ему элемента. Видно, что нам не надо что-то делать с каждым элементом в индивидуальном порядке.

[Someone]

GlobalMiwka в сообщении #1422688 писал(а):

сказали, существование определяется аксиомой

Неправда, сказано было другое.
И было сказано, что Вам это не нужно. И оно Вам действительно не нужно на данном этапе (а если потребуется — существование пересечения в формальной теории ZFC доказывается "в одну строчку" ссылкой на аксиому выделения).

Чтобы определить, какие элементы принадлежат пересечению, нужно только определение пересечения. "Вычислять" здесь ничего не нужно, тем более, что для вычисления требуется какая-то информация об отображении $f$, а в доказательстве это просто "произвольно взятое взаимно однозначное отображение одного множества на другое, о котором ничего не известно".

[GlobalMiwka]

Для меня это как-то запутанно. Хорошо, эти сложности оставлю. Спасибо.