Соответствие : Соответствием между множествами А и В называется некоторое подмножество 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 называется сюръективной, если для любого элементам y∈Y существует
элемент x ∈ X такой, что у = f(х).
Функция f называется биективной, если f одновременно сюръективна и инъективна. Если существует биективная функция f: Х→Y, то говорят, что f осуществляет
взаимно-однозначное соответствие между множествами Х и Y.
Суперпозиция бинарных отношений
Если f: Х→Y, а g: Y→Z, то функция F: X→Z, определенная для каждого x∈X формулой F(х) = g(f(х)), называется композицией (суперпозицией) функции f и g, или сложной функцией.
Обратная функция
Для произвольных A⊆X, B⊆Y определим f(А) = {y∈Y: существует такое 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).
