Композиция (суперпозиция) функций

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

Пусть даны две функции f: A ® B и g: C ® D с областями определения D(f) Í A, D(g) Í C и образами Im(f) Í B, Im(g) Í D. Композицией функций f и g называется множество

g o f = {(a; d) Î A´D | a Î D(f) Ù f(a) Î D(g) Ù d = g(f(a))},

если оно непусто (т.е. если g o f является бинарным отношением). Ясно, что D(g o f) = {a Î D(f) | f(a) Î D(g)},

Im(g o f) = {g(f(a)) Î C | a Î D(f) Ù f(a) Î D(g)}.

На самом деле композиция функций (в том случае, когда она определена) является функцией, т.к. удовлетворяет условию

" a Î D(g o f) $ ! d Î D a (g o f) d

функциональности: из определения видно, что если a (g o f) d, то d = g(f(a)) и это значение определено однозначно поскольку f, g – функции. Итак, композиция двух функций f: A ® B и g: B ® C является операцией, позволяющей построить новую функцию g o f: A ® D из А в D.

Примеры: 1. Пусть функции f : R ® R и g : R ® Rзаданы правилами f(x) = x – 1, g(y) = . Тогда A = B = C = D = Rи композиция gof : R ® Rвычисляется по правилу gof(x) = g(f(x)) = g(x – 1) = . При этом

D(gof) = {a Î D(f) | f(a) Î D(g)} = { a Î R | a – 1 Î R₊₀ } =

= {a Î R | a – 1 ³ 0} = [1; +∞ ],

Im(g o f) = {g(f(a)) Î C | a Î D(gof)} = { Î R | a ³ 1} = R₊₀ .

Таким образом, композиция gof – это знакомая сложная функция y = , области определения и значений которой можно найти непосредственно и убедиться, что они совпадут с вычисленными в примере 1множествами.

2. Если f: R ® R, f(x) = –1 –x², g: R ® R, g(y) = ln(y), то A = B = C = D = = R, но композиция gof не определена, т.к. D(gof) = {a Î D(f) | f(a) Î D(g)} = = {a Î R | –1–a² Î R₊} = Æ.

Это согласуется со школьным подходом: сложная функция y = ln(–1 – x²) нигде не определена.

3. Если f : R₊ ® R, f(x) = cos x, g : [0; 1] ® R, g(y) = y – , то A = R₊ , B = R = D, C = [0; 1] и композиция gof : R ® Rвычисляется по правилу gof(x) = g(f(x)) = g(cos x) = cos x – . При этом

D(gof) = {a Î D(f) | f(a) Î D(g)} = {a Î R₊ | cos a Î [0; 1]} =

= {a Î R₊ | 0+2p×n £ a £ + 2p×n } = [2p×n; 2p×n + ].

5.Если f : R₊ ® R, f(x)= x – , g: [0; 1] ® R, g(y) = cos y, то A = R₊, B = R= D, С = [0; 1] и композиция gof : R₊ ® R вычисляется по правилу gof(x) = g(f(x)) = cos(x – ) = sin x. При этом

D(gof) = {a Î D(f) | f(a) Î D(g)} = {a Î R₊ | a – Î [0; 1]} =

= {a Î R₊ | £ a £ 1+ } = [ ; 1 + ].

Теорема (об ассоциативности композиции функций). Пусть A, B, C, D – непустые множества, f : A ® B, g : B ® C, h : C ® D – функции. Тогда можно образовать композиции ho(gof) : A ® D и (hog)of : A ® D, которые на самом деле равны между собой. Таким образом, выполняется закон ассоциативности композиции ho(gof) = (hog)of .

Доказательство. Исходя из определения равенства функций, необходимо проверить два условия: D(ho(gof)) = D((hog)of) – равенство областей определенияи " a Î D(ho(gof)) ho(gof)(a) = ho(gof)(a) – совпадение значений.

Имеем

D(ho(gof)) = {a Î D(gof) | gof(a) Î D(h)} =

= {a Î {x Î D(f) | f(x) Î D(g)} | g(f(a)) Î D(h)} =

= { a Î D(f) | f(a) Î D(g) Ù g(f(a)) Î D(h)} =

= { a Î D(f) | f(a) Î {x Î D(g) | g(x) Î D(h)}} =

= {a Î D(f) | f(a) Î D(hog)} = D((hog)of).

Кроме того,

" a Î D(ho(gof)) ho(gof)(a) = h(gof(a)) = h(g(f(a))) = hog(f(a)) = (hog)of(a).

Теорема доказана.

