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

[irod]

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

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

А что Вы все-таки имели в виду под неиспользованием понятия конечного множества? Ниже мое доказательство 3.б) без использования определения 2, следующего за этой задачей, однако с привлечением конкретных одно- и двухэлементых множеств. Подобные контрпримеры я уже приводил к задачам предыдущего листка, и там это ни у кого нареканий не вызывало.

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

3. Верно ли, что если $|A| = |B|$ и $|C| = |D|$, то

б) $|A \cup C| = |B \cup D|$

Ответ. Нет, не верно. Например, это неверно в ситуациях когда $A = C$ или $B = D$.
Конкретный пример. Пусть $A = C = \{ 1 \}$, $B = \{ 2 \}$, $D = \{ 3 \}$. Единственно возможные тут биекции $A \to B$ и $C \to D$ очевидны. Тогда $A \cup C = \{ 1 \}$, $B \cup D = \{ 2,3 \}$. Очевидно, не существует никакой биекции $A \cup C \to B \cup D$, т.к. при любом отображении единственному элементу из $A \cup C$ соответствует ровно один из двух элементов из $B \cup D$ (по определению отображения) $\Rightarrow$ полный прообраз одного из элементов $B \cup D$ пустой.

[grizzly]

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

А что Вы все-таки имели в виду под неиспользованием понятия конечного множества?

Сделать самую безобидную из возможных подсказок :)

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

Например, это неверно в ситуациях когда $A = C$ или $B = D$.

Аккуратнее, ведь могут выполнятся оба равенства. А так да, правильно.

[irod]

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

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

Ок.

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

Сделать самую безобидную из возможных подсказок :)

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

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

Например, это неверно в ситуациях когда $A = C$ или $B = D$.

Аккуратнее, ведь могут выполнятся оба равенства. А так да, правильно.

Да, конечно, либо $A = C$, либо $B = D$ (но не и то и другое одновременно).

Насчет следующей задачи у меня вопрос: надо ли продолжать доказывать очевидные вещи, а именно что указанные мной биекции действительно являются биекциями? Или это не такие уж очевидные вещи?
Пока что вот у меня получилось.

4. Доказать, что следующие множества счетны:

а) множество четных натуральных чисел
Доказательство. Биекция $2n \mapsto n$, $n \in \mathbb{N}$.

б) множество нечетных натуральных чисел
Доказательство. Биекция $2n-1 \mapsto n$, $n \in \mathbb{N}$.

в) множество натуральных чисел без числа 2005
Доказательство. Биекция $f : \mathbb{N} \setminus \{2005\} \to \mathbb{N}$ такая что $\forall n \in \mathbb{N} \setminus \{2005\}$
\begin{equation*} f(n) = \begin{cases} n, & \text{если}\ n < 2005 \\ n-1, & \text{иначе} \end{cases} \end{equation*}

г) Множество целых чисел $\mathbb{Z}$
Доказательство. Биекция получается при выстраивании целых чисел в ряд $0,1,-1,2,-2,3,-3,\ldots$, далее ставим в соответствие целому числу из этого ряда с номером $n$ натуральное число $n$.

[arseniiv]

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

а) множество четных натуральных чисел
Доказательство. Биекция $2n \mapsto n$, $n \in \mathbb{N}$.

б) множество нечетных натуральных чисел
Доказательство. Биекция $2n-1 \mapsto n$, $n \in \mathbb{N}$.

Запись в текущем виде как бы предполагает, что мы уже до этого нашли биекции из натуральных в чётные (и что это $n\mapsto 2n$) и нечётные. Лучше просто перевернуть стрелки. Или можно написать деление нацело: $a\mapsto \lfloor a/2 \rfloor$.

Добавлено позже:

(Если нужно пояснение)

Пускай мы утверждаем, что есть функция $g\colon f(x)\mapsto x\colon A\to B, x\in B$, $f\colon B\to A$. Тогда если $f$ не сюръективна, $g$ не может быть определена на всём $A$, а если не инъективна, $g$ определяется неоднозначно.

