Доказательство попарной равносильности условий на множество

[gogoshik]

Прошу проверить, плиз.
Упражнение (принцип Дирихле). Показать, что следующие три условия на множество $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) доказано.

[Someone]

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 писал(а):

Очевидно, что можно установить отображение

Слово "очевидно" — не доказательство. Предъявите отображение явно.

Пока хватит.

[gogoshik]

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

-- 28.12.2017, 01:29 --

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

Вероятно, $Y$?

Это исправил. Да. Спасибо.

[Someone]

gogoshik в сообщении #1279338 писал(а):

Думаю, что это доказательство должно быть элементарное

Разумеется, оно совершенно элементарное. Для первокурсника вполне доступное.

[gogoshik]

Пусть справедливо (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$.
Такое рассуждение верно?

[eugensk]

Если это было рассуждение, то какой у него вывод?

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$. Верным или неверным.

[Someone]

gogoshik в сообщении #1279388 писал(а):

Выберем в $X$ счетное подмножество $Y$. Запишем все элементы $Y$ в виде последовательности: $\left\lbrace x_1, x_2, ..., x_n\right\rbrace$.

Фобос и Деймос! Сколько же элементов в счётном множестве? Другими словами, чему у Вас равно $n$? $10$? Или $100$? Или, о ужас, целая $1000$?

[gogoshik]

Я ошибся. Ничему не равно, иначе множество было бы конечным. Запишем все элементы $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}$. Это инъекция, но не сюръекция.

[mihaild]

gogoshik в сообщении #1279431 писал(а):

Отображение $f: X \rightarrow X $ зададим так: $x_n \mapsto x_{n+1}$.

$x_n$ - это только элементы $Y$, в $X$ может быть еще что-то, куда $f$ отправляет $X \setminus Y$?

[gogoshik]

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

[mihaild]

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

[gogoshik]

Если честно, я плохо это понимаю. Я из за этого сильно расстроен. Встрял на элементарных вещах.

mihaild в сообщении #1279559 писал(а):

Утверждение: $X \setminus Y$ может быть непусто.

Тогда пусть $X \setminus Y$ содержит хотя бы один элемент . Как-то предположим можно задать отображение образ которого будет включать этот элемент, ну например: $ x_n \mapsto x_1$. Только не понимаю как и зачем. Думаю, что в таком случае получим биекцию, а не инъекцию (ведь она нам нужна).

[mihaild]

Вы взяли бесконечное множество $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$ могут быть какие-то элементы, и вы ничего не сказали, что происходит с ними.

[gogoshik]

Пусть эти элементы отображаются сами на себя.

[gogoshik]

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