Парадокс цирюльника в наивной теории множеств

Парадокс цирюльника (парадокс Рассела), открытый Бертраном Расселом в 1901 году, показывает, что очевидно правдоподобный сценарий логически невозможен.

 Представьте, что в городе есть только один парикмахер-мужчина, который утверждает, что он побреет каждого мужчину в городе, который никогда не бреется, но не побреет никого, кто бреется. Это звучит очень логично, пока не зададут следующий вопрос: бреется ли парикмахер? Если парикмахер не бреется, он должен соблюдать свое правило и бриться. Однако, если он все же побреется, то по правилу он будет не бриться.

Парадокс Рассела, переформулированный в контексте так называемой «наивной» теории множеств, выявил огромную проблему и полностью изменил направление математики ХХ века.

В наивной теории множеств есть два типа множеств. Для первого типа наборов набор не является элементом самого себя. Например, набор всех наций не является нацией; набор всех мужчин не является мужчиной.

Для второго типа набора набор является элементом самого себя. Например, совокупность всего, что не является людьми, является элементом самого себя. А как насчет набора всех наборов, которые не являются элементами самих себя? Это элемент самого себя? Если он элемент, то он не элемент, а если он не элемент, то он элемент...

Также как цирюльник, который бреется, но не должен, а, следовательно, и не должен, и должен! Парадокс Рассела означает, что в основе наивной теории множеств лежит противоречие. То есть существует утверждение S такое, что и оно, и его отрицание (не S) истинны, где утверждение S следующее: «множество всех множеств, которые не являются элементами самих себя, содержит себя».

Теория множеств Цермело-Френкеля с аксиомой выбора была разработана, чтобы избежать парадокса Рассела.