Доказать неравномощность множеств (Q и сечения Q)

[venco]

Dialectic в сообщении #408752 писал(а):

Не вижу связи. Как именно она доказывается диагональю Кантора?

Сначала можно построить бинарное представление множества сечений. Ну и дальше как обычно.

[ewert]

Dialectic в сообщении #408750 писал(а):

Почему он сейчас неосмысленен?

Потому, что он попросту бессмысленен. Вы не дали никакого другого альтернативного определения тех чисел, кроме сечений. И потом спрашиваете: а почему, собственно, сечения -- не сечения, ну или почему не сечения -- это сечения. Согласитесь, это вполне бессмысленно.

Кантор тут, кстати, совершенно не при чём. Тут проблема гораздо тривиальнее.

[Dialectic]

venco в сообщении #408755 писал(а):

Dialectic в сообщении #408752 писал(а):

Не вижу связи. Как именно она доказывается диагональю Кантора?

Сначала можно построить бинарное представление множества сечений.

Хм... Как же это сделать?

[Xaositect]

Dialectic в сообщении #408752 писал(а):

Уважаемый Xaositect - помогите пожалуйста это доказать.

Берете, вводите на этом множестве структуру поля, доказываете представление в виде бесконечной последовательности двоичных цифр и используете диагональ Кантора.

[Dialectic]

ewert в сообщении #408757 писал(а):

Dialectic в сообщении #408750 писал(а):

Почему он сейчас неосмысленен?

Потому, что он попросту бессмысленен.
Вы не дали никакого другого альтернативного определения тех чисел, кроме сечений.

Каких "тех"? Мы говорим - только о множестве рациональных чисел и о множестве всех сечений. Никаких "тех" у нас пока нет.

ewert в сообщении #408757 писал(а):

Кантор тут, кстати, совершенно не при чём. Тут проблема гораздо тривиальнее.

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

-- Чт фев 03, 2011 23:37:47 --

Xaositect в сообщении #408759 писал(а):

Dialectic в сообщении #408752 писал(а):

Уважаемый Xaositect - помогите пожалуйста это доказать.

Берете, вводите на этом множестве структуру поля, доказываете представление в виде бесконечной последовательности двоичных цифр и используете диагональ Кантора.

Все понял, кроме того, как доказать "представление в виде бесконечной последовательности двоичных цифр".

-- Чт фев 03, 2011 23:41:00 --

Xaositect в сообщении #408759 писал(а):

Dialectic в сообщении #408752 писал(а):

Уважаемый Xaositect - помогите пожалуйста это доказать.

Берете, вводите на этом множестве структуру поля, доказываете представление в виде бесконечной последовательности двоичных цифр и используете диагональ Кантора.

Кстати Xaositect как должно пониматься тут слово "бесконечность"? Как нечто реально завершенное? Или как нечто возрастающее? Или ещё как-то?

[venco]

Dialectic в сообщении #408763 писал(а):

Все понял, кроме того, как доказать "представление в виде бесконечной последовательности двоичных цифр".

Для простоты рассмотрим только сечения из $(0,1)$, т.е. в меньшей половине есть число $>0$, а в большей есть число $<1$.
Теперь для каждой длины $n$ находим максимальное двоичное число с $n$ цифрами после запятой (они все рациональные) принадлежащее меньшему подмножеству сечения. Получаем последовательность двоичных строк увеличивающейся длины, так что каждая следующая строка отличается от предыдущей добавлением одной двоичной цифры. Всё.
Двум различным сечениям будут соответствовать различные бинарные последовательности, и наоборот.

[Xaositect]

Dialectic в сообщении #408763 писал(а):

Кстати Xaositect как должно пониматься тут слово "бесконечность"? Как нечто реально завершенное? Или как нечто возрастающее? Или ещё как-то?

У venco все правильно написано.

[Gortaur]

Dialectic
Прошу прощения, что не отвечал - Вам тут понаписали + я думал, что каждый такой класс можно соотнести с бесконечной последовательностью - например, десятичной записью числа (или бинарной, как Вам посоветовали). А отсюда уже известный факт, это будет множество действительных чисел.

[Someone]

