пользователей: 21281
предметов: 10473
вопросов: 178149
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Соответствие. Функция. Инъекция, сюръекция, биекция. Обратная функция. Суперпозиция бинарных отношений. Классификация отображений. Изоморфизм. Частично упорядоченные множества.

Соответствие : Соответствием между множествами А и В называется некоторое подмножество G их декартова произведения: .

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

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

Соответствие называется полностью определённым, если , то есть каждый элемент множества  имеет хотя бы один образ во множестве ; в противном случае соответствие называется частичным.

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

Соответствие  называется функциональным (однозначным), если любому элементу множества  соответствует единственный элемент множества .

Соответствие называется инъективным, если оно является функциональным, и при этом каждый элемент множества  имеет не более одного прообраза. Соответствие  называется взаимнооднозначным (биективным), если любому элементу множества  соответствует единственный элемент множества , и наоборот. Можно сказать также, что соответствие является взаимнооднозначным, если оно является полностью определённым, сюръективным, функциональным, и при этом каждый элемент множества  имеет единственный прообраз.

 

Функция

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

Пусть Х некоторое множество на числовой оси. Говорят, что на этом множестве определена функция f, если каждому числу хХ поставлено в соответствие определенное число у=f(х). При этом множество Х называется областью определения (задания) функции f, а совокупность значений у=f(х) множество Y областью ее значений. Для наглядности

функцию у=f(х) представляют ее графиком в координатных осях хОу

Инъекция, сюръекция, биекция

При использовании термина «отображение» различают отображение Х в Y и отображение Х на Y.

В том случае, когда Х отображается на некоторое собственное подмножество Yс Y, — это отображение Х в Y.

В противном случае, т.е. когда Yс=Y, — это отображение Х на Y. Оно называется сюръекцией.

Если для любых двух различных х1, и х2 функции f(x1) и f(x2) также различны, такая функция f называется инъективной.

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

Пусть f: Х Y. Функция f называется инъективной, если для любых х1, х2, y, из у = f(x1) и у = f(x2) следует, что x1 = x2.

Функция f называется сюръективной, если для любого элементам yY существует

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

взаимно-однозначное соответствие между множествами Х и Y.

Суперпозиция бинарных отношений

Если f: ХY, а g: YZ, то функция F: XZ, определенная для каждого xX формулой F(х) = g(f(х)), называется композицией (суперпозицией) функции f и g, или сложной функцией.

Обратная функция 

Для произвольных AX, BY определим f(А) = {yY: существует такое xА, что у = f(х)} f -1(В) = { x X : f (x)B }.

Если f(А) = Y, то будем говорить о функции из Х на Y. Функция f:Х→Y называется обратимой (взаимно однозначной), если для произвольных a, b X

а ≠ b f(а) f(b).Пусть задана функция f: Х Y и сf множество ее значений. Совокупность всевозможных упорядоченных пар вида <y, f-1(y)>, y ∈ ρ f образует функцию,

которая называется обратной функцией для функции f: и обозначается f-1.
Обратная функция f-1 ставит в соответствие каждому элементу y ∈ ρ f его прообраз f-

1(y), т.е. некоторое множество элементов. Заметим, что для того, чтобы f-1 являлась функцией, достаточно, чтобы функция f была инъективной

 

Классификация отображений

Пусть X и Y - два частично упорядоченных множества.

Отображение ζ множеств X на Y есть изоморфизм (или изоморфное отображение), если оно взаимно однозначно и сохраняет порядок, то есть неравенства х ≤ у и ζ (х) ≤ ζ (у) равносильны.

Обратное отображение ζ -1 есть также изоморфизм.

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

Отображение ц называется изотопным, если неравенство х ≤ у влечет ζ (х) ≤ ζ (у). Изоморфное отображение всегда изотонно (но не наоборот!).

Взаимно однозначное отображение ω множества X на Y называется дуальным изоморфизмом, если равносильны неравенства х ≤ у и ζ (х) ≥ ζ (у). Если такое отображение существует, то говорят, что X и Y дуально изоморфны

 

Частично упорядоченные множества

Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка с

 

Частичным упорядочением (частичным порядком) в непустом множестве X называется всякое подмножество множества P X 2 , удовлетворяющее следующим аксиомам:

I. При любом x X справедливо (x, x)P - рефлексивность отношений.

II. Если (x,x)P и (y,x)P, то y = x - антисимметричность отношений.

III. Если (x,y)P и (y,z)P, то (x,z)P - транзитивность отношений.

Часто вместо записи (x,y)P пишут x y или y x . Иногда вместо знака

могут применять и другие похожие символы например p . Тогда аксиомы можно записать в виде:

I. x x при всех справедливо x X - рефлексивность отношений. II. Если x y и y x, то y = x - антисимметричность отношений. III. Если x y и y z, то x z - транзитивность отношений.
Эти соотношения называются неравенствами.

Частично упорядоченное множество это некоторое множество X вместе с заданным на нем частичным порядком P, то есть пара (X, P)


08.06.2014; 21:21
хиты: 1465
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь