Упражнения

1. Если ρ есть отношение в R⁺, то его график есть некоторое множество точек первого квадранта координатной плоскости. Какова харак­теристическая особенность этого графика, если (а) ρ рефлексивно, (b) ρ симметрично, (с) ρ транзитивно?

2. Используя результаты упражнения 1, попытайтесь дать краткую формулировку характеристического свойства графика отношения эквивалентности в R⁺.

3. Семейство множеств {{1, 3, 4}, {2, 7}, {5,6}} есть разбиение мно­жества {1, 2, 3, 4, 5, 6, 7}. Постройте график соответствующего этому разбиению отношения эквивалентности.

4. Пусть ρ и σ — отношения эквивалентности. Докажите, также является отношением эквивалентности.

5. Докажите, что ρ есть отношение эквивалентности на множестве У тогда и только тогда, когда ρ  (Y*Y) есть отношение эквивалентности с областью определения Y.

6. Приведите примеры:

(а) отношения, рефлексивного и симметричного, но не транзитивного в некотором множестве;

(b) отношения, рефлексивного и транзитивного, но не симметрич­ного в некотором множестве;

(c) отношения, симметричного и транзитивного, но не рефлексивного в некотором множестве.

7. Завершите доказательство теоремы 1.5.

8. Каждое отношение эквивалентности на множестве X определяет по теореме 1.5 некоторое разбиение множества X. Каким отношением эквивалентности порождается самое мелкое разбиение? Самое крупное?

9. Завершите доказательство теоремы 1.6.

10. Пусть ρ—отношение, рефлексивное и транзитивное в множестве А. Определим для a, b  А отношение ~, полагая а~b, если aρb и bρа.

1. Докажите, что ~ есть отношение эквивалентности на А.

2. Докажите, что если а~а', b~b' и аρб, то a'ρb'. Выведите от­ сюда, что в фактормножестве А/~ можно определить новое отношение ρ': [а] ρ' [b], если aρb.

3. Докажите рефлексивность и транзитивность отношения ρ', а также, что если [а] ρ' [b] и [b] ρ' [а], то [а] =[b].

11. Во множестве Z⁺*Z⁺ положим по определению <а, b>~<c, d>, если a+d = b+c. Докажите, что ~ является отношением эквивалент­ности на данном множестве. Какой вид имеет график этого отношения? Опишите ~-классы эквивалентности.

1.8. Функции

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

(I) элементами f являются упорядоченные пары;

(II) если <x, у> и <x, z> суть элементы f, то y = z.

Примеры А

1. {<1, 2>, <2, 2>, <Рузвельт, Черчилль)} есть функция с областью определения {1,2, Рузвельт} и областью значений {2, Черчилль}.

2. Отношение {<1, 2>, <1, 3>, <2, 2>} не является функцией, так как различные элементы <1, 2> и <1, 3> имеют одинаковую первую коор­- динату.

3. Отношение {<х, х² + х + 1>|хR} есть функция, так как если х=и, то х²+ х + 1 = u² + u + 1

4. Отношение {<x2, x>| xR} не является функцией, так как его эле­- ментами являются как <1, 1>, так и <1, -1/.

Слово «функция» имеет многочисленные синонимы, в частности: пре­образование, отображение, соответствие, оператор¹. Если f—функция и <х, у>f, так что xfy, то х есть аргумент функции f. Для обозначе­ния у в этом случае терминология весьма разноречива; например, у называют значением функции f на х, образом элемента х при f, элемен­том, в который f переводит х. Для обозначения у также употребляют различные символы: xf, f (x) (или еще проще fx), x^f . Обозначение f (x) можно рассматривать как сокращение для f [{x}] — множества f-образов элемента х. В этих терминах характеристическое свойство функций, вы­деляющее их среди отношений вообще, можно сформулировать следую­щим образом: каждый элемент области определения имеет единственный образ.

