2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Счетные и несчетные множества
Сообщение25.01.2016, 22:51 


15/03/14
22
Доброго времени суток!
Прошу помочь в решении задач и указать на ошибки.
Есть три задачи из учебника Зорича по Математическому анализу, которые я пытаюсь решить.
a) Любое бесконечное множество содержит счетное подмножество.
b) Объединение бесконечного множества и не более чем счетного множества имеет ту же мощность, что и исходное множество.
c) Множество иррациональных чисел имеет мощность континуума.

Решение.
a) Пусть $A$ - бесконечное множество. Оно не пусто, поэтому найдём в нем хотя бы один элемент $x_{1}$. Далее, в множество $A-\{x_{1}\}$ также не пусто, так как если бы оно было пусто, то $A$ оказалось конечным множеством. Из $A-\{x_{1}\}$ берем элемент $x_{2}$. Продолжая, если у нас уже есть $n$ элементов $x_{1}, ..., x_{n}$, из бесконечного множества $A-\{x_{1}, ..., x_{n}\}$ возьмем элемент $x_{n + 1}$. Согласно принципу индукции, из $A$ мы можем выделить счетное подмножество.
b) Пусть $A$ - конченое или счетное множество, $B$ - бесконечное множество. Согласно доказаному утверждению в задаче a) в $B$ есть счетное подмножество $C = \{c_{1},...,c_{n},...\}$.
Построим биективное отображение $g: C \rightarrow A \cup C$
- если $A$ конечно, то $A = \{a_{1},...,a_{m}\}$ и
$g(c_{n}) = \begin{cases} a_{n} &\mbox{if } n \le m\\
c_{n+m} & \mbox{if } n > m\end{cases} $
- если $A$ счетно, то $A = \{a_{1},...,a_{n},...\}$ и
$g(c_{n}) = \begin{cases} a_{n} &\mbox{if } n = 2k + 1, k \in \mathbb{N} \\
c_{n} & \mbox{if } n = 2k,  k \in \mathbb{N}\end{cases} $
Теперь можно определить биекцию $f: B \rightarrow A \cup B$:
$f(x) = \begin{cases} g(x) &\mbox{if } x \in C\\
x & \mbox{if } x \not\in C\end{cases} $.
c) Из определения иррациональных чисел известно что $\mathbb{I} = \mathbb{R} - \mathbb{Q}$. Это значит что $\mathbb{I} \cup \mathbb{Q} = \mathbb{R}$. Нам надо показать что $card(\mathbb{I} \cup \mathbb{Q}) = card\mathbb{I}$.
Покажем что $\mathbb{I}$ - бесконечное множество. Если бы оно было конечным, то по доказанному в задаче b) получилось что $card\mathbb{Q} = card (\mathbb{I} \cup \mathbb{Q})$, а это бы означало что множество $ \mathbb{R}$ счетно, но мы знаем что множество действительных чисел несчетно. Значит $\mathbb{I}$ - бесконечное.
Применяя утверждение из задачи b) , где $\mathbb{I}$ - бесконечное множество, а $\mathbb{Q}$ счетное множество, получаем: $card (\mathbb{I} \cup \mathbb{Q}) = card\mathbb{I}$, а это означает, что $card \mathbb{R} = card\mathbb{I}$.

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение25.01.2016, 23:23 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
hanik в сообщении #1094295 писал(а):
- если $A$ счетно, то $A = \{a_{1},...,a_{n},...\}$ и
$$g(c_{n}) = \begin{cases} a_{n} &\mbox{if } n = 2k + 1, k \in \mathbb{N} \\
c_{n} & \mbox{if } n = 2k,  k \in \mathbb{N}\end{cases} $$

Здесь есть ошибка.

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение25.01.2016, 23:31 
Заслуженный участник


23/07/08
10626
Crna Gora
Ещё замечание по b).
Учтите коварную возможность, когда множества $A$ и $C$ имеют непустое пересечение (например, $a_2=c_2$), отчего определённая Вами $g$ может не быть биекцией (даже после исправления ошибки, о которой говорит Brukvalub).

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение25.01.2016, 23:38 


15/03/14
22
$g(c_{n}) = \begin{cases} a_{(n + 1)/2} &\mbox{if } n = 2k + 1, k \in \mathbb{N} \\
c_{n / 2} & \mbox{if } n = 2k,  k \in \mathbb{N}\end{cases} $
Так?

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение25.01.2016, 23:40 
Заслуженный участник


23/07/08
10626
Crna Gora
Да.

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение25.01.2016, 23:42 


15/03/14
22
Насчет непустого пересечения - ошибка остаётся?

-- 26.01.2016, 00:46 --

Если да - то делаем так: берем один элемент из $A$, затем один элемент из $C$, если он нам еще не встречался, потом из $A$ один, если он уникален, и так далее. Если выразить это формально, то нужно построить две последовательности индексов, правильно?

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение25.01.2016, 23:47 
Заслуженный участник


