Каждому такому отображению соответствует ровно одна (такое соответствие очевидно взаимно-однозначное) строчка длины Соответствие это строится следующим образом:

Давайте как-нибудь упорядочим элементы множества То есть, запишем в виде:

И вот, если то в этой строчке на ом месте будет стоять 0, а если то в этой строчке на ом месте будет стоять 1.

То есть, каждая функция - это просто набор из нулей и единиц длины

Причём же здесь множество всех поджмножеств множества ?
А притом, что любое подмножество множества можно задать так: сопоставить 0 тем элементам, которые в подмножество не входят, и 1 - тем элементам, которые в подмножество входят. Тогда различных подмножеств множества всего столько же, сколько строк длины составленных из нулей и единиц. То есть, ровно столько, сколько функций - как мы показали выше.