Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 4

Примером такого объединения является множество (.) Ап всех векторов с натуральными ком)шм понентами, Множество всех действительных чисел отрезка (О, Ц не является счетным (теорема Кантора). Действительно, предположим, что оно счетно и существует его нумерация. Расположим все числа, изображенные бесконечными десятичными дробями, в порядке этой нумерации: О, ам ахз агз .„ О, азх озз азз " О, ам аэз азз " Рассмотрим любую бесконечную десятичную дробь О, Ьь Ьь Ьзтм такую, что Ь,~аы, ЬзФазз, Ьзчьазз и т. д.

Эта дробь не может войти в указанную последовательность, так как от первого числа она отличается первой цифрой, от 'второго числа — второй цифрой и т. д. Следовательно, все числа из отрезка (О, Ц не могут быть пронумерованы, и множество всех действительных чисел отрезка (О, Ц несчетно. Его мощность называется континуу ~; множества такой мощности называются континуальньгми. Метод, использованный при доказательстве, называется диагональным методом Кантора. Множество всех подмножеств счетного множества кон- ' На примере множества Р видно, что нумерання числового множества может не иметь ничего общего с упорядаченяем его элементов по величине.

В множестве Р нет ни наименьшего элемента, нн двух соседних по величине элементов (для любых двух дробей р1 и рз всегда найдется дробь, лежащая между ними, например (р,+рз)/2), однако есть элемент с наименьшим номером и элементы с соседними иомерамн. тинуально. Это становится ясным, если воспользоваться, как и в теореме 1.2, представлением подмножества в виде последовательности (но теперь уже бесконечной!) нулей и единиц: на 1-м месте стоит 1, если (-й элемент множества входит в данное подмножество, и 0 в противном случае. Получаем взаимно однозначное соответствие между подмножествами счетного множества и правильными двоичнымн дробями, которые, в свою очередь, взаимно однозначно соответствуют множеству чисел отрезка 10, 11.

Как показывается в теории множеств (с помошью метода, аналогичного диагональному), для множества любой мощности множество его подмножеств имеет более высокую мощность. Поэтому не существует множества максимальной мощности. Парадокс, приведенный в отступлении 1.2 (парадокс Кантора), как раз и заключается в том, что «множество всех мтюжеств» должно содержать все множества и, следовательно, иметь максимальную мощность, что противоречит результатам теории множеств. Отображения и функции.. Функцией называется функциональное соответствие. Если функция 1 устанавливает соответствие между множествами А и В, то говорят, что функция1 имеет типА- В (обозначение 1:А — »В). Каждому элементу а из своей области определения функция 1 ставит в соответствие единственнь:й элемент Ь из области значений.

Это обозначается хорошо известной записью 1(а) =Ь. Иногда, если это не вызывает неудобств, используют обозначения та или аг. Элемент а называется аргументом фупкции, Ь вЂ” значением функции ва а. Полностью определенная функция (: А- В называется отображением А и В.

Образ А при отображении 1 обозначается 11А), Если соответствие 1 при этом сюръективно, т. е. каждый элемент В имеет прообраз в А, то говорят, что имеет место отображение А на В (сюръективное отображение), Если 1(А) состоит из единственного элемента, то 1 называется функцией-константой. Отображение типа А-э.А часто называют преобразованием множества А. Функции 1 и д равны, если их область определения— одно и то же множество А и для любого аыА 1(а) =д(а). Пример 1.8. а.

Функция 1(х) =2 является отображе" нием У в 1«' и Жо на М м 6. Всякая нумерация счетного множества является его отображением на Л~. в. Функция 1(х) = $' х не полностью определена, если ее тип У->-Ж, и полностью определена, если ее тип У- Р нли Р„- Р (Р+ — положительное подмножество Р). г. Пусть зафиксирован список (а„...,а„) всех элементов конечного множества А. Тогда любой вектор о;=(аь, ... ..., а, ) из А" можно рассматривать как описание функции 1н А — >А (т.

е. преобразования А), определяемой следующим образом: 1>(а>) =а;, т.е. значение 1> для а> равно 1ьй компоненте оь Число всех преобразований А равно, следовательно, 1А" ~ =и". Аналогично всякую функцию типа Н вЂ” >-У можно представить бесконечной последовательностью элементов У, т. е. натуральных чисел; отсюда нетрудно показать, что множество всех преобразований счетного множества континуально. д.

Каждое натуральное число п единственным образом разлагается на произведение простых чисел (простых делителей этого числа), Поэтому, если договориться располагать простые делители п в определенном порядке (например, в порядке неубывания), то получим функцию д(п) Р типа 1У->- О Лп, отображающую Ьу в множество векторов >=! произвольной длины. Например, 4>(42) = (2, 3, 7), д(23) = =23, д(100)=(2, 2, 5, 5). Это отображение не является сюръективным, так как в область значений д не входят векторы, для компонент которых ие выполнено условие неубывания, а также векторы с непростыми компонентами. е. Каждому человеку соответствует множество его знакомых.

Если зафиксировать момент времени (например, 1О января 1985 г., 5 ч 00 мин), то это соответствие будет однозначным и явится отображением множества М людей, живущих в этот момент, в множество подмножеств М. ;Функция типа А>ХА>Х...ХА„- В называется и-местной функцией. В этом случае принято считать, что функция имеет и аргументов: 1(аь аь ..., а ) =Ь, где а>~А>, а,~А„... „„а„енА„, ЬыВ. Сложение, умножение, вычитание и деление являются двухместными функциями на Р, т, е. функциями типа Р'->-Р. Таблица выигрышей лотереи задает двухместную не полностью определенную функцию, которая устанавливает соответствие между парами из Л" (серия, номер) и множеством выигрышей.

Пусть дано соответствие 6ыАх,'В. Если соответствие НаВХА таково, что (Ь„а)~Н тогда и только тогда, когда (а Ь)ен6 то соответствие Н называется обратным к 6 и обозначается 0-'. Если соответствие, обратное к функции !'; А- В, является функциональным, то оно называется ' функцией, обратной к ), н обозначается 1-'. Так как в обратном соответствии образы н прообразы меняются места- ' ми, то для существования функции, обратной к 1: А-+-В, требуется, чтобы каждый элемент Ь из области значений ! имел единственный прообраз, Это, в свою очередь, означает, что для функции 1: А-+.В обратная функция существует тогда и только тогда, когда 1 является взаимно однозначным соответствием между своей областью определения ..

и областью значений. Пример 1.9. а. Функция з!и х имеет тип !1- Я. Отрезок 1 — и/2, и/21 она взаимно однозначно отображает на отрезок ( — 1, !). Поэтому на отрезке 1 — 1, 11 для нее существует обратная функция агсз!и х. б. Ранее приводились примеры нодирующих функций, которые каждому объекту из своей области значений ставят в соответствие некоторый код. Для кодирующей функции обратной будет декодирующая функция, которая каждому коду ставит в соответствие закодированный этим кодом объект.

Если кодирующая функция не сюръективна, то декодирующая функция не всюду определена. Пусть даны функции 1: А-+В и д: В-+С. Функция 6: А-~С называется композицией функций 1 и а (обозначение 1од), если имеет место равенство 6(х) =д(1(х)),где хекА. Композиция 1 и д представляет собой последовательное применение функций 1 и д; д применяется к результату Г. Часто говорят, что функция Ь получена подстановкой 1 в у. Знак ~ аналогично умножению часто опускается. Для многоместных функций 1: А -эВ, у: В"- С возможны различные варианты подстановки 1 в а, дающие функции различных типов. Например, при т =3, п=4 функция й1=д(хь !" (уь ум уз), хз, х4) имеет шесть аргументов и тип ВХА'ХВ'-+С, а функция лз к(1(уь уь Уз), 1(гь гм гз), хз х4) имеет восемь аргументов и тип Аьз'зс'Вз-з-+-С.

Особый интерес представляет случай, когда задано множество функций типа !',: А з-~А, ..., !",: А "- А. В этом случае возможны, во-первых, любые подстановки функций друг в друга, а во-вторых, любые переименования аргументов, например переименование хз в хз, порождающее из функции 1(хи хз, хз, х4) функцию трех аргументов ((хи хз, х„х,). Функция, полученная из гь ...,(„ некоторой подстановкой их друг в друга и переименованием аргументов, на- зывается суперпозицией )н ..., („. Выражение, описывающее эту суперпознцию и содержащее функциональные знаки и символы аргументов, называется формулой. Пример 1.!О. а. Функции з!и х и ) х имеют тип 11-«-!т, т.

е. отображают одно и то же множество в себя. Поэтому их композиция возможна в произвольном порядке и дает функции з!п )~ х и )~ з!и х. Заметим, что области определения их различны: первая функция определена на положительной полуоси; вторая функция определена на множестве отрезков !2йп, (2х+1)п], где А=О, -~1, -92... Таким образом, область определения композиции может быть уже областей определения обеих исходных функций и даже казаться пустой.