2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Доказательство попарной равносильности условий на множество
Сообщение28.12.2017, 01:07 


11/12/16
403
сБп
Прошу проверить, плиз.
Упражнение (принцип Дирихле). Показать, что следующие три условия на множество $X$ попарно равносильны друг другу:
1) $X$ бесконечно;
2) существует инъекция $X \hookrightarrow X$, не являющееся сюръекцией;
3) существует сюръекция $X \twoheadrightarrow X$, не являющееся инъекцией.

Доказательство. Пусть справедливо (1). Выберем в $X$ счетное подмножество $Y$. Тогда $\left\lvert X \right\rvert > \left\lvert Y \right\rvert$ и множество $X$ содержит хотя бы один элемент, который не принадлежит $Y$. Очевидно, что можно установить отображение $X \to Y$, такое что в $Y$ найдутся два различных элемента, образы которых отличаются (принцип Дирихле). Такое отображение является сюръекцией и не является инъекцией (по определению). (1) $\Rightarrow$ (3) доказано.
Теперь пусть выполняется (3). Тогда существует $X \setminus Y$, в котором содержится хотя бы один элемент и $X = Y \cup (X \setminus Y)$, т.е. $\left\lvert X \right\rvert > \left\lvert Y \right\rvert$. Очевидно, что можно задать такое отображение, в котором каждому элементу $Y$ будет сопоставляться не более одного элемента $X$. Такое отображение является инъекцией. (3) $\Rightarrow$ (2) доказано.
Теперь пусть справедливо (2). Предположим, что $X$ конечное множество. Тогда существует элемент с номером $n$, такой что существует биекция $X \sim \left\lbrace1, 2, ..., n\right\rbrace$, что противоречит посылке. Следовательно множество $X$ бесконечное (2) $\Rightarrow$ (1) доказано.

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


23/07/05
17975
Москва
gogoshik в сообщении #1279328 писал(а):
Выберем в $X$ счетное подмножество $X$.
Вероятно, $Y$?
gogoshik в сообщении #1279328 писал(а):
Тогда $\left\lvert X \right\rvert > \left\lvert Y \right\rvert$
Это с какой стати? По определению получается только $\lvert X\rvert\geqslant\lvert Y\rvert$.
gogoshik в сообщении #1279328 писал(а):
и множество $X$ содержит хотя бы один элемент, который не принадлежит $Y$.
Вообще-то, это Вы должны доказать. Из того, что $Y$ — подмножество $X$, это не следует. Правда, мне бы это не потребовалось.
gogoshik в сообщении #1279328 писал(а):
Очевидно, что можно установить отображение
Слово "очевидно" — не доказательство. Предъявите отображение явно.

Пока хватит.

 Профиль  
                  
 
 Re: Доказательство попарной равносильности условий на множество
Сообщение28.12.2017, 01:27 


11/12/16
403
сБп
Думаю, что это доказательство должно быть элементарное, так как находится в начале учебника для первокурсников. На каждое условие, два-три предложения. Так как я только недавно начал учиться доказывать такие вещи, испытываю закомплексованность.

-- 28.12.2017, 01:29 --

Someone в сообщении #1279336 писал(а):
Вероятно, $Y$?
Это исправил. Да. Спасибо.

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


23/07/05
17975
Москва
gogoshik в сообщении #1279338 писал(а):
Думаю, что это доказательство должно быть элементарное
Разумеется, оно совершенно элементарное. Для первокурсника вполне доступное.

 Профиль  
                  
 
 Re: Доказательство попарной равносильности условий на множество
Сообщение28.12.2017, 10:25 


11/12/16
403
сБп
Пусть справедливо (1). Выберем в $X$ счетное подмножество $Y$. Запишем все элементы $Y$ в виде последовательности: $\left\lbrace x_1, x_2, ..., x_n\right\rbrace$. Так как $X$ бесконечно, то в $X$ существует элемент $x_{n+1}$. Запишем элементы $X$ в виде последовательности: $\left\lbrace x_1, x_2, ..., x_n, x_{n+1}\right\rbrace$.
Такое рассуждение верно?

 Профиль  
                  
 
 Re: Доказательство попарной равносильности условий на множество
Сообщение28.12.2017, 10:51 
Аватара пользователя


14/12/17
1510
деревня Инет-Кельмында
Если это было рассуждение, то какой у него вывод?

2) утверждает, что существует отображение $X \rightarrow X$ с такими-то свойствами.
Чтобы доказать что оно существует при условии 1), можно придумать его пример при условии 1),
и потом показать, что у него действительно будут эти свойства.

Например,

Пусть справедливо (1). Выберем в $X$ счетное подмножество $Y$. Запишем все элементы $Y$ в виде последовательности: $\left\lbrace x_1, x_2, ..., x_n, ...\right\rbrace$.
X разбивается на два подмножества, $Y$ (счетное) и $X\textbackslash Y$ (какое-то, может быть пустое).
Отображение $f: X \rightarrow X$ зададим так:...


Это было бы рассуждением для $1 \Rightarrow 2$. Верным или неверным.

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


23/07/05
17975
Москва
gogoshik в сообщении #1279388 писал(а):
Выберем в $X$ счетное подмножество $Y$. Запишем все элементы $Y$ в виде последовательности: $\left\lbrace x_1, x_2, ..., x_n\right\rbrace$.
Фобос и Деймос! Сколько же элементов в счётном множестве? Другими словами, чему у Вас равно $n$? $10$? Или $100$? Или, о ужас, целая $1000$?

 Профиль  
                  
 
 Re: Доказательство попарной равносильности условий на множество
Сообщение28.12.2017, 12:20 


11/12/16
403
сБп
Я ошибся. Ничему не равно, иначе множество было бы конечным. Запишем все элементы $Y$ в виде последовательности: $\left\lbrace x_1, x_2, ..., x_n, ...\right\rbrace$.

-- 28.12.2017, 13:09 --

eugensk в сообщении #1279396 писал(а):
Отображение $f: X \rightarrow X$ зададим так:...

Спасибо. Отображение $f: X \rightarrow X $ зададим так: $x_n \mapsto x_{n+1}$. Это инъекция, но не сюръекция.

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


16/07/14
9089
Цюрих
gogoshik в сообщении #1279431 писал(а):
Отображение $f: X \rightarrow X $ зададим так: $x_n \mapsto x_{n+1}$.
$x_n$ - это только элементы $Y$, в $X$ может быть еще что-то, куда $f$ отправляет $X \setminus Y$?

 Профиль  
                  
 
 Re: Доказательство попарной равносильности условий на множество
Сообщение28.12.2017, 18:22 


11/12/16
403
сБп
mihaild, я Вас плохо понимаю. Вы спрашиваете, "куда $f$ отправляет $X \setminus Y$" или "в $X$ может быть еще что-то, куда $f$ отправляет $X \setminus Y$?

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


16/07/14
9089
Цюрих
gogoshik, не очень понимаю, в чем разница.
Утверждение: $X \setminus Y$ может быть непусто.
Следствие: определив отображение только на $Y$, вы не определили отображение на $X$.

 Профиль  
                  
 
 Re: Доказательство попарной равносильности условий на множество
Сообщение28.12.2017, 23:44 


11/12/16
403
сБп
Если честно, я плохо это понимаю. Я из за этого сильно расстроен. Встрял на элементарных вещах.
mihaild в сообщении #1279559 писал(а):
Утверждение: $X \setminus Y$ может быть непусто.
Тогда пусть $X \setminus Y$ содержит хотя бы один элемент . Как-то предположим можно задать отображение образ которого будет включать этот элемент, ну например: $ x_n \mapsto x_1$. Только не понимаю как и зачем. Думаю, что в таком случае получим биекцию, а не инъекцию (ведь она нам нужна).

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


16/07/14
9089
Цюрих
Вы взяли бесконечное множество $X$, нашли в нем счетное подмножество $Y = \{x_1, x_2, \ldots\}$ - это сделать можно по определению бесконечного множества.
Но
gogoshik в сообщении #1279431 писал(а):
Отображение $f: X \rightarrow X $ зададим так: $x_n \mapsto x_{n+1}$.
, вообще говоря, не описывает отображение $X \ to X$, т.к. в $X \setminus Y$ могут быть какие-то элементы, и вы ничего не сказали, что происходит с ними.

 Профиль  
                  
 
 Re: Доказательство попарной равносильности условий на множество
Сообщение29.12.2017, 00:08 


11/12/16
403
сБп
Пусть эти элементы отображаются сами на себя.

 Профиль  
                  
 
 Re: Доказательство попарной равносильности условий на множество
Сообщение29.12.2017, 18:57 


11/12/16
403
сБп
Давайте еще попробую. В множестве $X$выделяем счетное подмножество $Y$. Тогда $X = Y \cup (X \setminus Y)$. Далее нужно показать как элементы $X$ переводятся в $Y$ и как элементы $X$ переводятся в $X \setminus Y$ или нужно сделать другое?

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

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



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

Сейчас этот форум просматривают: mihaild


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

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