Dialectic, я правильно понимаю, что нужно доказать несчётность множества сечений в множестве рациональных чисел, не апеллируя к действительным числам, а пользуясь только свойствами множества рациональных чисел и определением сечения?
Важными являются следующие свойства множества рациональных чисел $\mathbb Q$: оно
1) счётно,
2) линейно упорядочено;
3) не имеет наименьшего и наибольшего элементов;
4) плотно, то есть, между любыми двумя различными рациональными числами можно найти рациональное число, которое больше одного и меньше другого.
На самом деле эти четыре свойства однозначно характеризуют множество рациональных чисел среди всех линейно упорядоченных множеств: любое счётное плотное линейно упорядоченное множество без первого и последнего элементов подобно множеству рациональных чисел.

Сечение в множестве $\mathbb Q$ - это упорядоченная пара множеств $(A,B)$, удовлетворяющих следующим условиям:
1) $A\neq\varnothing$, $B\neq\varnothing$;
2) $A\cup B=\mathbb Q$;
3) для любых $a\in A$ и $b\in B$ выполняется неравенство $a<b$.
Сечение $(A,B)$ назовём рациональным, если либо в множестве $A$ есть наибольший элемент, либо в множестве $B$ есть наименьший элемент.
Заметим, что не может случиться так, чтобы одновременно множество $A$ имело наибольший элемент $a$, а множество $B$ - наименьший элемент $b$: тогда обязательно $a<b$, но тогда в силу плотности множества $\mathbb Q$ найдётся элемент $c\in\mathbb Q$, удовлетворяющий условию $a<c<b$, а это противоречит условию $A\cup B=\mathbb Q$.
Каждому рациональному сечению $(A,B)$ соответствует рациональное число - то самое, которое является наименьшим в $B$ или наибольшим в $A$; наоборот, каждому рациональному числу соответствуют два рациональных сечения $(A,B)$, для которых именно это число является наименьшим в $B$ или наибольшим в $A$ (при построении множества действительных чисел удобно из этих двух сечений оставить только одно, но для нас это несущественно).
Поэтому множество всех рациональных сечений счётно.
Сечение $(A,B)$ называется щелью, если в множестве $A$ нет наибольшего элемента, а в множестве $B$ нет наименьшего.

Наша цель - доказать, что множество щелей в множестве $\mathbb Q$ несчётно.
Пусть имеется некоторая последовательность сечений $\{(A_n,B_n):n\in\mathbb N\}$ ($\mathbb N=\{1,2,3,\ldots\}$ - натуральный ряд). Нужно построить сечение $(A,B)$, не совпадающее ни с одним из элементов этой последовательности.
Будем предполагать, что заданная последовательность содержит все рациональные сечения.

Для начала построения положим $a_0=0$, $b_0=1$.
Построим последовательность упорядоченных пар рациональных чисел $\{(a_n,b_n):n\in\mathbb N\}$, удовлетворяющую следующим условиям для каждого $n\in\mathbb N$:
1) $a_{n-1}\leqslant a_n<b_n\leqslant b_{n-1}$ ($a_0$ и $b_0$ уже определены);
2) либо $a_n\in B_n$, либо $b_n\in A_n$.
Предположим, что для некоторого $n\in\mathbb N$ требуемые пары $(a_k,b_k)$ уже построены для всех натуральных $k<n$. Построим $(a_n,b_n)$.
Рассмотрим возможные случаи.
a) $(A_n,B_n)$ - щель.
Если $b_{n-1}\in A_n$ или $a_{n-1}\in B_n$, то положим $a_n=a_{n-1}$, $b_n=b_{n-1}$.
Если $a_{n-1}\in A_n$ и $b_{n-1}\in B_n$, то положим $a_n=a_{n-1}$; так как в множестве $A_n$ нет наибольшего элемента, найдётся такое $b_n\in A_n$, что $b_n>a_n$ (можно, напротив, положить $b_n=b_{n-1}$; так как в множестве $B_n$ нет наименьшего элемента, найдётся такое $a_n\in B_n$, что $a_n<b_n$).
б) $(A_n,B_n)$ - рациональное сечение; пусть $c_n$ - рациональное число, которое является наименьшим в $B_n$ или наибольшим в $A_n$.
Если $c_n\leqslant a_{n-1}$, то положим $b_n=b_{n-1}$, $a_n=\frac 12(a_{n-1}+b_{n-1})$.
Если $c_n\geqslant b_{n-1}$, то положим $a_n=a_{n-1}$, $b_n=\frac 12(a_{n-1}+b_{n-1})$.
Если $a_{n-1}<c_n<b_{n-1}$, то положим $a_n=a_{n-1}$, $b_n=\frac 12(a_n+c_n)$ (можно, напротив, положить $b_n=b_{n-1}$, $a_n=\frac 12(b_n+c_n)$).
Выполнение условий 1) и 2) во всех случаях проверяется тривиально, и можно продолжать построение дальше.

