<< Предыдущая

стр. 70
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Непосредственно из определения следуют основные соотношения
из теории множеств, которые иллюстрируются диаграммами Венна.
Например, верна следуюш;ая лемма.

Лемма А.2. Если А С В и В С С, то А С С.
Доказательство. Пусть х — элемент множества А. Нам надо по­
казать, что он принадлежит множеству С. Поскольку А С В^ имеем
X ^ В по определению подмножества. Кроме того, нам известно,
что В С С. Значит, х Е С. Ш
Обратите внимание на то, что это рассуждение является стро­
гим доказательством, в то время как соответствуюп1;ая диаграм­
ма Венна лишь иллюстрирует свойство, но не доказывает его. Диа­
грамма Венна, подтверждаюш;ая утверждение, которое Вы хотите
А.2, Отношения


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


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

Определение А.З. Произвольное подмножество в прямом произ­
ведении Ах А называется (бинарным) отношением на множестве А.
Объясним это понятие на примере. Рассмотрим отношение «мень­
ше чем или равно» на множестве натуральных чисел. Ясно, что оно
дает нам совокупность
LE = {{х^у)\ д:,^ G N, X меньше или равно у}.
Любое отношение, с которым Вы встречались ранее, может быть
записано подобным теоретико-множественным образом. Есть даже
более удобный способ определения отношения LE^ а именно^
LE = {{x,y)\x,yeN, х-у^Щ.
Очевидно, такими громоздкими обозначениями неудобно пользо­
ваться на практике. Поэтому пару (ж, у) G Д, т. е. упорядоченную
пару элементов, находяш;уюся в отношении Д, обозначают как х Ry,
Если теперь заменить обозначение LE на стандартное «^», то мы
получим хорошо известное и полезное отношение порядка х ^ у.
Далеко не все отношения на множестве представляют интерес.
Однако все используемые отношения в математике обладают одним
или сразу несколькими из перечисленных в следуюш;ем определении
свойств.

Определение А.4. Отношение R на множестве А называется
- рефлексивным^ если для любого х Е А имеет место включение
{х,х) е R',
- симметричным^ если включение {х^у) G R влечет (у^х) G R;

^В этом определении, в отличие от российской традиции, число О относится к
натуральным числам. — Прим. перев.
Прилоэюение А, Основная математическая терминология

- антисимметичным^ если отношения xRy и yRx выполнены од­
новременно только для равных элементов х = у;
- транзитивным^ если включения xRy и yRz влекут xRz.

Вернемся к нашему примеру «^». Очевидно, оно рефлексивно,
поскольку X ^ х для всякого числа X. Оно не симметрично, т. к. из
неравенства х ^ у совершенно не следует неравенство у ^ х. Зато
оно антисимметрично. Действительно, все мы привыкли к тому, что
совместное выполнение неравенств х ^ у и у ^ х возможно только
тогда, когда х ˜ у. Следует отметить, что отношение «^» обладает
и транзитивностью.
Отношения, похожие на «^», встречаются столь часто, что им
дали специальное название:

Определение А.5. Рефлексивное, антисимметричное и транзи­
тивное отношение называется отношением частичного порядка.

Определение А.6. Антисимметричное и транзитивное отношение
R называется отношением линейного^ или полного, порядка^ если
для любой пары элементов х^ у либо (гг, у) Е Л, либо (^, х) G R.
Другой важный класс отношений — это отношения эквивалент­
ности.

Определение А.7. Рефлексивное, симметричное и транзитивное
отношение называется отношением эквивалентности.
Очевидным примером отношения эквивалентности на множестве
натуральных чисел служит отношение «равно». К одной из главных
задач в любой науке относится задача о классификации объектов,
т. е. задача о причислении каждого из изучаемых объектов к одному
из набора непересекаюш;ихся множеств. Каждое из таких множеств
можно называть классом эквивалентности. Если интересующие нас
свойства объектов постоянны на каждом классе эквивалентности,
то можно ограничиться рассмотрением лишь самих классов, не за­
ботясь об их содержании. Такой «упрош;енный» взгляд помогает луч­
ше понять ситуацию. На математическом жаргоне процесс перехо­
да от объектов к классам их эквивалентности называется факто­
ризацией по отношению эквивалентности. В алгебре и геометрии
процесс факторизации используют для построения новых объектов:
фактор-группы, фактор-многообразия и т. д. Пример, который мы
сейчас рассмотрим, вероятно, наиболее близок Вам, поскольку ка­
сается арифметики остатков.
A.S. Функции

Пусть т — фиксированное натуральное число. Рассмотрим от­
ношение эквивалентности на множестве целых чисел, согласно ко­
торому числа X и у эквивалентны, если их разность делится на т.
Вам следует убедиться, что данное отношение действительно явля­
ется отношением эквивалентности. Классы эквивалентности пред­
ставлены следуюш;им списком:
О = {..., —2т, —т, О, т , 2 т , ...} ,
Т = {..., - 2 т + 1, -т + 1, 1, m + 1, 2 т + 1, . . . } ,

m — 1 = {..., —m — 1, —1, ттг — 1, 2т — 1, З т — 1, . . . } .
Обратите внимание на то, что мы имеем ровно т классов эквива­
лентности, по одному для каждого из возможных остатков от деле­
ния на т . Их обычно называют классами вычетов по модулю т , а
всю совокупность классов | 0 , . . . , m — 1} обозначают через Z/mZ.
Это множество имеет структуру кольца и называется кольцом выче­
тов по модулю т. Если т — р — простое число, то кольцо вычетов
является полем и обозначается символом F^.


