Показать, что $%| \mathbb N_0 | < | \{ 0,1\}^{\mathbb N_0} |$% где $%\{ 0,1\}^{\mathbb N_0}$% множество всех функций $%f:\mathbb N_0 \to \{ 0,1\} $% следующим образом:

  1. Построить инъекцию: $%\mathbb N_0 \to \{ 0,1\}^{\mathbb N_0} $% (Я полагаю, что тут достаточно показать сколько существует возможных схем и привести пример одной из них)
  2. Показать, что не существует сюръекции: $%h:\mathbb N_0 \to \{ 0,1\}^{\mathbb N_0} $%

задан 22 Сен '15 21:18

10|600 символов нужно символов осталось
1

Вообще-то весь этот материал есть в учебниках (теорема Кантора). Но проще повторить основные моменты, чтобы не искать ссылки.

Инъекцию из пункта 1 построить очень просто: каждому $%n\in\mathbb N_0$% сопоставим функцию $%f_n$% из $%\mathbb N_0$% в $%\{0;1\}$%, полагая $%f_n(n)=1$% и $%f_n(m)=0$% при всех $%m\ne n$%. Ясно, что разным значениям $%n$% соответствуют разные функции. Инъекций такого вида имеется очень много, и достаточно рассмотреть самую простую из них.

Во втором пункте рассуждаем от противного. Допустим, что сюръекция $%h$% существует. Для каждого $%n\in\mathbb N_0$% рассмотрим функцию $%h_n\colon\mathbb N_0\to\{0;1\}$% (это значение $%h$% на элементе $%n$%). Положим $%f(n)=0$%, если $%h_n(n)=1$%, и $%f(n)=1$%, если $%h_n(n)=0$%. Получится функция $%f\colon\mathbb N_0\to\{0;1\}$%, причём $%f\ne h_n$% ни при каком $%n$% (по построению, у этих функций разные значения в точке $%n$%). Следовательно, функция $%f\in\{0;1\}^{\mathbb N_0}$% не лежит в образе $%h$%, то есть $%h$% не сюръекция. Противоречие.

ссылка

отвечен 22 Сен '15 21:48

@falcao Большое Спасибо за ответ! Какую литературу вы посоветуете по данной тематике и по комбинаторике тоже?

(22 Сен '15 21:53) Joaquín

@Vinster: здесь трудность состоит в том, что при разных способах изложения могут существенно меняться обозначения. Но если говорить об основных идеях, то они везде те же самые. И тогда имеет смысл почитать что-то на популярном (хотя и вполне строгом) уровне. Например, "Рассказы о множествах" Виленкина.

(22 Сен '15 22:15) falcao

@falcao вопрос по первому пункту: вы сказали, что достаточно рассмотреть самую простую функцию. Но как узнать какая будет самой простой? Не могли бы вы привести пример? Возмем например любую $%{f_n}$% из $%\mathbb N_0$% в $%\{0;1\}$%, предположим что такая функция имеет вид $%{f_n}:A \to \{ 0;1\} $%, тогда множество $%A$% должно состоять из двух элементов $%A = \{ {a_1},{a_2}\} $% где $%{a_1} \ne {a_2}$% и $%f({a_1}) = 0,\,\,f({a_2}) = 1$% или $%f({a_2}) = 0,\,\,f({a_1}) = 1$%. Если в $%A$% больше двух элементов то по принципу Дирихле по меньшей мере два из них будут иметь один и тотже образ.

(23 Сен '15 1:12) Joaquín

@Vinster: здесь не имеется строгого критерия простоты -- это понятие интуитивное. Вместо функций можно говорить о бесконечных последовательностях из нулей и единиц. Надо для каждого n указать свою последовательность. Будем считать, что наличие нулей делает последовательность "проще". Тогда числу n сопоставляется 0...01000... , где n стоит на n-м месте. Вообще, здесь надо подходить так. Пример правильный, он удовлетворяет условию? Да. Можно предложить что-то принципиально лучше? Вроде как нет.

По поводу последнего: если функция задана на $%\mathbb N_0$%, то её область определения бесконечна.

(23 Сен '15 1:33) falcao

@falcao то есть $%\{0,1\}$% это не множество с двумя элементами а бесконечная последовательность из нулей и единиц? Но если мы не знает точного вида такой последовательности то и точный пример функции мы привести не сможет. Достаточно ли тогда тех фактов что вы привели в начале? Я просто не совсем понимаю что значит "построить иньекцию" найти конкретный пример или сделать обобщение...

(23 Сен '15 1:45) Joaquín

@Vinster: Вам надо сначала понять само условие задачи. Конечно, $%\{0;1\}$% есть множество из двух элементов, но $%A^B$% обозначает множество всех отображений (функций) из $%B$% в $%A$%. В нашем случае это отображения из $%\mathbb N_0$% в $%\{0;1\}$%. Каждое такое отображение можно мыслить как бесконечную последовательность нулей и единиц. Значение на элементе n есть n-й член такой последовательности, при нумерации членов с нуля.

Пример функции привести можно -- я же его привёл, и он подходит.

(23 Сен '15 1:52) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×655
×305
×259

задан
22 Сен '15 21:18

показан
565 раз

обновлен
23 Сен '15 1:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru