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

[grizzly]

irod
По поводу задачи 3. Чтобы оформить строже, я предлагаю рассмотреть множество $(g\circ f)^{-1}(c_0)$, которое, очевидно, расписывается как $f^{-1}(\{g^{-1}(c_0)\})$. (Здесь рассматриваются множества, без использования обратных отображений.) Последнее множество состоит из одного элемента.
Вообще, это то же, что Вы написали словами, но выражено формулами.

[irod]

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

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

Ок, тут все понятно. Признаю, Ваше доказательство лучше чем мое.

(Оффтоп)

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

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

Когда только начал заниматься математикой вдумчиво и пришел в НМУ, были огромные проблемы с этим. Было непонятно, что можно считать "очевидным", а что нет. Но сейчас вроде более менее освоился с этим, понял что "очевидное" - это то, что ранее было явно обозначено в виде определений или выведено в предыдущих задачах, и ничто иное. Хотя конечно по моим постам здесь и по моим ошибкам видно, что путь мне еще предстоит долгий.

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

irod
По поводу задачи 3. Чтобы оформить строже, я предлагаю рассмотреть множество $(g\circ f)^{-1}(c_0)$, которое, очевидно, расписывается как $f^{-1}(\{g^{-1}(c_0)\})$. (Здесь рассматриваются множества, без использования обратных отображений.) Последнее множество состоит из одного элемента.
Вообще, это то же, что Вы написали словами, но выражено формулами.

Обновленное полное доказательство задачи 1 пункта 3.

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

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

Пусть $|A| = |B|$ и $|B| = |C|$. Значит:
а) существует какая-то биекция $f : A \to B$, такая что $\forall b \in B$ множество $f^{-1}(b) = \{ a \in A \mid f(a) = b \}$ состоит из одного элемента;
б) существует какая-то биекция $g : B \to C$, такая что $\forall c \in C$ множество $g^{-1}(c) = \{ b \in B \mid g(b) = c \}$ состоит из одного элемента.
Возьмем композицию этих биекций $g \circ f : A \to C$ и рассмотрим для произвольного $c_0 \in C$ множество

$$ (g \circ f)^{-1}(c_0) = $$

$$ \{ a_0 \in A \mid (g \circ f)(a_0) = c_0 \} = $$

$$ \{ a_0 \in A \mid f(a_0) = b_0 \land g(b_0) = c_0 \} = $$

$$ f^{-1}( \{ b_0 \in B \mid g(b_0) = c_0 \} ) = $$

$$ f^{-1}(g^{-1}(c_0)).$$

Из пунктов а) и б) следует что последнее множество состоит из одного элемента $\Rightarrow$ $g \circ f$ - биекция $\Rightarrow$ $|A| = |C|$.

[grizzly]

irod
Ок, всё хорошо. И я уже побаиваюсь, что мы немного перегибаем с формализмом :)

Там ещё пару подобных заданий, а потом будет и интереснее и проще, я думаю.

[arseniiv]

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

[irod]

2. Доказать, что $|X \times Y| = |Y \times X|$ для любых множеств $X$, $Y$.

Доказательство.
Рассмотрим произвольные множества $X$, $Y$ и отображение $f : X \times Y \to Y \times X$ такое что $(x,y) \overset{f}\mapsto (y,x)$.
Возьмем произвольный элемент $(y_0,x_0) \in Y \times X$. Согласно определению произведения множеств, из принадлежности $(y_0,x_0)$ множеству $Y \times X$ следует что $y_0 \in Y$ и $x_0 \in X$, и значит $(x_0,y_0) \in X \times Y$. По нашему определению отображения $f$, $ (x_0,y_0) \overset{f}\mapsto (y_0,x_0)$. Т.е. произвольный элемент из $Y \times X$ является образом элемента некоторого элемента из $X \times Y$ при отображении $f$.
Покажем, что каждому элементу из $Y \times X$ при отображении $f$ соответствует ровно один элемент из $X \times Y$. Пусть $(x_0,y_0) \overset{f}\mapsto (y_0,x_0)$ и пусть $\exists (x_0',y_0') \in X \times Y : \ (x_0',y_0') \overset{f}\mapsto (y_0,x_0)$. Очевидно, тогда $y_0 = y_0', x_0 = x_0'$.
Таким образом, $f$ является биекцией $\Rightarrow$ $|X \times Y| = |Y \times X|$.