Читатель должен привыкнуть ориентироваться в этих обозначениях функции, так как в разных книгах он будет встречать различные сим­волы и названия. Определения и теоремы, относящиеся к функциям, в этой книге всюду будут формулироваться в обозначениях f (х) или fx для (единственного) элемента, соответствующего элементу х в функции f. С этим хорошо согласуется также обозначение f[A] для множества {у | для некоторого х из А <х, у>f}. Впрочем, в приложениях понятия функции мы будем пользоваться различными обозначениями. Когда вместо f (х) нам будет удобнее применить обозначение xf, тогда естест­венно и вместо f[A] писать [А]f. Если же вместо f (х) мы будем пи­сать x^f, то в этих местах вместо f[A] будет использоваться обозначение [А^f] или A^f.

Поскольку функции являются множествами, к ним применимо обычное определение равенства: две функции f и g равны в том и только в том случае, когда они состоят из одних и тех же элементов. Очевидно, что то же самое можно сказать и другими словами: f =g тогда и только

¹ В математической литературе термины «соответствие», «функция», «отображе­ние», «преобразование» и «оператор» чаете не являются синонимами.—Прим. ред.

тогда, когда D_f=D_g и f(x)=g(x) для любого х из общей области оп­ределения. Следовательно, функцию можно определить, указав область ее определения и задав значения функции для каждого элемента об­ласти определения. Мы видим, таким образом, что вторая часть опре­делений такого рода имеет вид некоторого правила. Например, одно из возможных определений функции {<x, х² + x + 1 |х R} таково: функ­ция f с областью определения R такова, что f (х) = х²+х+1. Когда функция задается указанием на ее область определения и заданием ее значений для каждого элемента этой области, область ее значений мо­жет быть вовсе не очевидна. В приведенном только что примере, чтобы

прийти к заключению, что R_f={x R|x≥ ¾}, надо проделать неко­торые вычисления. С другой стороны, то обстоятельство, что в этом случае R_f R⁺, едва ли не очевидно. Вообще, при точном определении области значений мы сталкиваемся с определенными трудностями, но указать некоторое множество, включающее в себя область значений обычно, удается без труда. В связи с этим представляется разумным принять следующую терминологию. Функция f есть функция со значениями¹ в Y, если область значений функции f есть подмножество множества Y, и функция f есть функция со значениями на У, если R_f=Y. Вводя аналогичные терминологические соглашения для области определения функции, мы будем говорить, что f определена на X, если X есть об­ласть определения функции f. Желая сказать, что f есть функция, опре­деленная на множестве X со значениями в множестве Y, обычно поль­зуются символикой

f

f:X→ Y, или X→Y.

Множество всех функций, определенных на X со значениями в Y, есть подмножество множества Р(XxY); обозначим это подмножество через Y^x. Если X пусто, то Y^x состоит всего лишь из одного элемента, а именно из пустого подмножества множества XxY. Это единственное подмножество множества XxY, так как последнее само пусто, если пусто X. Если Y пусто, а X непусто, Y^x пусто.

Если f:X→ Y и А Х, то f ∩ (AxY) есть функция, определенная на А со значениями в Y (эту функцию называют сужением функции f на множество А и обозначают через f|A). Подробнее: f|A есть функ­ция, определенная на A и такая, что (f | A) (a) = f (а) для любого а, при­надлежащего множеству А. Функция g является сужением функции f

¹ Выделенные курсивом слова вставлены в эту и в следующую фразу при пере­воде во избежание двусмыслицы, связанной с одинаковым переводом двух различных английских предлогов: onto и on.— Прим. перев.

на некоторое подмножество области определения функции f тогда и только тогда, когда область определения функции g есть подмножество области определения функции f и для xD_g g(x) = f(x); иначе говоря, g f. В дополнение к определению сужения назовем функцию f про­должением функции g, если g Í f. В качестве примера, иллюстрирую­щего понятие продолжения функции, мы обратимся к описанному выше отношению тождества i_x в X. Очевидно, это отношение является функ­цией; поэтому, в соответствии с принятыми .нами обозначениями функ­ций посредством малых латинских букв, мы обозначим это отношение через i или i_х. Назовем i_x тождественным отображением на X. Если А Í X, то i_x| А = t_А. Если i_x|A рассматривается как функция, опреде­ленная на А со значениями в X, то это — инъективное отображение множества А в X.

