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

[grizzly]

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

А не дадите ссылку на подобную табличку?

Я имел в виду примерно это (найдите там табличку со стрелочками на следующей странице -- книжная стр.113).

Может, не нужно тратить много времени на "украшения"? Попробуйте описывать идею словами -- если что, уточним. Если решения задач однотипные, можете дать одну из набора (самую сложную в таком случае).

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

Т.е. различие между этими задачами только в алгоритме построения пронумерованной последовательности - именно он и является главной целью этих задач, я полагаю.

Всё верно. Но далеко не всегда сама идея бывает тривиальной.

[irod]

7. Доказать, что объединение конечного числа счетных множеств счетно.
Доказательство.
Пусть имеется $n$ счетных множеств $A_1,\ldots,A_n$, и пусть, аналогично предыдущим задачам, элементы каждого из этих множеств расставлены по порядку в последовательности $\{ a_1^i,a_2^i,\ldots \} = A_i$, $i \in [1,2,\ldots,n]$.
Построим пронумерованную последовательность из элементов $A_1 \cup \ldots \cup A_n$ с помощью следующего алгоритма. Сначала помещаем в новую последовательность все первые элементы $a_1^i$ один за другим: сначала берем первый элемент из $A_1$, затем из $A_2$ и далее до $A_n$. Затем в таком же порядке добавляем все вторые элементы $a_2^i$, затем третьи $a_3^i$ и т.д.

Построенная последовательность будет иметь вид:

$$\{ a_1^1, a_1^2, \ldots, a_1^n, a_2^1, a_2^2, \ldots, a_2^n, \ldots \}.$$

Произвольный элемент $a_j^i \in A_i = \{ a_1^i,a_2^i,\ldots \}$ в ней будет стоять на месте с номером $n(j-1) + i$.
Второстепенные моменты опускаю:

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

Чтобы решение обрело завершённость, не помешало бы ...

[ewert]

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

Построенная последовательность будет иметь вид:

Строго говоря, пока не будет, т.к. множества могут пересекаться.

[irod]

ewert
Да, упустил этот момент. Дополню свой алгоритм:

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

Затем в таком же порядке добавляем все вторые элементы $a_2^i$, затем третьи $a_3^i$ и т.д.

Добавляем каждый следующий элемент только если его еще нет в последовательности (для случая когда множества $A_1,\ldots,A_n$ пересекаются).
Тогда

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

Построенная последовательность будет иметь вид:

для непересекающихся множеств $A_1,\ldots,A_n$, в ином случае в ней будут пропуски, и тогда уже нельзя будет сказать, что

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

Произвольный элемент $a_j^i \in A_i = \{ a_1^i,a_2^i,\ldots \}$ в ней будет стоять на месте с номером $n(j-1) + i$.

[grizzly]

irod
Да, с уточнением всё нормально.

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

в ином случае в ней будут пропуски, и тогда уже нельзя будет сказать, что

Цитата:

Произвольный элемент $a_j^i \in A_i = \{ a_1^i,a_2^i,\ldots \}$ в ней будет стоять на месте с номером $n(j-1) + i$.

Чуть полезнее выглядит такое уточнение:
Произвольный элемент $a_j^i \in A_i = \{ a_1^i,a_2^i,\ldots \}$ в ней будет иметь номер, не превышающий $n(j-1) + i$.

-- 04.05.2016, 18:29 --

Кстати,

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

Добавляем каждый следующий элемент только если его еще нет в последовательности

Из описания не совсем понятно, что делаем если этот элемент уже есть. Оставляем в табличке пустое место? сдвигаем влево? сдвигаем вверх? Не все предложенные варианты верны, поэтому Вы не должны оставлять выбор читателю.

[ewert]

Можно чуть формальнее поступить (пользуясь тем, что количество множеств всё-таки конечно): достаточно доказать для двух множеств, тогда для произвольного количества утверждение верно по индукции. Ну а объединение двух распадается на не более чем трёх дизъюнктных.

[irod]

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

Кстати,

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

Добавляем каждый следующий элемент только если его еще нет в последовательности

Из описания не совсем понятно, что делаем если этот элемент уже есть. Оставляем в табличке пустое место? сдвигаем влево? сдвигаем вверх? Не все предложенные варианты верны, поэтому Вы не должны оставлять выбор читателю.

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

-- 05.05.2016, 10:46 --

8. Доказать, что если $X$ и $Y$ счетны, то $X \times Y$ также счетно.

