Отображения и соответствия

1. Понятие отображения. Отображение f множества X в множество Y считается заданным, если каждому элементу x из X сопоставлен ровно один элемент y из Y, обозначаемый f(x).

Множество X называется областью определения отображения f, а множество Y – областью значений. Множество упорядоченных пар

Г_f = {(x, y) | x∈X, y∈Y, y = f(x)}

называют графиком отображения f. Непосредственно из определения вытекает, что график отображения f является подмножеством декартова произведения X×Y:

Г_f ⊂ X×Y.

Строго говоря, отображение – это тройка множеств (X, Y, G) такая, что G⊂ X×Y, и каждый элемент x из X является первым элементом ровно одной пары (x, y) из G. Обозначая второй элемент такой пары через f(x), получаем отображение f множества X в множество Y. При этом G=Г_f. Если y=f(x), мы будем писать f:x→y и говорить, что элемент x переходит или отображается в элемент y; элемент f(x) называется образом элемента x относительно отображения f. Для обозначения отображений мы будем использовать записи вида f: X→Y. Часто отображения задают равенством вида y=f(x), где x и y – переменные; значениями переменной x, называемой аргументом, служат элементы множества X; переменная y принимает свои значения в множестве Y. В этом случае отображения называют также функциями.

Примеры. 1) Пусть X = Y – множество действительных чисел. Формула y=2x задает отображение множества X в множество Y.

2) Пусть X – множество всех треугольников на плоскости, а Y – множество действительных чисел. Сопоставляя треугольнику его площадь, получаем отображение первого множества во второе.

3) Пусть X = {1, 2, 3}, Y = {2, 3, 4}. Множество пар

G = {(1, 2), (2, 2), (3, 3)}

задает отображение f, при котором f(1)=f(2)=2, f(3)=3.􀀀

Отображение f конечного множества X = {a, b, …, c} в себя часто бывает удобно задать с помощью таблицы (матрицы), состоящей из двух строк. В первой строке располагаются элементы множества X, а под ними, во второй строке – их образы:

Например, таблица

задает отображение множества четвертей координатной плоскости в себя при повороте плоскости на 90º против часовой стрелки вокруг начала координат (естественно, вместо самих четвертей мы используем их номера). Пусть f: X→Y – отображение множества X в множество Y, а A и B – подмножества множеств X и Y соответственно. Множество

f(A)={y| y=f(x) для некоторого x∈A}

называется образом множества A. Множество

f ⁻¹(B)={x| f(x) ∈B}

называется прообразом множества B. Отображение f: A→Y, при котором x→f(x) для всех x∈A, называется сужением отображения f на множество A; сужение будет обозначаться через f|_A.

Отображение вида f:X×Y→Z называют функцией двух переменных и пишут z=f(x,y). Аналогично определяются функции большего числа переменных.

Пусть имеются отображения f: X→Y и g: Y→Z. Отображение X→Z, при котором x переходит в g(f(x)), называется композицией отображений f и g и обозначается через f⋅g или просто fg. Таким образом,

(fg)(x)=g(f(x)).

Например, если отображения f, g множества действительных чисел в себя заданы формулами

f(x)=x+1, g(x)=2x,

то

(fg)(x)=g(f(x))=g(x+1)=2(x+1);

(gf)(x)=f(g(x))=f(2x)=2x+1.

2. Специальные виды отображений. Отображение множества X в X, при котором каждый элемент переходит сам в себя, x→x, называется тождественным и обозначается через id_X.

Для произвольного отображения f: X→Y имеем

id_X ⋅f = f⋅id_Y.

Отображение f: X→Y называется инъективным, если образы различных элементов также различны, то есть f(x)≠f(y) при x≠y. Отображение f: X→Y называется сюръективным (говорят также, что f – отображение X на Y) если всякий элемент y из Y является образом некоторого элемента x из X, то есть f(X)=Y. Отображение f: X→Y называется биективным, если оно одновременно инъективно и сюръективно. Биективное отображение f: X→Y обратимо. Это означает, что существует отображение g: Y→X, называемое обратным к отображению f, такое, что

g(f(x))=x и f(g(y))=y

для любых x∈X, y∈Y.Ясно, что при этом отображение f является обратным к отображению g. Отображение, обратное к отображению f, обозначается через f ⁻¹. В соответствие с определением