А.З. Функции
Сформулируем два определения функции. Первое из них — словес­
ное, и поэтому легче воспринимается неопытным читателем. Вто­
рое — теоретико-множественное.

Определение А.8. Функцией называется правило, согласно кото­
рому каждому элементу одного множества, области определения^
ставится в соответствие элемент другого множества, мноэюества
значений. Причем каждому элементу области определения сопоста­
вляется один и только один элемент множества значений^.
Стоит отметить, что понятие «функция» включает в себя не
только правило, скажем f{x) = rr^, но и два множества: область
определения и множество значений.
Перейдем к примерам.
1. Формула f{x) = л/х не определяет функцию из М в R, посколь­
ку квадратный корень из отрицательных чисел не определен.

^В российской традиции такое правило называют отображением^ оставляя тер­
мин «функция» для отображений с числовым множеством значений. — Прим.
перев.
Прилоэюение А. Основная математическая терминология

Это не будет функцией и из множества положительных ве­
щественных чисел М^о в множество всех вещественных чисел
М, т. к. у каждого положительного вещественного числа есть
два квадратных корня. С другой стороны, это правило задает
функцию из М^о в М^о-
2. Правило / ( ^ ) — ^ не является функцией из R в R, но задает
функцию из R \ {0} в R.
3. Заметим, что в определении функции ничего не говорится о
том, что каждый элемент множества значений должен иметь
прообраз. Поэтому правило f{x) = х^^ переводящее веществен­
ное число в вещественное число, является функцией.
Наше определение не строго, поскольку мы четко не оговорили, что
означает слово «правило». Дадим менее понятное, но более форма­
лизованное определение на теоретико-множественном языке.

Определение А.9. Функцией F : А • В из множества А в мно­
жество В называется такое подмножество в прямом произведении
F d Ах В, что
(1) если [х,у) е F и {х^ z) е F, то у = z\
(2) f\R^ любого X Е А найдется такой у Е В^ что (ж, у) G F.

Множество А называется областью определения, В — множе­
ством значений функции. Первое условие определения означает, что
каждый элемент области определения переходит не более чем в один
элемент множества значений. Второе — каждый элемент области
определения переходит по крайней мере в один элемент множества
значений. Для функции F : А • В и элемента х Е А через F{x) мы
обозначаем тот единственный элемент из множества значений 5 ,
для которого {x^F{x)) G F.
Иногда определена композиция функций. Если даны две функции
/ :А • В и д :В • С, то их композицией называется функция
д оf :А • С, состоящая из пар {x^g{f{x))).

Лемма АЛО. Пусть даны три функции: / : А • В^ д : В •С
ик:С • D, Тогда
ho{go f) = {hog)of.
Доказательство. Пусть пара (а,й) лежит в h о [д о f). Тогда по
определению композиции существует b Е В^ при котором (а, Ь) Е f
и (Ь,d) Е (hog). Применяя определение композиции еще раз, полу­
чаем, что найдется такой элемент с Е С^ что (Ь, с) Е д и (с, d) Е h.
А.З. Функции 459

