Пусть M – множество и пусть Z – некоторое множество чисел, например, отрезок натурального ряда.

Отображение

f: M —→ Z

называется функцией. Т.е. функция – это отображение, значениями которого являются числа.

В частности, нумерации являются функциями.

Рассмотрим множество {0, 1}, состоящее из двух элементов 0 и 1. В этом контексте иногда 0 обозначают через Л (первая буква слова «ложь»), а 1 обозначают через И (первая буква слова «истина»).

Отображение

f: M —→ {0, 1}

называется свойством.

Зададимся вопросом, сколько всего имеется свойств множества M, если мощность множества M равна m ? Ответ на этот вопрос можно получить разными способами. Вот два.

1. Имеется естественное взаимно-однозначное соответствие между подмножествами множества M и свойствами множества M. Прежде, чем строить это взаимно-однозначное соответствие, заметим, что из его существования следует, что свойств множества M имеется ровно 2^m.

Теперь построим взаимно-однозначное соответствие. С каждым подмножеством P множества M сопоставим свойство f: M —→ {0, 1}, при котором элементы подмножества P переходят в 1, а остальные элементы в 0. Обратно, с каждым свойством f: M —→ {0, 1} сопоставим подмножество всех тех элементов a множества M, для которых f(a)=1. Легко проверить, что эти два сопоставления задают взаимно-однозначное соответствие между множествами подмножеств и свойств.

2. Зададимся вопросом: как изменится число свойств множества M при добавлении к нему одного элемента М υ {a}? Обозначим через s число свойств множества M. Имеется ровно s свойств множества М υ {a}, при которых элемент a переходит в 0 и ровно s свойств множества М υ {a}, при которых элемент a переходит в 1. Поскольку элемент a при любом свойстве переходит либо в 0, либо в 1, то всего свойств множества М υ {a} существует 2s.

Сколько всего свойств имеется у пустого множества? Одно.

Далее, множество M можно получить многократным добавлением к пустому множеству одного элемента. Следовательно, число свойств множества M мощности m равно 2^m.