Шептунов М. В. - Теория множеств (1023559), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

X=(h, v)

будет описывать состояние самолёта.

Определение 1.23. Длиной кортежа называется число его элементов.

Например, множество

a=(a₁, a₂, ..., a_n)

является кортежем длины n с элементами a₁, a₂, ..., a_n.

Кортежи длины 2 называют парами, кортежи длины 3 – тройками, 4 – четвёрками и т. д.

Для кортежей возможны следующие частные случаи:

1. кортеж (a) длиной 1;

2. пустой кортеж длины 0, обозначаемый ( ).

В отличие от обычного множества, в кортеже могут быть

одинаковые элементы, например, два одинаковых элемента во фразе, одинаковые значения долготы и широты географической точки и проч.

Определение 1.24. Точками пространства или векторами называются упорядоченные множества, элементами которых являются вещественные числа.

Например, кортеж (a₁, a₂) может рассматриваться как точка на плоскости или вектор, проведённый из начала координат в данную точку (рис. 1.7). Компоненты a₁ и a₂ будут проекциями вектора на оси 1 и 2, т. е.

Пр₁(a₁, a₂)= a₁; Пр₂(a₁, a₂)= a₂.

2

a₂ (a₁, a₂ )

a₁ 1

Рис. 1.7. Проекции 2-элементного кортежа

Трёхэлементный кортеж (a₁, a₂, a₃) может рассматриваться как точка в трёхмерном пространстве или как трёхмерный вектор, проведённый из начала координат в эту точку (рис. 1.8). Компоненты a₁, a₂, a₃ будут проекциями вектора на оси 1, 2, и 3, т. е.

Пр_i(a₁, a₂, a₃)= a_i, i=1, 2, 3.

3

a₃

(a₁, a₂, a₃)

a₂ 2

a₁

1

Рис. 1.8. Проекции 3-элементного кортежа

В дальнейшем мы будем рассматривать компоненты n-элементного кортежа как проекции его на соответствующие оси, т. е.

Пр_i a = a_i, .

Определение 1.25. Прямым произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая – множеству Y.

Т. о., элементы прямого произведения множеств представляют собой 2-элементные кортежи вида (x, y).

Формальное определение записывается следующим образом:

.

Пример 1.9. Пусть X={1, 2}, Y={1, 3, 4}. Тогда прямое произведение двух этих множеств будет таким:

={(1, 1), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4)}.

4

(x, y)

3 Y y

2

1

x

0 1 2 X

a б

Рис. 1.9. Геометрические иллюстрации прямого произведения

множеств

Полученный результат поясняется на рис. 1.9, а.

Пример 1.10. Пусть X и Y – это отрезки вещественной оси.

Их прямое произведение, , отображается заштрихованным прямоугольником, представленным на рис. 1.9, б.

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

.

Операция прямого произведения множеств распространяется и на большее количество множеств.

Частным случаем операции прямого произведения является понятие степеней множества.

Определение 1.26. s-той степенью произвольного множества M называется прямое произведение s одинаковых множеств, равных M.

Это выражается следующей записью:

s раз

1.5. Вопросы для самоконтроля

1. Что представляет собой множество и как оно обозначается ?

2. Что такое элементы множества и как они обозначаются ?

3. Что такое универсальное множество (универсум) ?

4. Какое множество называется пустым ?

5. Чем конечные множества отличаются от бесконечных ?

6. Что такое мощность множества ?

7. Какие множества называются равными, а какие равномощными ?

8. Какими свойствами обладает равенство множеств ?

9. Корректна ли запись {3, 3, 5, 7} и почему ?

10. Что такое счётные и несчётные множества ?

11. С какими важнейшими дисциплинами связана теория множеств ?

12. Перечислите способы задания множеств и области их применения.

13. Что такое верхняя и нижняя граница множества, точная верхняя

и точная нижняя граница множества ?

1. В чём состоит парадокс Рассела задания множеств ?

2. Как избежать парадокса Рассела ?

3. Что такое подмножество и надмножество ?

4. Сформулируйте теорему о верхней и нижней границах

подмножества.

1. Какие свойства присущи подмножествам ?

