Множества. Логика. Аксиоматические теории (стр. 4 )

Упражнения

1. Показать, что если = , то х = и, y = v и z = w.

2. Выписать элементы множества {1, 2}{2, 3, 4}. Каковы область определения и область значений этого отношения? Что представляет собой его график?

[43]

3. Найдите область определения и область значений каждого из следующих отношений, после чего постройте их графики:

(a) {| x2 + 4y2 = 1};

(b) {| x2 = y2};

(c) {| x | + 2| y | = 1};

(d) {| x2 + y2 < 1 и x > 0};

(e) {| y ≥ 0 и y ≤ x, и x +y ≤ 1}.

4. Представьте отношение из упражнения 3(с) в виде объединения четырех отношений, а отношение из упражнения 3(е) — в виде пересечения трех отношений.

5. Образование прямого произведения двух множеств есть бинарная операция над множествами («прямое умножение»). Покажите на примерах, что эта операция не является ни коммутативной, ни ассоциативной.

6. Пусть — отношение «...есть брат...», а — отношение «...есть сестра...». Опишите отношения , и — .

7. Пусть и имеют те же значения, что в упражнении 6. Пусть A — множество студентов, обучающихся в настоящее время в том же институте, что и читатель. Что представляет собой [A]? () [A]?

8. Доказать, что для произвольных множеств A, В, С, D (A В)(С D) = (A С) (В D). Доказать, что прямое умножение множеств дистрибутивно относительно операции пересечения, т. е. что для любых A, В и С (A В)С = (A С)(ВС) и A (ВС) = (A В)(АС).

9. Укажите такие четыре множества A, В, С и D, для которых (A В)(С D) ≠ (A С)(В D).

10. Несмотря на результат предыдущего упражнения, прямое умножение дистрибутивно относительно операции объединения. Доказать.

11. Исследуйте, дистрибутивны ли объединение и пересечение относительно прямого умножения.

12. Доказать, что для любых непустых множеств A и В и любого множества С из (A В)(ВА) = СС следует А = В = С.

1.7. Отношения эквивалентности

Отношение во множестве X называется рефлексивным, если для любого элемента х из X хх; симметричным, если ху влечет ух; транзитивным, если из ху и y z следует x z. Отношения, обладающие всеми этими свойствами, столь часто встречаются в математике, что им присвоили специальное название. Отношение в некотором множестве назы-

[44]

вается отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Если отношение в X есть отношение эквивалентности, то, очевидно, = X. Вследствие этого отношения эквивалентности в X называют также отношениями эквивалентности на X.

Примеры

Каждое из следующих отношений является отношением эквивалентности на соответствующем множестве:

1. Равенство в произвольной системе множеств.

2. Геометрическое отношение подобия в множестве всех треугольников в евклидовой плоскости.

3. Отношение сравнимости по модулю п в Z. Это отношение определяется для любого не равного нулю целого числа п следующим образом: х сравнимо с у по модулю п, если х - y делится на п; обозначение:

X y (mod n).

4. Отношение ~ в множестве всех упорядоченных пар положительных целых чисел, где ~ , если xv = yu.

5. Отношение параллельности в множестве прямых в евклидовой плоскости.

6. Отношение равночисленности в произвольной системе конечных

множеств.

7 Отношение «проживания в одном доме» в множестве жителей Соединенных Штатов.

Последний из приведенных примеров иллюстрирует на языке повседневной жизни основное свойство любого отношения эквивалентности: это отношение разбивает соответствующее множество на непересекающиеся подмножества, в данном случае — на множества людей, живущих в одном доме. Дадим обоснование этого предложения в общем виде. Если есть отношение эквивалентности на множестве X, то подмножество А множества X называется классом эквивалентности (-классом эквивалентности), если существует такой элемент x из A, что А совпадает с множеством всех у, для которых ху. Таким образом, А есть класс эквивалентности тогда и только тогда, когда существует такой х из X, что A = [{x}]. Если насчет самого отношения нет никаких неясностей, то множество -образов элемента х из X сокращенно обозначается через [х] и называется классом эквивалентности, порожденным элементом х. Вот два основных свойства классов эквивалентности:

(I) x [x];

(II) если ху, то [x]=[y].