f f ⁻¹=id_X, f ⁻¹f=id_Y, (f ⁻¹)⁻¹=f.

Нетрудно видеть, что отображение биективно тогда и только тогда, когда оно обратимо. Говорят, что обратимое отображение f: X→Y устанавливает взаимно однозначное соответствие между элементами множеств X и Y, или, короче, между множествами X и Y. Инъективное отображение f: X→Y устанавливает взаимно однозначное соответствие между множеством X и множеством f(X).

Примеры. 1) Функция f: R → R _>0, f(x)=e^x, устанавливает взаимно однозначное соответствие множества всех действительных чисел R с множеством положительных действительных чисел R _>0. Обратным к отображению f является отображение g: R _>0→ R, g(x)=ln x.

2) Отображение f: R → R _≥0, f(x)=x², множества всех действительных R на множество неотрицательных чисел R _≥0 сюръективно, но не инъективно, и поэтому не является биективным.􀀀

3. Операции. Бинарной операцией на множестве X называется отображение f:X×X→X. Результат применения бинарной операции к паре (x,y) принято записывать в виде x∗y, где ∗ – символ операции. Таким образом, f: (x,y)→x∗y.

Примеры. Отображение f: R × R → R, f(x,y) = x+y, – это операция сложения на множестве действительных чисел; f:2^X×2^X→2^X, f(A,B) = A∩B – операция пересечения на множестве подмножеств множества X.􀀀

Бинарная операция ∗ на множестве X называется:

коммутативной, если x∗y = y∗x для всех x, y из X;

ассоциативной, если (x∗y)∗z = x∗(y∗z) для всех x, y, z из X.

При записи повторенной несколько раз ассоциативной бинарной операции скобки можно опускать – результат от порядка выполнения операций не зависит. Например,

((x∗y)∗z)∗t = (x∗(y∗z))∗t = x∗((y∗z) ∗t) = x∗(y∗(z∗t)).

Операции сложения и умножения на множестве действительных чисел коммутативны и ассоциативны; операции объединения и пересечения подмножеств универсального множества также коммутативны и ассоциативны. Рассмотрим не столь очевидный пример.

Пример. Зададим бинарную операцию на отрезке [0; 1] формулой

x∗y = x+y–xy.

Очевидно, так определенная операция коммутативна. Покажем, что она и ассоциативна. Имеем

(x∗y)∗z = (x+y–xy))∗z = x+y–xy+z–(x+y–xy)z = x+y+z–xy–xz–yz+xyz;

x∗(y∗z) = x∗(y+z–yz) = x+y+z–yz–x(y+z–yz) = x+y+z–xy–xz–yz+xyz,

откуда (x∗y)∗z= x∗(y∗z).􀀀

Бинарная операция на конечном множестве может быть задана с помощью таблицы.

Пример. Зададим на множестве X={0, 1, 2, 3, 4} операцию «умножение по модулю 5» (остаток при делении произведения на 5):

Верхняя строка и левый столбец содержат элементы множества X, которые служат метками соответствующих столбцов и строк. На пересечении строки с меткой x и столбца с меткой y находится произведение xy по модулю 5. Например, произведение 2 на 3 по модулю 5 равно 1.

y находится произведение xy по модулю 5. Например, произведение 2 на 3 по модулю 5 равно 1.􀀀

4. Характеристические функции. Пусть X – некоторое множество, и A – его подмножество. Определим отображение χ_A множества X в двухэлементное множество {0,1} следующим образом: χ_A(x)=1, если x∈A, и χ_A(x)=0, если x∉A. Функция χ_A называется характеристической функцией подмножества A.

Очевидно, A⊂B тогда и только тогда, когда χ_A(x)≤χ_B(x) для всех x. Имеется простая связь между операциями над подмножествами множества X и операциями над их характеристическими функциями:

χ_A∩B(x) = min(χ_A(x), χ_B(x)) = χ_A(x)⋅χ_B(x);

χ_A∪B(x) = max(χ_A(x), χ_B(x)) = χ_A(x)+χ_B(x)−χ_A(x)⋅χ_B(x);

χ_A\B(x) = max(χ_A(x)−χ_B(x), 0) = χ_A(x)⋅(1−χ_B(x));

