Обратные отображения.

Пусть CÌ A. Множество f(C)={y|xÎ CÙ y=f(x)}Í B называется образом множества C. Если DÌ B, множество f^–1(D)={x|f(x)Î D}Í A называется полным прообразом множества D.

Теорема (основное свойство биекции): Если f - биективное отображение множества X на множество Y и A и B подмножества X, то f(AÇ B)=f(A)Ç f(B). (образ пересечения равен пересечению образов).

Доказательство:

Пусть yÎ f(AÇ B) Þ $xÎ AÇ B, такое что y=f(x) Þ xÎ A Ù xÎ B Þ f(x)Î f(A) Ù f(x)Î f(B) Þ f(x)=y Î f(A)Ç f(B).

Обратно, пусть yÎ f(A)Ç f(B) Þ yÎ f(A) Ù yÎ f(B), тогда, поскольку f – биекция, значит, у y есть единственный прообраз - x, причем xÎ A Ù xÎ B Þ xÎ AÇ B Þ f(x)=yÎ f(AÇ B).

Что и требовалось доказать.

Замечание 1: Требование биективности можно ослабить и заменить инъективностью (докажите).

Замечание 2: Для произвольной функции выполняется лишь f(AÇ B)Ì f(A)Ç f(B). (докажите и приведите пример, когда обратное включение не имеет места)

Определение 2: тождественным отображением множества X на себя называется тождественное отношение на X, то есть I_X: X®X по правилу

I_X: x a x.

Теперь мы готовы приступить к ответу на поставленный в начале параграфа вопрос. Ответ на него дает критерий:

Теорема (критерий инъективности): функция f: A® B инъективна тогда и только тогда, когда f ^-1: B® A является функцией.

Доказательство:

Отношение f ^-1 является функцией тогда и только тогда, когда

(z, x)Î f ^-1Ù (z, y)Î f ^–1 Þ x=y º (x, z)Î f Ù (y, z)Î f Þ x=y º z=f(x) Ù z=f(y) Þ x=y º (в силу транзитивности равенства и того, что x, y Î D_f) f(x)=f(y) Þ x=y. Но это и есть требование инъективности.

Что и требовалось доказать.

Следствие 1: если f инъективна, то f^-1 тоже инъективна. (самостоятельно)

Следствие 2: если f биективное отображение A на B, то f ^-1 тоже биективное отображение B на A.

Пусть функция f: A®B инъективна и aÎ D_f, тогда f(a) Î E_f. Ясно, что f^–1(f(a))=a, так как если бы полный прообраз элемента f(a) состоял не из одного элемента, то это противоречило бы инъективности f. С другой стороны, если bÎ E_f, то, поскольку E_f= , bÎ и так как f^-1 - функция, b=f(f^-1(b)). Тем самым доказано важное свойство инъективной функции:

Теорема: если функция f инъективна, то

f ^-1o f = и fo f ^–1= .

Следствие 1: если f биекция A на B, то

f ^-1o f = I_A и fo f ^–1= I_B..

Замечание: это утверждение можно обратить.

Определение 3: биективное отображение множества A на себя называется преобразованием множества A.

Следствие 2: если f есть преобразование множества A, то f ^-1o f = fo f ^–1= =I_A..

Далее. Если функции f: A®B и g: B ®C инъективны, то gof - тоже инъективна и значит определена (gof)^-1, которая, по соответствующему свойству отношений, равна f ^–1 o g ^-1 и действует из C в A. Оформим этот факт в виде утверждения:

Свойство 2 (композиции функций): если f и g инъективны и gof функция, то (gof)^-1= f ^–1 o g ^-1.

Следствие: если f: A®B и g: B ®C биективные отображения, то (gof)^-1 есть биекция C на A, при этом

(gof)^-1= f ^–1 o g ^-1.

§4. Мощность множества.

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

Определение 1: два множества называются биективными (обозначается X~Y), если существует биективное отображение X на Y.

Замечание. Очевидно, что отношение «быть биективными» («~») на множестве всех множеств является отношением эквивалентности (проверьте!). Поэтому во многих книгах по теории множеств вместо слова «биективные» используют слово - «эквивалентные»