Первое из этих свойств вытекает из рефлексивности отношения эквивалентности. Чтобы доказать второе свойство, допустим, что ху;

[45]

тогда [y][х]; в самом деле, из z [у] (что означает у z) и ху в силу транзитивности отношения вытекает x z, т. е. z[x]. Симметричность отношения позволяет доказать обратное включение [х][y], из чего уже следует равенство классов [х] и [у].

Из свойства (I) вытекает, что каждый элемент множества X принадлежит некоторому классу эквивалентности, а из (II) — что два класса эквивалентности либо не пересекаются, либо совпадают, так как, если z[х] и z[у], то [х] = [z] и [y] = [z]. Следовательно, [х] = [y]. Вспоминая определение разбиения непустого множества, мы получаем, что совокупность различных -классов эквивалентности является разбиением множества X.

[49]

1.8. Функции

Понятие функции мы можем определить в терминах уже введенных ранее понятий. Это определение исходит из известного по многим учебникам обсуждения понятия функции, согласно которому график функции есть множество упорядоченных пар. Поскольку ясно, что любая информация о функции может быть извлечена из ее графика, то нет никакой надобности различать функцию и ее график. Поэтому при определении функции имеет смысл исходить из таких характеристик множества упорядоченных пар, которые специфичны именно для графиков функций. Это достигается посредством соглашения, по которому функция есть такое отношение, никакие два различных элемента которого не имеют одинаковых первых координат. Таким образом, f тогда и только тогда является функцией, когда оно удовлетворяет следующим требованиям:

(I) элементами f являются упорядоченные пары;

(II) если и суть элементы f, то y = z.

[50]

Примеры А

1. {, , Рузвельт, Черчилль} есть функция с областью определения {1, 2, Рузвельт} и областью значений {2, Черчилль}.

2. Отношение {, , } не является функцией, так как различные элементы и имеют одинаковую первую координату.

3. Отношение {| xR} есть функция, так как если х = и, то x2+x+1 = u2+u+1.

4. Отношение {| x R} не является функцией, так как его элементами являются как так и .

Слово «функция» имеет многочисленные синонимы, в частности: преобразование, отображение, соответствие, оператор[20]. Если f — функция и f, так что xfy, то х есть аргумент функции f. Для обозначения у в этом случае терминология весьма разноречива; например, у называют значением функции f на х, образом элемента х при f, элементом, в который f переводит х. Для обозначения у также употребляют различные символы: xf, f(х) (или еще проще fx), xf. Обозначение f (x) можно рассматривать как сокращение для f[{x}] — множества f-образов элемента х. В этих терминах характеристическое свойство функций, выделяющее их среди отношений вообще, можно сформулировать следующим образом: каждый элемент области определения имеет единственный образ.

Читатель должен привыкнуть ориентироваться в этих обозначениях функции, так как в разных книгах он будет встречать различные символы и названия. Определения и теоремы, относящиеся к функциям, в этой книге всюду будут формулироваться в обозначениях f(х) или fx для (единственного) элемента, соответствующего элементу х в функции f. С этим хорошо согласуется также обозначение f[A] для множества {у | для некоторого х из А f}. Впрочем, в приложениях понятия функции мы будем пользоваться различными обозначениями. Когда вместо f(x) нам будет удобнее применить обозначение xf, тогда естественно и вместо f [А] писать [А]f. Если же вместо f(x) мы будем писать хf, то в этих местах вместо f[А] будет использоваться обозначение [Af] или Аf.

Поскольку функции являются множествами, к ним применимо обычное определение равенства: две функции f и g равны в том и только в том случае, когда они состоят из одних и тех же элементов. Очевидно, что то же самое можно сказать и другими словами: f = g тогда и только

[51]