χ_X(x)≡1; χ(x)≡0. ∅

5. Соответствия. Пусть даны множества X и Y. Будем говорить, что задано соответствие R из X в Y, если для каждого элемента x множества X указано подмножество R(x)⊂Y соответствующих ему элементов множества Y (возможно, пустое). Множество элементов x из X, для которых R(x) не пусто, будем называть областью определения соответствия R и обозначать через D(R). Множество всех тех элементов y из Y, которые принадлежат хотя бы одному множеству R(x), будем называть полным образом соответствия R и обозначать через B(R). Более общо, для произвольного A⊂X будем обозначать через R(A) и называть образом множества A множество всех тех y∈Y, которые принадлежат хотя бы одному множеству R(x) с x∈X, то есть R(A)= ∪_x∈AR(x). Полный образ соответствия R совпадает с образом множества X. Нетрудно видеть, что B(R)=R(X)=R(D(R)).

Понятие соответствия обобщает понятие функции. Если каждое множество R(x) содержит ровно один элемент, то соответствие R называется функциональным. Всякое функциональное соответствие R определяет отображение множества X в множество Y, при котором произвольному элементу x множества X соответствует единственный элемент множества R(x). Ясно, что R является графиком этого отображения. Допуская небольшую вольность, будем обозначать это отображение также через R.

Примеры. 1) Натуральному числу x поставим в соответствие совокупность его простых делителей. Тем самым определяется соответствие R из множества натуральных чисел в множество простых чисел. Имеем R(10)={2, 5}, R(30)={2, 3, 5}, R(7)={7}, R(1)=∅.

2) Пусть A – множество участников рынка, а T – множество товаров. Для каждого товара t указана его цена p, для каждого участника ранка a – его бюджет b. Назовем возможным планом потребления участника рынка набор товаров, суммарная стоимость которых не превосходит его бюджета. Сопоставим каждому участнику рынка a множество возможных планов потребления. Этим определяется соответствие R из A в множество всех подмножеств множества Т. Например, пусть T={t₀, t₁, t₂, t₃}, p₀=–2, p₁=1, p₂=2, p₃=3 (отрицательную цену имеет товар, который может быть продан на рынке, например, труд); A={a₁, a₂, a₃}, b₁=0, b₂=2, b₃=10. Тогда

R(a₁)={{t₀}, {t₀, t₁}, {t₀, t₂}},

R(a₂)={{t₀}, {t₁}, {t₂}, {t₀, t₁}, {t₀, t₂}, {t₀, t₃}, {t₀, t₁, t₂}, {t₀, t₃}}, R(a₃)=2^T.􀀀

Формально соответствие R из множества X в множество Y можно определить как подмножество декартова произведения X×Y, считая, что (x,y)∈R, если y∈R(x).

Рассматривая соответствия из X в Y как подмножества множества X×Y, можно говорить о том, что одно соответствие является частью другого, можно образовывать пересечение и объединение соответствий и т. п. Пусть S, R⊂X×Y – пара соответствий из X в Y. Непосредственно из определений вытекают следующие свойства соответствий:

1) S⊂R в том и только том случае, если S(x) ⊂R(x) для всех x∈R;

2) (S∩R)(x)=S(x) ∩R(x);

3) (S∪R)(x)=S(x) ∪R(x).

Пусть R⊂X×Y – соответствие из X в Y.

Сужением соответствия R на подмножество X’⊂X называется соответствие R’=R∩X’×Y. Легко видеть, что D(R’)=X’∩D(R) и R’(x)=R(x) для любого x∈X. Сужение будет иногда обозначаться через R|_X’.

Соответствие из Y в X, определяемое формулой

R^–1={(y,x)|(x,y)∈R},

называется обратным к соответствию R. Очевидно, x∈ R^–1(y) тогда и только тогда, когда y∈ R(x). Непосредственно из определений следует, что (R^–1)^–1=R; D(R^–1)= B(R); B(R^–1)=D(R).

Если соответствие R⊂X×Y функционально, то обратное соответствие R^–1 окажется функциональным лишь в том случае, когда отображение, задаваемое соответствием R, биективно; обратное соответствие задает в этом случае обратное отображение.

