ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ - Александр Соловьев

Оцените математическую красоту фразы:

Любой элемент, принадлежащий множеству, не содержащему ни одного элемента, принадлежит и любому другому множеству, которое не содержит ни одного элемента.

Чуть менее красива фраза:

Любое множество является собственным подмножеством.

Или то же самое, но более жестоко:

Любое множество включено само в себя.

Действительно, группа ух-002 (в которой, вполне возможно, есть студенты) включена в группу ух-002, поскольку все студенты, которые в ней числятся по-прежнему числятся в ней, даже если ее название ух-002 упоминается несколько раз.

Из последнего примера можно сделать важный вывод. Если два множества (возможно на первый взгляд различные, вроде множества чиновников и множества слуг народа) включены друг в друга, то эти множества равны – то есть состоят из одних и тех же элементов.

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

А как же иначе?!…

Правда, есть математики-диссиденты, которые это не признают. Но это скорее уже вопрос веры… другой математической конфессии…

А теперь следует признать, что математики сродни той категории больных людей, которых называют «правдоискателями». Как правило искатели (социальной) правды правы. Но их правота или бессмысленна, или нереальна, а главное, никому кроме них не нужна… Так вот и в теории множеств часто можно найти правду, которая для посторонних людей может выглядеть, мягко выражаясь, странной и вредной.

Например, студент Хведоров не может быть подмножеством студентов университета, поскольку он сам не множество, а элемент. Поэтому он, как элемент, может быть лишь элементом множества студентов университета. А вот группа ух-003, как множество студентов, есть полноправное подмножество множества студентов университета. Но группа ух-003 состоит всего лишь из одного неотчисленного студента. Того самого Хведорова! Вот и получается, что сам Хведоров не может быть подмножеством, но группа, состоящая из него одного, может.

С другой стороны, если вдруг ректор решит рассматривать университет, как множество студенческих групп, то группа ух-003 станет элементом множества студенческих групп университета. Тут ничего страшного, если понимать, что множество студентов университета и множество студенческих групп университета – два разных множества.

Впрочем, нас бюрократическими закорючками не удивишь мы и не такое в жизни видим каждый день…

Но, все-таки, теории множеств есть чем удивить даже нас. Это, так называемые парадоксы теории множеств – одно из потрясений первого года прошлого столетия для узкого круга людей.

Поясним на знаменитом примере про брадобрея.

Правитель (вроде Петра I) повелел единственному брадобрею в своем царстве-государстве брить всех тех и только тех, кто не бреется сам. А наказание за ослушание – казнь. Вот брадобрей и бросился брить всех небритых. В конце-концов дошло до того, что он сам зарос бородой… Он взял бритву. Но если он начнет бриться, значит он бреется сам, а таких он брить не имеет права.

Отложив бритву, он понял, что он сам не бреется. Значит он должен взять бритву и… И что?! А ничего хорошего! Казнят бедолагу за нарушение приказа в любом случае!

С точки зрения теории множеств брадобрей в данном случае не смог определиться с (фундаментальным!) отношением принадлежности: включать или не включать себя самого в множество тех, кто не бреется сам.

То есть в основе теории множеств, которая претендует на роль фундамента ВСЕЙ математики, начальное базовое отношение принадлежности выкидывает такие фортеля, которые просто не позволяют создать некоторые из множеств!… Математики приняли единственное разумное решение: Договорились не создавать в рамках теории множеств такие множества, которые нельзя создать!

То есть теория множеств оперирует со всеми множествами, кроме тех, которые нельзя создать. Все эти множества, об'единенные в одно множество, называются УНИВЕРСУМОМ.

Лекция 2. БЕСКОНЕЧНОСТЬ БЫВАЕТ РАЗНАЯ

Самое интересное в теории множеств то, что она рассматривает не только конечные множества – множества, содержащие конечное число элементов, но и бесконечные, для которых даже понятие числа бессмысленно. То есть, теория множеств может рассматривать не только множество студентов в группе и множество березок в лесу, но и множество точек на прямой, и множество звезд на небе…

