§ 2. Обратные функции и отображения

Используя результаты, полученные в предыдущем параграфе, исследуем сложные функции. Пусть дана функция f: А → В в этом случае f^-1 является функцией тогда и только тогда, когда / инъективна, а отображени­ем тогда и только тогда, когда f биективна. В большин­стве рассматриваемых нами случаев f — биекция; тогда — также биекция, а функции f~^l ° / и / ° /^_1 являют­ся тождественными отображениями.

Рассмотрим функции f: А → В и g: В→ С. Тогда:

а) если fиg инъективны, то существует g°f;

б) если fипсюръективны, то также существует g°f (см. упражнение 3.1, 8).

Обратным отношением к g ° f является . По­рядок должен быть обратным, как указано на рис, 3.2.

Заметим, что если g; — отображение, т. е. , то и, следовательно, . Аналогично, если то . Если f и g инъективны, то су­ществует g° f; следовательно, — функция. Сум­мируя вышесказанное, имеем: из ℛ_i=𝕯_g следует, что отображение; если f и g также инъек­тивны, то — биекция. Очевидно, что эти критерии выполняются, если fиg — биекции.

Упражнение 3.2.

1. Пусть ; показать следующее:

а) если f сюръективна и g — отображение, то

б) если fug — биекции, то

в) если

§ 3. Мощность множеств и счетность

Мы почти подошли к тому моменту, когда появляет­ся возможность использовать понятие биекции для фор­мализации понятия мощности и процесса вычислений. Вычисление важно не только само по себе, но также и потому, что функция является вычислимой тогда и толь­ко тогда, когда связанное с ней множество счетно. Вна­чале дадим определение множества N. Чтобы прояснить наши намерения, заметим, что любое число (1, 2 и т. д.) может быть использовано двумя различными способами: как существительное или как прилагательное, дающее номер другого существительного. Мы будем рассматри­вать числа как существительные.

В качестве предварительного определения N по­ложим

Из этого рекурсивного определения следует, что , и если к произвольному элементу из N прибавить 1, та полученный результат также принадлежит N. Следовательно, N содержит 1, и т. д.

К сожалению, это определение неприемлемо по при­чинам, которые будут рассмотрены ниже. Тем не менее здесь есть несколько важных моментов. Например, так как N (по крайней мере интуитивно) бесконечно, то мы должны иметь механизм, при помощи которого можно конструировать последующие элементы из конечного множества,— другими словами, никогда не сможем напи­сать точное представление N. Мы также должны приду­мать имя числу, которое называем «один», и аналогично для «два» (сокращение 1 + 1), «три» и т. д. Конечно,

мы могли бы выбрать любые имена или символы для этой цели, однако было бы неправильно использовать неудобные обозначения. Перейдем теперь к недостаткам данного определения. Проверка его обнаруживает, что оно содержит два новых символа: «1» и «+»; остальные символы известны из построения множеств. Символ «1» можно объяснить вышеуказанным способом. Однако сим­вол «+» означает операцию на N и, следовательно, не может быть использован для определения N. (Операции будут определены в § 6.)

Чтобы выйти из этого затруднения, вернемся к осно­вам теории множеств. Напомним, что нам нужно было построить число, которое на 1 больше максимального из всех предшествующих чисел. Легко получить аналогич­ный процесс для множеств (называемый построением сверхмножества с количеством элементов на 1 больше, чем в данном множестве).

Пример 3.1. Пусть А = {х, у, z) и В = {х, у, z, А). Тогда , поэтому В\А={А} и имеет толь­ко один элемент. //

Эта конструкция может быть перенесена на произ­вольное множество. Начиная от множества X, мы можем определить последующее множество (обозначается X^⨁): X^⨁ = . Чтобы использовать этот процесс для по­строения N, требуется некоторое начальное множество. Выберем в качестве такого множества (0). Оно имеет один элемент. (Многиз авторы начинают с 0, Это по­рождает множество {0} N. Мы не считаем 0 натураль­ным числом, и в этом причина такого выбора начально­го элемента. Не существует универсального условия по отношению к 0 и N. Всегда следует проверять условные обозначения, принятые в других книгах, при обращении к.ним.) Из {0} создадим последовательности {ø}:{ø}^⨁ = {ø, {ø}},{ø}^⨁⨁={ø,{ø},{ø,{ø}}} и т. д. Это при­водит к прогрессии, которая является более привлека­тельной, чем 1, 1 + 1, 1 + 1 + 1, ..., по крайней мере ее конструкция является строго определенной. Чтобы на­вести порядок в вышесказанном, выберем временно име­на для этих множеств.

