Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Эквивалентность множеств. Понятие мощности

Как мы уже отмечали ранее все непустые множества делятся на конечные и бесконечные. Действительно, для некоторых множеств можно точно указать число элементов, содержащихся в данном множестве. Например, для множества всех вершин некоторого многогранника, Для других множеств мы принципиально можем утверждать, что они конечны, хотя фактически указать число элементов не в состоянии. Например, число берез на Земле. С другой стороны, существуют множества, состоящие из бесконечного числа элементов. Например: множество всех натуральных чисел, множество всех точек на прямой, множество всех кругов на плоскости. Любое бесконечное в нашем представлении множество можно охарактеризовать тем, что, удаляя из него любое конечное число элементов, мы не сможем его исчерпать, т. е. в нем при этом всегда останутся элементы.

Любые два конечных множества можно сравнить по числу содержащихся в нем элементов. Можно ли подобным образом сравнивать бесконечные множества? Имеет ли смысл, например, вопрос о том, чего больше: кругов на плоскости или рациональных точек прямой?

Чтобы сравнить между собой два конечных множества, можно, во-первых, сосчитать число элементов в каждом из них; во-вторых, установить взаимно однозначное соответствие между элементами этих множеств, т. е. каждому элементу одного множества сопоставить один и только один элемент другого множества, и обратно. Очевидно, что взаимно однозначное соответствие между двумя конечными множествами можно установить тогда и только тогда, когда число элементов в этих множествах одинаково.

Метод подсчета числа элементов для сравнения бесконечных множеств очевидно не пригоден, но в силу последнего замечания в основу сравнения таких множеств можно положить метод установления взаимно однозначного соответствия между ними.

Простейшим среди бесконечных множеств является множество натуральных чисел.

Определение 1.6. Бесконечное множество А называется счетным. если между ним и множеством натуральных чисел N можно установить взаимно однозначное соответствие. Другими словами, элементы множества А можно перенумеровать числами натурального ряда, т. е.

A={ai,a2,...,an,...}.

Бесконечные множества не исчерпываются счетными, те из них, которые не являются счетными, называются несчетными. Приведем примеры счетных множеств.

П р и м е р 1.3. Убедиться, что счетным является множество целых чисел Z = {..., —п,..., —1,0,1,2,п,...}.

Очевидно, что соответствие, которое каждому неотрицательному числу 0 ставит в соответствие нечетное натуральное число 2п +1, а отрицательному числу п< 0 - четное число 2|п|, является взаимно однозначным между множествами Z и N.

П р и м е р 1.4. Показать, что множество С = {хх = 2п, п ? N} всех положительных степеней двойки является счетным.

Множество С счетное, так как соответствие 2п—>п является взаимно однозначным между множеством С и множеством натуральных чисел N.

П р и м е р 1.5. Показать, что счетным является множество рациональных чисел Q = {хх = п/т: п ? Z, in ? N}.

Действительно, каждое рациональное число х однозначно представимо в виде несократимой рациональной дроби х = п/т. Сумму |п|+ш назовем высотой числа х. Ясно, что множество дробей, имеющих заданную высоту р, конечно. Если нумеровать рациональные числа по возрастанию высоты, то каждое число получит свой номер, т. е. будет установлено взаимно однозначное соответствие между множествами рациональных и натуральных чисел.

Сформулируем некоторые общие свойства счетных множеств.

  • 1. Всякое непустое подмножество счетного множества конечно или счетно.
  • 2. Объединение конечного или счетного множества счетных множеств само является счетным множеством.
  • 3. Всякое бесконечное множество содержит счетное подмножество.

Определение 1.7. Два множества А и В называются эквивалентными (Л~/1), если между ними можно установить взаимно однозначное соответствие.

Очевидно, что для эквивалентных множеств справедливо:

  • 1) А
  • 2) если А^В, то В~А:
  • 3) если А~В и В^О, то А~С.

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

Существование несчетного множества утверждает следующая теорема.

Теорема 1.1. Множество всех действительных чисел, заключенных между нулем и единицей, несчетно.

Доказательство. Предположим противное. Пусть существует некоторое перечисление действительных чисел а, лежащих на отрезке [0,1]:

Здесь djk - к-ая десятичная цифра числа ар. Построим дробь

