XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 16
Текст из файла (страница 16)
Таким образом, множество Я счетно. ~ 1ОО П МНОЖЕСТВА И ОТНОШЕНИЯ В заключение приведем сводку результатов по мощностям некоторых конечных множеств. Теорема 1.22. Если М и Ф вЂ” конечные множества и ~М~ =т, а )Ф~ =п, то: 1) мощность множества всех отображений М в Ф равна пт; 2) мощность множества всех биекций ю Ф на себя равна Рн из 3) мощность множества всех инъекций ю М в Ф (т < и) и! равна А н (и т)ю~ 4) мощность множества всех подмножеств множества Ж равна 2"; 5) мощность множества всех к-элементных подмножеств множества Ф равна С„= „, » 6) мощность прямого произведения М х Ж равна тп.
Напомним Щ, что в комбинаторике число Р„называют числом перестановок и элементов, число А~~ — числом размещений без повторений из п элементов по п1, число С» (обозначаемое также (",)) — числом сочетаний из и элементов по к. Эти числа называются также биномиальными коэффиииэнтами, поп скольку (а+ Ь)" = ~~~ С»а" ~Ь (формула бинома Ньютона). »=о Дополнение 1.1. Об одном парадоксе теории множеств Задавал с помощью коллективизируищих свойств множества, следует иметь в виду, что не каждое высказывание опре.
деляет коллективизирующее свойство. Попробуем определить множество У = (Х: Х ф Х) — множество всех множеств, не являющихся элементами самих себя. Это множество не пусто. Те „нормальные" множества, с которыми мы привыкли иметь дело, например числовые, как раз не являются элемента- Д.1.1. Оо одпом парадоксе теорие множеств 1О1 ми самих себя: множество К всех действительных чисел не есть действительное число! Однако попытка определить множество всех множеств, которые не являются элементами самих себя, приводит к противоречию.
В самом деле, пусть У не является элементом самого себя, т.е. У ф У. Тогда, поскольку У есть множество всех множеств, не являющихся элементами самих себя, У Е У. В то же время, если У Е У, оно должно обладать свойством, которое указано в определении У как коллективизирующее, т.е. должно выполняться У ф У. Следовательно, мы доказали, что У ф У дь У Е У1 Это противоречие показывает, что высказывание о множествах Х ф Х не задает коллективизирующее свойство.
Указанный парадокс, называемый парадомсоде Расее,аа, приводится иногда в такой „сказочно-шутливой" редакции: еВ некоторой деревне живет брадобрей, который по долгу службы должен брить тех и только тех, кто не бреет себя сам". Брадобрей оказывается в незавидном положении: если он не будет себя брить, то тотчас окажется, что он должен себя брить, а следуя неумолимой инструкции, он немедленно должен прекратить бриться, ибо он будет брить себя сам, что запрещено.
Парадокс Рассела показывает, что интуитивное понимание множества и коллективизирующего свойства позволяет трактовать идею множества настолько широко и расплывчато, что может привести к противоречиям. Замечание 1.8. Не следует путать высказывание, определяющее пустое множество (например, „х есть четное число, не давпцееся на два"), и высказывание, не задающее коллективиэирующего свойства. Первое коллективвзирует, определяя пустое множество, а второе приводит к противоречию, не определяя никакого множества, в том числе и пустого. Обсуждение возможных путей выхода из противоречий, подобных парадоксу Рассела, не является предметом данного 102 1. МНОЖЕСТВА И ОТНОШЕНИЯ учебника". Мы же только заметим, что ввиду парадокса Рассела мы не можем мыслить конструкции, подобные множеству всех множеств, которые не являются элементами самих себя, в законченном виде, т.е.
считать, что нам сразу, одновременно представлены в наличии все мыслимые множества указанного вида. Вместо этого следует представлять себе процесс (обратим внимание на это слово!) порождения новых множеств (назовем их допустимыми), исходя нз определенного набора „исходных" допустимых множеств. К ним, в частности, можно отнести известные числовые множества, все конечные множества.
Важно понимать также, что укаэанный вьппе процесс никак не влияет на „объем" уже имеющихся допустимых множеств: все они жестко зафиксированы и „состав" их элементов никак не меняется. Всякое уже имеющееся допустимое множество всегда „равно самому себе". Но совокупность всех допустимых множеств меняется при порождении новых допустимых множеств из уже имеющихся, и именно поэтому она не может считаться множеством, ибо состав ее элементов не зафиксирован. Считая, что исходные допустимые множества как-то заданы, мы должны регламентировать операции, которые позволяют из уже имеющихся допустимых множеств строить новые допустимые множества. Такими операциями являются рассмотренные в главе 1 операции над множествами, в частности образование неупорядоченной и упорядоченной пары, булеана и фантпор-мноэсестпеа.
Дополнение 1.2. Метод характеристических функций Доказательство сложных теоретико-множественных тождеств методом двух включений часто бывает довольно громоздким, и при построении доказательства ход рассуждений 'Смс Архангельский А.А.; Шскфилд Дкс.; Киивиьввскиа К., Мвстпввскиа А.; Кви Н. Д.1.2. Метод характеристических фуикцют 10З не всегда очевиден. Одним из методов, не требующих „угадыванияе пути доказательства, является деетпод варпкеперистпических Функций. Харпктперистпическая функция Хл аеноксестпва А С У есть функция, отображающая универсальное мноэсестпео У в двухэлементное множество (О, 1): (1, яЕА; Хл(Я) = ~ ' ХА(Я) = ХА(Я). (1.10) Выразим характеристическую функцию пересечения множеств А и В через характеристические функции Хл(я) и ХВ(х) этих множеств.
Из определения пересечения следует, что искомая характеристическая функция должна принимать значение 1 для тех элементов х, которые принадлежат множествам А и В одновременно, и значение 0 в противном случае. Легко видеть, что функция ХАЕВ(х) = ХА(я)ХВ(х) удовлетворяет этому требованию. Можно предположить, что характеристическая функция объединения множеств А и В будет равна сумме характеристических функций множеств. Однако так ее определить нельзя, поскольку для элементов х Е А и В такая сумма будет иметь значение 2.
Введем „поправку" и в результате получим искомую формулу: Хлив(Я) = Хл(*) + Хв(*) - Хл(Я) ХВ(*). Непосредственно иэ определения А — дополнения множе. ства А — следует, что ХА(я) = 1 ХА(в). Из определения характеристической функции множества А вытекает справедливость тождества 104 1. МНОЖЕСТВА И ОТНОШЕНИЯ Для развостии А 1 В характеристическая функция имеет вид ХА~В(Х) ХА(Х) ХА(Х)ХВ(Х)) а для симметрической разности АЬВ— ХАЕВ(х) = ХА(х) + ХВ(х) 2ХА(х)ХВ(х). Отметим, что последнюю формулу можно получить, опираясь на свойство 19 (см. с. 35) и тождество (1.10), а также на характеристические функции для пересечения, объединения и разности: ХАЕВ(х) = Х(Аов)~(АоВ) (х) = = ХАЕВ(х) — ХАЕВ(х)ХАоВ(х) = = ХА(Х) +ХВ(Х) ХА(Х)ХВ(Х) (ХА(Х) + ХВ(Х) ХА(Х)ХВ(Х))ХА(Х)ХВ(Х) ш = ХА(Х) + ХВ(Х) — ХА(Х)ХВ(Х)- (ХА(Х)3~В(Х) + ХА(Х)ХВ(Х) ХА(Х)ХВ(Х)) = = ХА(Х) + ХВ(х) — 2ХА(Х) ХВ(Х).
С учетом равенства (1.10) полученную формулу можно записать в виде ХАЕВ(Х) =(ХА(Х)-ХВ(Х)) . Метод характеристических функций доказательства справедливости теоретико-множественного тождества заключается в выражении характеристических функций обеих его частей через характеристические функции входящих в него множеств. Тождество верно тогда и только тогда, когда характеристические функции левой и правой частей совпадают. Пример 1.22. Используя метод характеристических функций, выясним, справедливо ли тождество (АЬВ) П С = (А й С) Ь(В и С). Д.е.2.
Метод хврвктеркеткчееккх фуккякй 105 С одной стороны, Х(Аьв)ос(х) ХАЙВХс(х) = (ХА(х) + Хв(х) -2ХА(х) Хв(х)) Хс(х) = = ХА(х)Хс(х) + Хв(х)ХС(х) -2ХА(х)Хв(х)Хс(х). С другой стороны, Х(Аос)Ь(вос)(х) = = ХАос(х) + Хвпс(х) — 2ХАпс(х)хвпс(х) = = ХА(х)ХС(х) + Хв(х)ХС(х) — 2ХА(х)Хс(х) Хв(х)Хс(х) = = ХА(х) Хс(х) + Хв(х) Хс(х) — 2ХА(х) Хв(х) Хс(х). Характеристические функции левой и правой частей тождества совпадают. Следовательно, тождество верно. Пример 1.23.
Выясним, является ли тождеством следующее выражение: А~(В~С) =(А~В)~С. С одной стороны, ХА~(В1с)(х) = ХА(х) ХА(х)ХВ1с(х) = ХА(х) — ХА(х)(ХВ(х) — Хв(х)Хс(х)) = = ХА(х) ХА(х)ХВ(х) +ХА(х)ХВ(х)Хс(х). С другой стороны, Х(А1в)1С(х) = ХАЕВ(х) — ХАЕВ(х)ХС(х) = = ХА(х) — ХА(х)Хв(х) — (ХА(х) — ХА(х)ХВ(х))ХС(х) = = ХА(х) ХА(х)ХВ(х) ХА(х)Хс(х) + ХА(х)ХВ(х)Хс(х). Легко видеть, что получены разные характеристические функции.
Например, при х Е А, х ф В и х Е С ХАЕВ,с)(х) = 1, а Хр~в11С(х) = О. Таким образом, доказано, что А 1(В 1С) ~ ~ (А1В) 1С. 106 Е МНОЖЕСТВА и ОТНОШЕНИЯ Отметим, что метод характеристических функций не является универсальным. Так, его нельзя использовать при доказательстве тождеств, содержащих декартово произведение множеств, в частности, тождеств для соответствий (бинарных отношений).
Вопросы и задачи 1.1. Найти П Х„, если: а) Х„= [--, -]; б) Х„= [О, -~; я=1 в) Хп-(ОФ Ч. 1.2. Используя методы двух включений и характеристических функций, доказать свойства 1-18 (см. с. 35). 1.3. Доказать тождества: а) А х (В П С) = (А х В) П (А х С) > б) (АПВ) х (СПР) =(Ах С)П(В х Р). Проиллюстрировать графически, приняв в качестве множеств А, В, С и Р отрезки числовой прямой. 1.4. Доказать, что если (А С Х) и (В С У), то (А х В) С С (Х х У). 1.5. Показать, что (А х В) ф А х В. Вывести соответствующее тождество. 1.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