Переименуем {ø} как 1, 1^⨁ как 2, 2^⨁ как 3 и т. д. Тогда

1 = {ø},

2- {ø, 1},

3- {ø, 1, 2}, ...

Поэтому, например, множество 3 имеет три элемента. Чтобы избежать неточности, давайте снова изменим обозначения и определим множества

N_m = m^⨁\{ø}={1,2,…,m},

Тогда из определения следует, что (число т) и что если а, b ϵ N, то a ≤ b тогда и только тогда, когда . Поэтому наша вера в упорядоченность N фор­мально обоснована. Итак, множества N и N_m (для каж­дого m ϵ N) определены и могут быть использованы в дальнейшем. Введем некоторые понятия.

Определение. Два множества биективны (обо-вначается Х~У), если между ними существует биек­ция. Непустое множество конечно, если оно биективно некоторому N_m. (mϵN), Если X ~ N_m, то мощность множества (обозначается |X|) равна т. (Числа в дан­ном случае используются как прилагательные. Например, если Р — множество всех людей и X⊆P таково, что X ~ N_m, то X есть множество из т людей.) Напом­ним, что пустое множество ø биективно только по отно­шению к себе, является конечным и имеет мощность 0, т. е. |ø| =0.

Говорят, что множество счетно, если оно биективно N. Символ Nо (алеф-нуль) часто используют для обо­значения мощности N. Множество называется счетным, если оно конечно или счетно, и может быть сосчитано с использованием биекции f: , если X счетно, или биекция , если , или f: ø→X; i-й эле­мент X является образом i отображения f. //

Перед тем как установить несколько полезных ре­зультатов, отметим одно существенное свойство мно­жеств и биекций: отношение , определенное на множе­стве S посредством

= {(Х, У): X ~ У},

является отношением эквивалентности, а подмножества S, входящие в классы эквивалентности, состоят из мно­жеств, имеющих одинаковую мощность. Следовательно, чтобы продемонстрировать тот факт, что два множества имеют один и тот же размер, требуется построить биек­тивное отображение между ними.

Пример 3.2. Покажем, что |N|=|Z|, Отображение

является биекцией между N и Z. //

В предыдущем примере греческая буква использо­валась для обозначения биекции. Использование грече­ских букв , … для обозначения произвольных биекций является общепринятым в текстах по логике и будет здесь использоваться в этом контексте (среди дру­гих). Однако, чтобы не было путаницы с пустым множе­ством ø, мы будем избегать использования этих букв в этом параграфе.

Пример 3.3. Покажем, что |N| = |Q|. Это требует несколько более сложных рассуждений. Вначале рас­смотрим счетное количество копий N, каждая из них соответствует своему номеру п ϵ N. Мы можем записать это множество как и упорядочить его элементы, как указано на рис. 3.3, Такое упорядочивание является

биекцией , задаваемой отношением . Каждый положительный элемент Q может быть связан с дробью (р, q), где р и q взаимно простые, и связан с элементом (р, q) множест­ва естественным образом. Поэтому, записывая

Получаем

(Использование отношения «≤» между этими бесконеч­ными числами не обосновано. Соотношение |A|≤|B| следует читать как «A биективно подмножеству B». До­казательство неочевидного факта, что это отношение яв­ляется отношением порядка^-, лежит за пределами этой книги.) С другой стороны, каждое pϵN может быть представлено как р/1 и, следовательно, связано с парой (р, 1). Поэтому |N| ≤|T| ≤ |N|, откуда следует, что |Т| = |N|. Для достижения нашей цели существенно сказать следующее. Возьмем диагонально упорядоченное множество N N (см. рис. 3.3) и выбросил» из него па­ры, имеющие нетривиальный общий множитель. Это да­ет метод нумерации элементов Т, однако трудно дать формулу, которая связывала бы элементы Т с элемента­ми N. Теперь мы должны повторить наше рассуждение применительно ко всем радиационным числам. Это мож­но сделать несколькими способами. Выберем для нагляд­ности следующий. Расширяя уже полученное соответст­вие между Г и N N до оператора между Q и Z N, получаем

что дает требуемый результат. Построение биекции между Z N и N N оставляем в качестве упраж­нения. //

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

1. Если S конечно и χ: S→S — инъективное отобра­жение, тогда х биективно.

Доказательство. Пусть выполнены условия ут­верждения. Если S = ø, то требуемый результат триви­ален. Если , тогда существует биекция для некоторого m N и отображение инъективно: N_m → N_m и, следовательно, является биекцией. (Доказательство этого факта оставляем в качестве уп­ражнения.) Основная идея заключается в переупорядо­чивании m объектов и известна под названием «прин­цип раскладывания по гнездам». Даны m гнезд, каждое в своем ящике. Любая схема переселения, при которой в одном ящике может быть не более одного гнезда, должна использовать все m ящиков, т.е. является перестановкой N_m (рис. 3.4). Однако — биек­ция; следовательно, и χ также биекции. (Обратно, если χ: S → S не сюръективно, то S должно быть беско­нечным.)

2. Множество N бесконечно, так как отображение на N, определенное как и , инъективно, но не би- ективно (нет элемента, отображающегося в 1). Следова- тельно, обращая предыдущий результат, получаем, что N не может быть конечным.

Подмножество А из R ограничено сверху (снизу) ес­ли существует верхняя (нижняя) граница. А ограничен­но, если оно ограничено сверху и снизу.

3. Ограниченное подмножество из N конечно. Доказательство. Каждое подмножество из N

ограничено снизу нулем. Пусть А ⊆ N ограничено свер­ху некоторым mϵN. Определим отображение χ: А → N

так, что если и а₁ < а₂ < а₃ < ...<т (такой порядок возможен, так как A⊆N),то

Следствием этого является соотношение и χ, очевидно, ииъективпо. Оно также должно быть биек­цией, т. е. . для некоторого п ≤ т. Если это не так, тогда существует а_Р ϵ А такое, что и, таким образом, . Однако А ограничено т; поэтому мы пришли к противоречию. Следовательно, χ — биекция на N_n и А конечно.

4. Каждое подмножество конечного множества ко­нечно.

Доказательство. Пусть А ⊆ В и В конечно. Ес­ли В = ø, то А = ø, и утверждение доказано. В против­ном случае В ~ N_m для некоторого т ϵ N. Тогда суще­ствует биекция . Применение χ к А дает под­множество из N_m и поэтому χ(А) ограничено. Из слу­чая 3 следует конечность χ(А). Поэтому, так как χ(А) биективно с А, то А конечно.

5. Прямым следствием случая 4 является тот факт, что любое множество, имеющее бесконечное подмнояжество, само бесконечно.

Доказывая некоторые неочевидные факты о размер­ностях множеств Z, Q, N, N х N, ..., разумно задаться вопросом: существуют ли множества, мощность которых больше мощности N? Ответ на этот вопрос утвердитель­ный. Действительно, ив данного произвольного множест­ва мы можем (используя диагональную процедуру Кан­тора; см. ниже) соэдать множество, мощность которого строго больше мощности N.

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

Пример 3.4. Покажем, что