Для произвольного множества X обозначим через E_X соответствие, определяющее тождественное отображение множества X в себя, при этом соответствии каждому элементу множества X соответствует лишь сам этот элемент, то есть E_X(x)={x}. Соответствие E_X задается диагональю декартова квадрата множества X:

E_X = {(x,x) | x∈X} ⊂ X×X.

Мы будем называть соответствие E_X тождественным или диагональным.

6. Композиция соответствий. Пусть заданы соответствия R из X в Y и S из Y в Z. Их композицией (или произведением) называется соответствие P из X в Z такое, что P(x)=S(R(x)) для всех x из X. Композиция соответствий R и S обозначается через RS. Согласно определению имеем

RS = {(x,z) | существует y∈Y, для которого (x,y)∈R и (y,z)∈S}.

Если X=Y=Z и R=S, то вместо RR пишут R², вместо (R²)R – (R³) и т.д.

Пример. Пусть T – множество наборов товаров такое же, как в примере из предыдущего пункта. Будем считать, что набор товаров улучшается, если к нему добавляется один из товаров с положительной ценой или из него выводится товар с отрицательной ценой. Будем говорить, что набор товаров V лучше, чем набор товаров U, если V может быть получен из U несколькими последовательными улучшениями. Например, наборы {t₀,t₁}, {t₀,t₁,t₂}, {t₁,t₂} получаются последовательными улучшениям. Обозначим через P(U) множество тех наборов, которые получаются из набора U путем его однократного улучшения. Например, P({t₀,t₁})={{t₀,t₁,t₂}, {t₀,t₁,t₃}, {t₁}}; P({t₁,t₂,t₃})=∅. Тогда P²(U) – это множество наборов, которые получаются из U двумя последовательными улучшениями, P³(U) – это множество наборов, которые получаются из U тремя последовательными улучшениями и т.д. Очевидно, P⁵(U)= ∅ для любого набора U. Положим S=P∪P²∪P³∪P⁴. Тогда S(U) – это множество наборов, которые лучше, чем набор U.􀀀

Укажем некоторые свойства композиции соответствий.

1) Диагональные соответствия играют роль единиц: для любого R⊂X×Y имеем

E_XR=R=RE_Y.

2) Композиция ассоциативна: если R⊂X×Y, S⊂Y×Z, T⊂Z×W, то

(RS)T=R(ST).

3) Если R⊂X×Y, S⊂Y×Z, то

(RS)⁻¹=S⁻¹R⁻¹.

4) Композиция монотонна относительно включения: если R₁, R₂⊂X×Y, S⊂Y×Z, то

R₁⊂ R₂ влечет R₁S⊂ R₂S.

5) Если R₁, R₂⊂X×Y, S⊂Y×Z, то

(R₁∪R₂)S=R₁S∪R₂S.

Замечание. Аналог свойства 5 для пересечений, вообще говоря, неверен. Включение

(R₁∩R₂)S⊂R₁S∩R₂S

имеет место всегда, однако оно может оказаться строгим. Например, пусть

X=Y={1, 2}, Z={1};

R₁={(1,1), (2,2)},

R₂={(1,2), (2,1)},

S={(1,1), (2,1)}.

Тогда R₁∩R₂=∅, так что (R₁∩R₂)S=∅. С другой стороны, R₁S=S и R₂S=S, откуда R₁S∩R₂S=S.􀀀

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

Теорема. Соответствие R из множества X в множество Y функционально тогда и только тогда, когда выполняются следующие соотношения:

RR⁻¹⊃E_X , R⁻¹R⊂E_Y.

Доказательство. Предположим сначала, что соответствие R функционально. Тогда R состоит из пар вида (x,f(x)), x∈X, где f – отображение из X в Y. Для любого x∈X имеем (x,f(x))∈R и (f(x),x)∈R⁻¹, и, значит, (x,x)∈RR⁻¹. Этим доказывается первое включение. Для доказательства второго достаточно показать, что (y,y’)∈R⁻¹R лишь в том случае, когда y=y’. В самом деле, если (y,y’)∈R⁻¹R, то найдется x∈X такой, что (y,x)∈R⁻¹ и (x,y’)∈R. Эти два условия означают соответственно, что y=f(x) и y’=f(x), откуда y=y’. Обратно, предположим, что выполняются соотношения из формулировки теоремы и покажем, что R функционально. Из RR⁻¹⊃E_X вытекает, что для произвольного x∈X найдется такой y∈Y, что (x,y)∈R и (y,x)∈R⁻¹. Значит, y∈R(x) и R(x)≠∅. Следовательно, R определено на всем X, то есть D(R)=X. Далее, пусть (x,y)∈R и (x,y’)∈R. Тогда (y,x)∈R⁻¹ и, значит, (y,y’)∈R⁻¹R. Поскольку R⁻¹R⊂E_Y, отсюда следует, что y=y’.􀀀