Введем обозначение N _m={1, 2, 3,..., m}, где mÎ N. При этом, не вдаваясь в подробности, мы будем пользоваться тем, интуитивно ясным фактом, что N _m не биективно N _k, если m ¹ k

Определение 2. Два множества имеют одинаковую мощность (равномощны), если они биективны и будем писать |A|=|B|. При этом будем считать, что /Æ /=0, так как оно биективно только самому себе. Множество X называется конечным, если $ mÎ N (N _m~X), при этом говорят, что мощность X равна m, /X/=m. Множество называется счетным, если N ~X, обозначается | X| = À ₀. Множество X имеет мощность континуум, если оно биективно отрезку [0, 1] Ì R, обозначение: |X| = À ₁.

Обсудим сначала свойства конечных и счетных множеств. Установить биекцию между множеством X и N_m (или N) - это значит каждому элементу из X поставить в соответствие единственное натуральное число, начиная с 1, то есть попросту пронумеровать. Таким образом, если X ~ N_m, то его можно расположить в виде конечной последовательности x₁, x₂,..., x_m. А если X ~ N, то в виде бесконечной последовательности x₁, x₂,....

Поэтому, чтобы построить биективное отображение N_m на X или N на X, достаточно указать алгоритм перенумерования элементов множества X.

Обсудим некоторые свойства конечных множеств.

Свойство 1. Если S конечно и f: S ® S инъективное отображение, то f - биекция.

Доказательство. Если S = Æ, то результат тривиален. Пусть S ¹ Æ. Тогда существует биекция N_m ~ S для некоторого m Î N и S можно записать в виде S= {а_1, а₂,..., а_m }, тогда f(S) ={ f(a₁), f(a₂),..., f(a_m) }, причем все f(a_i)- различны, т.к. f- инъективно. Пусть f(S) ¹ S, т. е. есть элементы b_1, b₂,..., b_k которые не принадлежат f(S). Тогда S= { f(a₁), f(a₂),..., f(a_m), b₁, b₂,..., b_k }. Тогда рассмотрим отображения N _m+k ® S: 1® f(a₁),..., m® f(a_m), m+1 ® b₁,..., m+k ® b_k. Это биекция. Значит S ~ N _m+k. Противоречие. Что и требовалось доказать.

Следствие: Множество N - бесконечно (не является конечным).

Доказательство: Отображение f: N ® N, по правилу n a n+1 инъективно, но не сюръективно (у 1 нет прообраза). Значит N не является конечным.В качестве пояснения можно предложить следующую цепочку логически эквивалентных формул: (A Ù B Þ C º º º () º º B ).

Что и требовалось доказать.

Это значит, что N не биективно никакому своему конечному подмножеству.

Определение 2. Символ, соответствующий мощности некоторого множества, называется кардинальным (порядковым) числом.

В частности, к кардинальным числам относятся все натуральные числа, а также À ₀ и À ₁.

Определение 3: Кардинальное число, не являющееся натуральным, называется трансфинитным числом.

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

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

Множество А называется ограниченным, если оно ограниченно сверху и снизу.

Свойство 2. Ограниченное подмножество из N - конечно.

Доказательство: Поскольку N Ì R, то каждое подмножество из N ограничено снизу нулем. Пусть АÌ N ограничено сверху некоторым m Î N. Рассмотрим отображение f: A ® N, такое что если А= {a₁, a₂,..., a_i,...} и а₁ < а₂ < а₃ <... < m, то f(a_i) = i. Ясно, что f(a_i) £ a_i и ясно также, что f- инъективно. Должно существовать n £ m, такое что f: A® N_n - биективно. Если это не так, то $ а_р Î А (f(a_p) > m), а значит a_p ³ f(a_p) > m. Но А ограничено сверху числом m. Противоречие. Значит, А - конечно.

Свойство 3. Каждое подмножество конечного множества - конечно.

Доказательство: Пусть А Í В и В - конечно. Если В= Æ, то А=Æ и утверждение доказано. Пусть В ¹ Æ. Тогда существует биекция f: В ~ N_m, для некоторого m Î N. Тогда f(A) Í N_m, следовательно, f(A) ограничено, а значит, конечно. Но f(A) ~ A, значит А тоже конечно.

Что и требовалось доказать.

Следствие. Любое множество, имеющее бесконечное подмножество, само бесконечно.

Перейдем теперь к счетным множествам (см.[11], [12]).

Утверждение 1. Множество всех целых чисел счетно (|Z| = À ₀).

Доказательство: Построим биекцию N ® Z следующим образом:

0 «1, -1 «2, 1 «3, -2 «4, 2 «5.

Т.е. n «2n + 1, если n ³ 0

n «2|n|, если n < 0.

Что и требовалось доказать.

Упражнения:

1. Доказать, что множество всех четных положительных чисел счетно.

2. Доказать, что множество 2, 4, 8,..., 2ⁿ - счетно.

Утверждение 2: Множество всех рациональных чисел счетно. (|Q|= À ₀).

Доказательство: Каждое рациональное число однозначно записывается в виде несократимой дроби = , q Î N, p Î Z. Назовем сумму | p |+ q высотой рационального числа a. Ясно, что число дробей с данной высотой n- конечно. Например, высоту 1 имеет только одно число = 0; высоту 2 числа и ; высоту 3 числа ; ; ; . Будем нумеровать все рациональные числа по возрастанию высоты. Т.е. сначала выпишем числа высоты 1, потом- числа высоты 2 и т.д. При этом всякое рациональное число получит некоторый номер, т.е. будет установлено взаимно- однозначное соответствие между N и Q.

Что и требовалось доказать.

Установим теперь некоторые общие свойства счетных множеств.

Свойство 1. Всякое подмножество счетного множества конечно или счетно.

Доказательство: Пусть А- счетное множество, а В- его подмножество. Занумеруем элементы множества А= {а₁, а₂,..., а_n,...}. Пусть a_n1, a_n2,... те из них, которые входят в множество В. Если среди чисел n1, n2,... есть наибольшее, то В- конечно. В противном случае В- счетно, т.к. его элементы a_n1, a_n2,... занумерованы числами 1, 2,...

Что и требовалось доказать.

Свойство 2: Объединение любого конечного или счетного множества счетных множеств есть счетное множество.

Доказательство: Пусть А₁, А₂,... - счетные множества. Мы можем считать, что они попарно не пересекаются, т.к. иначе мы рассмотрели бы вместо них множества А₁, А₂ \ А₁, А₃\ (А₁ È А₂),..., каждое из которых не более чем счетно по свойству 1, а их объединение равно А₁È А₂È..... Поскольку каждое из множеств А₁, А₂,... счетно, то все элементы множества А₁, А₂,... можно записать в виде следующей бесконечной таблицы:

Занумеруем все элементы по диагоналям (как показано на рисунке).

Ясно, что при этом каждый элемент каждого из множеств получит определенный номер. Т.о. будет установлено взаимно- однозначное соответствие между А₁È А₂ È... и множества N.

Что и требовалось доказать.

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

Доказательство: Очевидно. Доказать самостоятельно (указание: выбираем, нумеруем, нехватки элементов не будет, поскольку множество бесконечно).

Теперь мы готовы к тому, чтобы ввести отношение порядка на множестве кардинальных чисел. Для мощностей конечных множеств это сделать несложно, поскольку (см.[4]) ½ N_k ½ £ | N_m |, если k £ m. Но как быть с бесконечными множествами? Основой для упорядочивания служит теорема Кантора- Бернштейна:

Теорема (Кантор- Бернштейн). Пусть А и В два произвольных множества. Если множество А биективно некоторому подмножеству множества В, а В биективно некоторому подмножеству множества А, то множества А и В биективны.

(Без доказательства, см.[11])

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

1) А биективно некоторому подмножеству В, а В биективно некоторому подмножеству А.

2) А содержит подмножество, биективное В, но в В нет подмножества биективного А.

3) В содержит подмножество, биективное А, но в А нет подмножества биективного В.

4) Ни в одном из этих двух множеств нет подмножества биективного другому.