тогда, когда Df = Dg и f(x) = g(x) для любого х из общей области определения. Следовательно, функцию можно определить, указав область ее определения и задав значения функции для каждого элемента области определения. Мы видим, таким образом, что вторая часть определений такого рода имеет вид некоторого правила. Например, одно из возможных определений функции { | } таково: функция f с областью определения R такова, что f(х) = х2+x+1. Когда функция задается указанием на ее область определения и заданием ее значений для каждого элемента этой области, область ее значений может быть вовсе не очевидна. В приведенном только что примере, чтобы прийти к заключению, что Rf = {| x ≥ }, надо проделать некоторые вычисления. С другой стороны, то обстоятельство, что в этом случае , едва ли не очевидно. Вообще, при точном определении области значений мы сталкиваемся с определенными трудностями, но указать некоторое множество, включающее в себя область значений, обычно удается без труда. В связи с этим представляется разумным принять следующую терминологию. Функция f есть функция со значениями[21] в Y, если область значений функции f есть подмножество множества Y, и функция f есть функция со значениями на Y, если Rf = Y. Вводя аналогичные терминологические соглашения для области определения функции, мы будем говорить, что f определена на X, если X есть область определения функции f. Желая сказать, что f есть функция, определенная на множестве X со значениями в множестве Y, обычно пользуются символикой

f: X → Y, или X Y.

Множество всех функций, определенных на X со значениями в Y, есть подмножество множества P () обозначим это подмножество через YX. Если X пусто, то YX состоит всего лишь из одного элемента, а именно из пустого подмножества множества XY. Это единственное подмножество множества XY, так как последнее само пусто, если пусто X. Если Y пусто, а X непусто, YX пусто.

Если f: X → Y и АХ, то f (А Y) есть функция, определенная на А со значениями в Y (эту функцию называют сужением функции f на множество А и обозначают через f |A). Подробнее: f |A есть функция, определенная на A и такая, что (f | A) (a) = f (а) для любого а, принадлежащего множеству А. Функция g является сужением функции f

[52]

на некоторое подмножество области определения функции f тогда и только тогда, когда область определения функции g есть подмножество области определения функции f и для xDg g(x) = f(x); иначе говоря, gf. В дополнение к определению сужения назовем функцию f продолжением функции g, если gf. В качестве примера, иллюстрирующего понятие продолжения функции, мы обратимся к описанному выше отношению тождества X в X. Очевидно, это отношение является функцией; поэтому, в соответствии с принятыми нами обозначениями функций посредством малых латинских букв, мы обозначим это отношение через или X. Назовем X тождественным отображением на X. Если A Х, то X|A = A. Если X|A рассматривается как функция, определенная на А со значениями в X, то это — инъективное отображение множества А в X.

Функция называется взаимно-однозначной, если она переводит различные элементы в различные. Иначе говоря, функция f тогда и только тогда взаимно - однозначна, когда

х1 ≠ х2 влечет f(xl) ≠ f(x2).

Взаимно - однозначность функции иногда удобнее доказывать, рассматривая контрапозицию к написанному выше:

f(x1) = f(x2) влечет х1 = х2.

Например, функция f на R такая, что f(x) = 2x + 1, взаимно-однозначна, так как 2х1+1 = 2х2+1 влечет х1 = х2.

Взаимно-однозначная функция f, определенная на X со значениями на Y, образует пары из элементов множеств X и Y; именно, в каждую пару входит f(x) из Y вместе с соответствующим х из X. В самом деле, поскольку f есть функция, f(x) есть однозначно определенный элемент множества Y; поскольку f принимает значения на Y, каждое у сопоставляется некоторому х; поскольку, наконец, f взаимно-однозначна, каждое у сопоставляется единственному х. Ввиду полной симметричности картины, возникающей при взаимно-однозначном отображении множества X на Y, его часто называют взаимно-однозначным соответствием между X и Y. Если два множества связаны между собой такой функцией, то говорят, что они находятся во взаимно-однозначном соответствии.

Примеры В

1. Хорошо известная читателю показательная функция есть функция, определенная на R со значениями в R; символически:

f: R → R, где f(x) = eX.

[53]

Мы можем также сказать более точно, что f есть функция, определенная на R со значениями на R+. Вообще, если f: X → Y, то f — функция, определенная на X со значениями на f [X], т. е. на области значении функции f.

2. {a, b, c}{1, 2} есть множество всех функций, определенных на {1,2} со значениями в {а, b, с}. Один из элементов этого множества — {}.

