Egor Urvanov

Barber paradox

Formal verification · a question about itself

A village barber shaves everyone who does not shave themselves, and only them. Does he shave himself? If he does, he must not; if he doesn’t, he must. So no such barber exists. Bertrand Russell used it as an illustration of his paradox about sets. The same trick, a question about itself, proves the halting problem undecidable.

AA = shave themselvesthe barber doesn’t shave themBB = shaved by the barberrule: B is everyone not in Athe barber is a villager too?in A → shaves himself,so the barber shaves him → he is in Bin B → the barber shaves him,that is, himself → he is in Aevery villager is in exactly one set; the barber has no place● model, people, systems, data  ● risk, stop, boundaryEvery villager is in exactly one set, A or B. The barber is in neither: put him in A and he lands in B, and vice versa

The point is two sets. The villagers split into set AA, those who shave themselves, and set BB, those the barber shaves. The rule says BB is exactly everyone not in AA, so every villager is in one and only one set. The barber is a villager too, and he has nowhere to go. If he is in AA, he shaves himself, so the barber shaves him, so he is in BB. If he is in BB, the barber shaves him, that is, he shaves himself, so he is in AA. The contradiction shows that such a rule can’t be satisfied.

Russell, 1901: sets that do or do not contain themselvesthe set of catsis not a cat → doesn’t contain itselfitselfeverything that is not a catis not a cat → lies inside itselfRR = all sets that do not contain themselvesR ∈ R ⇔ R ∉ Rthese go into R● model, people, systems, data  ● risk, stop, boundaryThe set R of all sets that do not contain themselves: R is in R exactly when R is not in R

Russell’s original 1901 paradox is about sets. An ordinary set does not contain itself: the set of cats is not a cat. Some sets do contain themselves: the set of everything that is not a cat is itself not a cat, so it lies inside itself. Take RR, the set of all sets that do not contain themselves: R={x:x∉x}R = \{x : x \notin x\}. If R∈RR \in R, then by definition R∉RR \notin R; if R∉RR \notin R, then RR fits the definition and R∈RR \in R. The barber is the same question in everyday clothes: villagers instead of sets and “shaves” instead of “contains”.

Source: Wikipedia: Barber paradox

Where it appears · 1

Related terms

Whole glossary

© 2026 Egor Urvanov