Замечание. Из доказательства теоремы видно, что условие RR⁻¹⊃E_X равносильно тому, что R определено на всем X. Условие R⁻¹R⊂E_Y означает, что R(x) состоит ровно из одного элемента для каждого x∈D(R), то есть сужение R на D(R) – функциональное соответствие. Про соответствие R, удовлетворяющее условию RR⁻¹⊃E_X , будем говорить, что оно всюду определено, а про соответствие R, удовлетворяющее условию R⁻¹R⊂E_Y, – что оно является частичным отображением (частичной функцией) и отображает D(R) в Y.

Отношения

1. Понятие отношения. Подмножество R⊂Xⁿ называется n-местным или n-арным отношением на множестве X. Говорят, что элементы x₁, x₂, …, x_n (в указанном порядке) связаны отношением R или находятся в отношении R, если (x₁, x₂, …, x_n)∈R. Наиболее часто в приложениях используются двухместные, или бинарные отношения, которые в основном и будут изучаться в дальнейшем. Иногда используются и другие отношения. При n=1 отношение называется унарным. Унарное отношение на множестве X – это просто некоторое подмножество R множества X. Унарное отношение можно трактовать как свойство: элемент x∈X обладает свойством R, если x∈R. При n=3 отношение называется тернарным. В качестве примера приведем отношение R на множестве действительных чисел, которое содержит все тройки чисел (x₁, x₂, x₃) такие, что x₃=x₁+x₂. Например, (1, 2, 3)∈R, (2, 3, 4)∉R.

По определению бинарное отношение R на множестве X – это подмножество декартова произведения X×X. Бинарное отношение можно рассматривать как соответствие из X в X. Тем самым для бинарных отношений на множестве X определены булевы операции (объединение, пересечение и др.), операция композиции, обращение. Диагональное соответствие E_X отвечает отношению равенства:

E_X = {(x, x) | x∈X} = {(x,y)| x=y, x,y∈X } ⊂ X×X.

Если x и y связаны отношением R, то часто вместо (x,y)∈R пишут xRy. Например, для отношения «равно» и отношения «меньше» на множестве действительных чисел вместо (x,y)∈= и (x,y)∈< принято писать соответственно x=y и x<y. Эти два отношения являются примерами двух важнейших классов бинарных отношений – отношений эквивалентности и отношений порядка.

2. Свойства бинарных отношений. Пусть R⊂X×X – бинарное отношение на множестве X (мы будем далее опускать слово «бинарное», когда это не ведет к недоразумениям).

Отношение R называется рефлексивным, если оно содержит все пары вида (x,x), то есть xRx для любого x из X. Отношение R называется антирефлексивным, если оно не содержит ни одной пары вида (x,x). Например, отношение x≤y рефлексивно, а отношение x<y антирефлексивно. Рефлексивное отношение на множестве действительных чисел изображается на координатной плоскости множеством точек, содержащим прямую y=x. В общем случае рефлексивность отношения R означает, что R⊃E_X, а антирефлексивность – что R∩E_X=∅.

Отношение R называется симметричным, если вместе с каждой парой (x,y) оно содержит также и пару (y,x), то есть xRy выполняется тогда и только тогда, когда выполняется yRx. Отношение R симметрично, если наличие (или отсутствие) связи между элементами x и y не зависит от порядка, в котором указаны эти элементы. Например, отношение x+y>0 симметрично, а отношение x+2y>0 – нет (симметричное отношение на множестве действительных чисел изображается на координатной плоскости множеством точек, симметричным относительно прямой y=x). Симметричность отношения R означает, что R=R^–1.

