2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Доказать неравномощность множеств.
Сообщение03.02.2011, 22:29 
Заслуженный участник


04/05/09
4582
Dialectic в сообщении #408752 писал(а):
Не вижу связи. Как именно она доказывается диагональю Кантора?
Сначала можно построить бинарное представление множества сечений. Ну и дальше как обычно.

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение03.02.2011, 22:29 
Заслуженный участник


11/05/08
32166
Dialectic в сообщении #408750 писал(а):
Почему он сейчас неосмысленен?

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

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

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение03.02.2011, 22:32 


27/08/06
579
venco в сообщении #408755 писал(а):
Dialectic в сообщении #408752 писал(а):
Не вижу связи. Как именно она доказывается диагональю Кантора?
Сначала можно построить бинарное представление множества сечений.

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

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение03.02.2011, 22:34 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Dialectic в сообщении #408752 писал(а):
Уважаемый Xaositect - помогите пожалуйста это доказать.
Берете, вводите на этом множестве структуру поля, доказываете представление в виде бесконечной последовательности двоичных цифр и используете диагональ Кантора.

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение03.02.2011, 22:36 


27/08/06
579
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 как должно пониматься тут слово "бесконечность"? Как нечто реально завершенное? Или как нечто возрастающее? Или ещё как-то?

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение03.02.2011, 23:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение03.02.2011, 23:22 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Dialectic в сообщении #408763 писал(а):
Кстати Xaositect как должно пониматься тут слово "бесконечность"? Как нечто реально завершенное? Или как нечто возрастающее? Или ещё как-то?
У venco все правильно написано.

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение03.02.2011, 23:49 


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

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение04.02.2011, 02:25 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
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$.
Надеюсь, от меня не потребуется выписывать здесь эту проверку.

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение04.02.2011, 14:59 
Заслуженный участник


13/12/05
4518
ewert в сообщении #408757 писал(а):
Dialectic в сообщении #408750 писал(а):
Почему он сейчас неосмысленен?

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

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

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение04.02.2011, 19:01 


27/08/06
579
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$?

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение04.02.2011, 20:22 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение04.02.2011, 20:48 
Заслуженный участник


11/05/08
32166
venco в сообщении #408789 писал(а):
принадлежащее меньшему подмножеству сечения. Получаем последовательность двоичных строк увеличивающейся длины, так что каждая следующая строка отличается от предыдущей добавлением одной двоичной цифры. Всё.Двум различным сечениям будут соответствовать различные бинарные последовательности, и наоборот.

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

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

 Профиль  
                  
 
 Re: Доказать неравномощность множеств.
Сообщение04.02.2011, 21:05 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group