Счетность множеств (задачи из Давидовича)

[irod]

Продолжаю прорешивать задачи из книжки Давидовича и ко http://www.mccme.ru/free-books/57/davidovich.pdf.
Эта тема посвящена листку №4 "Счетность множеств".

1. Доказать, что равномощность есть отношение эквивалентности, то есть:
1) $|A| = |A|$; 2) если $|A| = |B|$, то $|B| = |A|$; 3) если $|A| = |B|$ и $|B| = |C|$, то $|A| = |C|$.

Доказательство.
1) В качестве биекции из $|A|$ в $|A|$ используем тождественное отображение.
2) Пусть $|A| = |B|$, т.е. существует биекция (назовем ее $f$) из $A$ в $B$. Из задачи $15$ листка $3$ известно, что существует обратное отображение $f^{-1}$. Это обратное отображение также будет биекцией, значит $|B| = |A|$.
3) Пусть $|A| = |B|$ и $|B| = |C|$. Обозначим соответствующие биекции как $f: A \to B$, $g: B \to C$. Композиция $g \circ f$ будет биекцией из $A$ в $C$, значит $|A| = |C|$.
Доказательство утверждения если $f$ и $g$ -- биекции, то $g \circ f$ - также биекция.
Пусть $f: X \to Y$ и $g : Y \to Z$ - биекции. По определению, $\forall z_0 \in Z$ $|g^{-1}(z_0)| = 1$ и $\forall y_0 \in Y$ $|f^{-1}(y_0)| = 1$. Из этого следует, что $\forall z_0 \in Z$ $|(f^{-1} \circ g^{-1})(z_0)| = 1$. $f^{-1} \circ g^{-1}$ - это обратное отображение к $g \circ f$.

[Anton_Peplov]

irod, а Вы чего хотите-то? Чтобы проверили, все ли правильно? Да, все правильно.

[irod]

Anton_Peplov да, хочу чтобы проверили Спасибо.

[grizzly]

irod
Понятно, что здесь Вы вправе выкладывать только те рассуждения, в которых Вы сомневаетесь или ожидаете помощи. Но было бы полезно как-то отличать, что Вы пропустили по ошибке от того, что для Вас уже действительно очевидно. Два примера:

irod в сообщении #1113113 писал(а):

2) ...
Это обратное отображение также будет биекцией

irod в сообщении #1113113 писал(а):

3...
$f^{-1} \circ g^{-1}$ - это обратное отображение к $g \circ f$.

Эти факты ранее не упоминались, если не ошибаюсь.

Кстати, задачу 10 с прошлого листка я где-то не заметил. Она была / будет?

[Anton_Peplov]

grizzly, а Вы так жаждете сопровождать irod с точностью до задачи?:)

[grizzly]

Anton_Peplov

(Оффтоп)

Я на форуме занимаюсь только тем, что мне интересно В данном случае (и пока) мне это интересно по нескольким причинам.

[irod]

grizzly в сообщении #1113234 писал(а):

Кстати, задачу 10 с прошлого листка я где-то не заметил. Она была / будет?

Выложил ее: post1113324.html#p1113324

-- 08.04.2016, 12:13 --

grizzly в сообщении #1113234 писал(а):

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

Да, Вы правы. Доказательства этих фактов за мной, выложу их в следующих постах.

[grizzly]

irod
Ок.

Ответьте, пожалуйста, на простой вопрос. В п.3 Вы пишете:

irod в сообщении #1113113 писал(а):

По определению, $\forall z_0 \in Z$ $|g^{-1}(z_0)| = 1$

Что такое $g^{-1}(z_0)$? (В этой записи нет ошибки, мне просто нужно убедиться, что Вы её правильно понимаете.)

[irod]

grizzly в сообщении #1113335 писал(а):

Что такое $g^{-1}(z_0)$?

Это полный прообраз элемента $z_0$ при отображении $g$:
$g^{-1}(z_0) = \{ y \in Y \mid g(y) = z_0 \}$

[grizzly]

irod в сообщении #1113341 писал(а):

Это полный прообраз элемента $z_0$ при отображении $g$:

Верно!
Значит, Вы не ввели ещё никаких новых отображений и не считаете пока, что $g^{-1}$ является отображением. Но потом сразу же появляется композиция $(f^{-1} \circ g^{-1})(z_0)$. Скажите, здесь $f^{-1}$ и $g^{-1}$ -- это у Вас отображения? Если нет, то лучше было написать так $((g\circ f)^{-1})(z_0)$.

