Сколькими способами для мн-ва X можно выбрать функцию выбора, где h: 2^X{пустое мн-во}->X, h(Y) принадлежит Y при Y неравному {пустое мн-во}

задан 26 Июн 10:13

изменен 27 Июн 10:55

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

Здесь нужно использовать известные факты из теории множеств.

Случай конечного множества $%X$% в принципе тоже можно рассмотреть, хотя я думаю, что он здесь не предполагался. Если $%|X|=n$%, то $%k$%-элементных подмножеств имеется $%C_n^k$%. В каждом из них при $%k\ge1$% можно выбрать элемент $%k$% способами, что в итоге даёт произведение $%\prod\limits_{k=1}^nk^{C_n^k}$%.

Пусть $%X$% бесконечно. Покажем, что множество выбирающих функций имеет мощность $%2^{2^X}$%. В силу теоремы Кантора - Бернштейна, достаточно получить одинаковые оценки сверху и снизу. Ясно, что выбирающих функций не больше, чем отображений из $%2^X$% в $%X$%, то есть $%X^{2^X}$%. Так как $%X\preceq2^X$%, получается оценка сверху в виде $%(2^X)^{2^X}\sim2^{X\times2^X}$%. В показателе степени снова имеем не больше $%2^X\times2^X\sim2^{X+X}\sim2^X$%, так как ля бесконечного множества $%X+X\sim X$%. Это даёт оценку $%2^{2^X}$% сверху.

Для оценки снизу заметим, что в подмножестве из более чем одного элемента выбор осуществляется как минимум двумя способами. Фиксируя различные $%a,b\in X$%, рассматриваем все подмножества для $%X\setminus\{a,b\}\sim X$%. Их $%2^X$%, и при двух способах выбора уже получается $%2^{2^X}$%, что даёт оценку снизу.

ссылка

отвечен 27 Июн 2:18

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×883

задан
26 Июн 10:13

показан
100 раз

обновлен
27 Июн 10:55

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

по почте:

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

по RSS:

Ответы

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

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