В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах, страница 14

Следовательно,(( ( x0 ))( x0 )  f ( x0 )  (( ( x0 ))( x0 )  1, т.е. пришли к противоречию.Заметим теперь, что любое действительное число из [0;1] являетсядействительной функцией, заданной на [0;1] , откуда | [0;1] | | R [0;1] | ,а поскольку R [0;1] не эквивалентно [0;1] , то | [0;1] || R [0;1] | .Задача 5.33. Доказать, что множество всех подмножеств множества A не эквивалентно A , и при этом | A || 2 A | .Решение.

Предположим, что существует биекция  : A  2 A .Пусть A0  {a  A | a   (a)} . Из сюръективности  следует, чтоa0  A :  (a0 )  A0 . Возможны два случая: 1) a0  A0   (a0 )  a0  A0 ; 2) a0  A0   (a0 )  a0  A0 . В обоих случаях приходим кпротиворечию. Заметим, что инъективное отображение  : A  2 A82строится очевидным образом: a  A  (a)  {a} .Таким образом,| A || 2 A | и 2 A не эквивалентно A , а следовательно, | A || 2 A | .Задача 5.34.

Будем говорить, что последовательность натуральныхчисел b1 , b2 , ... растет быстрее, чем последовательность натуральныхan 0 . Доказать, что (а) для каждой послеn  bnдовательности натуральных чисел существует последовательность натуральных чисел, растущая быстрее ее; (б) если множество последовательностей натуральных чисел A обладает свойством, что для произвольной последовательности натуральных чисел существует последовательность из A , растущая быстрее этой последовательности, то множество A не является счетным.Решение. (а) Для любой последовательности натуральных чиселa1 , a2 , ...

и последовательности натуральных чисел b1 , b2 , ... , гдечисел a1 , a2 , ... , если limbn  nan выполняется limn an 0 . (б) Предположим, что существуетbnбиекция  : N  A . Положим bn  [( (1)) n  ...  ( (n)) n ]n , n  N. Тогда для любых n, i  N выполняется n  i ( (i)) n( (i)) n1 .bn[( (i)) n ]n n( (i )) n 0 , чтоn bnНо тогда для любого i  N справедливо равенство limпротиворечит условию, наложенному на множество A.Задача 5.35. Доказать теорему Кантора-Бернштейна: еслиA  B , B  A , то AB.Решение. По условиям теоремы существуют биекции f : A  B1  B, g : B  A1  A .

Не ограничивая общности , можно считать, что A  B   (если A  B  , то возьмем в качестве A множество A  {1}  A, а вместо B – множество B  {2}  B ; тогда A ∼∼ A, BB  , но A  B   ). Пусть x – произвольный элемент из A.83Положим x0  x и определим последовательность элементов {x n } согласно следующим правилам: (1) Полагаем k  0 . Если x0  A1 , топоследовательность состоит из единственного элемента x 0 . В противном случае полагаем k  1, x1  g 1 ( x0 )  B . (2) Если x1  B1 , то искомой последовательностью является {x0 , x1 } .

В противном случае,полагаем k  2, x2  f1( x1 )  A . (3) Пусть уже определены элементыпоследовательности {x0 , x1 ,..., xk }, где k  2 . Тогда возможны случаи:(3а) Пусть k четно. Тогда проверяем выполнение условия x k  A1 . Если это условие выполняется, то x k – последний член последовательности. В противном случае, добавляем к последовательности новый членxk 1  g 1 ( xk )  B . (3б) Пусть k нечетно. Тогда проверяем выполнениеусловия x k  B1 . Если это условие выполняется, то x k – последнийчлен последовательности.

В противном случае, добавляем к последовательности новый член xk 1  f 1 ( xk )  A и т.д.Возможны два случая: (а) Последовательность {x n } конечна, т.е.состоит из элементов x0 , x1 ,..., xk . Число k называется порядком элемента x . (б) Последовательность {x n } бесконечна. Тогда x называетсяэлементом бесконечного порядка.Разобьем теперь A на множества: Ae – множество элементов четного порядка; Ao – множество элементов нечетного порядка; A – множество элементов бесконечного порядка. Аналогично разобьем множество B (т.е. рассмотрим те же варианты относительно произвольногоэлемента x из B , которые были рассмотрены ранее относительно произвольного элемента x из A ).

Докажем теперь, чтоf : Ae  Bo ; f : A  B ; g 1 : Ao  Be .(5.3)Будем обозначать члены последовательности для определения84множеств Be , Bo , B через x n . Тогда для доказательства первого утверждения из (5.3) заметим, что если x0  Ae , и x0 , x1 ,..., xk – членыописанной последовательности {x n } , где число k (порядок элементаx0 ) четно и xk  A1 , то для x0  f ( x0 )  B1 членами последовательности {x n } будут x0 , x1  f1( x0 )  x0 , x2  x1 ,..., xk 1  xk , т.е.x0  Bo .

Второе утверждение очевидно. Для доказательства третьегоутверждения заметим, что, Ao  A1 . Но тогда, если x0  Ao иx0 , x1 ,..., xk – члены описанной последовательности {x n } , где число k(порядок элементаx0 ) нечетно, и xk  B1 , то для x0  g 1 ( x0 )  x1членами последовательности {x n } будут x0  x1 , x1  x2 ,...,xk 1  xk , т.е. x0  Be .Совершенно аналогично доказывается, чтоf1: Bo  Ae ; f1: B  A ; g : Be  Ao .(5.4)Из (5.3),(5.4) заключаем, что (5.3) задает биекцию  : A  B .85БИБЛИОГРАФИЧЕСКИЙ СПИСОК1.

Лавров И.А., Максимова Л.Л. Задачи по теории множеств,математической логике и теории алгоритмов. – М.: Наука, 1984.2. Нефедов В.Н., Осипова В.А. Курс дискретной математики. –М.: Изд-во МАИ, 1992.86ОГЛАВЛЕНИЕПредисловие……………………………………………………….……....3Тема №1. Алгебра множеств……………………………………….….…4Тема №2. Упорядоченные пары.

Прямое произведение множеств.Бинарные отношения. Функции………………………………………...25Тема №3. Рефлексивность, симметричность, антисимметричность,транзитивность бинарных отношений. Отношение эквивалентности…………………………………………………………………...….…41Тема №4. Отношение порядка. Частичный и линейный порядки………………………………………………….....................................52Тема №5. Равномощность множеств. Счетные, континуальныемножества…………………………………………………...……….…...68Библиографический список…………………………………...…….…..8687.