Подмножество счетного множества

[ellipse]

В книге «Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств» доказывается следующая теорема



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

Аналогично можно доказать и континуум гипотезу. Пусть $B$ — подмножество $\Bbb R$. Представим множество $\Bbb R$ как $\{a_\alpha, a_\beta, \cdots \}$. Выбросим из последовательности $a_\alpha, a_\beta, \cdots$ те элементы, которые не принадлежат $B$. Тогда оставшиеся элементы образуют либо конечную цепь, либо счетную, либо континуальную. ЧТД

Стоит ли дальше использовать эту книгу для знакомства с теорией множеств?

[mihailm]

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

[Sinoid]

ellipse в сообщении #1116037 писал(а):

В книге «Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов

ellipse в сообщении #1116037 писал(а):

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

Я тоже месяца два назад пытался начать изучать эти разделы математики с этой книги. Так у меня ну очень тяжело она шла, хоть мне ее и порекомендовали здесь. С трудом дочитал до теоремы Кантора-Бернштейна разбирал, разбирал ее доказательство, да так и не понял до конца, просто выдохся. Впечатления от этой книги остались почти до отвращения (потом, может, и подзабудется, а, может, даже и понравится), хотя в аннотации и сказано, что книга рассчитана на школьников, ну, думаю, подготовлюсь к основательному изучению этих штук. Ага, как бы не так! Короче, искал, искал, с чего бы начать и нашел я комплект Игошина. Сейчас изучаю да радуюсь. Все растолковано почти на пальцах. А импликация так вообще преподнесена с оригинальной точки зрения. Во всяком случае, у других авторов на такую интерпретацию импликацию есть только легкий, едва уловимый намек. Она ими преподносится как данность, ложная в единственном случае и баста! А у него совсем по-другому. Короче, очень его рекомендую. Хотя, справедливости ради, нужно сказать, что в его задачнике опечаток ну очень много.

[Someone]

ellipse в сообщении #1116037 писал(а):

Почему после выбрасывания останется конечное или счетное множество?

А там не сказано "конечное или счётное". Там сказано "конечное или бесконечное". И почему это бесконечное оказывается счётным, надо ещё сообразить.

[Anton_Peplov]

Скажите, ellipse, Вам знакомы термины
1) последовательность
2) подпоследовательность?

[ellipse]

Anton_Peplov в сообщении #1116121 писал(а):

Скажите, ellipse, Вам знакомы термины
1) последовательность
2) подпоследовательность?

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

Скорее всего, доказательство нужно основывать на факте, что всякое непустое подмножество натуральных чисел имеет минимальный элемент, предварительно упорядочив $A$ согласованно с натуральной индексацией.
Если $B=B_1$ не пусто, то в нем найдется минимальный элемент. Обозначим его $b_1$. Если $B_2=B_1\setminus \{b_1\}$ не пусто, то в нем также найдется минимальный элемент. Обозначим его $b_2$. Если уже определено $B_n$ и оно пусто, то останавливаемся, если $B_n$ не пусто, то в нем найдем элемент $b_{n}$ и положим $B_{n+1}=B_n\setminus \{b_n\}$. Действуя так, мы определим функцию $f:[1,n] \to B$ или $f:\Bbb N \to B$. Хотя это тоже надо как-то обосновать, используя понятие индуктивного (или рекурсивного) определения функции.

[iifat]

ellipse в сообщении #1116037 писал(а):

$\mathbb R$ как $\{a_\alpha, a_\beta, \cdots \}$

Вот тут бы поподробнее. Обычно так обозначаются последовательности, а индексы натуральные числа $1, 2, \dots$. Последовательность имеет конечную либо счётную мощность, это понятно? Поэтому теорема и верна. А ваша только маскируется — либо вы используете обычное определение последовательности, и тогда вам не удастся выстроить множество действительных числ; либо вы таким странным образом записываете $f:{\mathbb R} \rightarrow {\mathbb R}$, и всё не менее печально.

[Anton_Peplov]

ellipse в сообщении #1116127 писал(а):

Понятно, что элементы из $B$ образуют подпоследовательность.

Вероятно, авторы считали этот факт очевидным для читателя. Однако я соглашусь с Вами, что он сводится к утверждению "всякое бесконечное подмножество $\matbb{N}$ счетно", которое эквивалентно утверждению, которое мы пытаемся доказать.

[ellipse]

iifat в сообщении #1116135 писал(а):

ellipse в сообщении #1116037 писал(а):

$\mathbb R$ как $\{a_\alpha, a_\beta, \cdots \}$

Вот тут бы поподробнее. Обычно так обозначаются последовательности, а индексы натуральные числа $1, 2, \dots$.

Можно считать, что эта запись означает вполне упорядоченность. Хотя я просто хотел показать необоснованность рассуждений.

[Brukvalub]

ellipse в сообщении #1116152 писал(а):

Хотя я просто хотел показать необоснованность рассуждений.

Хотел, но не смог!

[ellipse]

Anton_Peplov в сообщении #1116142 писал(а):

Вероятно, авторы считали этот факт очевидным для читателя.

Мне кажется, теория множеств такой раздел математики, который и создан, чтоб строго доказывать такие очевидные факты.

[Anton_Peplov]

ellipse в сообщении #1116155 писал(а):

Мне кажется, теория множеств такой раздел математики, который и создан, чтоб строго доказывать такие очевидные факты.

Если уж доказывать строго, то это к формальной аксиоматической теории множеств. А если мы остаемся в рамках естественного языка, придется полагаться на те или иные "очевидности". И какие очевидности более очевидны - нетривиальный вопрос.

[Someone]

ellipse в сообщении #1116152 писал(а):

iifat в сообщении #1116135 писал(а):

ellipse в сообщении #1116037 писал(а):

$\mathbb R$ как $\{a_\alpha, a_\beta, \cdots \}$

Вот тут бы поподробнее. Обычно так обозначаются последовательности, а индексы натуральные числа $1, 2, \dots$.

Можно считать, что эта запись означает вполне упорядоченность. Хотя я просто хотел показать необоснованность рассуждений.

Нельзя. Это противоречит общепринятому в теории множеств смыслу использованных Вами символов.

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

ellipse в сообщении #1116037 писал(а):

Представим множество $\Bbb R$ как $\{a_\alpha, a_\beta, \cdots \}$. Выбросим из последовательности $a_\alpha, a_\beta, \cdots$ те элементы, которые не принадлежат $B$. Тогда оставшиеся элементы образуют либо конечную цепь, либо счетную, либо континуальную

последнее утверждение никак не следует из предыдущих. А в случае счётного множества следует.

[ellipse]

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

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

ellipse в сообщении #1116037 писал(а):

Представим множество $\Bbb R$ как $\{a_\alpha, a_\beta, \cdots \}$. Выбросим из последовательности $a_\alpha, a_\beta, \cdots$ те элементы, которые не принадлежат $B$. Тогда оставшиеся элементы образуют либо конечную цепь, либо счетную, либо континуальную

последнее утверждение никак не следует из предыдущих. А в случае счётного множества следует.

Почему следует? Мои рассуждения с использованием минимального элемента верные или можно проще?

[gefest_md]

ellipse
Могу порекомендовать книгу Daniel Velleman "How to prove it: a structured approach". Но может не очень разумно решать всё подряд из неё. В последней главе есть такая теорема, с доказательством: Если существует инъекция $f\colon A\to\mathbb{Z}^+$, тогда $A$ - счётно. Доказательство использует множество других теорем, "существование наименьшего элемента", и рекурсивное определение.