Счетность множеств

[____]

Доказать, что следующие множества счетны:
-- $\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$

[Joker_vD]

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

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

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

[____]

Цитата:

Если считать, что отображения вы все-таки построили

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

Для второго да, напутал. Должно быть так:
$\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}$

[gefest_md]

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

[____]

gefest_md в сообщении #882166 писал(а):

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

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

[gefest_md]

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

[iifat]

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

[____]

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

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

Соглашусь. и

Цитата:

равносильны

? Из инъекции $f: A \to \mathbb{Z}^+$ следует биективность ?

[gefest_md]

Идея решения первой задачи хорошая. Надо только записывать всё аккуратно. Пусть $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}^+$ следует биективность ?

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

[____]

Цитата:

Идея решения первой задачи хорошая. Надо только записывать всё аккуратно. Пусть $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|$ был доказан в пред. задаче.

[gefest_md]

____ в сообщении #882192 писал(а):

если $f$ биекция, то требует ли еще доказательства тот факт, что $f^{-1}$ тоже биекция ?

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

[____]

Цитата:

$\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}$

[gefest_md]

Доказательство биективности функции $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}$

[____]

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}$

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

[Lia]

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
Замечание за полное решение простой учебной задачи.