Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 12
Текст из файла (страница 12)
Что является областью определения л ° 1: а) когда (и л — функции; б) когда ? — функция, у — отображение; в) когда ? — отображение, а я — функция; г) когда 1 и я — отображения? 5. Доказать, что если функция 1 инъектцвна, то существует 1-'. б. Если функция ? сюръективна, следует ли отсюда, что ? ' — отображение? 7.
Построить пример, показывающий, что функция на А ( — 1, О, И, определенная как ~: х х', такова, что )-1,).,й 7' 8. Пусть ): А - В и я: В- С вЂ” функции. Доказать, что: а) если ) и л инъективны, то л ° ~ инъектнвна; б) если ) и л сюръективны, то л ° ) также сюръективна. 9. Пусть /: А - В и л: В- С вЂ” функции п я сюрьективна, Достаточно ли этого, чтобы обеспечить сюръектпзность р ° )3 5 2. Обратные функции и отображения Используя результаты, полученные в предыдущем параграфе, исследуем сложные функции.
Пусть дана функция ): А - В; в этом случае ) ' является функцией тогда и только тогда, когда ) инъективпа, а отображением тогда и только тогда, когда ) биективна. В большинстве рассматриваемых нами случаев ~ — биекция; тогда также бнекция, а функции )-' ° ~ и ~в ~ ' являются тождественными отображениями. Рассмотрим функции ~: А - В и я: В- С. Тогда: а) если 7' и л инъективны, го существует я ° ~; б) если ) и я сюръективны, то также существует я ° ~ (см, упражнение ЗЛ, 8). Обратным отношением к я / является,'-'ел-'.
Порядок должен быть обратным, как указано на рис, 3.2. Рас. 3.2 Заметим, что если я — отображение, т. е. Ж, ° В, то Я~шЯз н, следовательно, Яг,р = Яг. Аналогично, если Яуй-'Н>е то Яз,~ Яю Если ~ и л ипъективны, то существует л ° ); следовательно, 7 ' ° л ' — функция. Суммируя вышесказанное, имеем: из Я 2>з следует, что 72 я ° !: !й),— Я,= отображение; если ! н д также инъективны, то ! ' ° д ': Я, - йРг — биекцпя. Очевидно, что эти критерии выполняются, если ! н д — бпекции, У и р а ж н е н и е 3.2. 1.
Пусть !: А - В и йч С- В; показать следующее: а) если ! сюръективна и я — отображение, то б) если ! и я — биекции, то (д ' ° !) ' = ! ' л; в) если Я, ж Яь то (! ° ! ' ° я) С = Я,. 5 3. Мощность множеств и счетность Мы почти подошли к тому моменту, когда появляется возможность использовать понятие биекцин для формализации понятия мощности и процесса вычислений. Вычисление важно не только само по себе, но также и потому, что функция является вычислиз«ой тогда и только тогда, когда связанное с ней множество счетно. Вначале дадим определение множества Х.
Чтобы пронсннть наши намерения, заметим, что любое число (1, 2 и т. д.) может быть использовано двумя различными способами: как существительное нли как прилагательное, дающее номер другого существитель.ого. Мы будем рассматривать числа как существительные. В качестве предварительного определения Х положим Х - (1) 0 (я + 1: я ж %. Из этого рекурсивного определения следует, что 1жЖ, и если к произвольному элементу из Х прибавить 1, то полученный результат также принадлежит г). Следовательно, Х содержит 1, 1+ 1(=2), 2+ 1(=3), 3+ 1(-4) и т. д.
К сожалению, это определение неприемлемо по причинам, которые будут рассмотрены ниже. Тем не менее здесь есть несколько важных моментов. Например, так как )«(по крайней мере интуитивно) бесконечно, то мы должны иметь механиам, при помощи которого можно конструировать последующие элементы иа конечного мноя«ества,— другимв словами, никогда не сможем написать точное представление г(. Мы также должны придумать имя числу, которое называем «один», и аналогично для «два» (сокращение 1+ 1), «три» и т, д.
Конечно, уз мы могли бы выбрать любые имена или символы для этой цели, однако было бы неправильно использовать неудобные обозначения. Перейдем теперь к недостаткам данного определения. Проверка его обнаруживает, что оно содержит два новых символа: «1» и «+»; остальные символы известны из построения множеств. Символ «1» можно объяснить вышеуказанным способом. Однако символ «+» означает операцию ва г( и, следовательно, не может быть испольвован для определения г(.
(Операции будут определены в 3 6.) Чтобы выйти иэ этого затруднения, вернемся к основам теории множеств. Напомним, что нам нужно было построить число, которое на 1 больше максимального из всех предшествующих чисел. Легко получить аналогич. ный процесс для множеств (называемый построением сверхмножества с количеством элементов на 1 больше, чем в данном множестве). Пример ЗА. Пусть А (х, у, з) и В (х, р, з, А). Тогда А ыВ и АжВ, поэтому В~А (А) и имеет толька один элемент.
»' Эта конструкция может быть перенесена на произвольное множество. Начиная от множества Х, мы можем определить последующее множество (обозначается Х»): Х» Х О (Х). Чтобы использовать этот процесс для по. строения й(, требуется некоторое начальное множество. Выберем в качестве такого множества (И).
Оно имеет один элемент. (Многие авторы начинают с Ю. Это порождает множество (О) 0 Я. Мы не считаем 0 натуральным числом, и в этом причина такого выбора начального элемента, Не существует универсального условия по отношению к О и и(. Всегда следует проверять условные обозначения, принятые в других книгах, при обращении к.ним.) Из Ф) создадим последовательности (И): (И)» =(З, (О)), (И)»» (И, (9), (Ы, ФП) и т, д.
Это пркводит к прогрессии, которая является более привлекательной, чем 1, 1 + 1, 1 + 1 + 1, ..., по крайней мере ее конструкция является строго определенной. Чтобы навести порядок в вышесказанном, выберем временно имена для этих множеств. Переименуем Я) как 1, 1' как 2, 2» как 3 и т. д. Тогда 1 (ю), 2 (Ю,1), 3 Ф,1,2),... Поэтому, например, множество 3 имеет трн элемента. Чтобы набежать неточности, давайте снова иаменпм обовначения и определим множества Х шэЧЗ)-(т, 2, ..., и), Х = Х, () (Х„е: т ~ Х).
Тогда из определения следует, что 1Х 1 т (чнсло ш) и что если а, Ь ж Х, то а ~ Ь тогда и только тогда, когда Х, ж Хэ. Поэтому наша вера в упорядоченность Х формально обоснована. Итак, множества Х в Х (для каждого и ж Х) определены и могут быть использованы в дальнейшем. Введем некоторые понятия.
0 и р е д е л е н и е. Два множества биелтиены (обоаначается Х У), если между ними существует биекция. Непустоа множество конечно, если оно биективно некоторому Х (и ж Х). Если Х Х„, то мощность множества (обозначается 1Х1) равна ж. (Числа в данном случае испольэуются как прилагательные. Например, если Р— множество всех людей и Хы Р таково, что Х Х, то Х есть множество иэ ж людей.) Напомним, что пустое множество И бнективно только по отношению к себе, является конечным н имеет мощность О, т. е. 1 8 1 О.
Говорят, что множество счетно, если оно биектнвно Х. Символ Ис (алеф-нуль) часто используют для обозначения мощности Х. Множество называется счетным., если оно конечно нли счетно, и может быть сосчитано с испольаованием биекцнн ~: Х- Х, если Х счетно, илн биекция ~: Х - Х, если 1Х1 = ж, нли (: И - Х; ~-й элемент Х является обрааом ~ отображения ~. г" Перед тем как установить несколько полезных реэультатов, отметим одно существенное свойство множеств и биекций: отношение о, определенное на множестве Я посредством о = ((Х, у): Х - у), является отношением эквивалентности, а подмножества Я, входящие в классы эквивалентности, состоят иэ множеств, имеющих одинаковую мощность.
Следовательно, чтобы продемонстрировать тот факт, что два множества имеют один и тот же размер, требуется построить бнективное отображение между ниии. 75 Пример 3.2. Покажем, что (Х! Й(, Отображение 1 — « -« —, если я печатно, с)с; я ~-е. л/2 в противном случае является биекцией между Х и Е. У В предыдущем примере греческая буква <р использовалась для обозначения биекцни. Испольэование греческих букв <р, <р, )(..., для обозначения проиэвольных биекций является общепринятым в текстах по логике и будет здесь испольаоваться в этом контексте (среди других).
Однако, чтобы не было путаницы с пустым множеством Ю, мы будем избегать испольаования этих букв в этом параграфе. Пример 3.3. Попал<ем, что (Х! Щ!. Это требует несколько более сложных рассуждений. Вначале рассмотрим счетное количество копий Х, каждая иа ннх соответствует своему номеру я «а Х. Мы монсен ваписать это множество как ХХХ и упорядочить его элементы, как указано на рис. 3.3, Такое упорядочивание является (Р,б Ц<) Рис.
3.3 биекцией Х Х Х - Х, задаваемой отношением (х, у) (х'+ << — <) (~ + « — 2) + У, Каждый положительный элемент (1 может быть свяэан с дробью (р, р), где р и с) вэаимно простые, и связан с элементом (р, д) множества Х Х Х естественным образом, Поэтому, записывая Т-(х: х«а(1, х О), получаем )т! ~ )Х Х Х! - )Х!.
(Испольаование отношения ««Ц» между этими бесконечными числами ке обосновано, Соотношение (А! ~ )В( 76 следует читать как «А биективно подмножеству В». Доказательство неочевидного факта, что это отношение является отношением порядка; лежит за пределами этой книги.) С другой стороны, каждое р»в Х может быть представлено как р/1 и, следовательно, связано с парой (р, 1). Поэтому (Х| »~ 1Т! ~ !Х(, откуда следует, что ~Т! 1Х!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
