Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методическое указания по Сист анализу(Часть 1....doc
Скачиваний:
5
Добавлен:
13.11.2019
Размер:
1.3 Mб
Скачать

Методические указания по дисциплине «Системный анализ»

Часть 1. Теория множеств.

Глава 1. Понятие множества и отношения

Теория множеств как математическая дисциплина создана немецким математиком Г. Кантором (1845—1918).

Проводившиеся Кантором исследования, относящиеся к тригономет­рическим рядам и числовым последовательностям, привели его к задаче выяснения тех средств, которые необходимы для сравнения бесконечных множеств чисел по величине. Для решения этой проблемы Кантор ввел понятие мощности (или объема) множества, считая по определению, что два множества имеют одинаковую мощность, если члены любого из них можно сопоставить членам другого, образовав пары соответствующих членов. Поскольку между членами двух конечных множеств можно уста­новить такое попарное соответствие в том и только в том случае, когда они имеют одинаковое число членов, мощность конечного множества можно отождествить с количественным числом. Таким образом, понятие мощности бесконечного множества; представляет собой обобщение обыч­ного понятия количественного числа. В построении теории таких обоб­щенных (или трансфинитных) чисел, включающей в себя их арифметику, и состояло создание Кантором теории множеств. Полученные им в этом направлении результаты представляют собой исключительный образец математического творчества.

Были получены также приложения теории множеств к анализу и геометрии, так что к 1890 году канторовская теория множеств получила признание в качестве самостоятельного раз­дела математики. В самом конце прошлого столетия обнаружилось, что позиция эта связана с определенными опасностями—оказалось, что в теории множеств могут возникнуть противоречия. Но это обстоятель­ство не воспринималось как очень серьезный дефект теории1 — на это указывает и то, что эти противоречия стали именоваться парадоксами, т. е. такого рода дефектами теории, для устранения которых достаточно лишь как следует разобраться в сути дела.

Идеи канторовской теории не только оказались полезными для су­ществовавшей математики; они постепенно привели к созданию самостоятельной дисциплины — общей теории абстрактных множеств. Этой общей теории множеств и посвящена в основном данная глава.

В частности, в этой главе обсуждаются в рамках теории множеств три важных математических понятия: функция, отношение эквивалент­ности и отношение порядка.

1.1. Понятие множества

Согласно канторовскому определению, множество S есть любое собрание определенных и разли­чимых между собой объектов нашей интуиции или интеллекта, мыслимое как единое целое. Эти объекты называются элементами, или членами, множества S.

Существенным пунктом канторовского понимания является то, что собрание предметов само рассматривается как один предмет (мыслится как единое целое). Подчеркнем, что внимание, здесь переносится с отдельных предметов на их собрания, в свою очередь по­нимаемые как предметы — это обстоятельство некоторым образом отра­жено в таких словах, как «компания», «стая», «стадо».

Отметим также, что канторовская формулировка допускает рассматривать множества, элементы которых по той или иной причине нельзя точно указать. В этой связи стоит вспомнить, что элементы любого бесконеч­ного множества даже теоретически нельзя собрать в законченную сово­купность

Остается еще пояснить участвующие в канторовской концепции мно­жества слова «различимые» и «определенные».

В первом случае, как обычно, имеется в виду, что для любых двух предметов, рассматри­ваемых как элементы некоторого множества, должна иметься возможность решить, различны они или одинаковы. Эпитет «определенный» понимается в том смысле, что если дано какое-либо множество и неко­торый предмет, то можно определить, является этот предмет элементом данного множества или нет.

Отсюда следует, что каждое множество полностью определяется своими элементами.

1.2. Основные принципы интуитивной теории множеств

Согласно Кантору, всякое множество состоит из некоторых предме­тов, называемых его членами, или элементами.

Принад­лежность, или членство, есть отношение между предметами и множест­вами. Мы будем обозначать это отношение символом  и писать:

xA,

если предмет х является элементом множества А. Если же х не есть элемент множества А, то мы будем писать:

xA.

Записью x1, x2, … , xn A будем пользоваться в качестве сокращения для «х1 А и х2 А и … и xn A».

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

Интуитивный принцип объемности1. Два множества равны в том и только в том случае, когда они состоят из одних и тех же элементов. Равенство двух множеств X и Y будет обозначаться через

X = Y,

а неравенство множеств X u Y через

X Y.

Следует уяснить, что принцип объемности есть нетривиальное допущение об отношении принадлежности. Доказательство равенства каких- либо двух конкретных множеств А и В состоит, вообще говоря, из двух частей: в первой части доказывается, что если х А, то х В; во вто­рой — что если х В, то х А. Пример такого доказательства приводится ниже.

То (однозначно определенное) множество, элементами которого являются предметы х1, х2, …, хп, будет обозначаться

{x1, x2, …, xn}.

В частности, {x} — так называемое единичное множество — есть одно­элементное множество, единственным элементом которого является х.

Примеры А

  1. Докажем, что множество А всех положительных четных целых чисел равно множеству В положительных целых чисел, представимых в виде суммы двух положительных нечетных целых чисел. Допустим вначале, что хА, и докажем, что хВ. Если х А, то х = 2т, так что x=(2m - 1) +1. Это и означает, что хВ. Предположим теперь, что х В, и выведем отсюда, что х А. Если хВ, то х = (2р-1)+(2q-1), откуда x = 2(p+q-1), из чего следует, что х А. Таким образом, мы доказали, что множества А и В состоят из одних и тех же элементов.

  2. {2, 4, 6} есть множество, состоящее из первых трех положительных четных целых чисел. Поскольку 2, 4, 6} и {2, 6, 4} состоят из одних и тех же элементов, они являются равными множествами. Кроме того, по той же причине {2, 4, 6} = {2, 4, 4, 6}.

  3. Элементы какого-либо множества сами могут быть множествами. Например, географическая область, известная как Соединенные Штаты Америки, есть множество из 50 элементов - штатов, каждый из которых, в свою очередь, есть множество округов. Далее, {{1, 3}, {2, 4}, {5, 6}} есть множество из трех элементов, а именно: 1, 3, {2, 4 и {5, 6}. Множества {{1, 2}, {2, 3}} и {1, 2, 3} не равны, так как элементами первого являются {1, 2} и {2, 3}, а элементами второго - 1, 2 и 3.

4. Множества {{1,2}} и {1,2} не равны, так как первое - одноэлементное множество, имеющее единственным своим элементом {1, 2}, а второе имеет своими элементами 1 и 2. Это иллюстрирует то общее замечание, согласно которому следует различать предмет и множество, единственным элементом которого является этот предмет.

Сделаем небольшое отступление, чтобы пояснить символику, исполь­зуемую нами при обсуждении теории множеств. Как правило, мы будем пользоваться строчными курсивными латинскими буквами для обозначе­ния элементов, а для обозначения содержащих их множеств будем упо­треблять (пока) прописные курсивные латинские буквы. Далее, для обозначения множеств некоторых определенных видов мы будем исполь­зовать строчные греческие буквы. Если элементы какого-либо множества в свою очередь являются множествами и если мы желаем подчеркнуть это обстоятельство в обсуждении, мы будем употреблять для обозначе­ния таких множеств, содержащих множества, прописные рукописные ла­тинские буквы и будем называть их системами множеств. Например, мы можем в случае необходимости говорить о системе F всех конечных множеств А целых чисел х. Можно сказать в качестве мнемонического правила, что уровень, занимаемый множеством в рассматриваемой ие­рархии множеств, определяется размером и фасоном буквы, используемой для его обозначения.

Обозначение множества с помощью фигурных скобок, употребитель­ное для явного задания множеств, составленных из небольшого числа элементов, слишком громоздко, чтобы его использовать для задания множеств, имеющих хотя и конечное, но большое число элементов, и вовсе неприменимо для бесконечных множеств (множеств, имеющих бесконечно много элементов). Как можно задать множество, состоящее из большого числа элементов? Имеется инстинктивная тенденция различать конечные и бесконечные множества, исходящая из того, что конечное множество можно фактически представить в виде некоторой полностью составленной совокупности, а бесконечное - нельзя. Однако обширные конечные мно­жества (например, описанное в § 1.1 множество книг) в той же мере «не­исчерпаемы», как и любое бесконечное множество. Такого рода примеры приводят нас к заключению, что проблемы эффективного описания ка­кого-либо обширного конечного множества и описания бесконечного мно­жества практически представляют собой одну и ту же проблему.

Обычное решение этой проблемы, исходящее от Кантора, основано на понятии «формы от x»1. Пока мы ограничимся следующим интуитив­ным описанием. Будем понимать под высказыванием повествовательное предложение, которое можно охарактеризовать как истинное или ложное. Тогда под формой от х мы будем понимать конечную последователь­ность, состоящую из слов и символа х, такую, что если каждое вхож­дение х в эту последовательность заменить одним и тем же именем не­которого предмета соответствующего рода, то в результате получится высказывание. Например, каждое из следующих выражений есть форма от x:

5 делит х; х2 + х + 1 > x;

x любит Джона; х2 = 2.

х < х

Напротив, ни одно из следующих выражений формой от х не является:

для всех х х2 - 4 = (х - 2)(x + 2);

существует такое х, что хг.0.

Каждое из них попросту является высказыванием. С точки зрения грам­матики форму от х можно определить и по-другому - как предложение, в котором что-то утверждается об х. Ясно, что каждое предложение первого из приведенных списков обладает этим качеством, предложе­ния же из второго списка не обладают им. Еще один, отличный от пре­дыдущих подход к понятию формы использует понятие функции — так, как оно употребляется в элементарной математике. Форма от х может быть определена как функция одной переменной х, значениями которой (при надлежащим образом выбранной области определения функции) являются высказывания.

Мы будем пользоваться прописными латинскими буквами, стоящими перед символом (х) для обозначения форм от х. Если в некотором конкретном контексте Р (х) обозначает какую-либо определенную форму, то Р (а) будет обозначать ту же самую форму, но с заменой х на а.

Наша цель описывать множества в терминах форм достигается с по­мощью следующего принципа.

Интуитивный принцип абстракции1. Любая, форма Р (х) определяет некоторое множество А посредством условия, согласно которому элементами множества А являются в точности такие предметы а, что Р (а) есть истинное высказывание.

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

xPx,

что читается так: «множество всех таких х, что Р (х)». Таким образом, аxPxв том и только в том случае, если Р(а)—истинное выска­зывание. Можно сказать, что решение вопроса, является ли данный предмет а элементом множества xPx, есть решение вопроса, обла­дает ли а некоторым определенным свойством (качеством). Поэтому, когда какую-нибудь форму от х, Р (х), используют для построения некоторого множества, ее обычно называют свойством x-а (property of x) или, по-дру­гому, определяющим свойством множества xPx. В таком случае принцип абстракции можно сформулировать в виде утверждения: «Каждое свойство определяет некоторое множество».

Мы допускаем возможность вхождения в форму от х других симво­лов, отличных от х. Если Р (х) есть форма от х, а у - символ, не вхо­дящий в Р(х), то свойства Р(х) и Р (у) неразличимы, так что xPx= yPy. Равенство это, однако, не обязательно справедливо в том слу­чае, когда у входит в Р(х). Например,

{хх делится на и} = {уу делится на и},

но

{хх делится на и}  {уу делится на и}.

С другой стороны, если F (х) и G (х) - два свойства, такие, что F (х) справедливо для х тогда и только тогда, когда G(x) справедливо для х, то согласно принципу объемности xFx=xGx. Например,

xxA и xВ= xxВ и xА,

и

xxZ+ и x<5= xxZ+ и (x+1)2 29.

Примеры В

1. Введение в обращение бесконечных множеств с помощью опреде­ляющих их свойств - процедура, хорошо знакомая каждому, изучавшему аналитическую геометрию. Обычное определение таких геометрических мест, как, скажем, конические сечения, придется слегка переформули­ровать. Например, окружность радиуса 2 с центром в начале координат есть множество всех таких х, что х есть точка плоскости и х находится на расстоянии в две единицы от начала координат.

2. Легко видеть, что следующие выражения представляют собой мно­жества, определенные посредством некоторых свойств:

(а) хх есть целое число, большее 1 и не имеющее делителей, меньших или равных х1/2;

(b) хх есть положительное целое число, меньшее 9};

