RUDN-I

Определение 2. На множестве X задано бинарное отношение R, если указано непустое подмножество R X2. Если (x, y) R, то говорят, что элементы x и y связаны соотношением R.

Обозначение:

В примерах 1)—4): только 1) x = y — отношение эквивалентности; в 2) x ≥ y — нет симметричности; в 3) x < y — нет рефлексивности и симметричности.

Обозначение: x y или x ≈ y — означает, что x эквивалентно y.

Пример 3. X = Z = {0, ±1, ±2, . . .}. Скажем, что m n, если m и n имеют одинаковую четность. Это отношение эквивалентности. Отметим, что Z = Z0 Z1, где Z0 — совокупность четных чисел, Z1 — совокупность нечетных чисел.

Определение 4. Пусть R — отношение эквивалентности, a X. Множество всех элементов x X, эквивалентных a, называется классом эквивалентности,www порожденным элементом a. Итак,

Xa = {x X : x a} — класс эквивалентности, порожденный a.

Теорема 1. Класс эквивалентности порождается любым своим элементом, т.е. если b Xa, то Xb = Xa.

Доказательство. 1) Для y Xb имеем y b. Но b Xa, т.е. b a. Следовательно, по свойству транзитивности y a, т.е. y Xa. Итак, y Xb y Xa, т.е. Xb Xa.

2) С другой стороны, a b и для z Xa имеем z a, a b z b, т.е. z Xb.

Вывод: Xa = Xb.

32 Тема 2. Множества и отображения

Теорема 2. Два класса эквивалентности либо не пересекаются, либо совпадают.

эквивалентности (порожденный этим элементом). Таким образом, получаем разбиение X на непересекающиеся классы эквивалентности.

Определение 5. Множество классов эквивалентности называют фактор-множеством множества X по отношению эквивалентности R и обозначают X | R.

Пример 4. Z = Z0 Z1 — разбиение на классы четных и нечетных чисел.

Пример 5. Пусть p N, p > 1. Два числа m, n Z назовем эквивалентными — сравнимыми по модулю p, если m − n = pk, где k Z (иначе: при делении на p они имеют одинаковые остатки).

Обозначение: m ≡ n(mod p).

Это отношение эквивалентности: оно рефлексивно (m ≡ m(mod p)),

Это отношения эквивалентности (проверить!) Факторы V | R1 — классы коллинеарных между собой векторов; V | R2 — классы равных векторов

Определение 6. Бинарное отношение R на множестве X называется отношением порядка (обозначение x y, причем пишем x y, если x ≠ y), если выполнены свойства

Если на множестве X введено отношение порядка, то X называют частично упорядоченным множеством. При этом подмножество S X называется линейно упорядоченным, если a b или b a для любых a, b S, a ≠ b.

Пример 7.

1) X = R2 = {x = (x1, x2), xi R} — частично упорядочено, если ввести отношение порядка x y условием x1 ≤ y1, x2 ≤ y2. Его подмножество S = {x = (x1, 0), x1 R} — линейно упорядочено.

2) Множество S(X) всех подмножеств непустого множества X частично упорядочено, если ввести отношение порядка: для A, B S(X) A B

A B.

2.3. Отображения множеств

Пусть X, Y — два непустых множества. Отображением f множества X во множество Y называется правило, которое каждому элементу x X ставит в соответствие определенный элемент y Y .

Символ y = f(x) обозначает тот элемент y Y , который получен из x при отображении f (иначе y = f(x) есть образ элемента x при отображении f). Обозначим для A X

f(A) = {f(x) : x A} — образ множества A X при отображении f,

отображении f.

класс эквивалентности, порожденный элементом a X. Отображение f сюръективно, но не инъективно (если хотя бы один из классов содержит более одного элемента).

5) y = x3 : R → R — биективно.

Определение 4. Пусть f : X → Y, g : Y → Z — два отображения. Суперпозицией (композицией, произведением) отображений g ◦ f называется отображение g ◦ f : X → Z, действующее по правилу

Например, x X имеем (f ◦ eX )(x) = f(eX (x)) = f(x), т.е. f ◦ eX = f. Второе равенство проверить самостоятельно!

Теорема 1. Пусть f : X → Y, g : Y → Z, h : Z → W . Имеет место равенство

т.е. суперпозиция отображений ассоциативна.

(свойство "обратности" взаимно).

Определение 6. Отображение f : X → Y называется обратимым, если существует обратное отображение g = f−1 : Y → X.

Теорема 2. Отображение f : X → Y обратимо тогда и только тогда, когда f биективно. При этом обратное отображение также биективно.

Доказательство. 1) Пусть f биективно. Для y Y существует x X : y = f(x) (из сюръективности f). Такой элемент x единственный (из инъективности f). Значит определено отображение g : Y → X, действующее

2) Пусть теперь f обратимо, g = f−1 — обратное отображение, g : Y → X. Тогда верно (5). Для y Y имеем

(5)

y = eY (y) = (f ◦ g)(y) = f(g(y)).

сюръективно. Далее, пусть x1, x2 X таковы, что f(x1) = f(x2). Тогда

Итак, f(x1) = f(x2) x1 = x2, т.е. f инъективно.

В результате имеем: f — сюръективно и инъективно, т.е. f — биекция.

Осталось проверить, что g = f−1 тоже биекция. Согласно замечанию 2 g = f−1 f = g−1, т.е. g обратимо (см. (6)). Но, как показано в п. 2) из обратимости следует биективность. Следовательно, g также биективно.

Теорема 3. Если отображение f : X → Y обратимо, то обратное отображение единственно.

Доказательство. Пусть g1 : Y → X, g2 : Y → X два обратных отображения к f. Тогда

Рассмотрим отображение h = g1 ◦ f ◦ g2 : Y → X. По свойству ассоциативности имеем

Итак, h = g1, h = g2 g1 = g2.

Теорема 4. Пусть f : X → Y, g : Y → Z — обратимые отображения. Тогда h = g ◦ f : X → Z также обратимо, причем

p ◦ h = eX , h ◦ p = eZ.

(сумма wwwи пересечение могут быть и бесконечного набора множеств Aα).

2.3. Пусть f : X → Y — отображение, A, B — подмножества в X. Показать, что

f(A B) = f(A) f(B), A B f(A) f(B), f(A ∩ B) f(A) ∩ f(B).

2.4. Привести пример отображения f : X → Y и подмножеств A, B в X таких, что f(A ∩ B) ≠ f(A) ∩ f(B).

2.5. Пусть X — конечное множество, f : X → X — отображение.

а) Показать, что из инъективности отображения f следует его сюръективность.

б) Показать, что из сюръективности отображения f следует его инъективность.

2.6. Пусть f : X → Y, g : Y → X — отображения, g ◦ f = eX — тожде-

2.8. Пусть f : X → Y — обратимое отображение, B, C — подмножества в Y . Показать, что

f−1(B C) = f−1(B) f−1(C), f−1(Y \ B) = f−1(Y ) \ f−1(B), f−1(B ∩ C) = f−1(B) ∩ f−1(C).

2.9. Пусть f : X → Y, g : Y → Z — обратимые отображения. Показать, что g ◦ f обратимо и (g ◦ f)−1 = f−1 ◦ g−1.

2.10. Пусть f : X → X — обратимое отображение, fn = f ◦ f ◦ . . . ◦ f,

2.11. Пусть X, Y — конечные множества. Показать, что существование биекции X → Y равносильно условию равенства числа элементов в этих множествах.