Кажется, это самое что ни на есть

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

Про такие вещи обычно говорят, что очевидное доказывать хуже всего :)

Я очень старался в этом доказательстве использовать как можно меньше слов "очевидно", но совсем без них обойтись не получилось

[grizzly]

Годится. Но к одному месту я придерусь:

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

каждому элементу из $Y \times X$ при отображении $f$ соответствует ровно один элемент из $X \times Y$

Здесь всё-таки нужно говорить, что "каждый элемент имеет ровно один прообраз". Само слово соответствие у нас работает в одну сторону и для отображения $f$ это не та сторона.

[arseniiv]

irod
Вы ещё забыли здесь доказать, что $a\in X\times Y\Rightarrow \exists x,y.\;a=(x,y)$, и что, действительно, $(a,b)=(c,d)\Rightarrow a=c\wedge b=d$. Но, наверно, вы это доказывали раньше — при определении пары и декартова произведения.

[grizzly]

arseniiv
Первое вряд ли стоит требовать -- там произведение определено как множество упорядоченных пар, для которых не вводилось определение (даётся на интуитивном уровне, как я понимаю). Второе -- да, ТС спрятал его в своём "очевидно", но без определения упорядоченной пары доказывать это не так уж интересно. Или можно?

irod
Может проще было к Вашему $f$ добавить аналогичное (действующее в обратную сторону) $g$ и проверить что их композиция в любом порядке -- тождественное отображение? Тогда сразу бы получили обратимость и биекцию. Для такого рассуждения нам "очевидные" вещи не понадобятся.

[arseniiv]

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

Первое вряд ли стоит требовать -- там произведение определено как множество упорядоченных пар, для которых не вводилось определение (даётся на интуитивном уровне, как я понимаю).

Так всё равно утверждение остаётся содержательным. (Или надо будет явно упоминать проекции $\pi_i\colon A_1\times A_2\to A_i$.) Пусть даже пара понимается как дополнительно прибавленная к теории множеств конструкция. Хотя точно не настаиваю.

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

Второе -- да, ТС спрятал его в своём "очевидно", но без определения упорядоченной пары доказывать это не так уж интересно. Или можно?

Да, если пара определяется «экстенсионально», это будет как раз аксиома для неё, и добавлять будет нечего.

[irod]

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

Здесь всё-таки нужно говорить, что "каждый элемент имеет ровно один прообраз". Само слово соответствие у нас работает в одну сторону и для отображения $f$ это не та сторона.

Ок

arseniiv в сообщении #1114458 писал(а):

irod
Вы ещё забыли здесь доказать, что $a\in X\times Y\Rightarrow \exists x,y.\;a=(x,y)$, и что, действительно, $(a,b)=(c,d)\Rightarrow a=c\wedge b=d$. Но, наверно, вы это доказывали раньше — при определении пары и декартова произведения.

Честно говоря, не знаю как это доказать. Такие вершины доказывания очевидного мне пока не доступны Могу только сослаться на определение произведения множеств, что я и сделал. Мне кажется, grizzly прав:

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

arseniiv
Первое вряд ли стоит требовать -- там произведение определено как множество упорядоченных пар, для которых не вводилось определение (даётся на интуитивном уровне, как я понимаю).

и сам Давидович не стал бы требовать тут доказательства

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

Может проще было к Вашему $f$ добавить аналогичное (действующее в обратную сторону) $g$ и проверить что их композиция в любом порядке -- тождественное отображение? Тогда сразу бы получили обратимость и биекцию. Для такого рассуждения нам "очевидные" вещи не понадобятся.

Попробую. Обновленное доказательство задачи 2.

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

2. Доказать, что $|X \times Y| = |Y \times X|$ для любых множеств $X$, $Y$.

