02. Соответствия и функции

Соответствия. Соответствием между множествами А И В называется подмножество

Если , то говорят, что B соответствует А При Соответствии G. Множество называется Областью определения соответствия, множество — Областью значений Соответствия. Если , то соответствие называется Всюду определенным (в противном случае соответствие называется частичным); если , то соответствие называется Сюръективным.

Множество всех , соответствующих элементу , называется Образом А В В при соответствии G. Множество всех А, которым соответствует B, называется Прообразом B в А при соответствии G. Если то образом множества С называется объединение образов всех элементов С. Аналогично определяется прообраз множества D Для любого

Соответствие G называется Функциональным (или однозначным), если образом любого элемента из является единственный элемент из . Соответствие G между А и В Называется Взаимно-однозначным (иногда пишут «1-1-соответствие»), если оно всюду определено, Сюръективно, функционально и, кроме того, прообразом любого элемента из является единственный элемент из .

Пример 7.

1) Круг G радиуса 1 с центром в точке (3, 2) (рис. 1), т. Е. множество пар действительных чисел , удовлетворяющих соотношению задает соответствие между R и R (осью абсцисс и осью ординат). Образом числа 4 при этом соответствии является единственное число 2, образом числа 3 является отрезок [1, 3] оси ординат; этот же отрезок [1, 3] является образом отрезка [2, 4] оси абсцИСс, который, в свою очередь, служит прообразом числа 2. Данное соответствие не является функциональным. Примером функционального соответствия между действительными числами на том же рис. 1 служит дуга АВС.

Еще раз напомним, что для задания соответствия надо указать не только множество G, но и множества А и В, т. е. указать, подмножеством какого именно прямого произведения является G. В данном примере тот же круг Задает и другое соответствие: между отрезком [2, 4] и отрезком [1, 3]. При этом по некоторым свойствам соответствия и отличаются: например, второе соответствие в отличие от первого всюду определено и сюръективно. Учитывая эти соотношения, следовало бы определять соответствие как тройку множеств (G, А, В). Тогда не пришлось бы оговариватьСя, что один круг может задавать два соответствия; это И так было бы ясно из различия троек и Однако такие оговорки приходится делать редко: либо множества А и В ясны из контекста, либо различия в их выборе не влияют на исследуемые свойства соответствия. Поэтому «определение через тройку множеств» здесь использоваться не будет.

2) Англо-русский словарь устанавливает соответствие между множеством английских и русских слов. Это соответствие не является функциональным (так как одному английскому слову, как правило, ставится в соответствие несколько русских слов); кроме того, оно практически никогда не является полностью определенным: всегда можно найти английское слово, не содержащееся в данном словаре.

3) Позиция на шахматной доске представляет собой взаимно-однозначное соответствие между множеством оставшихся на доске фигур и множеством занятых ими полей.

4) Различные виды кодирования — кодирование букв азбукой Морзе, представления чисел в различных системах сЧиСления, секретные шифры, входящие и исходящие номера в деловой переписке и другие — являются соответствиями между кодируемыми объектами и присваиваемыми им кодами. Эти соответствия, как правило, обладают всеми свойствами взаимно-однозначного соответствия, кроме, быть может, одного — сюръективности. Единственность образа И прообраза в кодировании гарантирует однозначность шифровки и дешифровки. Отсутствие Сюръективности Означает, что не всякий код имеет смысл, т. Е. соответствует какому-либо объекту. Например, кодирование телефонов г. Москвы семизначными номерами не Сюръективно, так как некоторые семизначные номера не соответствуют никаким телефонам.

5) Множество векторов вида , где , задает взаимнооднозначное соответствие между множеством N Натуральных чисел и множеством степеней двойки.

Взаимно-однозначные соответствия и мощности множеств. Если между конечными множествами А и В существует взаимно-однозначное соответствие, то Действительно, если это не так, то либо и тогда, поскольку отображение всюду определено, в А найдутся два элемента, которым соответствует один и тот же элемент (нарушится единственность образа), либо и тогда, поскольку отображение Сюръективно, в В Найдутся два элемента, соответствующих одному и тому же И (нарушится единственность прообраза).

Этот факт, во-первых, позволяет установить равенство мощностей двух множеств, не вычисляя этих мощностей, а во-вторых, часто дает возможность вычислить мощность множества, установив его взаимно-однозначное соответствие с множеством, мощность которого известна или легко вычисляется. В качестве иллюстрации этого приема докажем важную теорему о числе подмножеств конечного множества.

Теорема 2. Если для конечного множества А То число всех подмножеств А равно 2N, т. е. .

Занумеруем элементы А номерами от 1 до П: и рассмотрим множество Вп двоичных векторов из нулей и единиц длины П. Каждому ПодмножеСтву поставим в соответствие вектор следующим образом:

Например, если , то подмножеству соответствует вектор (1, 0, 1, 1, 0), а подмножеству соответствует вектор (0, 1, 0, 0, 0). Пустому подмножеству любого А соответствует вектор из одних нулей, а самому А — вектор из одних единиц. Очевидно, что УстановЛенное соответствие между множеством всех подмножеств А И двоичными векторами длины П является взаимно-однозначным и число подмножеств А равно . А так как Вп является прямым произведением П двухэлементных множеств {0, 1}, то в силу следствия из теоремы 1 —

Множества Равномощны, если между их элементами можно установить взаимно-однозначное соответствие. Для конечных множеств это утверждение доказывается, что и было сделано ранее. Для бесконечных множеств оно является определением Равномощности. Множества, Равномощные N, называются Счетными. Соответствие, установленное в примере 7, показывает, что множество счетно. Вообще любое бесконечное подмножество N счетно. Действительно, пусть . Выберем в N' наименьший элемент и обозначим его ; в выберем наименьший элемент и обозначим его ; наименьший элемент обозначим и т. д. Поскольку для всякого натурального числа имеется лишь конечное множество меньших натуральных чисел, то любой элемент N' рано или поздно получит свой номер. Эта нумерация, т. е. соответствие , и есть взаимно-однозначное соответствие между N' и N.

Множество счетно. Нумерацию можно устроить следующим образом. Разобьем на классы. К первому классу отнесем все пары чисел с минимальной суммой. Такая пара всего одна: (1, 1). Ко второму классу Отнесем все пары чисел с суммой 3: В общем случае Каждый класс содержит ровно I пар. Упорядочим теперь классы по возрастанию индексов I, а пары внутри класса — по возрастанию первого элемента и занумеруем получившуюся последовательность пар номерами 1, 2, 3 ... Легко видеть, что если , то пара (А, B) получит ноМЕр Эта нумерация и Доказывает счетность , из которой, в свою очередь, непосредствеННо следует счетность множества Р положительных рациональных чисел, т. Е. дробей вида , где А и B — натуральные числа. Аналогично доказывается счетность и вообще Для любого натурального K.

Нетрудно понять, что объединение конечного числа счетных множеств счетно. Действительно, перенумеруем сначала все первые элементы множеств, затем все вторые и т. Д. Объединение счетного множества конечных множеств также счетно (сначала нумеруем все элементы первого множества, затем все элементы второго множества и т. д.). Из последнего утверждения следует, что множество всех слов в любом конечном алфавите счетно. Менее очевидно, что счетно и объединение счетного множества счетных множеств. Примером такого объединения является множество всех векторов с натуральными КомПонентами.

Множество всех действительных чисел отрезка [0, 1] не является счетным (Теорема Кантора). Действительно, предположим, что оно счетно и существует его нумерация. Расположим все числа, изображенные бесконечными десятичными дробями, в порядке этой нумерации:

Рассмотрим любую бесконечную десятичную дробь такую, что и т. д. Эта дробь не может войти в указанную последовательность, так как от первого числа она отличается первой цифрой, от второго числа — второй цифрой и т. д. Следовательно, все числа из отрезка [0, 1] не могут быть пронумерованы и мНОжество всех действительных чисел отрезка [0, 1] Несчетно. Его мощность называется Континуум; множества такой мощности называются Континуальными. Метод, использованный при доказательстве, называется Диагональным методом Кантора.

Множество всех подмножеств счетного множества континуально. Это становится ясным, если воспользоваться, как и в теореме 2, представлением подмножества в виде последовательности (но теперь уже бесконечной!) нулей и единиц: на 1-м месте стоит 1, если 1-й элемент множества входит в данное подмножество, и 0 в противном случае. Получаем взаимно-однозначное соответствие между подмножествами счетного множества и правильными двоичными дробями, которые в свою очередь, взаимно-однозначно соответствуют множеству чисел отрезка [0, 1]. Как показывается в теории множеств (с помощью метода, аналогичного диагональному), для множества любой мощности множество его подмножеств имеет более высокую мощность, Поэтому не существует множества максимальной мощности. Парадокс, приведенный в отступлении 2 (парадокс Кантора), как раз и заключается в том, что «множество всех множеств» должно содержать все множества и, следовательно, иметь максимальную мощность, что противоречит результатам теории множеств.

Отображения и функции. Функцией называется функциональное соответствие. Если функция F устанавливает соответствие между множествами А и В, то говорят, что функция F имеет тип (обозначение F: ). Каждому элементу А из своей области определения функция F Ставит в соответствие единственный элемент B из области значений. Это обозначается хорошо известной записью Иногда, если это не вызывает неудобств, испОЛьзуюТ обозначения Fа или АF. Элемент А называется Аргументом функции, B — значением функции на А. Полностью определенная функция F: называется Отображением А в В. Образ А при отображении F обозначается . Если соответствие F при этом Сюръективно, т. е. каждый элемент В имеет прообраз в А, то говорят, что имеет место отображение А на В (сюръективное отображение). Если состоит из единственного элемента, то F называется функцией-константой. Отображение типа часто называют Преобразованием множества А.

Функции F и G равны, если их область определения — одно и то же множество А и для любого

Пример 8.

1) Функция является отображением N в N И N на .

2) Всякая нумерация счетного множества является его отображением на N.

3) Функция не полностью определена, если ее тип , и полностью определена, если ее тип или (— положительное подмножество R).

4) Пусть зафиксирован список всех элементов конечного множества А. Тогда любой вектор иЗ Можно рассматривать как описание функции : (т. е. преобразования А), определяемой следующим образом: , т. е. значение для равно J-Й компоненте . Число всех преобразований А равно, следовательно, . Аналогично всякую функцию типа можно представить бесконечной последовательностью элементов N, т. Е. натуральных чисел; отсюда нетрудно показать, что множество всех преобразований счетного множества континуально.

5) Каждое натуральное число П единственным образом разлагается на произведение простых чисел (простых делителей этого числа). Поэтому, если договориться располагать простые делители П в определенном порядке (например, в порядке неубывания), то получим функцию типа , отображающую N в множество векторов ПроизВольной длины. Например, , , . Это отображение не является Сюръективным, так как в область значений Q не входят векторы, для компонент которых не выполнено условие неубывания.

6) Каждому человеку соответствует множество его знакомых. Если зафиксировать момент времени (например, 10 января 1976 г., 5 ч 00 мин), то это соответствие будет однозначным и явится отображением множества М людей, живущих в этот момент, в множество подмножеств М.

Функция типа называется П-местной функцией. В этом случае принято считать, что функция имеет П аргументов: где . Сложение, умножение, вычитание и деление являются двухместными функциями на R, т. е. функциями типа . Таблица выигрышей лотереи задает двухместную не полностью определенную функцию, которая устанавливает соответствие между парами из (серия, номер) и множеством выигрышей.

Пусть дано соответствие Если соответствие таково, что тогда и только тогда, когда то соответствие Н называется обратным к G и обозначается . Если соответствие, обратное к функции , является функциональным, то оно называется Функцией, обратной к F, и обозначается . Так как в обратном соответствии образы и прообразы меняются местами, то для существования функции, обратной к , требуется, чтобы каждый элемент B из области значений F имел единственный прообраз. Это в свою очередь означает, что для функции обратная функция существует тогда и только тогда, когда F является взаимнооднозначным соответствием между своей областью определения и областью значений.

Пример 9.

1) функция ИМеет тип Отрезок она взаимно-однозначно отображает на отрезок [-1, 1]. Поэтому на отрезке [-1, 1] для нее существует обратная функция

2) Ранее приводились примеры кодирующих функций, которые каждому объекту из своей области значений ставят в соответствие некоторый код. Для кодирующей функции обратной будет декодирующая функция, которая каждому коду ставит в соответствие закодированный этим кодом объект. Если кодирующая функция не Сюръективна, то декодирующая функция не всюду определена.

Пусть даНЫ функции и Функция называется Композицией функций F и G (обозначение ), если имеет место равенство где Композиция F и G представляет собой последовательное применение функций F и G; g применяется к результату F. Часто говорят, что функция H получена Подстановкой f в G. ЗнакАналогично умножению часто опускается.

Для многоместных функций возможны различные варианты подстановки F в G, дающие функции различных типов. Например, при Т = 3, N = 4 функция имеет шесть аргументов и тип а функция имеет восемь аргументов и тип Особый интерес представляет случай, когда задано множество функций типа В этом случае возможны, во-первых, любые подстановки функций друг в друга, а во-вторых, любые переименования аргументов, например переименование в , порождающее из функции Функцию трех аргументов . Функция, полученная из некоторой подстановкой их друг в друга и переименованием аргументов, называется СуперпозиЦИей . Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется Формулой.

Пример 10.

1) Функции и имеют тип т. Е. отображают одно и то же множество в себя. Поэтому их композиция возможНА в произвольном порядке и дает функции и . Заметим, что области определения их различны: первая функция определена на положительной полуоси; вторая функция определена на множестве отрезков , где Таким образом, область определения композиции может быть уже областей определения обеих исходных функций и даже оказаться пустой.

2) Множество команд ЭВМ отображается в машинные коды ЭТой ЭВМ, т. е. в натуральные числа. Кодирующая функция J имеет тип С помощью суперпозиции этой функции и арифметических функций оказываются возможными арифметические действия над командами (которые сами по себе числами не являются!), т. е. функции вида и т. Д.