В отличие от закона ассоциативности композиция функций, вообще говоря, не коммутативна: существуют функции f: A ® A и g: A ® A, для которых fog ¹ gof. Приведите примеры таких функций (ещё раз проанализируйте предыдущие примеры).

Теорема (о композиции функций специального вида). Пусть А, В, С – непустые множества, f : A ® B и g : B ® C – функции. Тогда

(1) если f и g – отображения, то gof – отображение,

(2) если f и g – инъективны, то gof – инъективна,

(3) если f и g – сюръективны, то gof – сюръективна,

(4) если f и g – биективны, то gof – биективна.

Доказательство. Все свойства доказываются однотипно, исходя из определений функций специального вида.

(1) Пусть f и g – отображения, т.е. D(f) = A, D(g) = B.Нужно доказать, что D(gof) = A. Если a Î A, то определены b = f(a) Î B и c = g(b) Î C, т.е. определено и значение gof(a) = g(f(a)) = g(b) = c, что и требовалось.

(2) Пусть f и g – инъективные функции, т.е. каждая принимает различные между собой значения при разных значениях своих аргументов. Нужно доказать, что " a₁ , a₂ Î D(gof) gof(a₁) = gof(a₂) ® a₁ = a₂ . В самом деле, если gof(a₁) = gof(a₂), то g(f(a₁)) = g(f(a₂)), откуда (ввиду инъективности функции g)следует f(a₁) = f(a₂). В свою очередь из этого равенства получаем a₁ = a₂ ввиду инъективности функции f,что и требовалось.

(3) Пусть f и g – сюръективны, т.е. Im(f) = B, Im(g) = C.Нужно доказать, что Im(gof) = C. Если c Î C, то (ввиду сюръективности g) найдётся такой элемент b Î B, что g(b) = c. Сюръективность функции f гарантирует существование для найденного b Î B такого элемента a Î A, что f(a) = b. Поэтому gof(a) = g(f(a)) = g(b) = c, что и требовалось.

(4) следует из (1), (2), (3).

Теорема доказана.

Следствие. Пусть А – непустое множество и

F(A) = { f : A ® A | D(f) = A}

– множество всех отображений из А в А. Тогда

(1) " f, g Î F(A) gof Î F(A),

(2) " f, g, h Î F(A) (hog)of = ho(gof),

(3) $ id_A Î F(A) " f Î F(A) foid_A = f = id_Aof.

Доказательство.(1) и (2) уже доказаны.

Для проверки (3) нужно проверить, что foid_A = f = id_Aof, т.е. " a Î A foid_A(a) = f(a) = id_Aof(a). Это проверяется непосредственно: например,

foid_A(a) = f(id_A(a)) = f(a) = id_A(f(a)) = id_Aof(a).

Следствие доказано.

Обратимые функции

Функцию f : A ® B называют обратимой, если $ g : B ® A gof = id_A Ù Ù fog = id_B . При этом функцию g : B ® A называют обратной к функции f и обозначают через f ^–1.

Примеры: 1. Для любого непустого множества A функция id_A обратима и обратна сама себе, т.е. id_A^–1 = id_A . Это следует из равенства id_Aoid_A = id_A .

2. Функция f : R ® R₊ , f(x) = e^x обратима. При этом обратной к ней является функция f ^–1 : R₊ ® R, где f ^–1(y) = ln(y).

Всё следует из тождеств e ^{ln x} = x (x Î R₊), ln(e^x) = x (x Î R).

3. Функция f : R ® R , f(x) = e^x не является обратимой. Действительно, предположим, что существует функция g : R ® Rсо свойством gof = id_R = fog. Тогда при x < 0 получаем 0 > x = id_R(x) = fog(x) = e^g(x) > 0 – противоречие.

4. Пусть функция f: A ® A обратима. Тогда график Г(f ^–1) обратной функции симметричен графику Г(f) исходной функции относительно диагонали D = {(a; a) Î A´A}.

В самом деле, (a; b) Î Г(f) Û b = f(a) Û a = f ^–1(b) Û (b; a) Î Г(f ^–1),а точки (a; b) и (b; a) симметричны относительно диагонали. Всё ли Вам понятно в этом рассуждении ? Восстановите все детали самостоятельно.

Теорема (критерий обратимости функции). Функция f : A ® B обратима тогда и только тогда, когда f биективна.

Доказательство. (Þ) Докажем, что обратимая функция f : A ® B с обратной функцией g : B ® A будет биективной, т.е. D(f) = A, f инъективна и сюръективна.

Действительно, во-первых, из условия gof = id_A следует, что " a Î A id_A(a) = a = g(f(a)), так что f(a) должно быть определено.

Во-вторых, f инъективно: если f(a₁) = f(a₂), то снова из условия gof = id_A получаем a₁ = id_A(a₁) = g(f(a₁)) = g(f(a₂)) = id_A(a₂) = a₂ , что и требовалось.

Наконец, f сюръективно: если b Î B, то для a = g(b) Î A имеем f(a) = = f(g(b)) = fog(b) = id_B(b) = b, что и требовалось.

(Ü) Докажем теперь, что любая биективная функция f : A ® B обратима. Для построения обратной функции f ^–1 : B ® A рассмотрим множество g = = {(b; a) Î B´A | b = f(a)} и докажем, что g = f ^–1 .

Во-первых, g – бинарное отношение, т.е. g ¹ Æ: в самом деле, " a Î A (f(a); a) Î g.

Во-вторых, g – функция: если (b; a₁), (b; a₂) Î g, то f(a₁) = b = f(a₂), откуда ввиду инъективности функции f следует a₁ = a₂ , что и требовалось для функциональности g.

Наконец, g – обратная функция к f, т.е. gof = id_A Ù fog = id_B . Это проверяется непосредственно: например, из очевидных равносильностей (a; b) Î f Û b = f(a) Û (b; a) Î g Û g(b) = a получаем gof(a) = g(f(a)) = = g(b) = a = id_A(a), т.е. gof = id_A .

Теорема доказана.

Следствие. Если А ¹ Æ и S(A) = { f Î F(A) | f биективно }, то

(1) " f, g Î S(A) gof Î S(A),

(2) " f, g, h Î S(A) (hog)of = ho(gof),

(3) $ id_A Î S(A) " f Î S(A) foid_A = f = id_Aof ,

(4) " f Î S(A) $ f ^–1 Î S(A) fof ^–1 = id_A = f ^–1of.

Таким образом, (S(A), o ) – группа.

§ 7*. Об аксиоматике Цермело-Френкеля теории множеств

Хотя основные понятия теории множеств были введены выше, развиваемая Г. Кантором на этом основании наивная теория множеств столкнулась в конце XIX в. с трудностями. Вот – лишь один пример парадокса наивной теории множеств.

Парадокс Рассела: Пусть U – множество всех множеств. Рассмотрим множество M = {A Î U | A Ï A} и попробуем ответить на вопрос: верно ли, что M Î M ? Если это утверждение истинно, т.е. M Î M, то получаем противоречие с определением множества M – оно образовано только из тех множеств, которые не являются элементами самих себя. Однако и предположение M Ï M тоже ведёт к противоречию, т.к. в этом случае (по определению множества M) должно быть выполнено M Î M. Итак, получено противоречие.

Выход из создавшейся ситуации только один – нельзя считать “множество всех множеств” U множеством: если U – не множество, то не является множеством и образованное из U с помощью конструкции выделения “множество” M, а значит, к нему не применимы дальнейшие рассуждения о множествах, и противоречие исчезает. Однако наивное изложение теории множеств не позволяет строго определить, является ли та или иная совокупность объектов множеством. Таким образом, требуется более строгий подход при определении операций над множествами.

Ниже неформально излагается система аксиом Цермело-Френкеля для формальной теории множеств, предложенная в 1908 г. Э. Цермело и усовершенствованная к 1922 г. А. Френкелем. Хотя за всё время пользования этой аксиоматикой не выявлено ни одного парадокса, её непротиворечивость невозможно доказать внутренними средствами теории множеств (теорема К. Гёделя). Поэтому математики и в настоящее время не могут спать спокойно, ибо почва под их ногами постоянно колышется и даже не видно средств хоть как-то её укрепить.

Неопределяемыми понятиями теории множеств будут “множество”, “элемент”, двухместный предикат принадлежности Î и двухместный предикат равенства элементов =. Как и при построении всякой математической теории, зафиксируем алфавит теории множеств, состоящий из объектных переменных, обозначаемых большими и малыми буквами латинского алфавита, двухместных предикатных символов Î и = , логических связок Ù , Ú , ® , « , , кванторов " , $ и служебных символов ( , ) –скобок. На этом этапе совокупность всех этих символов не рассматривается как множество, чтобы не возникало замкнутого круга, порочащего создаваемую теорию.

Хотя большие буквы, как правило, обозначают множества, а малые – элементы множеств, строгого разделения в обозначениях на элементы и множества не будет, ибо a’priori невозможно сказать, является ли элемент некоторого множества множеством: большие буквы будут использованы для обозначения множеств лишь в случаях, не вызывающих сомнения.