Следовательно, (а, с) G (g о / ) , откуда (а, d) Е ho [д о f). Значит,
ho{go f) c{hog)of.
Аналогично доказывается обратное включение. •
Особенно важное значение имеет так называемая тождественная
функция.

Определение А.11. Тоэюдественной функцией на множестве А
называется функция id^ = {(х,а;)| х G А}.

Лемма А.12. Любая функция / : А • В удовлетворяет соотно­
шениям:
/ о idA = id^ о / .
Доказательство. Пусть х — произвольный элемент множества А,
Тогда
( / о idA){x) = fiidAix)) = fix) = ideifix)) = (idB О f){x). Щ

Ha протяжении всей книги мы пользовались следующими двумя
свойствами:

Определение А.13. Функция / : А • В называется инъектив-
ной^ если равенство f{x) = f{y) возможно только при х — у.
Функция / : А • В называется сюръективной^ если ;1^ля ка­
ждого элемента b Е В найдется прообраз, т.е. такой а Е А^ что
/(а) = Ь.
Если функция обладает обоими свойствами, т. е. она инъективна
и сюръективна, ее называют биективной (или l-l-соответствием),
Обратимся к примерам.
1. Функция / : R • R, определенная формулой f(x) — х -\- 2^
биективна.
2. Функция / : N • N, определенная формулой f{x) = ж + 2,
инъективна, но не сюръективна, поскольку числа О и 1 не име­
ют прообразов.
3. Формула f{x) = х^ определяет сюръективную, но не инъектив-
ную функцию / : R • R^o? поскольку любое положительное
вещественное число имеет два вещественных корня степени 2.
Следующее утверждение мотивирует изучение биективных функций.
Прилооюение А. Основная математическая терминология

Лемма А. 14. Функция / : А • В биективна тогда и только
тогда, когда существует обратная ей функция д : В >- А, т. е.
такая функция, что fog и gof — тождественные функции. Функция
д обычно обозначается через д = f˜^.
Оставим проверку этого утверждения в качестве упражнения.
Заметим, что согласно лемме, функция д тоже будет биективной.


А.4. Перестановки
Пусть А — конечное множество, состоящее из п элементов. Без
ограничения общности можно предполагать, что А = {1, 2, . . . , п}.
Биективная функция / : А • А называется перестановкой или
подстановкой. Множество всех перестановок п-элементного множе­
ства обозначается через Ofi-
Пусть А = {1, 2, 3}. На нем есть, например, такая перестановка:
/(1) = 2, /(2) = 3 и /(3) = 1. Такой способ задания перестановок
слишком громоздок. Математики (будучи крайне ленивыми людь­
ми) предлагают следующий способ задания перестановок:


^ V2 3 1
Важно отметить, что в этом обозначении (которое легко распро­
страняется на любое п) в любой строчке каждое число между 1 и п
появляется лишь один раз. Первая строчка всегда содержит числа
от 1 до п, записанные в порядке возрастания. Любая такая матрица
изображает собой некоторую перестановку и любую перестановку
можно записать такой матрицей. Замечание о соответствии между
матрицами и перестановками подводит нас к следующей лемме.

Лемма А. 15. Число перестановок в Sn равно п\.
Доказательство. Ясно, что число перестановок совпадает с коли­
чеством разных вторых строчек матриц, их изображающих. Попы­
таемся заполнять эти строки, следя за количеством возможностей.
На первое место второй строки мы можем поставить любое из п чи­
сел. На второе — уже любое из п — 1, поскольку одно число занято.
На третье — любое из п — 2, и т. д. Осталось заметить, что число
всех вариантов заполнения второй строки совпадает с произведением
возможностей для каждой позиции: \Sn\ = п • {п — 1) - • • 1 — п\. Ш
Поскольку перестановки — это функции, мы можем брать их
композицию, что на математическом жаргоне называется умноже-
А.4' Перестановки

нием перестановок. Напомним, что д о f означает, что мы сначала
применяем функцию / , а потом д. Следовательно, композиция пере­
становок
, / 1 2 3 V /^ 1 2 3
^^^^U 3 1 ; Ч з 2 1
действует по правилу:
1 ь^Зь^ 1,
2 н-^ 2 ь^ 3,

<< Предыдущая

стр. 70
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>