22. Отображение множеств

Соответствие /, сопоставляющее каждому элементу х множеств X один и только один элемент множества Y, называется отображением мно­жества X во множество Y.

Элемент множества Y, соответствующий при отображении f элементу х из X, обозначают Дх) и называют образом элемента х при этом отобра­жении.

Если f(x) = у, то элемент х называют прообразом элемента у при отображении /.

Совокупность всех прообразов элемента у при отображении f назы­вается полным прообразом этого элемента и обозначается f ¹(у), т. е. / ¹ = {х : Дх) = у}.

же, как и для бинарных отношений. Если область определения 8/ = X и область значений р/ С У, то говорят, что функция / задана на множестве X со значениями во множестве У, при этом / отображает множество X во множество У. Это отображение обозначается как / : X —> У.

Если / — функция, то вместо (х, у) Е / пишут у = f(x) и говорят, что у — значение, соответствующее аргументу х, или у — образ элемента х при отображении /. При этом х называют прообразом элемента у.

Назовем / — «-местной функцией из X в У, если / : Х^п —> У. Тогда записываем у = f(x\,X/,) и говорим, что у — значение функции при значении аргументов Х\, ...,х_п.

Пусть / : X —> У. Функция/называется инъективной, если для любых х_1гх₂, у ИЗ у = /(xi)h у = f(x₂) следует, что *1 = х₂.

Функция / называется сюръективной, если для любого элемента у €Е У существует элемент х е X такой, что у = f{x).

Функция / называется биективной, если / одновременно сюръективна и инъективна.

Если существует биективная функция / : X —>• У, то говорят, что / осуществляет взаимно-однозначное соответствие между множествами X и У.

Если / : X —> У, a g : У —> Z, то функция F : X ^ Z, определенная для каждого х Е X формулой F(x) = g(f(x)), называется композицией (суперпозицией) функции fug, или сложной функцией.

Пусть задана функция / : X —> У и Pf — множество ее значений. Сово­купность всевозможных упорядоченных пар вида (у, f ¹(i/)}, у Е Pf обра­зует функцию, которая называется обратной функцией для функции / и обозначается f~^l.

Обратная функция f~¹ ставит в соответствие каждому элементу у Е р/ его прообраз f~¹(y), т. е. некоторое множество элементов. Заметим, что для того, чтобы /^_1 являлась функцией, достаточно, чтобы функция / была инъективной.

23. Функции

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

Функцией называется бинарное отношение /, если из (х, у) Е / и (х, z) Е f следует, что у = z.

Две функции fug равны, если они состоят из одних и тех же элемен­тов. Область определения функции и область ее значений задается так же, как и для бинарных отношений. Если область определения 8/ = X и область значений р/ С У, то говорят, что функция / задана на множестве X со значениями во множестве У, при этом / отображает множество X во множество У. Это отображение обозначается как / : X —> У.

Если / — функция, то вместо (х, у) Е / пишут у = f(x) и говорят, что у — значение, соответствующее аргументу х, или у — образ элемента х при отображении /. При этом х называют прообразом элемента у.

Назовем / — «-местной функцией из X в У, если / : Х^п —> У. Тогда записываем у = f(x\,X/,) и говорим, что у — значение функции при значении аргументов Х\, ...,х_п.

Пусть / : X —> У. Функция/называется инъективной, если для любых х_1гх₂, у ИЗ у = /(xi)h у = f(x₂) следует, что *1 = х₂.

Функция / называется сюръективной, если для любого элемента у €Е У существует элемент х е X такой, что у = f{x).

Функция / называется биективной, если / одновременно сюръективна и инъективна.

Если существует биективная функция / : X —>• У, то говорят, что / осуществляет взаимно-однозначное соответствие между множествами X и У.

Если / : X —> У, a g : У —> Z, то функция F : X ^ Z, определенная для каждого х Е X формулой F(x) = g(f(x)), называется композицией (суперпозицией) функции fug, или сложной функцией.

Пусть задана функция / : X —> У и Pf — множество ее значений. Сово­купность всевозможных упорядоченных пар вида (у, f ¹(i/)}, у Е Pf обра­зует функцию, которая называется обратной функцией для функции / и обозначается f~^l.

Обратная функция f~¹ ставит в соответствие каждому элементу у Е р/ его прообраз f~¹(y), т. е. некоторое множество элементов. Заметим, что для того, чтобы /^_1 являлась функцией, достаточно, чтобы функция / была инъективной.