Как и в любой специальной математической теории, вводится понятие формулы теории множеств – подмножество “осмысленных” предложений в алфавите. Кроме того, введём следующие общеупотребительные сокращения: x Ï A будет обозначать , A ¹ B будет употребляться вместо , формулы (" x Î A Ф(x)) и (" x Ï A Ф(x)) – вместо (" x ((x Î A) ® Ф(х))) и (" x (x Ï A ® Ф(х))) соответственно, а ($ x Î A Ф(x)) и ($ x Ï A Ф(x)) – вместо ($ x ((x Î A) Ù Ф(х))) и ($ x (x Ï A Ù Ф(х))). Запись ($ ! x Î A P(x)) является синонимом более длинной (($ x Î A P(x)) Ù (" y Î A (P(y) ® (y = x)))). В формулах теории множеств будем для краткости опускать внешние скобки, которые не несут информации.

Теперь рассмотрим аксиомы теории множеств.

1⁰. аксиома объёмности :" А, В ((А = В) « (" x (x Î A « x Î B)))

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

2⁰. аксиома равенства : " а, А, b ((a = b Ù a Î A) ® b Î A)

Эта аксиома согласовывает понятия равенства элементов с предикатом принадлежности: было бы странным, если бы равные элементы отличались бы принадлежностью к какому-нибудь множеству. Наивная теория множеств на такие “мелочи” внимания не обращает.

Назовём множество В подмножеством множества А, если " x (x Î В ® x Î A). В этом случае будем говорить также, что А содержит В (А включает В или А – надмножество В) и писать В Í А. Ясно, что " A, B ((А = В) « ((A Í B) Ù (B Í A)) . Для двух множеств X, Y будем писать коротко X Ì Y , если (X Í Y Ù X ¹ Y).

3⁰. аксиома выделения : " А ($ B (" x (x Î B « (x Î A Ù Р(х))))), где Р(х) – произвольная формула теории множеств со свободной переменной х, в которую не входят предметные переменные А и В.

Заметим, что при фиксированных значениях свободных переменных в формуле P(x) множество В определено однозначно: если C – другое множество, удовлетворяющее 3⁰, то " х (х Î В « (x Î A Ù P(x))) и " x (x Î C « (x Î A Ù P(x))), так что " x ((x Î В) « « (x Î C)), т.е. B = C по аксиоме объёмности. Множество В будет в дальнейшем обозначаться через {x Î A | P(x)}. Ограничение, накладываемое на формулу P(x) существенно ограничивает возможности принципа выделения.

Из аксиомы выделения следует, в частности, существование множества, не имеющего элементов, которое называется пустым множеством, и будет обозначаться символом Æ .Его можно задать, например, так: Æ = {x Î A | x ¹ x}, где А – любое множество. Легко понять, что пустое множество определено однозначно: если Е – любое множество без элементов, то " х (х Î Е « x Î Æ) и, по аксиоме объёмности, Е = Æ .

Кроме того, аксиома выделения позволяет построить пересечение и разность двух множеств: А Ç B = {x Î A | x Î B} , A \ B = {x Î A | x Ï B}. Следует отметить, что эти множества корректно определены, если A и B – разные буквы. Если же A = B, то дополнительно нужно положить А Ç A = A, A \ A = Æ. Аксиома выделения не позволяет образовать объединение двух множеств A È B = {x Î ? | x Î A Ú x Î B}, т.к. не известно, из какого множества нужно брать элементы объединения. В то же время, если A Í C, B Í C для некоторого множества C, то по аксиоме выделения можно создать A È B = {x Î С x Î A Ú x Î B} – объединение подмножеств А и В.

4⁰. аксиома существования булеана (множества всех подмножеств) :

" A ($ B (" X (X Î B « X Í A)))

Введённое множество В будем в дальнейшем обозначать через В(А) и называться булеаном множества А или множеством всех подмножеств множества А. Проверьте самостоятельно, что булеан определён однозначно.

5⁰. аксиома (неупорядоченной) пары :

" а, b ($ A (" x (x Î A « (x = a Ú x = b))))

Содержательно здесь говорится о возможности образовывать множество А = {a, b}, состоящее излюбых объектов а, b. Построенное множество тоже определено однозначно (?!). Оно не обязательно двухэлементно: если а = b, то {a, b} содержит один элемент, и в этом случае будет обозначаться просто через {a}.

