Эквивалентные множества
Мощность конечного множества
Мощностью конечного множества называют число элементов этого множества.
В общем случае мощность множества A обозначают |A|.
Для конечных множеств чаще встречается обозначение n(A).
Конечные множества легко сравнивать по мощности.
Если n(A) = n(B), то конечные множества A и B равномощны.
Например: Мощность множества A={1;3;5;7} равна n(A)=4.
Мощность множества B = {-3;13;2;4} равна n(B) = 4.
Множества A и B равномощны.
Взаимно однозначное соответствие двух множеств
Говорят, что между множествами A и B установлено взаимно однозначное соответствие, если:
1) каждому элементу множества A соответствует только один элемент множества B;
2) каждый элемент множества B при этом соответствует некоторому элементу множества A;
3) разным элементам множества A соответствуют разные элементы множества B.
Например:
Каждый раз, когда мы «считаем» множество каких-то объектов, мы устанавливаем взаимно однозначно соответствие между этим множеством и подмножеством натуральных чисел от 1 до некоторого n.
С этой точки зрения утверждение
«У Толи три друга: Вася, Коля и Петя» выглядит как соответствие:
Друзья Толи
Вася
Коля
Петя
№
1
2
3
Эквивалентность
Множества A и B называют эквивалентными (равномощными), если между ними можно установить взаимно однозначное соответствие.
Обозначение: $A \sim B$.
Такой подход даёт нам возможность сравнивать по мощности не только конечные, но и бесконечные (!) множества.
Например:
Сравним мощности множеств натуральных и натуральных чётных чисел:
A $ = \{n│n \in \Bbb N \},B = \{n|n⋮2, n \in \Bbb N\}$
Построим соответствие:
$ \begin{matrix} 1 & 2 & 3 & ... & n & ... \\ 2 & 4 & 6 & ... & 2n & ... \\ \end{matrix}$
Несмотря на бесконечность обоих множеств и отношение вложенности $B \subset A$, получаем взаимно однозначное соответствие, и может утверждать, что множества равномощны |A| = |B| и эквивалентны $A \sim B$.
Для мощности натуральных чисел используется специальное обозначение:
|N| = $\aleph_0$ – читается «алеф-нуль».
Счётные и несчётные множества
Множество называют счётным, если оно эквивалентно множеству натуральных чисел.
Чтобы доказать счётность множества достаточно придумать правило, по которому нумеруются его элементы.
Например:
Докажем, что множество целых чисел счётно.
Построим соответствие:
$ \begin{matrix} 1 & 2 & 3 & 4 & 5 & ... & 2n & 2n+1 & ... \\ 0 & 1 & -1 & 2 & -2 & ... & n & -n & ... \\ \end{matrix}$
Получаем взаимно однозначное соответствие между множествами целых и натуральных чисел. Значит, эти множества эквиваленты $\Bbb Z \sim \Bbb N$, и множество $\Bbb Z$ счётно.
Что и требовалось доказать.
Множество действительных точек отрезка [0;1] несчётно.
Мощность этого множества равна мощности континуума, $ c \gt \aleph_0$
Таким образом, множество отрезка [0;1]оказывается мощнее всего множества натуральных чисел.
Любой отрезок [a;b] и отрезок [0;1] эквивалентны.
Мощность любого действительного отрезка равна мощности континуума.
Любое множество, эквивалентное отрезку [0;1], называют континуальным.
Чтобы доказать несчётность множества, нужно показать, что нет таких правил, по которым можно его посчитать. Это значительно сложнее, чем доказать счётность.
Примеры
Пример 1. Среди данных конечных множеств укажите пары эквивалентных:
а) A = {1;3;5}, B = {5;7;9}, C = {0;1}
n(A) = 3, n(B) = 3, n(C) = 2
$A \sim B$
б) A = $ \{n|n \le 3, n \in \Bbb N \}$
B = $ \{n|1 \lt n \lt 5, n \in \Bbb N \}$
C = $ \{n||n| \le 1, n \in \Bbb Z \}$
Запишем с помощью перечисления:
A = {1;2;3}, B = {2,3,4}
C = {-1,0,1}
n(A) = 3, n(B) = 3, n(C) = 3
$A \sim B, B \sim C, A \sim C$
Пример 2. Пусть A - множество всех окружностей плоскости, B - множество всех правильных треугольников этой плоскости. Каждому треугольнику ставится в соответствие вписанная в него окружность. Является ли это соответствие взаимно однозначным?
Рассматриваем соответствие $B \rightarrow A$.
В каждый треугольник можно вписать окружность, и притом только одну. Условие единственности (1) выполняется.
Вокруг каждой окружности можно описать бесконечное количество правильных треугольников, поворачивая их на некоторый угол относительно центра окружности.
Условие (2) не выполняется.
Соответствие не является взаимно однозначным.
Пример 3. Постройте взаимно однозначное соответствие между отрезком [0;1] и отрезком [2;7] с помощью линейной функции.
Искомая функция имеет вид y = kx+b, где
$$x \in [0;1], y \in [2;7]$$
Прямая проходит через две точки: A(0;2),B(1;7).
Уравнение прямой:
$$ \frac{x-x_A}{x_B-x_A} = \frac{y-y_A}{y_B-y_A}$$
$$ \frac{x}{1} = \frac{y-2}{7-2} \Rightarrow 5x = y-2 \Rightarrow y = 5x+2 $$
$$ x \in [0;1] \overset {y=5x+2} \mapsto y \in [1;7] $$
Пример 4*. Постройте взаимно однозначное соответствие между отрезком [0;1] и отрезком [a;b], $a \in \Bbb R, b \in \Bbb R$ с помощью линейной функции.
Искомая функция имеет вид y=kx+b, где $x \in \Bbb [0;1], y \in \Bbb [a;b]$
Прямая проходит через две точки: A(0;a),B(1;b). Уравнение прямой:
$$ \frac{x-x_A}{x_B-x_A} = \frac{y-y_A}{y_B-y_A} $$
$$ \frac{x}{1} = \frac{y-a}{b-a} \Rightarrow (b-a)x = y-a \Rightarrow y = (b-a)x+a $$
$$ x \in [0;1] \overset{y = (b-a)x+a} \mapsto y \in [a;b] $$