Рассмотрим произвольные множества $X$, $Y$ и отображения $f : X \times Y \to Y \times X$ такое, что $(x,y) \overset{f}\mapsto (y,x)$, и отображение $g : Y \times X \to X \times Y$ такое, что $(y,x) \overset{g}\mapsto (x,y)$.
(Мы можем построить такие отображения, потому что по определению произведения множеств, $(x,y) \in X \times Y \Leftrightarrow x \in X \land y \in Y \Leftrightarrow (y,x) \in Y \times X$.)
Рассмотрим для произвольных элементов $(x_0,y_0) \in X \times Y$ и $(y_0,x_0) \in Y \times X$ композиции

$$ (g \circ f)(x_0,y_0) = g(y_0,x_0) = (x_0,y_0),$$

$$ (f \circ g)(y_0,x_0) = f(x_0,y_0) = (y_0,x_0).$$

Композиции тождественны $\Rightarrow$ $g = f^{-1}$ $\Rightarrow$ $f$ является биекцией (по задаче 15 листка 3) $\Rightarrow$ $|X \times Y| = |Y \times X|$.

-- 14.04.2016, 12:45 --

Перед доказательством следующей задачи я все-таки распишу доказательство пункта 2 задачи 1, как Вы его предложили на прошлой странице, чтобы затем на него сослаться.

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

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

Доказательство. По определению равномощности существует взаимно однозначное отображение $f : A \to B$. По задаче 15 листка 3 $f$ -- обратимо, и пусть $g = f^{-1}$. По определению обратного отображения, композиции $f \circ g$ и $g \circ f$ тождественны. Но тождественность этих композиций является также условием для того, чтобы и $f$ было обратным отображением к $g$. Значит $g$ -- обратимо. Наконец, по задаче 15 листка 3, обратимое отображение $g$ взаимно однозначно. Значит $|B| = |A|$.

Следующая задача.

3. Верно ли, что если $|A| = |B|$ и $|C| = |D|$, то
а) $|A \times C| = |B \times D|$
Ответ. Да, верно.
Обозначим существующие биекции $f: A \to B$, $g: C \to D$, и отметим существование согласно листку 3 задаче 15 обратных к ним $f^{-1} : B \to A$, $g^{-1} : D \to C$. Из задачи 1.2 этого листка следует, что $f^{-1}$ и $g^{-1}$ сами будут биекциями.
Исходя из определения произведения множеств, можно построить отображение $h : A \times C \to B \times D$ такое что $h(a,c) = (f(a),g(c))$, и отображение $h' : B \times D \to A \times C$ такое что $h'(b,d) = (f^{-1}(b),g^{-1}(d))$. Рассмотрим их композиции для произвольных пар $(a_0,c_0) \in A \times C$ и $(b_0,d_0) \in B \times D$:

$$ (h' \circ h)(a_0,c_0) = h'(f(a_0),g(c_0)) = ((f^{-1} \circ f)(a_0),(g^{-1} \circ g)(c_0)) = (a_0,c_0) $$

$$ (h \circ h')(b_0,d_0) = h(f^{-1}(b_0),g^{-1}(d_0)) = ((f \circ f^{-1})(b_0),(g \circ g^{-1})(d_0)) = (b_0,d_0). $$

Композиции являются тождественными $\Rightarrow$ $h' = h^{-1}$ $\Rightarrow$ $h$ -- биекция $\Rightarrow$ $|A \times C| = |B \times D|$.

Пункт б) будет чуть позже.

[grizzly]

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

Рассмотрим для произвольных элементов $(x_0,y_0) \in X \times Y$ и $(y_0,x_0) \in Y \times X$ композиции

Только первый элемент в этой записи выбран произвольно. Второй -- нет. И такое рассуждение может привести к ошибке. Или используйте другие индексы, или доведите до конца рассуждение с первым элементом, потом проделайте то же со вторым.

[arseniiv]

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

Честно говоря, не знаю как это доказать. Такие вершины доказывания очевидного мне пока не доступны

Если у вас пара $(x,y)$ не определяется как множество определённого вида (часто используют $\{\{x\},\{x,y\}\}$), тогда вы действительно не сможете выжать ничего больше. А если определяется, то это ещё надо доказывать, что она для любых $x, y$ существует (и потом про равенство), что существует декартово произведение $A\times B$ (для случая определения в скобках его выделяют из $2^{2^{A\cup B}}$, существование которого — прямое следствие аксиом ZFC (есть аксиома для неупорядоченной пары $\{A,B\}$, объединения множеств $\bigcup\{A,B\} = A\cup B$, и аксиома существования булеана применяется два раза, и потом одна из аксиом схемы выделения с интересненьким таким предикатом)), и т. д.. Если пары даны свыше, поводов для беспокойства совершенно никаких.

[grizzly]

irod
Как видите, строгое изложение несколько отличается от школьного. В упомянутом Вами учебнике Н.К.Верещагина и А.Шеня упорядоченная пара определяется и даже объясняется разница в подходах -- аксиоматическое введение упорядоченной пары (как у Давидовича) и через определение. Хотя и у А.Шеня изложение не строится до уровня "от аксиом", но всё же гляньте (я смотрю 2012 г. на стр. 36).

С задачей 3.а) я согласен. С 3.б) любопытно будет, как Вы выкрутитесь (чур, понятием конечного множества не пользоваться).