Эта аксиома позволяет ввести понятие упорядоченной пары – математического объекта (a; b), удовлетворяющего следующему свойству упорядоченной пары " а, b, c, d (((a; b) = = (c; d)) ® ((a = b) Ù (c = d))). Именно, назовём упорядоченной парой объектов а и b множество (a; b) = {{a}, {a, b}}, существование которого гарантируется аксиомой (неупорядоченной) пары. Проверим, что при этом выполняется свойство упорядоченной пары. В самом деле, согласно аксиомам объёмности и неупорядоченной пары, если {{a}, {a, b}} = = {{c}, {c, d}}, то возможны следующие случаи:

1) {a} = {c}. Тогда а = с. Если при этом {a, b} = {c, d} , то {a, b} = {а, d} и b = d (возможно, b = a = d).Если же {a, b} = {с}, то a = c = b и {a} = {a, b} = {с, d}, т.е. {a, d} = {a}, и последнее равенство опять даёт b = a = d , что и требовалось.

2) {a} ¹ {c}, т.е. a ¹ c. Тогда {a} = {c, d}, что невозможно, т.к. с Ï {a} .

Итак, определено понятие упорядоченной пары, которое не задаёт объект “упорядоченная пара” однозначно: например, множество {{{a}, {a, b}}} тоже удовлетворяет свойству упорядоченной пары. Проверьте это и придумайте другие упорядоченные пары. Всюду далее обозначение (a; b) будет означать, что (а, b) = {{a}, {a, b}}.

6⁰. аксиома объединения : " А ($ U (" х (х Î U « ($ C (C Î A Ù x Î C)))))

Множество U состоит из всех элементов, принадлежащих хотя бы одному множеству, являющемуся элементом множества А.

Эта аксиома значительно сильнее, чем утверждение о существовании объединения двух множеств: она постулирует существование объединения U всех множеств, входящих в качестве элементов в заданное множество А. Построенное множество U определено однозначно (?!), называется объединением по А и обозначается через È {C Î A} или .

Теперь с помощью аксиомы выделения можно определить для множества А и пересечение по А, полагая Ç {C Î A} = {x Î È {C Î A} | " C Î A x Î C}. Это множество состоит из всех элементов, принадлежащих одновременно всем множествам, являющимся элементами множества А и обозначается также через .

Упражнение.Чему равно объединение и пересечение по пустому множеству ?

Как теперь построить объединение двух множеств А и В ? Рассмотрим неупорядоченную пару P = {A, B} и применим к ней аксиому объединения. Тогда множество È {C Î P} и будет объединением множеств А и В, которое в дальнейшем будет обозначаться просто через А È В : по аксиоме объединения " x ((x Î È {C Î {A, B}}) « (x Î A Ú x Î B)), что и требовалось.

С помощью конструкций пересечения и объединения двух множеств можно построить пересечение и объединение любого конечного числа множеств:

A₁ Ç ... Ç A_n = ((...(A₁ Ç A₂) Ç ... ) Ç A_n–1) Ç A_n ,

A₁ È ... È A_n = ((...(A₁ È A₂) È ... ) È A_n–1) È A_n .

Если теперь а₁ , ... , а_n – произвольные элементы, то по аксиоме пары, существуют множества {a₁}, ... , {a_n}, объединение которых, даёт конечное множество {a₁ , ... , a_n } .

Если А и В – множества, а Î А, b Î B, то можно спросить – какому множеству принадлежит упорядоченная пара (а; b) = {{a}, {a, b}} ?

Ясно, что {a} Î B(A È B) , {a, b} Î B(A È B), поэтому (а; b) Î B(B(А È В)). Теперь можно применить аксиому выделения, чтобы построить декартово произведение

A´В = {x Î B(B(A È B)) | ($ a ($ b (a Î A Ù b Î B Ù x = (a; b))))} .

Так как упорядоченная пара существует для любых объектов, то А´В = Æ тогда и только тогда, когда А = Æ или В = Æ .

Упражнение.Докажите следующие свойства декартова произведения:

1) А´В Í С´D тогда и только тогда, когда А Í С и В Í D ,

2) А´В = С´D тогда и только тогда, когда А = С и В = D ,

3) А´(В´С) = (А´В)´С тогда и только тогда, когда А = С = Æ .

7⁰. аксиома регулярности : " А ¹ Æ ($ В Î А (" а Î А а Ï В))

Содержательно эта аксиома говорит о том, в любом непустом множестве A существует элемент В Î А, не содержащий никаких элементов из А.

Важное следствие этой аксиомы заключается в том, что не существует множеств А, В со свойством А Î В Î А : если бы нашлись такие множества, то множество-пара {A, В} не удовлетворяла бы аксиоме регулярности, т.к. любой из его элементов содержит хотя бы один элемент множества {A, В}, т.к. А содержит В, а В содержит А.