Отношение R называется асимметричным, если невозможно одновременное выполнение условий xRy и yRx. Например, отношение x<y асимметрично. Асимметричность отношения R означает, что R∩R^–1=∅. Отношение R называется антисимметричным, если одновременное выполнение условий xRy и yRx невозможно при x≠y, то есть, если xRy и yRx, то x=y. Например, отношение x≤y антисимметрично. Антисимметричность отношения R означает, что R∩R^–1⊂E_X. Ясно, что всякое асимметричное отношение является антисимметричным и антирефлексивным.

Отношение R называется транзитивным, если вместе с любыми парами (x,y) и (y,z) оно содержит также и пару (x,z), то есть из xRy и yRz следует xRz. Например, отношение x<y транзитивно, а отношение x+y>0 – нет. Транзитивность отношения R означает, что R²⊂R. Приведем некоторые свойства отношений, которые непосредственно вытекают из определений.

Каково бы ни было отношение R, отношение R∪E_X рефлексивно.

Каково бы ни было отношение R, отношения R∩R^–1 и R∪R^–1 симметричны.

Если отношение R рефлексивно и транзитивно, то R²=R.

Докажем последнее утверждение.

Доказательство. Поскольку R транзитивно, имеем R²⊂R. Обратно, так как R рефлексивно, то E_X⊂R, откуда, умножая на R, получаем R=RE_X⊂R².􀀀

Примеры. Рассмотрим несколько отношений на множестве всех подмножеств некоторого множества U. Отношение включения X⊂Y рефлексивно, антисимметрично и транзитивно. Отношение строго включения X⊂Y, X≠Y, асимметрично и транзитивно. Пусть R – отношение, которое связывает множества X и Y, имеющие непустое пересечение, X∩Y≠∅. Это отношение симметрично, но, вообще говоря, не транзитивно (транзитивным оно окажется лишь в том случае, когда множество U состоит из одного элемента). Отношение R не рефлексивно; рефлексивным является его сужение на множество непустых подмножеств множества U.􀀀

3. Отношения эквивалентности. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. Таким образом, R⊂X×X – отношение эквивалентности на множестве X, если

R⊃E_X , R^–1=R и R²=R.

Простейшим примером отношения эквивалентности на множестве X может служить отношение равенства E_X. Для обозначения отношений эквивалентности принято использовать символ ~.

Рассмотрим несколько примеров.

Примеры. 1) Пусть X – множество функций, определенных на всей числовой прямой. Будем считать, что функции f и g связаны отношением ~, если они принимают одинаковые значения в точке 0, то есть f(x)~g(x), если f(0)=g(0). Например, sinx~x, e^x~cosx. Отношение ~ рефлексивно (f(0)=f(0) для любой функции f(x)); симметрично (из f(0)=g(0) следует, что g(0)=f(0)); транзитивно (если f(0)=g(0) и g(0)=h(0), то f(0)=h(0)). Следовательно, ~ является отношением эквивалентности.

2) Пусть ~ – отношение на множестве натуральных чисел, при котором x~y, если x и y дают одинаковые остатки при делении на 5. Например, 6~11, 2~7, 1~6. Легко видеть, что это отношение рефлексивно, симметрично и транзитивно и, значит, является отношением эквивалентности.􀀀

Следующая теорема описывает в общем виде типичную ситуацию, в которой возникают отношения эквивалентности.

Теорема. Пусть ϕ – отображение множества X в некоторое множество Y. Определим отношение ~ на X, полагая x~y, если ϕ(x)=ϕ(y). Тогда отношение ~ является отношением эквивалентности.

Доказательство. Достаточно заметить, что отношение ~ рефлексивно, поскольку ϕ(x) = ϕ(x) для любого x, симметрично, поскольку ϕ(x)=ϕ(y) влечет ϕ(y)=ϕ(x), и транзитивно, поскольку из ϕ(x)= ϕ(y) и ϕ(y)=ϕ(z) следует, что ϕ(x)=ϕ(z).􀀀

Про отношение эквивалентности, описанное в предыдущей теореме, будем говорить, что оно порождается отображением ϕ. Будем обозначать это отношение эквивалентности через ~_ϕ или просто через ~, когда ясно, о каком отображении идет речь. Далее мы увидим, что всякое отношение эквивалентности может быть представлено как ~_ϕ для подходящего отображения.