23/07/08
10626
Crna Gora
hanik в сообщении #1094309 писал(а):
Насчет непустого пересечения - ошибка остаётся?
Если пересечение $A$ и $B$ непусто (что вполне возможно), то при неудачном выборе $C$ некоторые его элементы будут также элементами $A$. Тогда один и тот же элемент $A\cup C$ встретится в правой части Вашего определения функции $g$ дважды, при двух различных $n$: как элемент $A$ и как элемент $C$. Это, конечно, уже не биекция.
hanik в сообщении #1094309 писал(а):
Если да - то делаем так: берем один элемент из $A$, затем один элемент из $C$, если он нам еще не встречался, потом из $A$ один, если он уникален, и так далее. Если выразить это формально, то нужно построить две последовательности индексов, правильно?
Ну, или покажите, что $C$ всегда можно выбрать так, чтобы оно не пересекалось с $A$.

-- Пн янв 25, 2016 22:55:30 --

Нет, я неправ насчёт своего предложения. Возможен вариант, когда $A,B$ — счётные множества, и $A=B$.

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение25.01.2016, 23:59 


15/03/14
22
Хорошо.
Предположим, уже выбрали $n$ уникальных элементов из $A \cup C$.
Пусть $n$- нечетно. $n$ конечно, поэтому в множестве $\{a_{n},...,a_{n+n}\}$ хотя бы один элемент будет отличен от выбранных ранее.
Аналогично с множеством $C$.

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение26.01.2016, 00:17 
Заслуженный участник


23/07/08
10626
Crna Gora
Другими словами можно так: составляем последовательность
$a_1, c_1, a_2, c_2, a_3, c_3, ...$,
затем вычеркиваем из неё все элементы, совпадающие с одним из предыдущих (где-то это называлось «прополка»), и элементы полученной последовательности уже ставим в соответствие $(c_n)$ поэлементно.

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение26.01.2016, 00:24 


15/03/14
22
Да. В остальном правильно?

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение26.01.2016, 00:40 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
б) По-моему, перемудрили с этими $A$ и $C$. Поскольку $A\cup B=(A\setminus B)\cup B$, без ограничения общности можно считать, что $A\cap B=\varnothing$; в противном случае можно заменить $A$ на $A'=A\setminus B$.

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение26.01.2016, 00:52 


15/03/14
22
Someone в сообщении #1094330 писал(а):
б) По-моему, перемудрили с этими $A$ и $C$. Поскольку $A\cup B=(A\setminus B)\cup B$, без ограничения общности можно считать, что $A\cap B=\varnothing$; в противном случае можно заменить $A$ на $A'=A\setminus B$.

В этом случае $C$ нужно выбрать из $B - A$?

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение26.01.2016, 09:47 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
hanik в сообщении #1094333 писал(а):
В этом случае $C$ нужно выбрать из $B - A$?
Someone в сообщении #1094330 писал(а):
без ограничения общности можно считать, что $A\cap B=\varnothing$

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение26.01.2016, 23:19 


15/03/14
22
Someone в сообщении #1094330 писал(а):
без ограничения общности можно считать, что $A\cap B=\varnothing$

Я не очень понимаю выражение "без ограничения общности". Здесь говорится про частный случай объединения, разве это не ограничение общности?

Помогите решить следующую задачу из того же учебника Зорича:
Множество $\{n_{1} < n_{2} < ...\}$ возрастающих последовательностей натуральных чисел равномощно множеству дробей вида $0,a_{1}a_{2}...$.
Насколько я понял, нужно показать, что множество этих последовательностей имеет мощность континуума.
Пусть $P$ - множество возрастающих последовательностей натуральных чисел.
Я могу показать, что $cardP \ge card\mathbb_{N}$ следующим образом:
Каждому $k \in \mathbb_{N}$ сопоставим последовательность $k, k+1, k+2,...$. Значит $P$ не менее чем счетное множество.
Проблема в том, чтобы показать что оно равномощно континууму.
Предположим, что $cardP = card\mathbb_{N}$. Тогда последовательности можно выстроить вот так:
$n_{1,1}, n_{1,2}, n_{1,3},...$
$n_{2,1}, n_{2,2}, n_{2,3},...$
$n_{3,1}, n_{3,2}, n_{3,3},...$
$.$

$.$

$.$

$n_{k,1}, n_{k,2}, n_{k,3},...$
где при элементе $n_{i,j}$: $i$ - номер последовательности, $j$ - номер элемента в этой последовательности.
Построим последовательность $a_{n}$.
$a_{1} = n_{1,1}$. Для $a_{2}$ выберем такой элемент из второго столбца, который бы не равнялся $n_{1,2}$ и был бы больше $a_{1}$. Так, если мы уже выбрали $q$ элементов, то для $a_{q+1}$ выберем элемент из $(q+1)$-го столбца такой что $a_{q+1} > a_{q}$ и $a_{q+1} \not\in \{n_{1,q+1}, n_{2,q+1}, ..., n_{q, q+1}\}$. Таким образом получается последовательность, которая отличается от всех последовательностей $\{n_{k}\}$, но все же принадлежит к их множеству. Вот...
Что-то не так со второй частью доказательства.

 Профиль  
                  
 
 Re: Счетные и несчетные множества
Сообщение26.01.2016, 23:32 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Попробуйте позвать дедушек Кантора с Бернштейном.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group