Упражнение
1. Доказать справедливость последней теоремы для случаев, когда множества Ai могут быть конечными или пересекающимися.
2. Доказать, что пересечение счетно-бесконечного семейства счетных множеств является счетным.
Теорема 1.3
Для любого множества A множества A и 2A не являются равномощными.
Доказательство
Предположим противное. Пусть для некоторого множества A существует взаимно однозначное соответствие элементов этого множества и множества 2A .
Обозначим как Bx множество, соответствующее элементу x A.
Рассмотрим множество D
= {x
| x
Bx}.
То есть это все такие элементы из A,
которым соответствуют подмножества A,
не содержащие эти элементы. Если для
некоторого элемента- y
A справедливо равенство
By = ,
то y
D.
Следовательно, D
.
Возьмем y A такое что D = By .
Возможен лишь один из следующих случаев:
а) y By;
b) y By.
В первом случае имеем: если y By, то y D, т.е. y By.
Во втором случае: если y By, то y D. Поэтому y By, т.е. в обоих случаях получаем противоречие.
Поэтому предположение о существовании взаимно однозначного соответствия между элементами A и 2A является неверным.
Доказательство окончено.
1.2. ОТОБРАЖЕНИЯ И ФУНКЦИИ
Понятие отображения является фундаментальным для современной математики, поскольку всякий ее раздел связан с исследованием специальных множеств объектов вместе с системой операций над элементами множеств. Отображения являются важным случаем таких операций.
1.2.1. Основные понятия
Пусть A и B непустые множества. Отображением множества A во множество B называется всякое соотнесение каждому элементу множества A единственного элемента множества B.
При этом множество A называется областью определения, а B множеством значений отображения.
Для обозначения отображений будем использовать малые символы латинского алфавита.
Если f
отображение
множества A
во множество B,
то для представления этого факта
применяется специальное обозначение
f :
A
B.
Пусть отображение f: A B ставит в соответствие элементу a A элемент b B. В этом случае будем говорить, что f переводит a в b, и использовать запись f(a) = b.
Если f: A B, то запись f(A) обозначает множество элементов, в которые f переводит элементы A.
Отображение f: A B называется отображением множества A на множество B (или сюръекцией), если f(A) = B. В противном случае отображение называется отображением множества A во множество B.
Отображение f называется инъективным, если оно переводит разные элементы A в разные элементы B.
Замечание. Содержательно отображение f является сюръективным, если в каждый элемент B отображается хотя бы один элемент множества A. Отображение f инъективно, если в каждый элемент множества B отображается не более одного элемента из A.
Наглядным способом представления произвольных отображений являются диаграммы, имеющие вид (рис. 1.1):
A
B
a f
3
b 1
c 2
d
Рис. 1.1
Здесь элементы множеств A и B изображаются точками замкнутых областей на плоскости, а отображение f, сопоставляющее элементам A элементы B, ориентированными дугами, соединяющими элементы A с соответствующими им элементами B.
Рассмотрим пример диаграммы (рис. 1.2), на которой изображено неинъективное и несюръективное отображение.
A B
a
f
b x
c y
d z
Рис. 1.2
Отображение f неинъективно, поскольку f(a) = f(c). Кроме того, f это несюръективное отображение, так как элементу y не соответствует ни один элемент A.
Пусть f: A B. Обозначим как f1 соответствие элементам множества B совокупностей элементов A, определяемое по следующему правилу: если b B, то f1 ставит в соответствие b те элементы множества A, которые отображением f переводятся в элемент b.
Обозначим совокупность таких элементов как f1(b). Для приведенной ранее диаграммы соответствие f1 имеет следующий вид:
f1(x)
= {a, c,
d},
f1(y)
=
,
f1(z)
= {b}.
Если f1 сопоставляет каждый элемент B с одноэлементным множеством, то это соответствие порождает отображение, переводящее каждый элемент B в единственный элемент множества, соответствующего этому элементу. Такое отображение называется отображением (или функцией), обратным к f, и обозначается тем же символом, что и определяющее его соответствие элементов B и подмножеств A. Очевидно, что в приведенном примере отображение f не имеет обратного к нему отображения.
ТЕОРЕМА 1.4
Отображение f имеет обратное отображение тогда и только тогда, когда f является инъективным и сюръективным.
Доказательство
Необходимость. Пусть отображение f : A B имеет обратное отображение. По определению обратной функции это означает, что в каждый элемент множества B отображение f переводит хотя бы один элемент A. Поэтому f(A) = B, т.е. f это сюръективное отображение.
Поскольку f1 отображение, то отображение f переводит в каждый элемент b B ровно один элемент a A. Следовательно, f это инъективное отображение.
Достаточность. Пусть отображение f - инъективное и сюръективное. Тогда в каждый элемент b B отображение f переводит единственный элемент a A, т.е. f1 является отображением.
Теорема доказана.