Теорема применима к обоим рассмотренным перед ней примерам. В первом примере в качестве Y можно взять множество действительных чисел, а отображение ϕ определить на множестве функций соответствием ϕ:f→f(0). Во втором примере в качестве ϕ(x) можно взять остаток от деления x на 5.

Отображение ϕ порождает разбиение множества X на классы, содержащие элементы, имеющие одинаковый образ, то есть эквивалентные относительно ~_ϕ. Описываемая ниже конструкция устанавливает взаимно однозначное соответствие между отношениями эквивалентности на множестве X и его разбиениями в общем случае. Будем говорить, что дано разбиение множества X, если задано семейство его непустых подмножеств, такое, что два различных подмножества из этого семейства не пересекаются, а объединение всех подмножеств есть X.

Всякому разбиению множества X отвечает отношение эквивалентности, задаваемое следующим образом: x~y в том и только том случае, когда x и y содержатся в одном общем подмножестве из разбиения.

Опишем теперь обратное построение.

Пусть ~ отношение эквивалентности на X. Для произвольного элемента x∈X обозначим через A_x множество всех элементов, эквивалентных x, то есть

A_x={y | y~x}.

Множества вида A_x называются классами эквивалентности. Так как x~x, то x∈A_x, так что классы эквивалентности непусты, и их объединение дает все множество X. Покажем, что различные классы эквивалентности не пересекаются. Предположим, что A_x∩A_y≠∅, и покажем, что в этом случае A_x=A_y. Пусть z∈A_x∩A_y. Тогда z~x и z~y. Так как отношение эквивалентности симметрично, то y~z. Теперь из y~z и z~x в силу транзитивности следует y~x, так что y∈A_x. Пусть z – произвольный элемент из A_y. Тогда z~y. Так как y~x, отсюда по транзитивности следует, что z~x, то есть z∈A_x. Таким образом, A_x⊂A_y. Аналогично A_y⊂A_x. Замечание. Соответствие x→A_x задает отображение ϕ:X→2^X множества X в множество его подмножеств 2^X. При этом ϕ(x)=ϕ(y) тогда и только тогда, когда A_x=A_y, то есть когда x~y. Значит, ~ = ~_ϕ.Таким образом, произвольное отношение эквивалентности на множестве X порождается некоторым отображением.􀀀

Натуральные числа

1. Натуральный ряд. Под натуральным рядом понимают последовательность чисел

0, 1, 2, 3, ….

В современной математике существование натурального ряда является одним из базовых постулатов. Постулируется существование множества N, удовлетворяющего определенным условиям – аксиомам натурального ряда.

Натуральный ряд – это множество N вместе с отображением непосредственного следования s: N → N, s(x)=x’, удовлетворяющие следующим условиям (аксиомам).

1) Множество N содержит элемент, обозначаемый через 0, который не следует ни за каким элементом: 0∈ N и 0≠x’ каков бы ни был элемент x∈ N.

2) Отображение непосредственного следования инъективно: если x’=y’, то x=y.

3) Аксиома индукции: единственное подмножество множества N, которое, во-первых, содержит 0 и, во-вторых, вместе с каждым элементом x содержит непосредственно следующий за ним элемент x’, – это само множество N.

Из первых двух условий следует, что последовательность

0, 0’, 0’’, 0’’’ …

не содержит повторяющихся элементов. В самом деле, если, например, 0’’=0’’’’, то, по аксиоме 2, 0’=0’’’ и 0=0’’, что противоречит аксиоме 1. Аксиома индукции говорит о том, что элементами этой последовательности исчерпывается все множество N. Таким образом, повторяя отображение s, можно, начав с 0, добраться до произвольного x∈ N за конечное число шагов. Используя привычные обозначения 0’=1, 0’’=2, 0’’’=3, …, получаем

N = {0, 1, 2, 3, …}.

2. Метод математической индукции. Многие математические доказательства основываются на аксиоме индукции, которую можно переформулировать следующим образом.

Принцип полной индукции. Пусть P – утверждение относительно натуральных чисел n такое, что

1) P верно для n=0;

2) из справедливости P для n=k следует справедливость P для n=k+1.

Тогда P верно для всех натуральных чисел.

Замечание. Чтобы показать, что эта формулировка следует из предыдущей, достаточно рассмотреть множество A={x∈ N | P верно для x}.