Функция называется взаимно-однозначной, если она переводит различ­ные элементы в различные. Иначе говоря, функция f тогда и только тогда взаимно-однозначна, когда

х₁≠х₂ влечет f (х₁) ≠ f (x₂).

Взаимно-однозначность функции иногда удобнее доказывать, рассмат­ривая контрапозицию к написанному выше:

f(х₁) = f(х₂) влечет х₁ = х₂.

Например, функция f на R такая, что f(x) = 2x+ 1, взаимно-однозначна, так как 2х₁ + 1 = 2х₂ + 1 влечет х₁ = х₂.

Взаимно-однозначная функция f, определенная на X со значениями на Y, образует пары из элементов множеств X и Y; именно, в каждую пару входит f(x) из Y вместе с соответствующим х из X. В самом деле, поскольку f есть функция, f(x) есть однозначно определенный элемент множества Y; поскольку f принимает значения на Y, каждое у сопостав­ляется некоторому х; поскольку, наконец, f взаимно-однозначна, каж­дое у сопоставляется единственному х. Ввиду полной симметричности картины, возникающей при взаимно-однозначном отображении множества X на Y, его часто называют взаимно-однозначным соответствием между X и Y. Если два множества связаны между собой такой функцией, то говорят, что они находятся во взаимно-однозначном соответствии.

Примеры В

1. Хорошо известная читателю показательная функция есть функция, определенная на R со значениями в R; символически:

f : R→R, где f(x) = e^х.

Мы можем также сказать более точно, что f есть функция, определен­ная на R со значениями на R⁺. Вообще, если f:X→Y, то f — функция, определенная на X со значениями на f[X], т. е. на области значений функции f.

2. {а, b, с}^{1,2} есть множество всех функций, определенных на {1, 2} со значениями в {а, b, с}. Один из элементов этого множества — {<1, а>, <2, с>}.

3. Если А и В — множества, имеющие одинаковое число элементов, то они, очевидно, находятся во взаимно-однозначном соответствии¹. Тогда, как легко показать, для любого множества X множества А^х и В^х находятся во взаимно-однозначном соответствии. В соответствии с этим множество всех функций, определенных на некотором множестве X со значениями в произвольном множестве, состоящем из п элементов, обо­ значают обычно через п^х. Так, 2^х обозначает множество всех функций, определенных на X со значениями в множестве из двух элементов, в качестве какового обычно берут множество {0, 1}. Если А Í X, то один из элементов множества 2^х есть функция χ_А, определяемая следующим образом:

χ_А(х)=1, если хА, и χ_А(х) = 0, если xХ — А.

Мы будем называть χ_А характеристической функцией множества А. Рас­смотрим теперь функцию f, определенную на p f. P(Х) со значениями в 2^х, взяв в качестве образа подмножества А множества X [А является эле­ментом множества P(Х)] характеристическую функцию этого подмно­жества А (являющуюся элементом множества 2^х). В качестве упражне­ния предлагаем доказать, что f есть взаимно-однозначное соответствие между P (X) и 2^х. В силу этого взаимно-однозначного соответствия мно­жества P(X) и 2^х обычно просто отождествляют, свободно заменяя в рассуждениях одно из этих множеств другим, если это удобно по каким-либо соображениям.

4. Пусть f —функция, а A и В — множества. Можно доказать, что f[A Ư B] = f[A] Ư f[B] и f[A∩Я] f[A]∩f[В]. В случае А∩В отношение включения усилить нельзя.

В элементарной математике приходится использовать и функции не­скольких переменных. В рассматриваемых нами терминах функция (от) п

¹ Точнее было бы сказать: «могут быть поставлены во взаимно-однозначное со­ответствие», так как никакой конкретной функции, осуществляющей такое соответ­ствие между равночисленными множествами, вместе с ними не задается (хотя такие функции существуют, и не одна). Подобные небрежности встречаются в тексте и дальше; там, где игнорирование их могло бы привести к недоразумениям, они будут оговариваться.— Прим. перев.

