Пусть имеется два множества M и N. Отображением множества M в множество N называется соответствие с каждым элементом m множества M некоторого элемента множества N. Например, пусть у нас имеется некоторое количество игрушек и некоторое количество красок, и мы хотим все эти игрушки покрасить имеющимися красками. Для того, чтобы это сделать, нам нужно для каждой игрушки задать краску (цвет), которой мы будем её красить. При этом важно, чтобы краска (цвет) была задана для всех игрушек, поскольку нам надо раскрасить все игрушки. Но совсем не обязательно, чтобы при этом были использованы все краски, а также не обязательно, чтобы любые две игрушки были раскрашены разными красками. Это задание цвета для каждой игрушки является отображением множества игрушек в множество красок.

Отображение множества M в множество N принято обозначать так:

f: M —→ N

при этом если m - элемент множества M, то через f(m) обозначают элемент множества N, который при отображении f соответствует элементу m.

Пусть имеется два множества M и N и пусть заданы два отображения первого во второе:

f: M —→ N

g: M —→ N.

Мы говорим, что эти два отображения равны, или совпадают, если для любого элемента m множества M элементы f(m) и g(m) множества N совпадают.

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

Начнём с такой задачи:

Пусть имеется два конечных множества M и N, и пусть множество M состоит из m элементов, а множество N состоит из n элементов. Сколько существует разных отображений

f: M —→ N

множества M в множество N?

Правильный ответ: n^m, другими словами n в степени m или n*n*n* … *n – произведение m сомножителей, каждый из которых равен n.

Доказательство. Каждый элемент множества M можно отобразить в множество N n способами, поскольку в множестве N всего n элементов, и любой элемент множества M можно отобразить в любой из них. Выберем произвольный элемент a множества M, этот элемент можно отобразить в множество N ровно n способами. Выберем любой другой элемент b множества M, его тоже можно отобразить в множество N ровно n способами. Поскольку при любом выборе отображения элемента a элемент b возможно отобразить n способами, то два элемента a, b можно отобразить в множество N ровно n*n способами. Аналогично три элемента множества M можно отобразить в множество N ровно n*n*n способами. Продолжая это рассуждение, получаем, что m элементов множества M (т.е. все) можно отобразить n^m способами, что и требовалось.

Вложением множества M в множество N называется такое отображение

f: M —→ N,

при котором разные элементы множества M переходят в разные элементы множества N. Другими словами если a и b – элементы множества M и a ≠ b, то и f(a) ≠ f(b).

Пусть, как и выше, множество M состоит из m элементов, а множество N – из n элементов.

Задача: сколько имеется всего вложений множества M в множество N?

Решение. Как и в предыдущем рассуждении выберем произвольный элемент a множества M. Этот элемент можно отобразить в множество N ровно n способами. Пусть b – произвольный другой элемент множества M. Его мы можем отобразить в множество N лишь n - 1 способом, т. к. его можно отобразить в любой элемент множества N, кроме того, в который мы уже отобразили элемент a. Два элемента a, b можно отобразить n*(n - 1) способами. Продолжая это рассуждение для трёх, четырёх и т. д. элементов, получаем, что число вложений множества M в множество N равно n*(n - 1)*(n - 2)*…*(n – m + 1).

Заметим, что если m > n, то это число равно нулю, т.е. в этом случае нет ни одного вложения M в N.

Имеется широко распространённое обозначение n! = 1*2*3* … *n, словами называется n-факториал. Очевидно:

n*(n - 1)*(n - 2)*…*(n – m + 1) = n!/(n – m)!

Пусть n = m, т. е. пусть множества M и N состоят из одинакового числа элементов. В этом случае число вложений M в N равно n!.