|
Dec. 22nd, 2008|10:09 pm |
Сравнение мощности множеств
Счётным называют бесконечное множество, элементы которого можно пересчитать, т.е. которое равномощно натуральному ряду.
Та задача слишком простая, конечно (замечу, что доказательство аналогично доказательству того, что счётное объединение счётных множеств счётно). Но в своё время меня впечатлило её простое и элегантное решение. Сейчас дам ещё пару не менее, а даже более красивых задачек.
Множество А более мощное, чем В, если можно биективно отобразить В в подмножество А, но нельзя построить инъективное отображение из А в В.
Элегантная простая задача. Доказать, что множество подмножеств действительных чисел R не равномощно самому R. Кстати, это записывается как |2^R| > |R|.
Подсказка: наиболее известный способ доказательства называется "диагональная процедура".
Если это слишком простая задача, вот посложнее. Доказать, что для любого (бесконечного) множества |2^X| > |X|.
Здесь должна была быть подсказка, но я забыл, как эта теорема доказывается, хехе. |
|