3. Если А и В — множества, имеющие одинаковое число элементов, то они, очевидно, находятся во взаимно-однозначном соответствии[22]. Тогда, как легко показать, для любого множества X множества Ах и Вх находятся во взаимно-однозначном соответствии. В соответствии с этим множество всех функций, определенных на некотором множестве X со значениями в произвольном множестве, состоящем из п элементов, обозначают обычно через пх. Так, 2х обозначает множество всех функций, определенных на X со значениями в множестве из двух элементов, в качестве какового обычно берут множество {0, 1}. Если AX, то один из элементов множества 2х есть функция , определяемая следующим образом:

(x) = 1, если хА, и (х) = 0, если хХ—А.

Мы будем называть характеристической функцией множества А. Рассмотрим теперь функцию f, определенную на P (X) со значениями в 2х, взяв в качестве образа подмножества А множества X [А является элементом множества P (X)] характеристическую функцию этого подмножества А (являющуюся элементом множества 2х). В качестве упражнения предлагаем доказать, что f есть взаимно-однозначное соответствие между P (Х) и 2х. В силу этого взаимно-однозначного соответствия множества P (Х) и 2х обычно просто отождествляют, свободно заменяя в рассуждениях одно из этих множеств другим, если это удобно по каким-либо соображениям.

[61]

§ 1.10. Отношения порядка

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

[62]

вующем множестве X для некоторых пар его различных элементов х и у имеет место ху, но не ух. В этом случае при помощи отношения можно решить, в каком порядке поставить эти элементы: х, у, а не у, х, так как имеет место ху, но не ух. Из такого рода отношений для множества действительных чисел хорошо известны отношения <, ≤, > и ≥. Аналогичную роль для систем множеств играют отношения и .

Первый тип отношений порядка, который мы сейчас рассмотрим, будет характеризоваться основными свойствами, общими для упомянутых выше отношений ≤ для чисел и для множеств. Предварительно мы введем одно понятие: отношение во множестве X будет называться антисимметричным, если для любых элементов х и у множества A из одновременной истинности ху и ух следует х = у. Частичным упорядочением, или отношением частичного порядка, во множестве X мы будем называть рефлексивное, антисимметричное и транзитивное отношение в X. Поскольку можно пожелать рассматривать частичное упорядочение в X относительно некоторого другого, отличного от X множества (например, обычное упорядочение в Z относительно множества четных чисел), удобно ввести еще одно определение: отношение частично упорядочивает множество Y, если (YY) есть частичное упорядочение в Y. Отношение (YY) есть «сужение» отношения на множество Y в том смысле, что оно исключает из рассмотрения те упорядоченные пары, у которых хотя бы одна из координат не есть элемент множества Y.

Примеры.

1. Отношение «является целым кратным» в Z+ есть частичное упорядочение.

2. Иерархия или схема организации в торговой фирме определяется частичным упорядочением в некотором множестве должностей.

3. Если есть частичное упорядочение в X, то (АА) частично упорядочивает подмножество А множество X.

4. Для любого отношения обратным к нему называется такое отношение , что ух равносильно ху. Если есть частичное упорядочение, то также есть частичное упорядочение.

5. Любое рефлексивное и транзитивное отношение называется предупорядочением. Такого рода отношение может обладать тем неудобством, что при попытке упорядочить с его помощью какое-либо множество это отношение не позволяет «различать» некоторые пары различных объектов х, у — в том смысле, что будет иметь место как ху, так и ух. Например, пусть для некоторого множества людей w будет функцией веса.

[63]

а А — функцией роста, т. е. w(x) и h(x) будут, соответственно, означать вес и рост некоторого индивида х. В таком случае отношение такое, что ху равносильно w(х) ≤ w (y) и h(x) ≥ h(у), будет предупорядочением, но не частичным упорядочением, если найдутся два индивида, имеющие одинаковый вес и одинаковый рост.

Если есть предупорядочение множества X, то это отношение определяет частичное упорядочение, в некотором разбнении множества X (согласно упражнению 10 из § 1.7). Во-первых, утверждается, что отношение ~, для которого х ~ у равносильно по определению ху и ух, является отношением эквивалентности. Во-вторых, устанавливается, что отношение ', для которого [x] ' [y], если ху, является частичным упорядочением, областью определения которого служит соответствующее множество классов эквивалентности [x]. Окончательно можно сказать, что если есть предупорядочение в некотором множестве X, то оно является частичным упорядочением в множестве, получающемся из X в результате идентификации элементов, не различимых с помощью отношения .