В частности, не существует множества, содержащего себя в качестве элемента, ибо если А Î А, то А Î А Î А, вопреки доказанному. Это ставит вне закона “множество всех множеств”, ибо такой объект должен содержать как элемент сам себя.

Кроме того, аксиома регулярности позволяет решать и некоторые другие вопросы. Например, с её помощью можно доказать, что равенство а = (а; b) невозможно: если допустить, что а = (а; b) = {{a}, {a, b}}, то а Î {a} Î a , что невозможно.

Упражнения: 1.Докажите, что объект {a, {a, b}} также удовлетворяет свойству упорядоченной пары.

2.Докажите, что не существует множеств А, В, С со свойством А Î В Î С Î А.

3.Обобщите предыдущее упражнение на случай произвольного числа множеств.

Введём теперь понятие функции f : ? ® ? с неопределёнными областями определения и значений, понимая под этим любое множество f, удовлетворяющее следующему обобщённому условию функциональности:

(" х Î f ($ u, v x = (u; v))) Ù (" u, v, w ((u; v) Î f Ù (u; w) Î f) ® v = w).

При этом если (u; v) Î f, то будем кратко писать f(u) = v и называть v значением функции f на элементе u.

Следует отметить, что для функции f с неопределёнными областями определения и значений нельзя применить аксиому выделения для построения области её определения и множества значений. Например, пытаясь задать Im(f) = { b Î ? | $ a (a; b) Î f}, невозможно указать из какого множества выбирать значения b. Поэтому необходима специальная аксиома, присваивающая статус множества этому объекту.

8⁰. аксиома существования области значений : для любой формулы Ф(х, у) со свободными переменными х, у справедливо свойство

" А (" х Î A (" у, z (Ф(х, у) Ù Ф(х, z) ® y = z))) ® ($ B(" y (y Î B « ($ x Î A Ф(х, у)))))

Эта аксиома имеет дело с более широким классом зависимостей, чем обычные функции: она утверждает существование “области значений” В = Im_А (Ф) для любого функционального на Азакона, выражаемого с помощью формулы Ф(х, у), даже в том случае, если a’priori неизвестно, определяет ли Ф функцию на А (ведь пока не ясно, будет ли множеством объект {(x; y) Î ? | x Î A Ù Ф(х, у)}).

Теперь можно с полным основанием ввести области значений и определения функции f с неопределёнными областями определения и значений на заданном множестве А: нужно только заметить, что формула Ф(х, у) = ((х; у) Î f) функциональна на А, т.е. удовлетворяет посылке аксиомы существования области значений. Значит, определено множество Im_А (f) = = Im_А (Ф), состоящее из всех тех у,для которых найдётся х Î А со свойством (х; у) Î f . Поэтому по аксиоме выделения можно ввести область определения функции f на множестве А – множество D_А (f) = {a Î A | $ b Î Im_А (f) (a; b) Î f}. Если D_А (f) = A, то будем называть функцию f отображением на А.

Узаконив функции, можно определить индексированные элементами одного множества последовательности: если I – множество, то говорят, что задана последовательность объектов а_i , где i Î I, если задана функция а : I ® ?, где а_i = a(i). Ясно, что можно рассматривать множество всех членов последовательности, поскольку оно является областью значений функции а: {a_i}_iÎI = Im_I (a).

Возникает вопрос, зачем нужны функции с неопределёнными областями определения и значений ? Дело в том, что если A и B – два множества, то можно было бы определить понятие функции из A в B как любое множество f (обычно обозначаемое через f : A ® B), удовлетворяющее свойству функциональности:

