Элементы дискретной математики Лекция № 1. Множества, алгебры, функции

1.1. Понятие множества и функции

Понятие множества является фундаментальным в математике и определяется, как правило, через равносильные понятия такие, как совокупность, семейство, класс, алфавит и др. Например: множество есть совокупность объединенных по некоторым признакам различных объектов, называемых элементами множества. Множество не содержит двух одинаковых элементов, мультимножество может содержать каждый элемент x в количестве m_x1, при этом говорят, что m_x – кратность элемента x в мультимножестве.

Если x – элемент множества (мультимножества) X, то говорят, что x принадлежит X, записывается: xX. В противном случае записывается: xX или x X.

Два множества X и Y равны (или не равны), запись - X=Y (XY), если состоят из одних и тех же элементов (найдется элемент одного множества, не являющийся элементом другого множества). Два мультимножества X и Y равны, если состоят из одинаковых элементов, кратности которых совпадают.

Множество, состоящее из конечного (бесконечного) числа элементов, называют конечным (бесконечным). Мультимножество конечно, если оно состоит из конечного числа элементов и кратность каждого элемента конечна.

Для описания конечного множества X, состоящего из n элементов x₁,…,x_n, часто используют запись: X={x₁,…,x_n}, порядок следования элементов несущественен.

Число n элементов конечного множества X называют мощностью или порядком множества и обозначают через X. Множество мощности n часто называют n-множеством. Для описания конечного мультимножества X, состоящего из элементов x₁,…,x_n кратности m(1),…, m(n), символически запишем:

X={x₁^[m(1)],…,x_n^[m(n)]},

Бесконечное множество X, элементы которого можно занумеровать (то есть между множеством X и натуральным рядом существует взаимно однозначное соответствие), называется счётным. Остальные бесконечные множества называются несчётными.

Кроме перечисления элементов конечного множества, для задания множества (в том числе, и бесконечного) применяют описательный способ и рекурсивный способ. Например, если N – множество всех натуральных чисел, то множество M четных натуральных чисел можно описать так: M={iN: i делится на 2 без остатка}, или

M={2i: iN},

или M задаётся рекурсивным способом:

M={iN: 2M, и если iM, то i+2M}.

Если каждый элемент множества Y является элементом множества X, то Y называется подмножеством множества X, обозначается YX. При этом говорят, что множество X содержит (включает) множество Y или множество Y содержится во множестве X (включается во множество X). В соответствии с определением YX. Если при этом YX, то Y называется собственным подмножеством X (обозначается YX), при этом Y<X.

Множество, не содержащее элементов, называется пустым и обозначается через . Считается, что  является подмножеством любого множества и  =0.

Однозначным отображением f (далее – отображением) множества X в множество Y или функцией f (обозначается f:XY) называется соответствие, определяющее для каждого элемента xX единственный элемент yY. При этом записывается: f(x)=y. Множество X называется областью определения функции f, множество Y - областью значений функции f. Если xX, yY и f(x)=y, то элемент y называется образом элемента x относительно функции f, а элемент x называется прообразом элемента y относительно функции f.

Для подмножества Y множества X обозначим: f(Y)={f(x):xY} - образ множества Y относительно f. Полным прообразом элемента y относительно f называют множество всех прообразов элемента y (обозначается f^{-1}(y)).

Если X,Y - конечные множества, то функцию f:XY можно задать таблицей, под которой понимается множество пар {(x,f(x)):xX}, упорядоченных некоторым образом. Пару (x,f(x)) назовем элементом таблицы функции f.

Функции f,:XY равны, если совпадают их области определения, области значений и таблицы, то есть f(x)=(x) для любого xX. Функция :XY называется ограничением (или подфункцией) функции f на множестве X, где XX, если f(x)=(x) для любого xX. Функции f и  равны  равны ограничения этих функций на любом подмножестве множества X.

Функция f:XY называется взаимно однозначным соответствием или биекцией, если каждому элементу yY соответствует единственный элемент xX такой, что f(x)=y; при этом записывается: f:XY.

Биекция f является обратимой функцией, то есть имеется функция :YX со свойством:

f((x))=(f(x))=x

для любого xX. Такая функция  называется обратной к функции f и обозначается f^-1. Понятия биекции и обратимой функции тождественны.

Функция f:XX называется преобразованием множества X. Преобразование е:XX называют тождественным, если е(x)=x для любого xX.