Заодно можно разобрать, что требуется от функций $f\colon C\to A$, $g\colon C\to B$, чтобы функцией $A\to B$ была функция с графиком $\{(f(x),g(x)) : x\in C\}$. Тогда мы сможем эту функцию записать как $f(x)\mapsto g(x)$.
Ответ:

(Оффтоп)

$f$ должна быть сюръективной, и $g(f^{-1}(\{a\}))$ должны быть одноэлементными для всех $a\in A$ (так что если $g$ — инъекция, инъективной должна быть и $f$, что согласуется с написанным вначале). Если функция $f^{-1}$ существует, наша будет равна $g\circ f^{-1}$.

P. S. Внесены небольшие стилистические изменения.

[grizzly]

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

Насчет следующей задачи у меня вопрос: надо ли продолжать доказывать очевидные вещи, а именно что указанные мной биекции действительно являются биекциями?

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

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

[irod]

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

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

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

выстраивании целых чисел в ряд $0,1,-1,2,-2,3,-3,\ldots$

пусть $a_n$ - число из этого ряда с номером $n$, $n \in \mathbb{N}$. Далее строим биекцию $a_n \mapsto n$.
Или Вы имели в виду формулу, переводящую произвольное целое число из этого ряда в соответствующее натуральное? Если так, то я пока затрудняюсь ее придумать (точнее затрудняюсь ее записать красиво).

-- 16.04.2016, 10:09 --

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

Запись в текущем виде как бы предполагает, что мы уже до этого нашли биекции из натуральных в чётные (и что это $n\mapsto 2n$) и нечётные. Лучше просто перевернуть стрелки. Или можно написать деление нацело: $a\mapsto \lfloor a/2 \rfloor$.

Хорошо. А для пункта б) тогда пусть будет $a\mapsto \lfloor a/2 \rfloor + 1$

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

Если нужно пояснение

Дальнейшее пояснение пока не понял, надо над ним подумать еще.

-- 16.04.2016, 10:16 --

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

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

Насчет следующей задачи у меня вопрос: надо ли продолжать доказывать очевидные вещи, а именно что указанные мной биекции действительно являются биекциями?

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

Ок. Я думаю что в задачах, подобных 4й, я буду пропускать подобные доказательства.

[grizzly]

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

пусть $a_n$ - число из этого ряда с номером $n$, $n \in \mathbb{N}$. Далее строим биекцию $a_n \mapsto n$.
Или Вы имели в виду формулу, переводящую произвольное целое число из этого ряда в соответствующее натуральное?

Сейчас Вы записали аккуратно. Но да, я имел в виду формулу. А что сложного? на чётных местах у Вас что? -- натуральные. А на нечётных? отрицательные, сдвинутые на 0. А перед этим 3 пункта уже решено :)

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

Хорошо. А для пункта б) тогда пусть будет $a\mapsto \lfloor a/2 \rfloor + 1$

А ещё лучше -- прислушайтесь к совету:

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

Лучше просто перевернуть стрелки.

[irod]

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

Но да, я имел в виду формулу. А что сложного? на чётных местах у Вас что? -- натуральные. А на нечётных? отрицательные, сдвинутые на 0. А перед этим 3 пункта уже решено :)

Так все понятно стало, спасибо.
Биекция $f : \mathbb{Z} \to \mathbb{N}$ такая что
\begin{equation*} f(m) = \begin{cases} 2m, & \text{если}\ m \in \mathbb{N} \\ 1-2m, & \text{иначе} \end{cases} \end{equation*}
где $m \in \mathbb{Z}$.

[grizzly]

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

иначе, ... где $m \in \mathbb{Z}$.

$m\in \mathbb Z \setminus \mathbb N$

[arseniiv]

Есть ещё красивая биекция $\mathbb N^2\to\mathbb N$ (в обе стороны неплохо смотрится, но вечно забываю точный вид обеих).

[irod]

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

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

иначе, ... где $m \in \mathbb{Z}$.

$m\in \mathbb Z \setminus \mathbb N$

Мое "где $m \in \mathbb{Z}$" относилось ко всей фигурной скобке. Понятно, что в строке с "иначе" $m \not\in N$ и значит $m\in \mathbb Z \setminus \mathbb N$, как Вы и написали. Вы это имели в виду?

[irod]

