2014 dxdy logo

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

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


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


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

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

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

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

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



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


17/06/14
17
Доказать, что следующие множества счетны:
-- $\mathbb{N} \setminus \{12345\}$
-- $\mathbb{Z}$

Для первого множества: если $|A| = |\mathbb{N}|$ и $f$ -- биекция между ними, а $B \subset A$ конечно и непусто, то $A \setminus B$ счетно. Если $B$ конечно и непусто, то оно равномощно $\{1, 2, 3, ..., n\}$ для некоторого $n_B$. Тогда $\forall a \in A \setminus B$ биекцией в $\mathbb{N}$ будет $a=f(a)-n_B$

Для $\mathbb{Z}$. $n = \frac{-n}{2}$ для четных $n \in \mathbb{N}$ и $n = \frac{n-1}{2}$ для нечетных $n \in \mathbb{N}$.
Обратными для $n \ge 0$ будет $2n+1$, для $n < 0$ будет $(-2)n$

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


09/09/10
3729
Если считать, что отображения вы все-таки построили, то во втором пункте оно все-таки не биекция, у вас $0\in\mathbb N$ и $1\mathbb N$ отображаются в $0\in\mathbb Z$.

-- Пн июн 30, 2014 05:12:01 --

То есть, я-то понял, что вы хотели сказать ("четное числа — в свой взятый с минусом номер в ряду четных чисел, нечетные — в свой номер в ряду нечетных чисел"), но оформление у вас все-таки ужасное. "$n=\frac{-n}{2}$"?

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 04:57 


17/06/14
17
Цитата:
Если считать, что отображения вы все-таки построили

А что в таком случае значит "построить отображение" ?

Для второго да, напутал. Должно быть так:
$\forall x \in \mathbb{Z}: f \left({x}\right) = \begin{cases} 2x - 1 : x < 0 \\ - 2x  : x \le 0 \end{cases}$

-- 30.06.2014, 06:18 --

Joker_vD в сообщении #882162 писал(а):
"$n=\frac{-n}{2}$"?

$n \mapsto -\frac{n}{2}$

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 05:47 
Аватара пользователя


01/12/06
697
рм
В первой задаче мне кажется удобно и интересно воспользоваться теоремой одной и определить сюръекцию только лишь.

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 06:04 


17/06/14
17
gefest_md в сообщении #882166 писал(а):
В первой задаче мне кажется удобно и интересно воспользоваться теоремой одной и определить сюръекцию только лишь.

У меня есть шансы до нее дойти самому ?

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 06:36 
Аватара пользователя


01/12/06
697
рм
Теорема. Пусть $A$ - множество. Следующие предложения равносильны:
1. $A$ - счётно.
2. $A=\varnothing$ или существует сюръекция $f\colon\mathbb{Z}^+\to A.$
3. Существует инъекция $f\colon A\to\mathbb{Z}^+.$

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


16/02/13
4105
Владивосток
Что-то я, простите, не понимаю. Из п.2 следует, что пустое множество счётно, нет? Вы действительно так считаете?

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 08:09 


17/06/14
17
iifat в сообщении #882177 писал(а):
Что-то я, простите, не понимаю. Из п.2 следует, что пустое множество счётно, нет? Вы действительно так считаете?

Соглашусь. и
Цитата:
равносильны
? Из инъекции $f: A \to \mathbb{Z}^+$ следует биективность ?

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 08:10 
Аватара пользователя


01/12/06
697
рм
Идея решения первой задачи хорошая. Надо только записывать всё аккуратно. Пусть $A=\mathbb{Z}^+\setminus\{1,\ 2,\ 3,\ 4,\ 5\}$.
Тогда $f\colon A\to\mathbb{Z}^+,\ f(n)=n-5$ - очевидно биекция. Тогда можно доказать, что (искомая) $f^{-1}\colon\mathbb{Z}^+\to A$ - тоже биекция.

Идея второй задачи тоже известная: определите счётность не через $\mathbb{N}\cup\{0\}$, а через $\mathbb{Z}^+.$

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

-- Пн июн 30, 2014 07:20:21 --

____ в сообщении #882177 писал(а):
Из инъекции $f: A \to \mathbb{Z}^+$ следует биективность ?

Существование биекции. Да.

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 09:35 


17/06/14
17
Цитата:
Идея решения первой задачи хорошая. Надо только записывать всё аккуратно. Пусть $A=\mathbb{Z}^+\setminus\{1,\ 2,\ 3,\ 4,\ 5\}$.
Тогда $f\colon A\to\mathbb{Z}^+,\ f(n)=n-5$ - очевидно биекция. Тогда можно доказать, что (искомая) $f^{-1}\colon\mathbb{Z}^+\to A$ - тоже биекция.

Спасибо, а если $f$ биекция, то требует ли еще доказательства тот факт, что $f^{-1}$ тоже биекция ? В задаче нужно доказать равномощность, что есть существование биекции, а т.к. $f$ очевидно ею является, то задача решена !?

P.S. Факт о том, что если $|A|=|B|$, то $|B|=|A|$ был доказан в пред. задаче.

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 10:00 
Аватара пользователя


01/12/06
697
рм
____ в сообщении #882192 писал(а):
если $f$ биекция, то требует ли еще доказательства тот факт, что $f^{-1}$ тоже биекция ?

Действительно, воспользуетесь теоремой о симметричности отношения равномощности.

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 12:39 


17/06/14
17
Цитата:
$\forall x \in \mathbb{Z}: f \left({x}\right) = \begin{cases} 2x - 1 : x < 0 \\ - 2x : x \le 0 \end{cases}$


$\forall x \in \mathbb{Z}: f \left({x}\right) = \begin{cases} 2x - 1 : x > 0 \\ - 2x : x \le 0 \end{cases}$

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение30.06.2014, 14:47 
Аватара пользователя


01/12/06
697
рм
Доказательство биективности функции $f\colon A\to\mathbb{Z}^+,\ f(n)=n-5$:

1. $\forall n_1\in A\forall n_2\in A(f(n_1)=f(n_2)\to n_1=n_2)$ (инъективность).
Пусть $n_1,n_2\in A$ и $f(n_1)=f(n_2).$ Тогда $n_1-5=n_2-5.$ Тогда $n_1=n_2$, ч.т.д.

2. $\forall m\in\mathbb{Z}^+\exists n\in A(f(n)=m)$ (сюръективность).
Пусть $m\in\mathbb{Z}^+.$ Пусть $n=m+5.$ Тогда $n\in\{x\mid x\in\mathbb{Z}^+\wedge x\geqslant 6\}$, т.е. $n\in A$ и $f(n)=n-5=(m+5)-5=m$, ч.т.д.

Доказал, что $A$ равномощно $\mathbb{Z^+}$ (пишу $A\sim\mathbb{Z}^+$). Отношение равномощности симметрично, поэтому $\mathbb{Z}^+\sim A$, т.е. $A$ - счётно.

____ в сообщении #882155 писал(а):
Обратными для $n \ge 0$ будет $2n+1$, для $n < 0$ будет $(-2)n$

Это не нужно. Докажите, что биективна функция

$f\colon\mathbb{Z}^+\to\mathbb{Z},\ f(n)=\begin{cases}\frac{n}{2}, n-\text{чётно},\\ \frac{1-n}{2}, n-\text{нечётно}.\end{cases}$

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение01.07.2014, 01:32 


17/06/14
17
gefest_md в сообщении #882266 писал(а):
Доказательство биективности функции $f\colon A\to\mathbb{Z}^+,\ f(n)=n-5$:

1. $\forall n_1\in A\forall n_2\in A(f(n_1)=f(n_2)\to n_1=n_2)$ (инъективность).
Пусть $n_1,n_2\in A$ и $f(n_1)=f(n_2).$ Тогда $n_1-5=n_2-5.$ Тогда $n_1=n_2$, ч.т.д.

2. $\forall m\in\mathbb{Z}^+\exists n\in A(f(n)=m)$ (сюръективность).
Пусть $m\in\mathbb{Z}^+.$ Пусть $n=m+5.$ Тогда $n\in\{x\mid x\in\mathbb{Z}^+\wedge x\geqslant 6\}$, т.е. $n\in A$ и $f(n)=n-5=(m+5)-5=m$, ч.т.д.

Доказал, что $A$ равномощно $\mathbb{Z^+}$ (пишу $A\sim\mathbb{Z}^+$). Отношение равномощности симметрично, поэтому $\mathbb{Z}^+\sim A$, т.е. $A$ - счётно.

____ в сообщении #882155 писал(а):
Обратными для $n \ge 0$ будет $2n+1$, для $n < 0$ будет $(-2)n$

Это не нужно. Докажите, что биективна функция

$f\colon\mathbb{Z}^+\to\mathbb{Z},\ f(n)=\begin{cases}\frac{n}{2}, n-\text{чётно},\\ \frac{1-n}{2}, n-\text{нечётно}.\end{cases}$

Да, с этим, кажется, все понятно теперь, спасибо.

 Профиль  
                  
 
 Re: Счетность множеств
Сообщение01.07.2014, 01:50 


20/03/14
12041
gefest_md в сообщении #882266 писал(а):
Доказательство биективности функции $f\colon A\to\mathbb{Z}^+,\ f(n)=n-5$:

1. $\forall n_1\in A\forall n_2\in A(f(n_1)=f(n_2)\to n_1=n_2)$ (инъективность).
Пусть $n_1,n_2\in A$ и $f(n_1)=f(n_2).$ Тогда $n_1-5=n_2-5.$ Тогда $n_1=n_2$, ч.т.д.

2. $\forall m\in\mathbb{Z}^+\exists n\in A(f(n)=m)$ (сюръективность).
Пусть $m\in\mathbb{Z}^+.$ Пусть $n=m+5.$ Тогда $n\in\{x\mid x\in\mathbb{Z}^+\wedge x\geqslant 6\}$, т.е. $n\in A$ и $f(n)=n-5=(m+5)-5=m$, ч.т.д.

Доказал, что $A$ равномощно $\mathbb{Z^+}$ (пишу $A\sim\mathbb{Z}^+$). Отношение равномощности симметрично, поэтому $\mathbb{Z}^+\sim A$, т.е. $A$ - счётно.

 !  gefest_md
Замечание за полное решение простой учебной задачи.

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

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



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

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


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

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