[irod]

irod в сообщении #1113113 писал(а):

2) если $|A| = |B|$, то $|B| = |A|$

А давайте-ка я изменю свое доказательство этого пункта, чтобы в нем не использовались никакие лишние утверждения, которые в свою очередь потребовали бы отдельного доказательства.
Итак, новое доказательство.
Пусть $|A| = |B|$. Значит, существует какая-то биекция $f : A \to B$, которая каждому $a \in A$ ставит в соответствие ровно один $b \in B$. Но это значит что и обратно, каждому $b \in B$ можно поставить в соответствие ровно один $a \in A$ (при каком-то отображении). Как именно назвать это отображение из $B$ в $A$ - в данном случае не важно (возможно, это будет обратное отображение к $f$, возможно нет), главное что оно существует и является взаимно однозначным. Значит $|B| = |A|$.

[arseniiv]

irod в сообщении #1113542 писал(а):

Как именно назвать это отображение из $B$ в $A$ - в данном случае не важно (возможно, это будет обратное отображение к $f$, возможно нет), главное что оно существует и является взаимно однозначным.

Если пойти конструктивно, то проще предъявить всё-таки $f^{-1}$, чем $a\circ f^{-1}$, $f^{-1}\circ b$ или $a\circ f^{-1}\circ b$, где $a,b$ — не тождественные биекции $A\to A$ и $B\to B$ соответственно.

[irod]

irod в сообщении #1113542 писал(а):

Значит, существует какая-то биекция $f : A \to B$, которая каждому $a \in A$ ставит в соответствие ровно один $b \in B$.

Я подумал, что это лучше сказать аккуратнее: существует какая-то биекция $f : A \to B$, которая (по определению отображения) каждому $a \in A$ ставит в соответствие ровно один $b \in B$, и (по определению биекции) каждому $b \in B$ соответствует ровно один $a \in A$.

-- 09.04.2016, 13:48 --

arseniiv
я постарался сейчас не плодить лишние сущности без надобности

[irod]

irod в сообщении #1113113 писал(а):

3) если $|A| = |B|$ и $|B| = |C|$, то $|A| = |C|$.

grizzly в сообщении #1113344 писал(а):

Значит, Вы не ввели ещё никаких новых отображений и не считаете пока, что $g^{-1}$ является отображением. Но потом сразу же появляется композиция $(f^{-1} \circ g^{-1})(z_0)$. Скажите, здесь $f^{-1}$ и $g^{-1}$ -- это у Вас отображения? Если нет, то лучше было написать так $((g\circ f)^{-1})(z_0)$.

Я вижу что в п.3 я тоже привлек лишние сущности. Вот новое доказательство, без упоминания обратных отображений вообще.
Пусть $|A| = |B|$ и $|B| = |C|$. Значит, существует какая-то биекция $f : A \to B$, такая что $\forall b \in B$ найдется единственный $a \in A : \ f(a) = b$, и каждый $a \in A$ используется, и существует какая-то биекция $g : B \to C$, такая что $\forall c \in C$ найдется единственный $b \in B : \ g(b) = c$, и каждый $b \in B$ используется. Следовательно, $\forall c \in C$ найдется единственный $a \in A : \ g(f(a)) = c$, и каждый $a \in A$ при этом используется. Это значит, что $g \circ f : A \to C$ - биекция, и значит $|A| = |C|$.

[grizzly]

irod в сообщении #1113554 писал(а):

Я подумал, что это лучше сказать аккуратнее: существует какая-то биекция $f : A \to B$, которая (по определению отображения) каждому $a \in A$ ставит в соответствие ровно один $b \in B$, и (по определению биекции) каждому $b \in B$ соответствует ровно один $a \in A$.

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

Я бы предложил такую идею доказательства (расписывать её не обязательно, но подтвердите, пожалуйста, что Вам эта идея понятна или задайте вопросы):
По определению равномощности существует взаимно однозначное отображение $f:A\to B.$ По задаче 15.часть1 листка 3 $f$ -- обратимо и пусть $g=f^{-1}$. Из определения 8 листка 3 следует, что отображение $g$ является обратимым (убедитесь в этом) и по задаче 15.часть 2 -- взаимно однозначным.

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