следующим образом: за Ь примем произвольную цифру, не совпадающую с ап, за 6-2 - произвольную цифру, не совпадающую с аоо, и т. д. Вообще, за Ьп примем произвольную цифру, не совпадающую с апп. Эта десятичная дробь не может совпасть ни с одной дробью, содержащейся в перечне (1.1). Действительно, от ац дробь /3 отличается, по крайней мере, первой цифрой, от второй дроби - второй цифрой и т. д., вообще, так как Ьпфапп для всех п. то дробь (3 отлична от любой из дробей ар, содержащихся в перечне (1.1). Таким образом, никакой перечень действительных чисел, лежащих на отрезке [0,1], не исчерпывает этого отрезка.

Итак, множество точек на отрезке [0,1] несчетно. Приведем примеры множеств, эквивалентных множеству точек отрезка [0,1].

П р и м е р 1.6. Показать, что множество точек любого отрезка [а, Ъ] эквивалентно отрезку [0,1].

Взаимно однозначное соответствие между отрезками [0,1] и [а, Ь] показано на рис. 2 (р <—> с/). Аналогично устанавливается эквивалентность любых двух отрезков.

Рис. 2

Рис. 3

Пример 1.7. Показать, что множество точек отрезка [—1,1] эквивалентно множеству всех действительных чисел.

На рис. 3 показано, что каждой точке р из отрезка [—1,1] взаимно однозначно соответствует точка d на полуокружности, а точке d - точка q числовой прямой, т. е. действительное число (p^q). При этом очевидно, что 0^0, 1 сю, —1 сю. Отметим, что рис. 3 кроме того иллюстрирует эквивалентность отрезка [—1,1] и множества точек полуокружности.

Рассматривая примеры, связанные с бесконечными множествами, можно заметить, что бесконечное множество оказывается эквивалентным своему собственному подмножеству (множество целых и множество натуральных чисел, отрезок [а. Ь и вся числовая прямая). Более того, это обстоятельство является характерным для всех бесконечных множеств. Справедливо следующее утверждение:

Всякое бесконечное множество эквивалентно некоторому своему собствен и юму подлоюжеству.

Это свойство можно принять за определение бесконечного множества, поскольку оно является для него характеристическим.

Два эквивалентных между собой множества (M~N) называют равномощным,и или говорят, что они имеют одинаковую мощность. Таким образом, мощность - это то общее, что присуще всем эквивалентным между собой множествам. Для конечных множеств понятие мощности совпадает с понятием числа элементов. Мощность множества натуральных чисел, а следовательно, и любого счетного множества обозначается No (читается: «алеф нуль»). Мощность всех действительных чисел отрезка [0,1] и всех эквивалентных ему множеств называют континуальной или говорят, что эти множества имеют мощность континуума. Эта мощность обозначается символом с (или символом N).

Для конечных множеств, кроме понятия равенства мощностей имеются понятия «больше» и «меньше». Выясним, можно ли эти понятия распространить на бесконечные множества? Для произвольных множеств А и В обозначим через т(А) и т(В) их мощности. Если А эквивалентно В, то по определению т(А) = т(В). Если А эквивалентно некоторому подмножеству В] С В, а при этом в А нет подмножества, эквивалентного В, то естественно считать, что т(А) <т(В). Однако логически, кроме указанных возможностей, есть еще две:

  • а) BdBi^A, AdAi^B:
  • б) А и В не эквивалентны и ни в одном из них нет подмножеств, эквивалентных другому множеству.

В случае а) множества А и В оказываются эквивалентными друг другу, т. е. т(А) = т(В). Это утверждает следующая теорема.

Теорема 1.2 (Кантора - Бернштейна). Пусть А и В два произвольных множества. Если в А имеется подмножество А], эквивалентное В, а в В имеется подмножество /Д, эквивалентное А, то А и В эквивалентны между собой.

Случай б), который означал бы существование несравнимых между собой мощностей, на самом деле невозможен.

Таким образом, мощности любых двух множеств А и В или совпадают т(А)=т(В), или удовлетворяют одному из двух неравенств:

В связи с тем, что мощности можно сравнивать, возникают следующие вопросы: 1) существуют ли мощности, промежуточные между мощностью «самого маленького» из бесконечных множеств - счетного множества и мощностью континуума; 2) существуют ли множества, мощность которых больше, чем континуальная мощность; 3) вообще, существует ли «наивысшая» мощность? Оказывается, верна следующая теорема.

Теорема 1.3. Пусть М - некоторое множество и S(M) - множество всех подмножеств множества М. Тогда мощность S(M) больше мощности самого множества М.

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

Вопросы и задания для самоконтроля

  • 1. Что такое множество? Перечислите способы задания множеств.
  • 2. Поясните, почему {0}у^0?
  • 3. Является ли а элементом множества [1]?
  • 4. Приведите пример множеств Л, В, С таких, что Л^В,В ?(7, но

А

  • 5. Что такое подмножество?
  • 6. Для множества {1,2,3,4,5,6, 7,8} найдите число а) всех подмножеств; б) трехэлементных подмножеств.
  • 7. Перечислите основные операции над множествами.
  • 8. Докажите, что А СВ, тогда и только тогда, когда ЛПВ = А.
  • 9. Докажите, что Л = В, тогда и только тогда, когда ЛАВ = 9.
  • 10. Докажите равенства: а) Ли В = ЛПВ: б) А(АВ) = АП В;
  • в) АА{ВАС) = {ААВ)АС.
  • 11. Изобразите диаграммы Эйлера - Венна для пересечения и объединения трех множеств.
  • 12. Найдите тах|Л1Ш| и тт|Л1Ш|, если |Л|=п, В=т и т<п.
  • 13. Найдите |ЛПВ|, если |Л| = 10, В = 7. Аи В = 12.
  • 14. Найдите |ЛПВ|, если |Л| = 15, В=9. и В С А.
  • 15. Докажите эквивалентность множеств [0; 1] и (0; 1).
  • 16. Докажите, что объединение счетных множеств является счетным множеством.
  • 17. Укажите мощности множеств Ли В, АпВ, АВ, ВА, если Л конечное множество, а В счетное.

  • [1] а}, {6}, {с
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>