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

Эту же важную формулу можно доказать, используя для каж ­ дого элемента множества А отдельный символ (подробнее об ал ­ фавитах см. в гл. 6 ). Булеаном множества М назовем множество всех его подмно­ жеств, которое обозначается 2м, т.е. 2м - {А\А с М). Можно дока ­ зать, что для конечного множества М мощность булеана \2М\ = 2|л/1 В частности, множество всех подмножеств любого конечного множества, состоящего из п элементов, является конечным м но ­ жеством, состоящим из 2я элементов. Так как множество целых чисел Z счетно, то надо показать, что оно эквивалентно нату­ ральному ряду чисел, т.е. надо пронумеровать все его элементы. 0 1 Но как это сделать, если числовая прямая бесконечна и влево от нуля, и вправо: (Z = {..., -3, -2, -1 , 0, 1 , 2, 3,...})? Для установления соответствия между целыми и натуральны­ ми числами будем чередовать положительные и отрицательные числа, начиная от нуля. Тогда индекс элементов полученной п о ­ следовательности указывает на соответствующее натуральное число: й[ = 0, а2 - 1) аъ = ^4 = 2, а5 = -2 , а6 = 3, а2 = -3 , ..., а2„ = л, а 2п+1 = -«••• Для конечных множеств справедливо утверждение, которое называется основной теоремой о конечных множествах. Теорема. Любое конечное множество не эквивалентно никакому его собственному подмножеству, кроме самого себя. Следствие. Всякое непустое конечное множество эквивалентно одному и только одному отрезку натурального ряда чисел { 1 , ..., п). Тогда мощность конечного множества совпадает с количеством его элементов. Например, мощность множества сторон пятиуголь­ ника равна 5. Из любого бесконечного множества можно выделить счетное подмножество. Так, счетными являются множество Z целых чисел и Q рациональных чисел. Но множество К действительных чисел несчетно. Счетным будет и множество квадратов натуральных ч и ­ сел {1, 4, 9, 16, ...}, так как каждому квадрату можно поставить в соответствие единственное натуральное число п, соответствую­ щее его порядковому номеру. Поскольку для бесконечных множеств нельзя указать число, которое является его мощностью, то будем их сравнивать по э к ­ вивалентным им основным множествам N и К. Всякое бесконечное множество, равносильное множеству д ей ­ ствительных чисел, называется множеством мощности континуу­ ма (от лат. continuum — непрерывный). Поэтому для сравнения мощности множеств с множеством действительных чисел R бу ­ дем употреблять условное обозначение |R| как символ мощности континуума. 31