переменных (n≥2) есть попросту функция, аргументами которой слу­жат упорядоченные n-ки. Под эту схему можно подвести и случай n=1, согласившись, что «упорядоченная 1-ка» <х> есть просто х. Если обозначить множество всех упорядоченных n-ок <х_1, х₂, ..., х_n>, где каждое х_i - (i=l, ..., n) принадлежит некоторому множеству X, через Х^п, то можно сказать, что функция, определенная на Х^п и при­нимающая значения в X, есть п-арная операция в X. Вместо «1-арная» мы будем говорить «унарная»¹; например, дополнение есть унарная операция в множестве всех подмножеств какого-либо множества; вместо «2-арная» мы будем говорить «бинарная»². Фактически мы уже исполь­зовали это понятие, рассматривая операции над множествами; так, пе­ресечение есть ,бинарная операция в соответствующей системе множеств. Аналогично, сложение в Z есть бинарная операция; если х, yZ, то значение этой функции от <х, у> обозначается через х+у.

Упражнения

1. Привести пример функции, определенной на R со значениями на Z.

2. Показать, что если АÍХ, то i_x|A = i_A.

3. Если X и Y суть множества, состоящие, соответственно, из п и т элементов, то из скольких элементов состоит множество Y^x. Какое число элементов множества P(X*Y) суть функции?

4. Пользуясь только отображениями вида f:Z⁺→ Z⁺, приведите при­- мер функции:

1. взаимно-однозначной, но со значениями не на Z⁺;

2. со значениями на Z⁺, но не взаимно-однозначной.

5. Пусть А = {1, 2,..., я}. Доказать, что если отображение f:A→А принимает значения на А, то оно взаимно-однозначно, и что если отобра­- жение g:A→А взаимно-однозначно, то оно принимает значения на А.

x

5. Пусть f:R⁺→ R, где f(x)=∫ dt/t. Доказать любым доступным спо-

1

собом, что f есть взаимно-однозначная функция, принимающая значения на R.

7. Доказать, что функция f, определенная в третьем из примеров В, является взаимно-однозначным соответствием между Р(Х) и 2^х.

8. В связи с четвертым из примеров В доказать, что если f—функ­ ция, а A и B—множества, то f[AB] = f[A] f[B].

¹ Иначе—одномастная, или сингулярная.—Прим. перев.

² Иначе—двуместная.— Прим. перев.

9. В связи с предыдущим упражнением доказать, что при тех же предположениях f [A∩В] Í f[A] ∩ f[В], и показать, что случай стро­ гого включения действительно может иметь место.

10. Доказать, что f[A∩В] = f[A]∩f[В] для любых множеств A и В тогда и только тогда, когда f взаимно-однозначна.

Замечание. В упражнениях 11—13 читателю предлагается отобрать только легко доказываемые утверждения и доказать их. Доказательство остальных утвержде­ний можно отложить до изучения § 1.9.

11. Пусть А, В, А', В' —множества, причем А находится во взаимно­ однозначном соответствии с А'', а В — во взаимно-однозначном соответст­- вии с В'. Показать, что:

(а) можно установить взаимно-однозначное соответствие между АхВ и А'хВ';

(b) можно установить взаимно-однозначное соответствие между А^в и А'^в';

(c) если A∩В =ø и А'∩В' =ø, то можно установить взаимно­- однозначное соответствие между AВ и A' В'.

12. Для произвольных множеств A, В и С доказать, что:

1. АхВ находится во взаимно-однозначном соответствии с ВхА;

2. (АхВ)хС находится во взаимно-однозначном соответствии с Ах{ВхС);

(c) A х (В  С) находится во взаимно-однозначном соответствии с (AхВ)и(AхС).

13. Для произвольных множеств A, В, С доказать, что:

(a) {АхВ)^с находится во взаимно-однозначном соответствии с А^схВ^с;

(b) (А^в)^с находится во взаимно-однозначном соответствии с А^ВхС; fс) если В∩С = ø, то A^вс находится во взаимно-однозначном

соответствии с А^вхА^с.