§2. Отображения, соответствие, равномощность

Пусть каждому элементу множества А по какому-нибудь закону или правилу сопоставлен некоторый элемент множества В, тогда это сопоставление называют однозначным соответствием между А и В или однозначным отображением А в В. Для обозначения таких отображений используют записи вида : А  В , где буква  обозначает закон, правило или формулу, по которым это соответствие осуществляется. При этом множество А называется областью определения отображения  и обозначается D_. Все элементы множества В, которые сопоставлены некоторым элементам множества А образуют область значений отображения , которая обозначается Е_. Отображение А в В называется разнозначным, если разным элементам множества А сопоставляются разные элементы множества В. Отображение : А  В называется полным, если А = D_ и Е_ = В. Разнозначное и полное отображение

: А  В называется взаимно однозначным отображением А на В, такое отображение  имеет обратное отображение В на А, обозначение: ^1: В  А.

Пример 10. Пусть А  множество студентов, присутствующих на лекции, В  множество стульев и С  множество столов в аудитории, где читается эта лекция. Тогда каждому студенту соответствует стул, на котором он сидит, это соответствие является отображением А в В, обозначение: ₁: А  В. Здесь ₁ обозначает условие: «стул, на котором сидит студент». При этом ₁ однозначное и разнозначное отображение, так как каждый студент сидит на одном стуле. Область определения D_1 = А, и область значений Е_1 – это множество стульев, на которых сидят студенты. Если все стулья заняты, то Е_1 = В, и ₁ является взаимно однозначным отображением А на В, при этом его обратное отображение ₁^1 каждому стулу сопоставляет студента, который на нем сидит.

Имеется второе соответствие: каждому студенту соответствует стол, за которым он сидит, это отображение А в С, обозначение: ₂: А  С. Здесь ₂ обозначает условие: «стол, за которым сидит студент». При этом ₂ однозначное, но не разнозначное, так как за одним столом могут сидеть несколько студентов. Область определения = А, и область значений – это множество столов, за которыми сидят студенты. Если все столы заняты, то = С, и ₂ будет однозначным отображением А на С, при этом ₂ не имеет обратного отображения, так как обратное соответствие не является однозначным.

Определение 1. Множества А и В называются равномощными, если существует взаимно однозначное отображение одного множества на другое. Обозначение: |A| = |B|. Конечные множества будут равномощными, если они имеют одинаковое число элементов. Ниже описываются возможные ситуации для равномощных бесконечных множеств.

Определение 2. Бесконечное множество А называется счетным, если оно равномощно множеству натуральных чисел N = {1, 2, ..., n, ...}.

Это означает, что все элементы множества А можно занумеровать без повторений, т. е. представить его в виде: А = {а₁, а₂, ... , а_n, ... }.

Пример 11. 1). Для любого натурального числа k множество А = { k n / nN} является счетным. Здесь взаимно однозначное отображение N на А задается формулой (n) = kn.

2). Множество целых чисел Z = {0, 1, 2, ..., n, ...} является счетным. Здесь взаимно однозначное отображение N на Z определяется так: (2n) = n, (2n+1) = n. Действительно: (1) = 0, (2) = 1, (3) = 1, (4) = 2, (5) = 2, ... .

3). Множество всех пар целых неотрицательных чисел является счетным. Действительно, это множество можно представить в виде указанной ниже бесконечной таблицы пар чисел. Тогда взаимно однозначная нумерация пар этого множества определяется формулой:

Эта формула нумерует по порядку все элементы таблицы по ее диагоналям сверху вниз, например:

(0; 0) = 1, (0; 1) = 2, (1; 0) = 3, (0; 2) = 4, (1; 1) = 5, (2; 0) = 6.

Тем самым, имеется взаимно однозначное отображение указанного множества пар на N.

( 0; 0)	( 0; 1)	(0; 2)	. . . . .	(0; m)	. . . . .
(1; 0)	(1; 1)	(1; 2)	. . . . .	(1; m)	. . . . .
(2; 0)	(2; 1)	(2; 2)	. . . . .	(2; m)	. . . . .
. . . . . . . . . .	. . . . . . . . . .	. . . . . . . . . .	. . . . . . . . . .	. . . . . . . . . .	. . . . . . . . . .
(m;0)	(m;1)	(m;2)	. . . . .	(m; m)	. . . . .
. . . . .	. . . . .	. . . . .	. . . . .	. . . . .	. . . . .

4). Множество рациональных чисел Q является счетным.

Действительно, каждое рациональное число х взаимно однозначно представимо парой (m, n) целых чисел: х = , где mZ , nN и дробь несократимая. Так же, как в предыдущем примере, доказывается, что множество таких пар счетное, следовательно, Q тоже счетное.

Определение 3. Бесконечные множества, не являющиеся счетными, называются несчетными.

Пример 12. 1). Множество всех бесконечных последовательностей натуральных чисел является несчетным.

Доказательство использует так называемый диагональный метод

(см. ).

2). Множество иррациональных чисел I и множество вещественных чисел R несчетные.

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

3). Множество всех точек на прямой линии несчетное.

Действительно, на каждой прямой можно выбрать начало, направление и масштаб. Тогда эта прямая превратится в числовую ось, и на ней каждой точке будет соответствовать (взаимно однозначно) ее числовая координата. Следовательно, множество точек на прямой равномощно R, и поэтому оно несчетное. Аналогично доказывается, что любые интервалы или сегменты являются несчетными множествами.

Еще одну важную операцию над множествами надо определить в этом разделе. Упорядоченная пара – это два объекта, расположенных в некотором определенном порядке. В теории множеств упорядоченную пару множеств А и В обозначают через (А, В) и определяют следующим образом:

(А, В) = {{А}, {А, В}}. (39)

Это двухэлементное множество, один элемент которого есть неупорядоченная пара {А, В}, а другой, {А}, определяет первый элемент упорядоченной пары. Такие пары обладают следующим свойством: (А₁, В₁) = (А₂, В₂) тогда и только тогда, когда А₁ = А₂ и В₁ = В₂. В паре (39) множество А называется первой координатой, и В – второй координатой.

В терминах упорядоченных пар можно определить упорядоченные тройки множеств, например: Это упорядоченная пара, первый элемент которой есть (А, В), а второй элемент есть С. При этом, множества А, В. С называются 1-й, 2-й, 3-й координатами этой тройки, и две тройки равны между собой, если равны их соответствующие координаты. Аналогично определяются упорядоченные n-ки множеств:

(А₁, А₂, …, А_n) = (((А₁, А₂, …, А_n-1), А_n).

Такие множества называются кортежами длины n.

Определение 4. Декартовым произведением множеств М₁, М₂, … , М_n

Называется множество всех упорядоченных n-ок (х₁, х₂, …, х_n), в которых координаты х₁, х₂, …, х_n пробегают множества М₁, М₂, … , М_n, соответственно. (Обозначение: М₁М₂ … М_n). n-ой декартовой степенью множества М называется декартово произведение n множеств М. (Обозначение: Мⁿ = ММ … М).

Пример 13. Записать все элементы декартова произведение множеств

A = {2, 3} и B = {a, b, c}.

Решение: АВ = {(2, a), (2, b), (2, с), (3, a), (3, b), (3, с)}.

Любое подмножество Р декартовой степени Мⁿ называется n-местным отношением на множестве М: РМⁿ. При этом считается, что кортеж (х₁, х₂, …, х_n) удовлетворяет отношению Р, если этот кортеж принадлежит множеству Р. Обозначение: Р(х₁, х₂, …, х_n)  (х₁, х₂, …, х_n)  Р.