[irod]

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

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

Рассмотрим для произвольных элементов $(x_0,y_0) \in X \times Y$ и $(y_0,x_0) \in Y \times X$ композиции

Только первый элемент в этой записи выбран произвольно. Второй -- нет. И такое рассуждение может привести к ошибке. Или используйте другие индексы, или доведите до конца рассуждение с первым элементом, потом проделайте то же со вторым.

Хорошо, я обозначу второй элемент как $(y_1,x_1)$, соответственно далее будет $(f \circ g)(y_1,x_1)$... Так пойдет?

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

Как видите, строгое изложение несколько отличается от школьного. В упомянутом Вами учебнике Н.К.Верещагина и А.Шеня упорядоченная пара определяется и даже объясняется разница в подходах -- аксиоматическое введение упорядоченной пары (как у Давидовича) и через определение. Хотя и у А.Шеня изложение не строится до уровня "от аксиом", но всё же гляньте (я смотрю 2012 г. на стр. 36).

Посмотрю.

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

С задачей 3.а) я согласен.

Как Вы считаете, можно ли сократить мое доказательство этого пункта, сразу сказав после этой строчки

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

Исходя из определения произведения множеств, можно построить отображение $h : A \times C \to B \times D$ такое что $h(a,c) = (f(a),g(c))$

что $h$ будет биекцией, т.к. $f(a)$ имеет при $f$ единственный прообраз $a$, $g(c)$ имеет при $g$ единственный прообраз $c$ $\Rightarrow$ $( f(a),g(c) )$ имеет при $h$ единственный прообраз $( a, c )$.
?
Тогда доказательство на этом будет закончено, и даже все упоминания об $f^{-1}$ и $g^{-1}$ в самом начале можно будет выкинуть.

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

С 3.б) любопытно будет, как Вы выкрутитесь (чур, понятием конечного множества не пользоваться).

Мне самому любопытно пока в процессе.

[grizzly]

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

Хорошо, я обозначу второй элемент как $(y_1,x_1)$, соответственно далее будет $(f \circ g)(y_1,x_1)$... Так пойдет?

Да. Переписывать не нужно, конечно, -- важно только, чтобы Вы поняли, в чём суть этого замечания.

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

Как Вы считаете, можно ли сократить мое доказательство этого пункта, сразу сказав после этой строчки

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

Исходя из определения произведения множеств, можно построить отображение $h : A \times C \to B \times D$ такое что $h(a,c) = (f(a),g(c))$,

что $h$ будет биекцией, т.к. $f(a)$ имеет при $f$ единственный прообраз $a$, $g(c)$ имеет при $g$ единственный прообраз $c$ $\Rightarrow$ $( f(a),g(c) )$ имеет при $h$ единственный прообраз $( a, c )$.
?
Тогда доказательство на этом будет закончено, и даже все упоминания об $f^{-1}$ и $g^{-1}$ в самом начале можно будет выкинуть.

Да, можно. Только Вы забыли упомянуть, что единственный прообраз можно указать для любого элемента $B \times D$.