Случайная функция, часть 2
В продолжение темы.
Совместными усилиями мы с deja_vecu доказали, что множество биекций
имеет мощность континуума. Для тренировки попробуйте найти ошибку в следующем рассуждении:
Множество биекций
равномощно множеству всех отображений
.
Построим биекцию между этими двумя множествами. Очевидно, что для любой биекции f существует и единственно представление в следующем виде: f(k) заменяется на номер f(k) в последовательности 1,2,3,... , где вычеркнуты f(1), ..., f(k-1). Пример: 1 2 3 4 5 6 ... → 1 1 1 1 1 1 ...
Аналогично для любой последовательности натуральных чисел строится единственное обратное представление в виде биекции. Следовательно, множество биекций и отображений
равномощно.
1. Множество биекций имеет мощность, большую, чем счетная.
Построим биекцию между множеством подмножеств
, обладающего мощностью континуума, и подмножеством множества биекций. Для этого для каждого x из первого множества поменяем в натуральном ряде 1, 2, 3,... местами элементы
и
. Полученная последовательность всегда соответствует биекции, причем каждая биекция получается не более одного раза. ■
2. Множество отображений
равномощно континууму.
Очевидно, что множество отображений
изоморфно множеству натуральных последовательностей (a1, a2, a3, ...). Составим бесконечную непериодическую (в общем) двоичную дробь:
Очевидно, что так мы можем представить любое вещественное число из (0,1] за исключением его счетного подмножества, члены которого имеют вид
, где
. ■
Вопрос о выборе случайной биекции и вероятность того, что аргумент и значение в ней никогда не совпадут, пока остается открытым.
Совместными усилиями мы с deja_vecu доказали, что множество биекций
имеет мощность континуума. Для тренировки попробуйте найти ошибку в следующем рассуждении:
Множество биекций
равномощно множеству всех отображений
.
Построим биекцию между этими двумя множествами. Очевидно, что для любой биекции f существует и единственно представление в следующем виде: f(k) заменяется на номер f(k) в последовательности 1,2,3,... , где вычеркнуты f(1), ..., f(k-1). Пример: 1 2 3 4 5 6 ... → 1 1 1 1 1 1 ...
Аналогично для любой последовательности натуральных чисел строится единственное обратное представление в виде биекции. Следовательно, множество биекций и отображений
равномощно.
1. Множество биекций имеет мощность, большую, чем счетная.
Построим биекцию между множеством подмножеств
, обладающего мощностью континуума, и подмножеством множества биекций. Для этого для каждого x из первого множества поменяем в натуральном ряде 1, 2, 3,... местами элементы
и
. Полученная последовательность всегда соответствует биекции, причем каждая биекция получается не более одного раза. ■
2. Множество отображений
равномощно континууму.
Очевидно, что множество отображений
изоморфно множеству натуральных последовательностей (a1, a2, a3, ...). Составим бесконечную непериодическую (в общем) двоичную дробь:
Очевидно, что так мы можем представить любое вещественное число из (0,1] за исключением его счетного подмножества, члены которого имеют вид
, где
. ■
Вопрос о выборе случайной биекции и вероятность того, что аргумент и значение в ней никогда не совпадут, пока остается открытым.