(с) хх есть кривая третьего порядка в координатной плоскости};

(d) хх есть функция, непрерывная на замкнутом отрезке от 0 до 1}.

  1. хх = х1 или х = х2 или ... или х = хп есть множество, которое мы выше договорились обозначать через {х1, х2, ... , хп.

  2. В некоторых случаях язык позволяет нам дать более краткое определение какого-либо конечного множества, чем то, которое получается перечислением его элементов. Например, некоторое конкретное множество из 100 людей может быть более коротко определено с помощью свойства «х - сенатор», нежели перечислением имен его элементов1.

  3. Если А - множество, то х А есть форма от х, которая может быть использована в качестве определяющего свойства некоторого множества. Поскольку уxxA в том и только в том случае, если у А,то по принципу объемности

А = xxA.

Для обозначения множеств используются и различные видоизменения основной скобочной записи. Например, для того чтобы обозначить мно­жество всех предметов, являющихся элементами множества А и обла­дающих свойством Р, вместо { х | х А и Р (х)} часто пишут; {х А Р (x)}. Это множество можно по-другому охарактеризовать как «множество всех элементов из А, обладающих свойством Р (х, и новая запись как раз отражает этот способ описания. Например, {х R | 0 x  1} обозначает множество всех действительных чисел между 0 и 1 (включительно), а {x Q+ | x2<2} - множество всех положительных рациональных чисел, квадраты которых меньше числа 2.

Если Р (х) есть некоторое свойство, а f - функция, то через

{ f (x) Р (x)}

мы будем обозначать множество всех таких у, для которых имеется х, обладающий свойством Р (х) и такой, что y = f(x). Например, вместо того, чтобы писать {у  имеется такой х, что х есть целое число и у = 2х , мы будем писать

 xx  .

Аналогично через {х2 xZ} обозначается множество квадратов целых чисел. Такие обозначения допускают естественные обобщения; для пони­мания смысла в каждом конкретном случае достаточно опираться на интуицию. Скажем, имея дело с координатной плоскостью, точки кото­рой отождествляются с элементами множества R2 всех упорядоченных пар  x , у 1действительных чисел х и у, естественно понимать под { x, y   R2 y = 2x} прямую, проходящую через начало координат и имеющую угловой коэффициент, равный 2.

Принцип объемности, принцип абстракции и принцип выбора (пока, за ненадобностью, не сформулированный) на которой строится канторовская теория множеств. Интересно отметить, что, хотя мы и постарались, прежде чем вводить первые два из этих принципов, пояснить, что такое множество, ни один из этих принципов (так же как и третий) не использует определение термина «множество». Факти­чески каждый из них есть некоторое допущение о множествах. Основ­ное понятие, используемое при формулировке этих принципов, - это принадлежность. Таким образом, в качестве важнейшего понятия теории множеств выступает не столько само понятие множества, сколько отно­шение принадлежности.

Мы уже упоминали о том, что в интуитивной теории множеств могут быть получены противоречия. Источником этих неприятностей является неограниченное употребление принципа абстракции. Самым простым из известных теоретико-множественных противоречий является то, которое было открыто Бертраном Расселом в 1901 году. Оно связано с мно­жеством R, определяющим свойством которого служит форма хх, и может быть сформулировано следующим образом: с одной стороны, RR, а с другой — RR. Неформальные доказательства обоих этих противо­речащих друг другу утверждений читатель проведет без труда.

Упражнения

  1. Объясните, почему 2  {1, 2, 3}.

  2. Верно ли, что {1, 2}{{1, 2, 3}, {1, 3}, 1, 2}? Ответ обосновать.

  1. Попробуйте указать множество, являющееся своим собственным элементом.

  2. Приведите пример таких множеств А, В и С, что АВ, ВС, но не АС.

  1. Опишите словесно каждое из следующих множеств:

(а) {x  Zx делится на 2 и х делится на 3};

(b) хх  А и х  В};

(с) {х х А или х B};

(d) {х  Z+ | х  {x  Z | для некоторого целого у, х=2yи x  x для некоторого целого у, х = 3y}};

(е) {х2х - простое число};

(f) {a/b Qa + b = 1 и a, b Q;

(g) {<x, y>  R2 | x2 + y2 = 1};

(h) {<x, y>R2 y = 2x и y = 3x}

6. Докажите, что для любых, не обязательно различных между собой предметов а, Ь, с и d {{а}, {а, b}} = {{с}, {с, d}} в том и только в том случае, когда а = с и b = d.