АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Сравнение мощностей

Теорема 1 (Кантора-Бернштейна).Пусть для множеств А и В существуют множества А₁ ÍА и В₁ ÍВ такие, что множество А равномощно с В₁, а множество В с А₁, то множества А и В равномощны.

Доказательство. Пусть f - биекция В на А₁, а g - биекция А на В₁. Тогда f(В)=А₁ и f(В₁)=А₂ ÍА₁. Суперпозиция h=fog функций является также биекцией А на А₂. Тогда функция h отображает

А на А₂

А₁ Í А на А₃ Í А

А₂ Í А₁ на А₄ Í А₃

А₃ Í А₂ на А₅ Í А₆ и т.д.

Отсюда следует, что h является биекцией

из А – А₁ на А₂ – А₃

из А₁ – А₂ на А₃ – А₄

из А₂ – А₃ на А₄ – А₅ и т.д.

Зададим множества

Е = (А – А₁)È(А₂ – А₃)È(А₄ – А₅)È(А₆ – А₇)È...

F = (А₂ – А₃)È(А₄ – А₅)È(А₆ – А₇)È...

D = АÇА₁ÇА₂ÇА₃ÇА₄Ç...

G = (А₁ – А₂)È(А₃ – А₄)È(А₅ – А₆)È...

Из замеченного выше следует, что h является биекцией E на F. Кроме того, справедливы равенства А = DÈGÈE и А = DÈGÈF. Следовательно отображение Т из А в А₁, определяемое соотношением

является биекцией А на А₁, т.е. множества А и А₁ равномощны. Последнее означает, что все четыре множества в теореме равномощны.

Теорема 2. Пусть Х и У два множества такие, что Х¹Æ, У¹Æ и в У не менее двух элементов. Тогда множество всех функций, действующих из Х в У является множеством, мощность которого больше мощности множества Х.

Доказательство. Обозначим множество функций, действующих из Х в У через У^Х. Доказательство разобьем на две части. Сперва покажем, что существует инъекция множества Х на часть множества У^Х. Пусть у₁ÎУ, у₂ÎУ, у₁ ¹ у₂ и х₀ÎХ. Построим функцию f[х₀] следующим образом: f[х₀](х₀) = у₁, а если х ¹ х₀, то f[х₀] (х) = у₂. При таком построении различным элементам в Х соответствуют различные функции. Например, если х₁ ¹ х₀, то f[х₁](х₀) = у₂. Таким образом, получаем инъекцию из Х в У^X.

Покажем теперь, что не существует биекции между Х и У^X. Предположим противное, что g является биекцией из Х на У^X и g(x) = f^x ÎУ^Х. Покажем, что существует fÎУ^Х такое, что f ¹ f^х для любого хÎХ. Пусть хÎХ и f^хÎУ^Х соответствующая функция. Определим f(х) = аÎУ из условия а ¹ f^х(x). Такой элемент а в У обязательно найдется, т.к. в У не менее двух элементов. Таким образом построенная функция f не будет совпадать ни с одной функцией f. Следовательно g не может быть биекцией.

Теорема 3. Множество всех подмножеств произвольного непустого множества Х имеет мощность большую, чем мощность множества Х.

Доказательство. Положим У={0,1}. Рассмотрим множество У^Х. Если fÎУ^Х, то f разбивает Х на два множества: Х₀(f) = {xÎX: f(x)=0} и Х₁(f) = {xÎX: f(x) = 1}. Таким образом, каждому fÎУ^X соответствует множество Х₁(f). Наоборот, если Х₁ - некоторое подмножество из Х, то полагая

получим fÎУ^Х. Этим мы построили биекцию между множеством всех подмножеств множества Х и множеством У^Х. Следовательно они равномощны и по теореме 2 мощность множества Х меньше мощности множества всех подмножеств.

Дата добавления: 2015-09-27 | Просмотры: 507 | Нарушение авторских прав