Спирина, М.С. Дискретная математика

валентными, или равномощными, А ~ В, если между их элементами можно установить взаимно-однозначное соответствие (биекцию). Тогда И = \В\. Пусть даны два множества А и В. ? Как сравнить эти множества? Каковы критерии оценки множеств? Если они конечны, то сравнивают их мощности, т .е . количе­ ство элементов этих множеств. Обозначим через А, В, С, D соответ­ ственно множества букв слов «крот», «корт», «кран» и «рот». Тог­ да И = |2?| = |С| = 4, \D\ - 3. Отсюда делаем вывод, что А, В и С имеют равные мощности, а мощность D меньше, чем, например, мощ ­ ность A: |Z)| < \А\, так как 3 < 4. Множества А, В и С равномощны. Понятие «равномощные множества» не означает, что они обяза­ тельно равны. Например, среди перечисленных равномощных мно ­ жеств А, В и С множества А и В равны, так как они состоят из одних и тех же элементов, а множества А и С различны. Говорят, что такие равномощные, но не равные множества эквивалентны между собой. Эталоном для сравнения множеств служит натуральный ряд чисел. Поэтому все числовые последовательности, содержащие различные элементы, эквивалентны натуральному ряду чисел, что видно по индексам их членов. Если / : А -> В — инъекция множества А в В, будет справедливо неравенство \А\ > |Д|, а если / : А -> В — сюръекция множества А на В, то справедливо неравен­ ство \А\ < |2?|. Множества можно классифицировать в зависимости от коли ­ чества элементов (их мощности) и характера соответствия нату­ ральному ряду чисел (рис. 1 . 10 ). Множество, содержащее конечное число элементов, называ­ ется конечным. Например, конечным является множество одно ­ значных натуральных чисел {1, 2, 3, 4, 5, 6 , 7, 8 , 9}. Мощность конечного множества из п элементов равна п. Пустое множество 0 по определению не содержит элементов. Оно также является ко ­ нечным и имеет мощность, равную нулю, т.е. |0 | = 0. Множество, не являющееся конечным, называется бесконечным. о . Но как сравнить бесконечные множества? Ведь для них нельзя ука­ зать точное число элементов! Бесконечное множество, эквивалентное множеству натуральных чисел N, называется счетным. Говорят, что все элементы счетного множества можно пронумеровать. В противном случае бесконечное множество будет несчетным. Г. Кантор (1878) доказал, что несчет­ но множество точек, расположенных на отрезке между 0 и 1. По определению Б. Больцано (1837) и Р.Дедекинда (1887) множе­ ство называется бесконечным, если оно равномощно одному из своих собственных подмножеств. Можно доказать эквивалентность 29