5. Доказать, что всякое подмножество счетного множества конечно или счетно.

Доказательство. Пусть $A$ - счетное множество с биекцией $a_n \overset{f}\mapsto n$, где $a_n \in A$, $n = 1,2,\ldots$ Выделим из $A$ произвольное подмножество $B \subset A$. Пусть $B$ не конечно (иначе доказательство окончено). Т.к. $\forall b \in B: \ b \in A$, то существует биекция между $B$ и некоторыми натуральными числами: $b_n = a_{k_n} \overset{f}\mapsto k_n$, где $k_n \in \mathbb{N}$, $n = 1,2,\ldots$ Расставим эти натуральные числа по порядку и перенумеруем их:
$k_n \overset{g}\mapsto n$. Получили биекцию $b_n \overset{g \circ f}\mapsto n$.

[arseniiv]

Вы не использовали бесконечности $B$, так что ваше доказательство не годится, потому что оно должно тогда быть верным и для конечных. А именно, факт биективности $f$ зависит от того, каково $B$.

[irod]

arseniiv
не могли бы Вы развернуть Вашу мысль?
Разве я сразу не обозначил, что считаю $B$ бесконечным:

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

Пусть $B$ не конечно (иначе доказательство окончено).

?

-- 18.04.2016, 13:39 --

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

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

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

Посмотрю.

Посмотрел, спасибо за совет. Стало понятней, о чем же была речь:

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

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

Но я предлагаю здесь и далее все-таки следовать именно курсу Давидовича, и касательно упорядоченных пар

Шень и Верещагин писал(а):

... считать понятие упорядоченной пары не- определяемым, а это свойство — аксиомой.

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

(Оффтоп)

Курс Давидовича - это не единственное, что я сейчас самостоятельно прохожу. Еще я занимаюсь линалом по книге Serge Lang. Linear algebra с проверкой своих решений по Rami Shakarchi. Solutions Manual for Langs Linear Algebra. И вот на днях я сталкиваюсь с задачами там, которые требуют какого-то понимая аналитической геометрии (задачи к главе 3 "Линейные отображения"), которую я совершенно не знаю. И я понимаю, что мне надо отложить линал в сторону и разобраться с ангемом, хотя бы на уровне первых глав из Беклемишева. А Беклемишев в самом начале пишет, что эти нужные мне первые главы являются продолжением школьного курса геометрии. А школьную геометрию я совершенно не помню и не знаю. Думаю теперь что мне делать: повторять элементарную геометрию по Погорелову, или сразу Беклемишева начать, или что-то еще?.. В общем я теперь беспокоюсь, как бы мое "вдумчивое" изучение математики не оказалось слишком уж медленным. Я хочу усваивать материал качественно, но итеративно, т.е. не привлекать ненужные мне на данном этапе понятия. Надеюсь, вы все меня понимаете.

[arseniiv]

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

Разве я сразу не обозначил, что считаю $B$ бесконечным:

Но дальше-то вы нигде бесконечность не использовали! То есть, если это доказательство, мы можем выкинуть «пусть $B$ не конечно» и получить тоже доказательство. Уже неверного факта, ну и это было бы не очень хорошо.

Теперь детальнее:

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

Т.к. $\forall b \in B: \ b \in A$, то существует биекция между $B$ и некоторыми натуральными числами: $b_n = a_{k_n} \overset{f}\mapsto k_n$, где $k_n \in \mathbb{N}$, $n = 1,2,\ldots$ Расставим эти натуральные числа по порядку и перенумеруем их:
$k_n \overset{g}\mapsto n$. Получили биекцию $b_n \overset{g \circ f}\mapsto n$.

Предположим, что $B$ здесь может быть любым. Тогда все функции здесь определяются нормально, но $g$ не будет биекцией, а оттого и $g\circ f$. Т. е. надо доказать, что если $B$ бесконечно, $g$ биективна, и тогда доказательство спасено. Или это можно включить в круг очевидных вещей.

Кстати, в соседней теме «Подмножество счетного множества» речь об этом же.

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

Но я предлагаю здесь и далее все-таки следовать именно курсу Давидовича

Да, разумеется. Это было лирическое отступление.