Материал: baldin_kv_red_matematika_dlia_gumanitariev

2) всякое бесконечное множество содержит счетное подмножество;

) объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.

Множество действительных чисел (R) или множество бесконечных последовательностей 0 и 1 несчетно. Мощность множества R больше мощности любого счетного множества и называется мощностью континуума.

Приведем без доказательства теорему Кантора—Берн- штейна.

Если множество Х равномощно какому-то подмножеству множества Y, а множество Y равномощно какому-то подмножеству множества Х, то множества Х и Y равномощны.

Дадим также общую формулировку теоремы Кантора. Никакое множество Z не равномощно множеству всех сво-

их подмножеств.

Наглядные представления о множествах могут приводить к противоречиям.

Приведем, например, парадокс Рассела [5].

Типичные множества не являются своими элементами. Например, множество целых чисел (Z) само не является целым числом и не будет своим элементом. Но в принципе можно представить себе множество, которое является своим элементом, например, множество всех множеств (U). Такие множества назовем “необычными”. Теперь рассмотрим множество всех обычных множеств. Если оно обычное, то является своим элементом и, следовательно, оно — необычное, и наоборот.

В принципе понятие “множество” не является непосредственно очевидным: разные люди (научные школы) могут понимать его по-разному.

Функции,прямыепроизведения,отношения

Сначала дадим традиционное определение функции [18]. Даны два множества Х и Y. Функцией, которая определена

на множестве Х и принимает значение на множестве Y, называ-

21

ется закон (f), по которому каждому элементу х из множества Х (х [ Х) ставится в соответствие один элемент у из множества Y (у [ Y). Обычно это записывают в виде у = f(х). Множество Х есть область определения функции f, а множество Е = {у [ Y | ' х [ Х у = f(х)} # Y — множеством значений функции f. Функцию f, определенную на множестве Х и принимающую значения на множестве Y, обозначают так f : Х Y.

Элемент х [Х называется независимой переменной (аргументом), элемент f(х) называется значением функции на элементе х.

Пусть задана однозначная функция f, т. е. различным значениям ее аргументов соответствуют различные значения

функции (;х1 [ Х) (;х2 [ Х) (х1 х2) (f(х1) f(х2)). Знак “ ”

означает эквивалентность, например А В значит, что А эквивалентно В. (А тогда и только тогда, когда В).

Тогда ;у [ Е может быть поставлен в соответствие единственный элемент х [ Х, такой что у = f(х) и который обозначается х = f-1(у). Это значит, что на множестве Е определена функция f-1, которая принимает значения на множестве Х и называется обратной к функции f. Если задана функция f-1: Е Х и Y = Е, т. е. когда множество значений функции f совпадает со всем множеством Y, функцию f называют взаимно однозначным соответствием между множествами Х и Y.

Теперь сформулируем определение прямого или декартова произведения.

Прямым произведением множеств Х1, Х2, Х , …, Хn, n $ 2

называется множество различных упорядоченных наборов (n-мерныхвекторов)(х1,х2,х ,…,хn),гдех1[Х1,х2[Х2,х [Х …,

хn [ Хn, обозначаемое Х1 Х2 Х … Хn = = {(х1, х2, …,

(“;” — тождественно равно) и называется n-й степенью мно-

жества Х. [14,18].

22

В частном случае, если имеется два множества Х и Y, их прямым произведением будет множество различных упорядоченных наборов (двумерных векторов) (х, у), где х [ Х, а у [ Y, обозначаемые Х Y = {(х, у) | х [ Х, у [ Y}.

Например, имеем два множества Х={5, 6}, Y={ln , ln7}.

Х Y = {(5, ln ), (5, ln7), (6, ln ), (6, ln7)}. Y Х = {(ln , 5), (ln7, 5), (ln , 6), (ln7, 6)}.

т. е. Х Y Y Х.

Теперь дадим определение отношения. Даны множества

Х1, Х2, …, Хn, n $ 1; n-местным отношением между элементами множеств Х1, Х2, …, Хn называется любое подмножество пря-

мого произведения этих множеств, т. е. # Х1 Х2 , …, Хn.

отношение на множестве Х. [14, 18].

Для одноместных, двухместных и трехместных отношений часто используют специальные названия: унарные, бинарные, тернарные соответственно, т. е.

n = 1 — бинарное отношение # Х1;

n = 2 — бинарное отношение # Х1 Х2;

n = — тернарное отношение # Х1 Х2 Х .

Если отношение совпадает с прямым произведением, оно

называется полным, т. е. = Х1 Х2 … Хn. Рассмотрим конкретные примеры отношений.

Пример 1.1

X = {1, 2, 7, 2 , 5, 56}, = {х | х [Х и х < 2 }, = {1, 2, 7}, т. е.

при n = 1 отношение есть подмножество множества Х.

Пример 1.2

Х1 = {0, 1, 2}; Х2 = {5, 6, 7};

= {(х1, х2) | х1 [ Х1, х2 [ Х2, х2 < 6}; = {(0, 5), (1, 5), (2, 5)}.

Особый интерес представляют бинарные отношения, которые мы рассмотрим более подробно.

Если есть отношение между элементами множеств Х и Y, т. е. # Х Y, можно использовать запись х у, т. е. x связано с y соотношением .

2

Обратным к отношению # Х Y называется отношение

-1={(у,х)|(х,у)[ } # Y Х.

Геометрически понятие бинарного отношения показано на рис. 1.7.

Рис 1.7

D ={х | х [ Х, (ху) [ } — множество определения отношения , Х Y

Е ={у | у [ Y, (ху) [ } — множество значений отношений

, Х Y.

Заметим, что для -1 , Y Х D и Е поменяются местами. Точка х — элемент множества D , а множество (х) есть -образ элемента х, а точка у является некоторым элементом из (х).

Отсюда видно, что бинарное отношение является многозначной функцией [18].

Заметим, что прямое произведение множества действительных чисел (R) само на себя R R=R2 представляет собой систему координат на плоскости х0у.

Отношение # Х Y # R2 является графиком отношения .

Теперь рассмотрим конкретный пример бинарного отношения.

Пример 1.3 [14].

Дано множество Х = {1, 2, , 4, 5, 6, 7, 8, 9, 10}. Найдем отно-

шение , если оно задано так:

= {(х1, х2) | х1[Х1 х2[Х2 х1 — делитель х2, х1 # 5}.

Отношение имеет вид.

24

= {(1,1), (1,2), (1, ), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10), (2,2), (2,4), (2,6), (2,8), (2,10), ( , ), ( ,6), ( ,9), (4,4), (4,8),

(5,5), (5,10)}.

Теперь найдем множество определения и множество значений отношения :

D = {1, 2, , 4, 5}, Е = Х.

Представим полученное отношение в графическом виде. Для этого зададим систему координат. Осью абсцисс будет D , а осью ординат Е . По этим осям отложим элементы исходного множества Х, затем соответствующие пары (х1х2) отметим точками и получим графическое изображение нашего отношения

(рис. 1.8).

10

9

8

7

6

5

4

2

1

Рис. 1.8

Бинарные отношения можно представить в виде графа (множества вершин и множества ребер, см. раздел “Основы теории графов”).

Вершинами будут элементы исходного множества Х, а ребрамипары(х1х2).Вданномслучаеваженпорядокследованияэле-

25