Однако эти множества также являются достаточно сложными для исследования. Поэтому для большинства примеров мы будем использовать некоторые абстрактные множества, такие как множества чисел,
10
Множества обычно обозначают прописными буквами, например .4, п специфицируют одним из двух путей. Если множество содержит несколько элементов, то мы просто записываем все его элементы. Например, если мы определим А как множество всех целых чисел строго между 6 и 10, то это можно записать следующим образом:
Однако эти множества также являются достаточно сложными для исследования. Поэтому для большинства примеров мы будем использовать некоторые абстрактные множества, такие как множества чисел,
10
Множества обычно обозначают прописными буквами, например .4, п специфицируют одним из двух путей. Если множество содержит несколько элементов, то мы просто записываем все его элементы. Например, если мы определим А как множество всех целых чисел строго между 6 и 10, то это можно записать следующим образом:
А = {7, 8, 9} п прочитать как
“А — множество, содержащее 7, 8, 9”. Здесь символ “=” используется в определенном смысле: А равно множеству... Далее будет использоваться высказывание “равно ли А...”. Поэтому мы должны предложить процедуру установления справедливости этого утверждения. Другими словами, множество можно охарактеризовать определенными свойствами, и, следовательно, множество А можно определить как
А == {х: х — целое число и 6 < х < 10} и прочитать как
“А есть множество всех х таких, что ...”. Множеству А принадлежат только те элементы, которые являются целыми числами, большими 6 а меньшими 10, т. е. 7, 8 и 9, и, следовательно, мы имеем 7, 8, 9, как и ранее.
Множества часто рассматривают как “неупорядоченные совокупности элементов”, хотя иногда полезно подчеркнуть, что, например,
{7, 8, 9) - {8, 9, 7} = {9, 8, 7) = ...;
мы не делаем никакой оговорки о порядке, в котором рассматриваются элементы, поэтому было бы неправильным допускать какой-либо определенный порядок.
Для любого заданного объекта можно определить, принадлежит ли он множеству А. В частности, если число принадлежит множеству, то будем говорить, что “оно является элементом множества”. Так, например, если 7 является элементом множества А, то это утверждение может быть записано следующим образом:
“7 е А”.
Утверждение “б не является элементом А” будем обозначать как
“6/еА”,
Символ е происходит от греческой буквы е. Отрицание обозначается через /е. Такое обозначение отрицания операции (или операционного символа) является общим в математике и часто будет использоваться в дальнейшем.
Надо подчеркнуть, что следовало бы обратить большее внимание на спецификацию множеств. Для каждого множества должна быть записана его спецификация. Процесс образования множества может продолжаться бесконечно долго. В результате получается множество, соответствующее определению. Частичная спецификация может быть полезной в том случае, когда не ясно, принадлежит данный элемент множеству или нет.
До сих пор нам встречались символы {:}, {,„}, е и /е. Их применение кажется достаточно простым, однако оно требует определенных навыков, которые будут проиллюстрированы на следующих примерах.
Пример 1.1. Какие из приведенных определений множества являются правильными:
А = {1, 2, 3), В = {5, б, 6, 7), С={х: х/еа}, D = [А, С},
Е == {х: х = 1 или х = {у} иy e Е),
F = (множества, которые не являются элементами самих .себя) = {х: х —х /е x}? множество и
Если число членов множества А легко вычисляется и среди элементов множества нет повторений, то определение верно.
Множество В выглядит также правильным, за исключением лишь того, что число 6 встречается дважды. Мы можем проверить, принадлежит ли элемент множеству или нет. Таким образом, это наиболее важное требование в определении множества выполнено. Следовательно, мы может рассматривать эту запись как верную и эквивалентную {5, 6, 7). Однако в этой ситуации возникают следующие проблемы. Если мы рассмотрим первоначальное определение В и выбросим одно из чисел 6 из множества, то мы, очевидно, будем иметь 6 е В и 6 /е В. Возникает противоречие. Поэтому мы будем рассматривать повторе-ние символов в определении множеств как упоминание одного и того же символа, а его дублирование как недо-
12
смотр; удаление повторяющихся символов образует основу для некоторых дальнейших .математических...рассуж-дении._
Множество А содержит числа; это может вызвать недоумение, так как числа не существуют. Более точно, мы используем символы чисел; эти символы называются так же, как и числа. Поэтому В — множество имен, и мы обычно используем имена, чтобы представить объекты (элементы), на которые ссылаемся. В вычислениях имена имеют особое значение, особенно в изучении семантики программных языков (смысла программ). Здесь не место входить в детальное обсуждение этих проблем; достаточно указать ловушки и необходимость адекватных спецификаций рассматриваемых объектов.
Возьмем, например, множество
Х = (“Введение в Паскаль”, “Основы структурных данных”, “Введение в Паскаль”}.
Это - Е - множество названий двух книг с одним элементом, по невнимательности записанным дважды, или же это — множество трех книг, две из которых имеют одно и то же название? Если верно последнее, то две книги “Введ” ние в Паскаль” следует разделить каким-либо способом. Из данной информации нельзя выяснить правильный ответ, поэтому в данном случае следует быть осторожным.
Определение С также справедливо как А, так как, если х е А, то х Ф С и, если х Ф А, то х е С. Множество С очень велико: оно содержит “всё”, за исключением чисел 1, 2 и 3. Обозначение “всё” выделено и, как мы скоро увидим, “опасно” с математической точки зрения.
Так как определения D, А а С представляют множества, то отсюда получаем, что определение D также справедливо. Заметим, что это — множество множеств (ничего неверного в этом нет!) такое, что оно имеет только два элемента, в частности 1 94 D,А а А е D, Это легко проверить, так как i^A, I ^ С а только А ц С являются элементами D. даже если 1 е
Множество Е является первым примером рекурсивно определяемого множества; оно определяется (частично) в терминах самого себя. Конструктивный процесс продолжается бесконечно, поэтому мы должны иметь правило для определения элементов. Мы не можем записать их явно. Заметим, что Е не определяется полностью в терминах Е, Мы должны знать о. множестве что-то, что не зависит от определения; в данном случае это то, что 1 е Е. Имеем:
1 е Е, поэтому {1} e E, {1}еE, поэтому {{1}}еE, {{1}}еE, поэтому {{{1}}}еE и т. д.
Хотя конструктивный процесс неограничен, беря любой элемент и располагая достаточным временем, можно определить, содержится ли этот элемент в Е.
Перейдем теперь к F; это достаточно трудная задача. Чтобы увидеть, почему F не может существовать, мы сначала допустим существование, а затем продемонстрируем, что существует особый элемент (обозначим его через у) такой, что мы не можем определить, у е F или у /е F. Вообще исследование “неудобного” ' примера, на котором мы можем показать логический изъян, проводится нелегко; однако в данном случае мы можем использовать само множество F. Чтобы прояснить дело, давайте обозначим это множество через G. Если, как мы предполагаем, F — искомое множество, то или G е F, или G /е - F. Рассмотрим два возможных случая:
а) GeF. Тогда G удовлетворяет условию содержания, т. е. G /е G, и, следовательно, G /е F;
б) G /е F говорит о том, что G не удовлетворяет условию вхождения в F, и, следовательно, G e F.
Следовательно, во всех случаях мы приходим к противоречию. Поэтому F не может существовать. Где же была сделана ошибка? Множества множеств, вероятно, разрешаются, и бесконечно большие множества (например, рассмотренное выше множество Е) также разрешаются; однако с “множеством всех множеств” нельзя работать в обычной теории множеств — это требует другого рода математики. Эта аномалия теории множеств известна как парадокс. Рассела. Если мы уже имеем множество Н, то можно определить /:
J= {х: х e Н и х е х}.//
Таким образом, мы будем использовать только множества, которые могут быть явно записаны или же построены путем хорошо определенных процессов. Поэтому множества не так тривиальны, как они могли вначале показаться. Однако, следуя приведенным выше правилам, работа с ними не будет особо трудной. Попытайтесь сделать самостоятельно следующее упражнение,
14
зависит от определения; в данном случае это то, что 1 е Е. Имеем:
1 е Е, поэтому {1} e E, {1}еE, поэтому {{1}}еE, {{1}}еE, поэтому {{{1}}}еE и т. д.
Хотя конструктивный процесс неограничен, беря любой элемент и располагая достаточным временем, можно определить, содержится ли этот элемент в Е.
Перейдем теперь к F; это достаточно трудная задача. Чтобы увидеть, почему F не может существовать, мы сначала допустим существование, а затем продемонстрируем, что существует особый элемент (обозначим его через у) такой, что мы не можем определить, у е F или у /е F. Вообще исследование “неудобного” ' примера, на котором мы можем показать логический изъян, проводится нелегко; однако в данном случае мы можем использовать само множество F. Чтобы прояснить дело, давайте обозначим это множество через G. Если, как мы предполагаем, F — искомое множество, то или G е F, или G /е - F. Рассмотрим два возможных случая:
а) GeF. Тогда G удовлетворяет условию содержания, т. е. G /е G, и, следовательно, G /е F;
б) G /е F говорит о том, что G не удовлетворяет условию вхождения в F, и, следовательно, G e F.
Следовательно, во всех случаях мы приходим к противоречию. Поэтому F не может существовать. Где же была сделана ошибка? Множества множеств, вероятно, разрешаются, и бесконечно большие множества (например, рассмотренное выше множество Е) также разрешаются; однако с “множеством всех множеств” нельзя работать в обычной теории множеств — это требует другого рода математики. Эта аномалия теории множеств известна как парадокс. Рассела. Если мы уже имеем множество Н, то можно определить /:
J= {х: х e Н и х е х}.//
Таким образом, мы будем использовать только множества, которые могут быть явно записаны или же построены путем хорошо определенных процессов. Поэтому множества не так тривиальны, как они могли вначале показаться. Однако, следуя приведенным выше правилам, работа с ними не будет особо трудной. Попытайтесь сделать самостоятельно следующее упражнение,
Упражнение 1.1.
1. Рассмотреть по крайней мере две возможные интерпретации множества
{Смит, Смит, Браун}.
Определить каждую из них настолько однозначно, насколько это возможно.
2. Рассмотреть следующие четыре множества. Выяснить, как записи этих множеств могут быть упрощены п какие из них эквивалентны. Предложить все возможные интерпретации, удовлетворяющие описанным выше предположениям:
а) {1, 2, 3, 4}; 6) {I, II, III, IV, V};
в) {1, один, one, uno, ein}; г) {5, V, пять, five}.
3. Проверить справедливость утверждений
“Это утверждение неверно” и “я лгун”.
Какие слова в утверждении требуют собственного (т. е. математически точного) определения для того, чтобы сделать ответы математически строгими?
4. Пусть Х — множество {1, 2}, a Y—множество [х: х = у + z; у, zeX}. Определить в явном виде множество Y. Какие это множества:
{у: у = х + z; х, z е X} и {у: х == у + z; х, z е X}?
5. Предположим, что х является элементом, а не множеством. Тогда у /e х для любого у, и отсюда следует, что х /e х. Можно ли упростить множество {х, {х}, {{а;}}}? Что можно сказать относительно {х, у, {х, у}}?
6. Пусть А — множество всех целых чисел. Описать словами множество
Х={х: х е А и x = 1 или (х - 2) e X}.
14
1.4