Подскажите как определить мощность множества

[Dialectic]

Чему равна мощность множества всех отображений натурального ряда в себя?
Если "счётно" то подскажите пожалуйста как можно это доказать.

[AD]

Для начала, зацените мощность множества всех отображений натурального ряда в своё подмножество {1,2}.

[Dialectic]

AD писал(а):

Для начала, зацените мощность множества всех отображений натурального ряда в своё подмножество {1,2}.

Не могу нечего заценить. У меня такая проблема: я вообще не могу понять как можно нумеровать такие обьекты как функции. Как можно нумеровать яблоки мне понятно, а как закономерности - нет.

[ewert]

<было вставлено по рассеянности>

[AD]

Dialectic в сообщении #179332 писал(а):

У меня такая проблема: я вообще не могу понять как можно нумеровать такие обьекты как функции.

Ну так в таком случае с этого и надо было начинать.

Прежде всего, функция - это не "закономерность"; это множество специального вида. Так что нумеруем мы множества. Но это в задаче не важно.

Далее, вспомните, что значит "нумеровать". Что такое взаимно однозначное соответствие. Это функция такая, но не совсем любая.

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

Подумайте о том, что такое "характеристическая функция" подмножества, и как она может быть полезна. После этого Вы сможете осознать моё предыдущее сообщение.

Еще Вам почти наверняка пригодится теорема Кантора-Бернштейна. Тоже придётся вспомнить и осознать. Без неё никуда.

[Really]

Dialectic в сообщении #179332 писал(а):

Не могу нечего заценить. У меня такая проблема: я вообще не могу понять как можно нумеровать такие обьекты как функции.

Нумеровать в данном случае не обязательно. А вот установить биекцию между всеми отображениями $f:\mathbb N\to \{0,1\}$ и множеством $\displaystyle 2^{\mathbb N}$ проще
простого.

[Dialectic]

AD писал(а):

Подумайте о том, что такое "характеристическая функция" подмножества, и как она может быть полезна. После этого Вы сможете осознать моё предыдущее сообщение.

Еще Вам почти наверняка пригодится теорема Кантора-Бернштейна. Тоже придётся вспомнить и осознать. Без неё никуда.

Всё кроме этих двух моментов вспомнил. Не могли бы кратко напомнить о чём там речь?
Вот Вы говорите, что функции это множества. Я так понимаю, что речь идёт о бинарном отношении т.е. подмножестве Декартого произведения, обладающего определёнными свойствами. Поэтому функцию можно рассматривать как множество упорядоченых пар
вида f= <x,y> , где выполнены следующие условия, а именно: для любого элемента из области определения бинарного отношения существует только один элемент из области значения бинарного отношения. С самого начала, я хотел действовать так: пусть например
даны две различные функции:
1.$ F_1={<1,a_1>,<2,a_2>,...,<n,a_n>..>$
2.$ F_2={<1,b_1>,<2,b_2>,...,<n,b_n>..>$
так как функции различны, то они различны хотя-бы в одной паре. т.е. для некоторого k
верно,что $<k,b_k> <> <k,a_k>$. Значит, в этом сотоит уникальная специфика этих функций.
Тогда я собирался присвоить каждой такой функции, некоторый номер например $p=k+x_k$.
Но потом я быстро понял, что такой номер не будет уникальным - существует много функций
с одним и тем же номером. Поэтому биекции не получается. На этом и застрял.

Добавлено спустя 7 минут:

Really писал(а):

Dialectic в сообщении #179332 писал(а):

Не могу нечего заценить. У меня такая проблема: я вообще не могу понять как можно нумеровать такие обьекты как функции.

Нумеровать в данном случае не обязательно. А вот установить биекцию между всеми отображениями $f:\mathbb N\to \{0,1\}$ и множеством $\displaystyle 2^{\mathbb N}$ проще
простого.

Я закончил университет 7 лет назад. Я уже ничего не помню. Что такое $\displaystyle 2^{\mathbb N}$? Множество двоичных последовательностей? Нельзя ли проще объяснить?

Добавлено спустя 5 минут 28 секунд:

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

[AD]

Если $X$ - множество, а $A$ - его подмножество, то характеристической функцией множества $A$ как подмножества $X$ называется функция $\chi_A:X\to\{0,1\}$,
$\chi_A(x)=\begin{cases}1,&x\in A\\0,&x\notin A\end{cases}$
Несложно установить взаимно-однозначное соответствие между множеством таких функций и множеством подмножеств $X$.

Теорема Кантора-Бернштейна.С её помощью можно разбить задачу на две: на оценку мощности "снизу" и "сверху". Оценку снизу вот только что мы с Really разжевали донельзя. Теперь надо устроить оценку сверху. Это несколько менее тривиально. Предлагаю Вам с этой целью устроить вложение вашего множества в множество подмножеств множества натуральных чисел.

[Really]

Dialectic в сообщении #179346 писал(а):

Я закончил университет 7 лет назад. Я уже ничего не помню. Что такое $\displaystyle 2^{\mathbb N}$? Множество двоичных последовательностей? Нельзя ли проще объяснить?

$2^{\mathbb N}$ - множество всех подмножеств множества $\mathbb N$. Обозначение
стандартное. Посмотрите, например Булеан и Мощность множества

[kim4ik_kor]

Помогите решить:
Какова мощность семейства рекурсивно перечислимых,но не рекурсивных подмножеств w(омега)?

[Профессор Снэйп]

kim4ik_kor в сообщении #389862 писал(а):

Помогите решить:
Какова мощность семейства рекурсивно перечислимых,но не рекурсивных подмножеств w(омега)?

Наш пострел везде поспел

Открывайте лекции и учите теорию. На крайний случай есть Гугл и Википедия.

[Kira-sempai]

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

Могу только предположить, что это |2^(алеф-1)|

[Профессор Снэйп]

Kira-sempai в сообщении #426850 писал(а):

Требуется найти мощность множества всех конечных подмножеств множества мощности континуума.

Если $A$ бесконечно, то множество $\mathcal{P}_{\mathrm{fin}}(A)$ всех конечных подмножеств множества $A$ имеет ту же мощность, что и само $A$.

Так что ответ очевиден

-- Чт мар 24, 2011 12:40:50 --

Kira-sempai в сообщении #426850 писал(а):

Могу только предположить, что это |2^(алеф-1)|

Лучше не надо!!! Предположения --- не самая сильная Ваша сторона

[Kira-sempai]

Спасибо большое) Учту совет)
Да, в принципе, если так трактовать, то тогда все вроде понятно

[Профессор Снэйп]

Лемма. Пусть $A_0$ бесконечно и для любого $i \in \mathbb{N}$ выполняется $|A_0| \geqslant |A_i|$. Тогда

$$ |A_0| = \left| \bigcup_{i \in \mathbb{N}} A_i \right| $$

Доказательство. Для каждого $i \in \mathbb{N}$ зафиксируем инъекцию $f_i : A_i \to A_0$. Пусть для $x \in \bigcup_{i \in \mathbb{N}} A_i$ выражение $k_x$ означает минимальный $k$, для которого $x \in A_k$. Пусть $h$ --- инъекция $\mathbb{N}$ в $A_0$. Тогда $x \mapsto \langle h(k_x), f_{k_x}(x) \rangle$ --- инъекция $\bigcup_{i \in \mathbb{N}} A_i$ в $A_0 \times A_0$. $\qed$

Следствие. Для бесконечного множества $A$ множество $A^{<\omega}$ всех конечных последовательностей, составленных из элементов $A$, имеет ту же мощность, что и само $A$.

Доказательство. $A^{<\omega} = \bigcup_{k \in \mathbb{N}} A^k$ $\qed$

Следствие. Для бесконечного $A$ множество $\mathcal{P}_{\mathrm{fin}}(A)$ всех конечных подмножеств множества $A$ имеет ту же мощность, что и $A$.

Доказательство. Отображение $\langle a_1, \ldots, a_k \rangle \mapsto \{ a_1, \ldots, a_k \}$ есть сюрьекция $A^{<\omega}$ на $\mathcal{P}_{\mathrm{fin}}(A)$ $\qed$