2. Что такое собственное и несобственное подмножества ?

3. Что такое булеан ?

4. Что такое диаграмма Эйлера-Венна ?

5. Перечислите операции над множествами и дайте характеристику

каждой операции.

1. Запишите формальное определение каждой названной операции.

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

3. Какие множества называются непересекающимися ?

4. Приведите примеры непересекающихся множеств.

5. Что такое множества, находящиеся в общем положении ?

6. Приведите пример для двух множеств, находящихся в общем

положении.

1. Какому условию удовлетворяет универсальное множество, играя

в алгебре множеств роль единицы ?

1. Какие пять соотношений возможны между двумя множествами ?

31. Назовите основные логические высказывания и соответствующие им операции теории множеств.

32. В чём состоит “закон противоречия и “принцип исключённого третьего” ?

1. Как установить истинность тождества, не прибегая к диаграмме

Эйлера-Венна ?

1. Дайте определение кортежа, его элементов; приведите примеры.

2. Что называется длиной кортежа ?

3. Назовите возможные частные случаи кортежа (в смысле его

возможной длины).

1. Может ли кортеж содержать одинаковые элементы ?

2. Что называется точками пространства (векторами) ?

3. Изобразите проекции двух- и трёхэлементного кортежа,

запишите соответствующие формулы.

1. Дайте определение прямому произведению множеств, приведите

примеры.

1. Верно ли тождество: ?

2. Что называется s-той степенью произвольного множества ?

2. ОТНОШЕНИЯ И ФУНКЦИИ

2.1. Отношения

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

Рассмотрим элемент yRx. Элемент y находится в отношении R к элементу x, что записывается в виде:

y R x.

Пример 2.1. Пусть X – множество людей. Для каждого человека xX обозначим через Rx множество его детей. Тогда R²x – множество внуков человека x; R³x – множество правнуков человека x; R^-1x – это множество родителей человека x.

Если изобразить людей точками и нарисовать стрелки, идущие из x в Rx, получим генеалогическое дерево.

x

Rx

R²x

Рис. 2.1. Генеалогическое дерево

Таким образом, в этом примере символ R обозначает не что иное, как “быть детьми данного человека” (рис. 2.1).

Определение 2.1. n-местным отношением R на множествах A₁… A_n называется подмножество прямого произведения множеств

.

Наиболее часто встречаются отношения при n=2. Это уже

упомянутые бинарные отношения.

Как следует из данного выше определения, бинарное отношение между двумя множествами A и B есть подмножество прямого произведения .

Если же эти множества эквивалентны, например равны A, то подмножество A² определяет отношение на множестве A.

Если связать с каждым бинарным отношением R между множествами A и B ещё два множества – область определения D(R) и область значений Q(R), то их возможно определить следующим образом:

, .

Хотя каждое отношение является множеством и может быть обозначено прописной буквой, существует также практика обозначения отношений строчными греческими буквами, например . Часто используют следующие обозначения:

a) , т. е. (a, b) находится в ;

б) a b, a связано с b отношением ;

в) .

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

Рассмотрим шесть основных свойств отношений. При описании этих свойств будем считать, что x, y и z – любые элементы из

множества X.

1. Рефлексивность: x R x – истинно

2. Антирефлексивность: x R x – ложно

3. Симметричность: x R y  y R x

4. Антисимметричность: x R y и y R x  x=y

5. Несимметричность: если x R y – истинно, то y R x – ложно

6. Транзитивность: x R y и y R z  x R z.

Опираясь на шесть перечисленных свойств, рассмотрим теперь

некоторые важные виды отношений.

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

Примерами отношений эквивалентности являются:

1. отношение “быть на одном курсе”;

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

и т. д.

Для более чёткого формулирования отношения эквивалентности будем считать, что термин “отношение эквивалентности” применяется

лишь при выполнении следующих трёх условий:

1. каждый элемент эквивалентен самому себе;

2. высказывание о том, что 2 элемента являются эквивалентными,

не требует уточнения, какой из элементов рассматривается первым и какой вторым;

1. два элемента, эквивалентные третьему, эквивалентны между

собой.

Для обозначения эквивалентности применяют символ .

Характеристики

Список файлов книги