Определим множества
$A=\{x\in\mathbb Q:\text{ существует такое }n\in\mathbb N\text{, что }a_n\geqslant x\}$ и
$B=\{x\in\mathbb Q:\text{ существует такое }n\in\mathbb N\text{, что }b_n\leqslant x\}$.
Из этих определений следует, что для всех $n\in\mathbb N$ выполняются условия $a_n\in A$ и $b_n\in B$.

Собственно говоря, $(A,B)$ - требуемое сечение. Но для завершения доказательства требуется ещё некоторая возня. Конкретно, нужно проверить, что
А) $(A,B)$ - сечение в множестве $\mathbb Q$, то есть, выполняются условия 1), 2) и 3) определения сечения;
Б) это сечение не совпадает ни с одним из сечений заданной последовательности.
Для доказательства достаточно использовать условия 1) и 2), сформулированные при построении, и свойство, сформулированное сразу после определения множеств $A$ и $B$.
Надеюсь, от меня не потребуется выписывать здесь эту проверку.

[Padawan]

ewert в сообщении #408757 писал(а):

Dialectic в сообщении #408750 писал(а):

Почему он сейчас неосмысленен?

Потому, что он попросту бессмысленен.

Вопрос корректно был сформулирован. Вы просто сознательно пытаетесь этого не увидеть.

[Dialectic]

Someone в сообщении #408836 писал(а):

Dialectic, я правильно понимаю, что нужно доказать несчётность множества сечений в множестве рациональных чисел, не апеллируя к действительным числам, а пользуясь только свойствами множества рациональных чисел и определением сечения?

Совершенно правильно.

Someone в сообщении #408836 писал(а):

Для начала построения положим $a_0=0$, $b_0=1$.
Построим последовательность упорядоченных пар рациональных чисел $\{(a_n,b_n):n\in\mathbb N\}$, удовлетворяющую следующим условиям для каждого $n\in\mathbb N$:
1) $a_{n-1}\leqslant a_n<b_n\leqslant b_{n-1}$ ($a_0$ и $b_0$ уже определены);
2) либо $a_n\in B_n$, либо $b_n\in A_n$.

Someone, я так понимаю, что оба эти условия совместны только тогда, когда $a_n$ и $b_n$ - принадлежат к одному и тому же множеству $a_n, b_n\in B_n$, либо $a_n,b_n\in A_n$?

[Someone]

Разумеется. Эти условия для того и задумывались. А потом, определив указанным способом сечение $(A,B)$, мы придём к выводу, что $(A,B)\neq(A_n,B_n)$, так как $a_n\in A$, а $b_n\in B$.

[ewert]

venco в сообщении #408789 писал(а):

принадлежащее меньшему подмножеству сечения. Получаем последовательность двоичных строк увеличивающейся длины, так что каждая следующая строка отличается от предыдущей добавлением одной двоичной цифры. Всё.Двум различным сечениям будут соответствовать различные бинарные последовательности, и наоборот.

В принципе да, только не совсем так быстро. Во-первых, надо всё-таки зафиксировать, к какому конкретно из классов будет принадлежать рациональная граница сечения, если она рациональна (в данном случае естественнее, если к нижнему). Во-вторых, с биективностью придётся хоть немножко, но повозиться: надо будет ещё доказать, что при этом дробь не может заканчиваться на цепочкой единиц или наоборот, не может заканчиваться цепочкой нулей (в зависимости от вышеупомянутого выбора).

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

[Padawan]

Можно брать вместо сумм вида $\sum\frac{\chi(n)}{2^n}$ $(\chi(n)=0,1)$ суммы $\sum\frac{\chi(n)}{3^n}$. Получится инъекция $2^{\mathbb N}$ во множество сечений.