В первом случае множества А и В в силу теоремы Кантора- Бернштейна биективны, а значит | А | = | В |. Во втором случае естественно считать, что | В | < | А |, а в третьем | А | < | В |. Наконец, в четвертом случае нам пришлось бы считать, что мощности множеств А и В несравнимы между собой. На самом деле этот случай невозможен! (см. [11]).

Итак, для любых двух множеств А и В можно сказать, что либо | А | = | В |, либо | А | < | В |, либо | В | < | А |.

Таким образом, учитывая свойство 1 счетных множеств и следствие из свойства 1 конечных множеств, можно сказать, что " k Î N (k < À ₀). Более того, учитывая свойство 3 счетных множеств, можно сказать, что счетное множество есть самое «маленькое» из бесконечных множеств. А что можно сказать про À ₀ и À ₁ -?

Утверждение 3: À ₀ < | [0, 1] | = À ₁.

Доказательство: Пусть | [ 0, 1] | = À ₀, т.е. все элементы множества [ 0, 1] можно перенумеровать. Пусть

a₁= 0, а₁₁ а₁₂ а₁₃... а_1n...

a₂= 0, а₂₁ а₂₂ а₂₃... а_2n...

a₃= 0, а₃₁ а₃₂ а₃₃... а_3n... (1)

.....................................

a_n= 0, а_n1 a_n2 a_n3... a_nn...

.....................................

здесь a_ik- k-я десятичная цифра числа a_i. Построим число b= 0, b₁b₂b₃...b_n..., применив так называемую диагональную процедуру Кантора: пусть b₁- любая цифра не совпадающая с а₁₁, b₂- любая цифрв не совпадающая с а₂₂ и т.д., b_n- произвольная цифра, не совпадающая с а_nn. Эта дробь не может совпадать ни с одной дробью из списка (1), поскольку b отлична от a₁, по крайней мере первой цифрой, от a₂- второй, от a_n- n- ой. Таким образом, никакое счетное множество действительных чисел, лежащих на отрезке [0, 1] не исчерпывает этого множества. Значит À ₀ < À ₁.

Что и требовалось доказать.

Замечание 1. Некоторые числа могут быть записаны в виде десятичной дроби двумя способами: с бесконечным числом нулей или с бесконечным числом девяток. Таким образом, несовпадение двух десятичных дробей еще не гарантирует различия изображаемых ими чисел ( = 0, 5000... = 0, 4999...). Однако, если дробь b строить осторожнее, так, чтобы она не содержала ни нулей, ни девяток, полагая, например, b_n= 2, если a_nn= 1 и b_n= 1, если a_nn¹ 1, то доказательство становится корректным.

Упражнение: Доказать, что существует биекция между

1). [0, 1] и (0, 1), 2). [0, 1] и [0, 1), 3). [0, 1] и (0, 1 ].

Утверждение 4: | [a, b ]| = |[c, d ] |, если a< b и c< d.

Доказательство: Надо установить биекцию:

[a, b] ~ [c, d]. Ее легко построить, рассмотрев рисунок:

Для построения требуемой биекции достаточно выписать уравнение прямой, проходящей через точки А (а, с) и В (b, d).

Что и требовалось доказать.

Таким образом (с учетом результатов упражнения 4) получаем, что все отрезки, интервалы и полуинтервалы - равномощны (они имеют мощность континуум).

Утверждение 5: | R | = À ₁.

Доказательство: В силу утверждения 4 (0, 1) ~ (- ; ). Биекцию же между (- ; ) и R дает отображение тангенс:

tg: (- ; ) ® R. Таким образом, множество всех действительных чисел имеет мощность континиум.

Можно доказать, что если есть множество некоторой мощности, то всегда можно построить множество большей мощности. В частности, если А - некоторое множество, то его мощность | А | < | Р (А) |. Известно (см. [12]), что | Р (N) | = À ₁, а мощность множества всех непрерывных на [0. 1] функций больше À _{1 .} Естественно, что | Р (R)|, больше À _{1 .} Однако | R´ R | и | R´ R´ R | равны À _{1 .}

(Доказательство и подробное обсуждение есть в книгах [11] и [12]).