Парадокс Рассела. Основной принцип комбинаторики. Число элементов декартового произведения множеств.
Парадокс Рассела — открытая в 1903 году Бертраном Расселом и позднее независимо переоткрытая Э. Цермело теоретико-множественная антиномия, демонстрирующая противоречивость наивной теории множеств Г. Кантора.
Антиномия Рассела формулируется следующим образом:
Пусть K — множество всех множеств, которые не содержат себя в качестве своего элемента. Содержит ли K само себя в качестве элемента? Если да, то, по определению K, оно не должно быть элементом K — противоречие. Если нет — то, по определению K, оно должно быть элементом K — вновь противоречие.
Существует много популярных формулировок этого парадокса. Одна из них традиционно называется парадоксом брадобрея и звучит так:
Одному деревенскому брадобрею приказали «брить всякого, кто сам не бреется, и не брить того, кто сам бреется», как он должен поступить с собой?
Основной принцип комбинаторики.
Если А и В – мн-ва и 
Предположим утверждение неверно:
а) 
, тогда 
противоречит (фи)-биек
б) 
, тогда 
противоречит (фи)-биек
Число элементов декартового произведения множеств.
Пусть А и В — два множества. Прямым (декартовым) произведением двух множеств А и В называется множество упорядоченных пар, в котором первый элемент каждой пары принадлежит А, а второй принадлежит В: 
.
ТЕОРЕМА. 
; Доказательство ;
Первый компонент упорядоченной пары можно выбрать |А| способами, второй — |В| способами. Таким образом, всего имеется |А||В| различных упорядоченных пар. то есть количество элементов равно |А|*|В|