(" х Î f ($ u Î A ($ v Î B x = (u; v)))) Ù (" u Î A " v, w Î B ((u; v) Î f Ù (u; w) Î f)) ® v = w).

Для таких функций области значений и определения существуют просто по аксиоме выделения: Im(f) = {b Î B | $ a Î A (a; b) Î f}, D(f) = { a Î A | $ b Î B (a; b) Î f}.

Значение аксиомы существования области значений состоит в том, что она даёт средство с помощью формул теории множеств, обладающих свойствами функциональности получать универсальные задания “функций”, определённых на всех мыслимых множествах сразу. Действительно, для любой формулы Ф(х, у) со свойством функциональности можно рассмотреть объект f = {(a; b) Î A´Im_А (Ф) | Ф(a, b)} являющийся множеством согласно аксиоме выделения. (Это описание не слишком формально. Вставьте в него определение декартова произведения А´Im_А (Ф) и сформулируйте строго условие, которому должна удовлетворять формула Ф(x, y)). Таким образом, на каждом множестве А рассматриваемая формула определяет функцию, но задана эта функция сразу для любого мыслимого множества.

Например, можно определить ординальные числа или ординалы как множества из “область истинности” следующего универсального “предиката”-формулы:

Ord(X) = (" Y, Z ((Z Î Y Ù Y Î X) ® Z Î X))) Ù (" Y, Z Î X (Z Î Y Ú Y = Z Ú Y Î Z)).

“Предикат” Ord является конъюнкцией двух условий: транзитивности относительно Î и линейной упорядоченности относительно Î .

На самом деле, конечно, говорить о предикате Ord и о его области истинности можно, только ограничив действие Ord на некотором фиксированном множестве А, т.е. для соблюдения формальностей нужно ввести формулу Ф(х, у) = (у Î х Ù Ord(y)) и воспользоваться аксиомой существования области значений для получения множества Im_А (Ф) всех ординальных чисел из множества А. Это соответствует описанной выше общей схеме использования аксиомы существования области значений.

9⁰. аксиома бесконечности : $N (Æ Î N) Ù (" X Î N X È {X} Î N)

Эта аксиома впервые утверждает существование некоторого множества. До сих пор все конструкции множеств “повисали в воздухе”, поскольку не было ясно, существует ли хотя бы одно множество. Интуитивно ясно, что множество N должно быть бесконечным, т.к. оно содержит попарно различные элементы

n₀ = Æ , n₁ = Æ È {Æ}, n₂ = Æ È {Æ} È {Æ È {Æ}}, …

Упражнение.Упростите вид элементов n₁ , n₂ , n₃ , … , n_i , … и докажите, что все они попарно различны.

Говорят, что два множества X и Y равномощны, если существует биективное отображение (биекция) Х на Y, т.е. такая функция f: X ® Y, для которой D(f) = X, Im(f) = Y и выполнено условие инъективности " a, b Î X (f(a) = f(b) ® a = b). В этом случае пишут кратко X » Y.

Примеры: 1. Z » 2·Z » N.

Здесь, как обычно, 2·Z = {x Î Z | $ z Î Z x = 2·z}. Можно взять следующие отображения f : Z ® 2·Z, где f(z) = 2·z, j : N ® Z, где j(n) = .

Легко понять, что f и j – биекции, и воспользоваться следующим примером.

2.А » А ; если А » В, то В » А; если А » В и В » С, то А » С. Эти три свойства – рефлексивность, симметричность и транзитивность отношения равномощности.

Достаточно рассмотреть биекции id_A : A ® A – тождественное отображение множества А, f ^–1 : B ® A, где f : A ® B – биекция, и g o f : A ® C, где f : A ® B и g : B ® C – биекции.

Эти примеры неформальны, т.к. множества натуральных чисел N, как и множества Z целых чисел и Q рациональных чисел ещё не построены.

Формализуем теперь понятия конечного и бесконечного множеств. Множество А называется бесконечным, если оно равномощно некоторому своему собственному подмножеству, и конечным, если оно не является бесконечным. Эти определения можно записать формально в несколько этапов:

(A – бесконечно) º ($ B Æ ¹ B ¹ A) Ù ($ f : A ® B – би),

($ B Æ ¹ B ¹ A) º ($ B ($ b Î B) Ù ($ a Î A a Ï B)),

($ f : A ® B – би) º ($ f : A ® B – функция) Ù (D(f) = A) Ù (Im(f) = B) Ù (f – инъ),

($ f : A ® B – функция) º ($ f (" u Î f ($ a Î A ($ b Î B u = (a; b))))) Ù (f – функционально),

(f – функционально) º (" a Î A (" b, c Î B (((a; b) Î f Ù (a; c) Î f) ® b = c))),

(D(f) = A) º (" a Î A ($ b Î B (a; b) Î f)),

(Im(f) = B) º (" b Î B ($ a Î A (a; b) Î f)),

(f – инъ) º (" x, y Î A ($ z Î B ((x; z) Î f Ù (y; z) Î f) ® x = y)).

Условие бесконечности множества А можно теперь записать в виде формулы, последовательно подставив все приведённые фрагменты в самую первую из квазиформул. Взяв отрицание этой формулы, получим в виде формулы условие конечности множества А.

Упражнение. Совпадает ли введённое новое понятие конечного множества с прежним понятием конечного множества {a₁ , … , a_n} ?

Теперь можно выделить “натуральные числа” из бесконечного множества N . Для этого запишем квазиформулу, задающую “натуральные числа”:

Nat(y) = (Ord(y) Ù (" zÎ y (z = Æ Ú ($ t z = t È {t}))) Ù (y – конечно))

и снова воспользуемся аксиомой существования области значений для формулы Ф(х, у) = = (у Î х Ù Nat(у)), чтобы получить множество N всех “натуральных чисел”, принадлежащих бесконечному множеству N. При этом элементы Æ , Æ È {Æ}, Æ È {Æ} È {Æ È {Æ}}, … множества N в дальнейшем обозначаем через 1, 2, 3, … , отождествляя их с “обычными” натуральными числами.

Упражнения. 1.Докажите, что для любого конечного множества А и произвольного объекта b множество A È {b} конечно. Выведите отсюда, что для любого n Î N множество {a₁ , … , a_n } конечно.

3.Докажите бесконечность построенного множества N.

4.Докажите, что множество, содержащее бесконечное подмножество, само бесконечно.

5.Докажите, что N, Z и Q равномощны, как равномощны R и R´R.

6.Проверьте условие функциональности для Ф(х,у) = у Î х Ù Nat(у) .

7.Докажите, что множество N = {n Î N | Nat(n)} является ординалом и что это – первый бесконечный ординал (обозначаемый обычно через w), в котором содержатся все конечные ординалы Æ , Æ È {Æ}, Æ È {Æ} È {Æ È {Æ}} , … .

Может возникнуть резонный вопрос: откуда такие определения конечных и бесконечных множеств ? Докажем неформально следующую теорему:

Теорема (об эквивалентных понятиях конечности (бесконечности) множеств).Следующие условия эквивалентны:

(1) либо А = Æ , либо A = {a₁ , … , a_n },

(2) A не содержит последовательности {x_i}_{i Î N} со свойством x_i ¹ x_j при i ¹ j,

(3) A конечно.

Эквивалентны и следующие условия:

(1¢) А ¹ Æ и не представимо в виде А = {a₁ , … , a_n },

(2¢) A содержит последовательность {x_i}_{i Î N} со свойством x_i ¹ x_j при i ¹ j,

(3¢) А бесконечно.

Доказательство. Прежде всего, отметим, что если множество A бесконечно, т.е. существует биекция f : A ® B на собственное подмножество Æ ¹ B ¹ A, то множество B тоже бесконечно. Действительно, отображение f можно рассматривать как отображение на свой образ: f : B ® f(B) = {c Î B | $ b Î B c = f(b)}. Проверим, что f(B) – собственное подмножество в B. Ясно, что Æ ¹ f(B) Í B. Если f(B) = B и a Î A \ B, то f(a) Î B и найдётся b Î B со свойством f(b) = f(a), откуда ввиду инъективности f получим a = b Î B, что невозможно.

(1) Þ (2) Для А = Æ утверждение (2) очевидно. Если A = {a₁ , … , a_n }, то " x Î A (x = a₁) Ú (x = a₂ ) Ú … Ú (x = a_n). Поэтому существование последовательности {x_i}_{i Î N}со свойством x_i ¹ x_j при i ¹ j приводит к противоречию: среди первых её n членов содержатся все элементы множества A.

(2) Þ (3) Пусть A не содержит последовательности элементов {x_i}_{i Î N}со свойством x_i ¹ x_j при i ¹ j. Если А не конечно, то оно бесконечно, т.е. равномощно своему собственному подмножеству B. Приведём это предположение к противоречию. В частности, A ¹ Æ, т.к. Æ ¹ A \ B Í A. Выберем элемент x₁ Î A. Предположим, что уже построено множество {x₁ , … , x_k } попарно различных элементов множества А.

Если А ¹ {x₁ , … , x_k }, то в непустом множестве A \ {x₁ , … , x_k } можно выбрать элемент x_k+1 , который не совпадает ни с одним из элементов x₁ , … , x_k , и получить новое множество {x₁ , … , x_k , x_k+1 } попарно различных элементов. Если эта процедура продолжится сколь угодно долго, то будет построена последовательность {x_i}_{i Î N} попарно различных элементов, вопреки (2).

Значит, на некотором шаге, получим А = {x₁ , … , x_k }. Проверим, что это множество конечно, вопреки допущению о бесконечности множества А. Если существует биекция f : {x₁ , … , x_k } ® B на некоторое собственное подмножество B Ì {x₁ , … , x_k }, то B бесконечно, т.е. f(B) Ì B. Поэтому получим убывающую цепь бесконечных множеств:

{x₁ , … , x_k