Основоположник теории множеств Георг Кантор именно из-за бесконечности попортил себе много крови, да так крепко попортил, что пришлось подключаться врачам-психиатрам. Хотя с бесконечностью математики до него уже давным-давно работали. Взять то же бесконечно большое множество точек на прямой или наоборот, бесконечно малые величины из высшей математики…

Но вся беда в том, что ни один живой человек не видел, не слышал, не щупал бесконечности! Поэтому до Кантора математики признавали и использовали так называемую ПОТЕНЦИАЛЬНУЮ бесконечность. Самый кондовый пример – это понятие бесконечно большого числа в высшей математике. Бесконечно большое число это число, которое больше любого наперед заданного. Если человек не понимает, о чем речь, то его просят назвать самое большое число в мире!… Образованный человек обычно называет число миллиардмиллиардов. А ему об'ясняют, что бесконечно большое число больше этого числа – «даже больше чем на еще миллиардмиллиардов».

То есть у нас с вами всегда в запасе есть число потенциально(!) большее, чем придумает эрудит…

Кантор же позволил себе в математике АКТУАЛЬНУЮ бесконечность. То есть то, что до этого могли позволить себе лишь поэты, с которых, как известно, никто строго не спросит… «звездам числа нет, бездне дна». Поэты не любят, чтобы по крохам, по каплям… Любят, чтоб сразу! "Вот она, ВСЯ бездна вашего падения!… Дарю тебе ВСЕ звезды – такой ничтожной малости, для тебя моя, бесценная-единственная, не жалко!"… То есть по Кантору бесконечность существует сразу вся. А раз бесконечные множества есть, и сразу целиком, то с ними можно производить математические манипуляции. Их даже можно сравнивать на больше-меньше.

Поэтому Кантор начал задавать себе «поэтические» вопросы и искать на них математические ответы. Один из ключевых вопросов: "БЕСКОНЕЧНО МНОГО – это всегда ОДИНАКОВО БЕСКОНЕЧНО МНОГО? Или могут быть большие и меньшие бесконечности?"

Чего больше, звезд на небе или точек на прямой?…

Кантор доказал великую теорему, из которой следует, что бесконечности могут быть разные по величине. Поскольку «число» и «количество» – слова в этом случае неуместные, то он ввел термин «мощность». Мощность – это то что остается, когда нас не интересует сущность элементов множества и порядок, в котором они располагаются. То есть, он определил понятие мощности строго, хотя определение и кажется на первый взгляд странным. На второй взгляд этого, обычно, так уже не кажется. От множества студентов останется только мощность, если мы перестанем их различать и будем воспринимать их вне всякого порядка (в естественных условиях).

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

Пересчитывая что-то мы используем целые (положительные) числа 1, 2, 3… Их еще называют «натуральными». Странные американцы любят начинать этот ряд с нуля (и заразили этим, например, всю вычислительную технику). Их не смущает, что «3-блок» на самом деле 4-ый по счету… Впрочем, нам сейчас все равно! При добавлении или удалении нуля ничего не меняется.

Главное, мы знаем, что чисел нам хватит для пересчета чего угодно. Мы также знаем, что это множество бесконечное. Кантор назвал это множество СЧЕТНЫМ и его мощность – мощностью счетного множества.

Мощность этого множества Кантор взял за эталон и стал сравнивать ее с мощностями других множеств.

Во-первых, он установил, что эта мощность больше мощности любого конечного множества (студентов, березок и т.п.).

Во-вторых, и это любопытно, он доказал, что многие бесконечные множества имеют ту же мощность (то же «количество» элементов), что и счетное. Один из самых поразительных примеров – это то, что множество целых положительных чисел имеет столько же элементов, сколько и множество целых четных положительных чисел! То есть они равномощны!

Действительно, запишем друг под другом:

1 2 3 4…

2 4 6 8…

Ясно, что обе последовательности имеют одинаковое количество элементов, поскольку любому числу первой, ВСЕГДА соответствует строго одно число второй последовательности. Так что вторая последовательность не может исчерпаться раньше первой. И наоборот!