Доказательство.
Алгоритм построения пронумерованной последовательности из элементов $X \times Y$:
Вход: пронумерованные последовательности $\{ x_1,x_2,\ldots \} = X$ и $\{ y_1,y_2,\ldots \} = Y$, где $X$,$Y$ -- счетные множества;
Выход: пронумерованная последовательность из элементов $X \times Y$;
Для $i=1,2,\ldots$ цикл:
\begin{itemize} \item[] Для $j=1,2,\ldots,i$ цикл: \begin{itemize} \item[] Для $k=1,2,\ldots,i$ цикл: \begin{itemize} \item[] Если пара $(x_j,y_k)$ ранее не была добавлена в последовательность $X \times Y$: \begin{itemize} \item[] Добавляем пару $(x_j,y_k)$ в последовательность $X \times Y$; \end{itemize} \item[] Конец если; \end{itemize} \item[] Конец цикла по $k$; \end{itemize} \item[] Конец цикла по $j$; \end{itemize}
Конец цикла по $i$;

Для непересекающихся множеств $X$ и $Y$ построенная последовательность будет иметь вид:

$$\{ (x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2),(x_1,y_3),(x_2,y_3),(x_3,y_1),(x_3,y_2),(x_3,y_3), \ldots \}.$$

Если же $X$ и $Y$ пересекаются, то повторяющиеся элементы будут отсутствовать, но общий порядок членов сохранится.

-- 05.05.2016, 11:13 --

grizzly
не понял Вас. Что не так с этой фразой?

[grizzly]

(Здесь было удалённое сообщение.)

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

Если же $X$ и $Y$ пересекаются, то повторяющиеся элементы будут отсутствовать, но общий порядок членов сохранится.

Объясните, что Вы имеете в виду.

[irod]

Я стал расписывать и понял что зря я это сюда приплел, тут ситуация с повторяющимися элементами невозможна Давайте просто уберем эту фразу.

[grizzly]

Ок. Обратите также внимание, что проблема с пересекающимися множествами в прошлой задаче есть ничто иное, как вопрос о том, что каждый элемент получает уникальный номер. Так что это не совсем "второстепенные детали" и их проверка далеко не всегда очевидна.

[irod]

9. Доказать, что объединение счетного числа различных конечных множеств счетно.

Доказательство.
Пусть $A_1,A_2,\ldots$ -- конечные множества, $n_i$ -- мощность множества $A_i$, и пусть все элементы каждого $A_i$ пронумерованы: $\{ a_1^i,a_2^i,\ldots,a_{n_i}^i \} = A_i$. Расположим все такие пронумерованные последовательности одна за другой, начиная с $A_1$, затем $A_2$ и т.д., сохраняя при этом порядок элементов внутри каждой последовательности. Если какой-то элемент будет повторяться (при ненулевом пересечении некоторых $A_i$-х), то оставляем его в формируемой последовательности только первый раз, а каждый его повтор отбрасываем и ставим на его место следующий элемент, чтобы в последовательности не было пропусков.

Получим пронумерованную последовательность из элементов $\bigcup\limits_{i=1}^{\infty} A_i$:

$$ \{ a_1^1,a_2^1,\ldots,a_{n_1}^1, a_1^2,a_2^2,\ldots,a_{n_2}^2, \ldots \}, $$

в которой, возможно, будут отсутствовать некоторые (повторяющиеся) элементы.

[grizzly]

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

в которой, возможно, будут отсутствовать некоторые (повторяющиеся) элементы.

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

[ewert]

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

Расположим все такие пронумерованные последовательности одна за другой, начиная с $A_1$, затем $A_2$ и т.д.

Так Вы не то что до и т.д., но даже и до второго множества никогда не доберётесь.

-- Чт май 05, 2016 13:17:03 --

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

Вы нигде не использовали в доказательстве тот факт, что множества различны.

А вот это как раз и не важно. Возможное совпадение множеств -- не более чем частный случай непустоты пересечения.

[irod]

ewert в сообщении #1121177 писал(а):

Так Вы не то что до и т.д., но даже и до второго множества никогда не доберётесь.

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

[grizzly]

ewert в сообщении #1121177 писал(а):

Так Вы не то что до и т.д., но даже и до второго множества никогда не доберётесь.

Там конечные множества. А слово "последовательности" было неуместно.

ewert в сообщении #1121177 писал(а):

А вот это как раз и не важно.

А вот здесь как раз принципиально важно.