3) В функции переименование в приводит к функции , которая равна функции двух аргументов Переименование и в приводит к одноместной функции

4) Элементарной функцией в математическом анализе называется всякая функция F, являющаяся суперпозицией фиксированного (т. е. не зависящего от значений аргументов F) числа арифметических функций, а также функций Например, функция элементарна, так как является результатом нескольких последовательных суперпозиций

5) Всякая непрерывная функция П переменных Представима в виде суперпозиции непрерывных функций двух переменных. (Этот результат получен в 1956—1957 гг. в работах А. Н. Колмогорова и В. И. Арнольда и является решением 13-й проблемы Гильберта.)

6) Рассмотрим множество {1, 2, 3} и два преобразования этого множества: и . Обычно преобразования конечных множеств записывают так:

КомПозиция преобразований — этО новое преобразование:

Способы задания функций. Наиболее простой способ задания функций — это таблицы, т. е. конечные списки пар . Однако таким образом могут быть заданы только функции, определенные на конечных множествах. Таблицы функций, определенных на бесконечных множествах (например, логарифмических, тригонометрических и т. д.), Задают эти функции только в конечном числе точек. Для вычисления значений (приближенных!) функций в промежуточных точках служат правила интерполяции.

Другим не менее известным способом задания функций является формула, описывающая функцию как суперпозицию других (исходных) функций (пример 10). Если способ вычисления исходных функций известен, то формула задает процедуру вычисления данной функции как некоторую последовательность вычислений исходных функций. Вычисления функций по таблицам, формулам, а также с помощью графиков являются частным видом вычислительных процедур. Для функции, заданной таблицей, процедура заключается в поиске соответствующей строки таблицы; для формулы — в последовательном вычислении всех функций, входящих в суперпозицию. Существуют вычислительные процедуры, не относящиеся к указанным трем видам. Среди них особенно следует выделить рекурсивные процедуры. Рекурсивная процедура задает функцию F, определенную на N, следующим образом: 1) задается значение F(1) (или F(0)); 2) значение определяется через суперпозицию и других, считающихся известными функций. Простейшим примером рекурсивной процедуры является вычисление функции 1) 0! = 1; 2) В правой части последнего равенства имеется формула, однако это задание функции существенно отличается от задания формулой типа примера 10. Отличие состоит в том, что для того, чтобы вычислить 8!, необходимо сначала вычислить 7!, тогда как в примере 10 вычисление для любой тройки аргументов происходит «непосредственно». Более точно для вычИСления П! требуется П умножений, т. Е. число вычислительных шагов растет с ростом аргумента; для вычисления же функции примера 10 требуется независимо от значения аргументов всегда одно и то же число шагов (если шагом считать вычисление функции, входящей в суперпозицию), равное восьми.

Наконец, возможны описания функций, которые не содержат способа вычисления функции, хотя сомнений в том, что функция однозначно задана, не возникает. Определим, например, функцию следующим образом:

Из описания (см. п. 1.1.) не видно, как убедиться в том, что , поэтому нет гарантии, что можно вычислить.

Отступление 3. Для функций возникает тот же вопрос, что и для множеств; что значит «задать функцию»? По смыслу нашего определения задать функцию — это значит описать определяющее ее подмНОжество А ´ В, поэтому вопрос сводится к заданию некоторого множества. Однако можно определить понятие функции, не используя языка теории множеств: функция считается заданной, если задана вычислительная процедура, которая по любому заданному значению аргумента выдает соответствующее значение функции. Функция, определенная таким образом, называется Вычислимой. Процедура должна быть эффективной, т. е. однозначно приводящей к результату. Как уже говорилось ранее (см. отступление 2), уточнение понятия эффективной процедуры привело к созданию теории алгоритмов.

Понятие эффективной вычислительной процедуры — алгоритма, может быть принято за исходное, при построении всей системы понятий математики. Такой подход к обоснованию математики, называемый Конструктивным, допускает только те математические объекты и утверждения, которые могут быть получены с помощью алгоритмов. С этой точки зрения описанная Ранее функция вообще не заслуживает названия функции, поскольку для нее не указан алгоритм вычисления. Понятие множества перестает быть первичным; оно определяется с помощью разрешающей или порождающей процедуры (см. п. 1.1.). МножеСТва, для которых нет таких процедур, просто не рассматриваются,

Достоинства конструктивного подхода достаточно ясны. Однако ею последовательное проведение показало, что он требует более радикальной ревизии основных понятий математики, чем это кажется с первого взгляда, и иногда приводит к значительным концептуальным и языковым неудобствам. Поэтому в качестве «математического мировоЗЗрения» конструктивизм разделяется относительно небольшим числом маТЕматиков, хотя, пожалуй, никто не отрицает преимуществ конструктИВных методов в тех случаях, когда они возможны.

< Предыдущая		Следующая >