Доказательство (А. Кантор). Каждое число между 0 и 1 может быть записано в виде бесконечной десятичной дроби ... Предположим, что эти числа могут быть перенумерованы и что п-е число име­ет значение, данное выше. Будем конструировать следу­ющее число: возьмем п-ю цифру десятичной формы, рав­ную n-му числу. Это дает нам число ... По­строим новое число: где каждая цифра отличается от соответствующей цифры d₁₁. Тогда это построенное число будет отличаться от каждого числа из первоначального перечня, а именно от n-го числа оно будет отличаться n-й цифрой. Следовательно, мощность [0, 1[ строго больше, чем мощность N, и счетной биекции не существует.

Принцип построения числа в предыду­щем доказательстве является наиболее существенным моментом, хотя проницательный читатель может заме­тить, что существуют вадачи, где десятичное представле­ние чисел не единственно. Это встречается тогда, когда представление заканчивается бесконечной последователь­ностью 0 или 9. (Например, 0.3999... и 0.4000...) Чтобы построенное число 0. ... отличалось от уже вы­писанного списка чисел, мы можем оговорить, что должны отличаться от 0, и 9. Соответствующие про­блемы возникают и в других подобных конструкциях, однако, чтобы не отвлекать внимание от основных идей, в большинстве случаев мы будем их игнорировать.

На самом деле можно показать, что [0, 1[ ~ R. Оче­видно, что R — важное множество. Поэтому его мощ­ность обозначают специальным символом (алеф-один). Рассмотрим теперь способы, с помощью которых можно объединять множества и отношения между мощ­ностями отдельных множеств и мощностью результиру­ющего множества. Первый из них довольно очевиден.

Теорема. Если А ~ В и С ~ D, то (A×C)~(B×D). Доказательство. Пусть — биекции. Тогда является биекцией между A×C и B×D. //

Теорема. Если Z — конечное множество и {X, Y) — разбиение Z, тогда |Z|=|X|+|Y|.

Рис. 3.4

Доказательство. Так как Z конечно, то Z ~ N_m для некоторого и существует биек­ция (рис. 3.5). Более того, так как и , то и . Пусть явля­ется биекцией из в N _p для некоторого , где

Аналогично пусть — биекция из в N_p2 для некоторого р₂ ≤ m, .Тог­да если , то является биекцией между

Следовательно, отобра­жение

является инъекцией и биективно (так как Z конечно), между Z и N_p1+p2, Таким образом, Z ~ N_p1+p2, Следо­вательно, m=p₁+p₂ и |Z|=|X|+|Y|

Пример 3.5. Чтобы проиллюстрировать применение предыдущей теоремы, рассмотрим случай, когда

Тогда биекция между Z и N₆. задается следующим об­разом:

, и поэтому

Подходящими отображениями , являются

Поэтому если определяется как

Комбинирование и нужный резуль­тат. //

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

Закончим обсуждение следующим основным резуль­татом. Если А и В — конечные множества, то А × В ко­нечно и . Этот результат не только интересен сам по себе, но и дает способ для введения доказательства по индукции.

Доказательство по индукции использует два основ­ных понятия, содержащихся в определении N:

1. Существует некоторый начальный элемент (в N это 1).

2. Для заданного утверждения, соответствующего некоторому элементу, существует метод, позволяющий перейти к следующему (в случае N это — создание сле­дующего числа за наибольшим до сих пор числом, вклю­ченным в N).

Более конкретно, если для некоторого (обыч­но = 1, но не обязательно) мы можем доказать, что утверждение Р( ) справедливо и для любого n N (п≥п_о) справедливость Р(п) влечет справедливость Р(n + 1) (здесь п + 1 — следующий эа п элемент), то заключаем, что Р(п) справедливо для всех . Шаг (I) является основанием индукции, шаг (П)— шагом индукцииВесь процесс, по существу, является прямым доказа­тельством

Р(п₀) . ..=>Р(m)

и, следовательно, осуществляет непосредственную проверку промежуточных результатов.

Рассмотрим следующий пример.

Пример 3.6. Если A и B конечны, то

Доказательство. Поскольку А и В конечны, то А ~ N_m с биекцией для некоторых т, п N. Будем использовать индукцию по n — размер­ности В. Заметим, что от размерности А требуется ко­нечность, так как мы предполагаем знакомство только с умножением конечных величин.

Основание индукции. Если В=Ø, то A×B=Ø, и поэтому имеем тривиальное равенство

Если B={b}, то отображение такое, что , очевидно, биективно, и поэтому

Шаг индукции. Предположим, что

где и . Тогда

и существует биекция . Если к<п, то можно взять подмножество В, которое имеет f = k + 1 элементов. Пусть , где B_h — множество из k элементов, и пусть отображение , оп­ределяется следующим образом:

Очевидно, что является биекцией на N и

Поэтому . Следовательно, тождество справедливо для всех подмножеств В, содер­жащихся в В, и поэтому . //

Упражнение 3.3.

1. Доказать, что отношение между множествами

{(А, В): А~В)

является отношением эквивалентности.

2. Построить биекцию между множествами Z × N и N × N.

3. Доказать, что если А и В — множества и конечно, то

4. Доказать (от противного), что произвольная инъ­екция является биекцией.

5. Доказать (без использования равенства , что для любого конечного множества А, такого что , справедливо соотношение .

6. Показать, что результат задачи 5 имеет место и для бесконечных множеств.

7. Пусть множество {0,1}^N представляет собой после­довательность , где . Дока­зать, что .

8. Доказать (построением подходящих биекций и рассуждений по индукции), что если А₁, А_п — ко- нечные множества, то