Для доказательства в обратную сторону, множеству A⊂ N можно сопоставить свойство P «быть элементом множества A».􀀀

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

•устанавливается справедливость P для n=0 (посылка индукции);

•предполагается, что P справедливо для некоторого произвольного, но фиксированного n=k (индуктивное предположение);

•доказывается, что из индуктивного предположения, следует, что P верно для n=k+1 (индуктивный шаг).

Примеры. Проведем два доказательства методом математической индукции.

1) Сумма первых натуральных чисел от 0 до n включительно равна 0,5n(n+1):

0+1+…+n = 0,5n(n+1).

Доказательство. Утверждение верно при n=0: имеем 0=0,5⋅0⋅(0+1) (посылка индукции).

Предположим, что доказываемое утверждение верно для n=k (индуктивное предположение), то есть

0+1+…+k = 0,5k(k+1). Покажем, что тогда оно верно и для n=k+1, то есть

0+1+…+k+(k+1) = 0,5(k+1)(k+2)

(индуктивный шаг). Сумма во втором равенстве отличается от суммы из первого равенства слагаемым k+1. Поэтому, в силу индуктивного предположения, получаем

0+1+…+k+(k+1) = 0,5k(k+1)+k+1 = 0,5(k+1)(k+2),

что и требовалось доказать.

В соответствии с принципом математической индукции, доказываемое утверждение верно для всех n.

2) Число подмножеств множества, содержащего n элементов, равно 2ⁿ.

Доказательство. Утверждение верно при n=0: пустое множество ∅ (единственное множество, содержащее 0 элементов) имеет ровно одно подмножество ∅.

Предположим теперь, что всякое множество с n=k элементами имеет 2^k подмножеств, и покажем, что множество с n=k+1 элементами имеет 2^k+1 подмножеств. Пусть A – произвольное множество с n=k+1 элементами. Так как k+1>0, то A не пусто и содержит хотя бы один элемент. Пусть a∈A. Разобьем совокупность всех подмножеств множества A на два класса. В класс U входят все подмножества, содержащие a, в класс V входят все подмножества, не содержащие a:

U={X⊂A | a∈X}; V={Y⊂A | a∉Y}. Положим A’=A\{a}. Множество A’ содержит k элементов, так что по индуктивному предположению, число его подмножеств равно 2^k. Но подмножества множества A’ – это в точности подмножества множества A, не содержащие a. Следовательно, |V|=2^k. Пара взаимно обратных отображений U→V, X→X\{a} и V→U, Y→Y∪{a} устанавливает между U и V взаимно однозначное соответствие, так что |U|=|V|=2^k. Поэтому общее число подмножеств множества A составляет

|U|+|V|=2^k +2^k =2^k+1,

что и требовалось доказать.􀀀

Иногда принцип полной индукции применяется в следующей форме.

Пусть P – утверждение относительно натуральных чисел n такое, что

1) P верно для n=n₀;

2) из справедливости P(n) для n= n₀, n₀+1, …, n₀+k следует справедливость P(n) для n= n₀+k+1.

Тогда P верно для всех n≥ n₀.

Принцип полной индукции в этой форме может быть сведен к предыдущей формулировке заменой утверждения P утверждением P’: утверждение P имеет место для всех t, таких, что n₀≤t≤n.

Возможны и другие модификации принципа полной индукции.

Теорема. Всякое непустое подмножество натурального ряда содержит наименьший элемент.

Доказательство. Пусть A⊂N – непустое подмножество. Возможны два случая: 0∈A и 0∉A. В первом случае 0 является наименьшим элементом множества A. Рассмотрим второй случай. Предположим, что в A нет наименьшего элемента. Пусть A’ – это множество всех таких n, что ни одно число t из промежутка от 0 до n не содержится в A. Так как 0∉A, то 0∈A’. Далее, если k∈A’, то и k+1∈A’. В самом деле, в противном случае мы имели бы 0,1,…,k∉A, но k+1∈A – а это означает, что k+1 – наименьший элемент множества A в противоречие с предположением об отсутствии такового. По аксиоме индукции множество A’ совпадает с N. Но это находится в противоречии с предположением о том, что множество A не пусто.􀀀

Не нашли, что искали? Воспользуйтесь поиском: