Лекции_по_ДМ

Равномощность и мощность множеств

Два множества А и В называются равномощными или эквивалентными, если между их элементами можно установить взаимно-однозначное соответствие или если существует биекция А на В. Обозначение: А~В. Мощность – это то общее, что имеется у всех равномощных между собой множеств. Будем обозначать мощность множества А так: Р(А) или |A|.

Некоторые свойства равномощности:

1) Рефлексивность: А~А для любого множества А.

2) Симметричность: для любых множеств А и В, если А~В, то В~А.

3) Транзитивность: для любых множеств А, В и С, если А~В и В~С, то А~С.

Для доказательства каждого из этих свойств достаточно указать биекцию между множествами. Так в первом случае – это тождественное отображение А на А.

Утверждение: два конечных множества равномощны или эквивалентны тогда и только тогда, когда у них одинаковое число элементов.

Таким образом, мощность характеризует количество элементов множества. И для конечного множества, состоящего из n элементов, его мощность равна n. Для бесконечных множеств понятие «мощности» аналогично понятию «числа элементов», говорят, что бесконечные множества имеют бесконечную мощность. Итак, каждому множеству можно сопоставить некоторый объект – «мощность», называемый также «кардинальным числом», причем |A| = |В|  А~В и |A| < |В|  C B: |A| = |C| и |C|  |B|. Вообще говоря, множество может иметь одинаковую мощность со своим собственным подмножеством.

Примеры:

1) А={1,2,3,4,5…} и B={1,4,9,16,25…}  А~В, т.к. существует биективное отображение А на В по закону f(x)=x²,где xА.

2) Функция f(x)=10x устанавливает равномощность отрезков [0;1] и [0;10].

3) Два любых отрезка [a,b] и [c,d], а также два любых интервала (a,b) и (c,d) равномощны. Действительно, запишем уравнение прямой, проходящей через точки (а,с) и (b,d): . Тогда функция , где x[a,b], взаимно однозначно отображает [a,b] в [c,d], а функция , где y[c,d], отображает [c,d] в [a,b] и тоже взаимно однозначно.

4) Интервал (-/2; /2) ~ ℝ, т.к. y = tg(x), где x(-/2; /2) – биекция.

5) Любое конечное множество, состоящее из k элементов, равномощно отрезку натурального ряда {1,2,3,,k}. Поэтому элементы конечного множества могут быть перенумерованы: а₁,а₂,,а_k.

Конечное множество не равномощно никакому собственному подмножеству и никакому собственному надмножеству.
Число элементов конечного множества всегда больше числа элементов любого его собственного подмножества. Или мощность конечного множества всегда больше мощности любого его собственного подмножества.
Любое подмножество конечного множества само конечно. Любое надмножество бесконечного множества само бесконечно.

Из последней теоремы следует, что отрезок [0,1] – бесконечное множество, т.к. является надмножеством бесконечного множества чисел вида 1/n, где n – натуральное.

Бесконечное множество, равномощное множеству всех натуральных чисел называется бесконечно–счетным. Т.е. счетность множества есть не что иное, как возможность перенумеровать все элементы множества при помощи натуральных чисел так, чтобы все числа были использованы и различным элементам соответствовали различные числа. Конечные множества и счетно–бесконечные называются просто счетными.

Свойства счетных множеств.

1) Любое подмножество счетного множества само счетно.

2) Объединение конечного числа счетных множеств – счетное множество.

3) Объединение счетного числа конечных множеств – счетное множество.

4) Объединение счетного числа счетных множеств – счетное множество.

Действительно, обозначим множества М₁, М₂,, а элементы i–го множества: m_i₁,m_i₂,. Существует лишь конечное число элементов m_ik, для которых i+k=2, аналогично существует лишь конечное число элементов m_ik: i+k=3 и т.д.. Перенумеруем сначала все элементы, для которых i+k=2 (например, по возрастающим значениям i), затем (с помощью последующих чисел) все элементы, для которых i+k=3 и т.д.. При этом каждый элемент m_ik получит номер и различные m_ik будут иметь различные номера.

5) Если А и В – счетные множества, то А  В – счетное. Действительно, т.к. АВ={(а_i,b_j): a_iA, b_jB}, то для нумерации таких пар можно воспользоваться той же идеей, т.е. перенумеровать сначала пары, для которых i+j=2, затем с помощью следующих натуральных чисел пары, для которых i+j=3 и т.д..

6) Множество рациональных чисел счетно. Действительно, т.к. ℚ={x: x=a/b, где aℤ и bℕ}, то хℚ х является корнем уравнения bx–a=0. Рассмотрим h=b+|a|, перенумеруем сначала все рациональные корни, для которых h=1, затем новые корни, получающиеся при h=2 и т.д..

7) Множество полиномов с рациональными коэффициентами счетно. Сопоставим каждому полиному последовательность (а₁, а₂, ,а_n), составленную из его коэффициентов. Далее поступим аналогично тому, как это было сделано в пункте 6.

8) Множество всех алгебраических чисел (корней полиномов с рациональными коэффициентами) счетно.

Множество называется множеством мощности континуум, если оно равномощно множеству точек отрезка [0,1].

(Кантора) Множество точек отрезка [0,1] несчетно.

Доказательство: (от обратного) пусть это множество счетно. Это означает, что все точки отрезка можно перенумеровать: х₁, х₂, х₃, , х_j, . Каждое число x_j из этого промежутка можно представить в виде бесконечной десятичной дроби с периодом, не равным 9, причем единственным образом. Т.е. x_j = 0,x_j₁x_j₂x_jj, где x_jk – это k‑ая цифра десятичной дроби, представляющей число x_j. Построим теперь число b=0,b₁b₂b₃b_j таким образом, чтобы цифра b₁х₁₁, b₂х₂₂, b₃х₃₃, , b_jх_jj, . Очевидно, это можно сделать, например, взяв каждое b_i=1, если x_ii1, и b_i=2, если x_ii=1. Понятно, что число b[0,1], более точно b[0.1; 0.3]. Поэтому оно находится среди чисел х₁, х₂, х₃, , х_j, ., занимая в этой последовательности некоторое определенное, например, k-ое место. Т.е. b=x_k и 0,b₁b₂b₃b_k=0,x_k₁x_k₂x_k₃x_kk. Но тогда b₁=x_k₁, b₂=x_k₂, b₃=x_k₃, , b_k=x_kk, , что невозможно, т.к. выбор b_j осуществлялся так, чтобы b_jх_jj. Полученное противоречие доказывает теорему.

Из этой теоремы следует, что всякий отрезок [a,b] числовой прямой имеет мощность континуум, поскольку [a,b]~[0,1], т.к. f(x)=a+(b–a)x, где х[0,1] – биекция. Кроме того, всякий интервал (a,b) имеет мощность континуум, поскольку (a,b)~(0,1), а (0,1)~[0,1]; в последнем случае закон биективного отображения может быть, например, таким:

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

Из всех бесконечных множеств счетные множества являются «наименьшими».

Всякое бесконечное множество содержит счетное подмножество.

Доказательство: (по индукции) Пусть М – бесконечное множество. Тогда М. Выберем какой-нибудь элемент из М и обозначим его а₁. Пусть в М выбрано уже таким образом n различных элементов: а₁, а₂, , а_n. Так как M – бесконечно, то множество A_n=M \ {а₁, а₂, , а_n}, и можно выбрать элемент из A_n и обозначить его а_n₊₁. Ясно, что а_n₊₁ отличается от всех ранее выбранных, и множество {а₁, а₂, , а_n}∪ {а_n₊₁} счетно и является подмножеством М.

(О равномощности бесконечного множества собственному подмножеству) Всякое бесконечное множество равномощно своему некоторому собственному подмножеству.

Д оказательство: по предыдущей теореме множество М содержит счетное подмножество A={а₁,а₂,,а_n, }. Пусть В=М \ А  . Определим отображение f: MM следующим образом:

Очевидно, что f является биективным отображением множества М на его собственное подмножество М \ {a₁}, что и доказывает теорему.

Содержание