Paradoxo do barbeiro

O paradoxo do barbeiro é um paradoxo que relaciona lógica matemática e teoria de conjuntos. O paradoxo considera uma aldeia onde, todos os dias, um barbeiro faz a barba de todos os homens que não se barbeiam sozinhos e não faz a barba de quem se barbeia sozinho. Isso vale para todos que estão na aldeia. Ora tal aldeia não pode existir:

Se o barbeiro é um homem que não se barbeia sozinho, então ele deve fazer a barba a si mesmo imediatamente, tornando-se um homem que se barbeia sozinho.

Se agora ele é um homem que se barbeia sozinho, então ele deve parar imediatamente de fazer a própria barba, tornando-se um homem que não se barbeia sozinho.

A regra resulta num paradoxo, pois o barbeiro ao mesmo tempo deve e não deve fazer a própria barba, não podendo se decidir sem quebrar a regra.

O paradoxo costuma ser atribuído a Bertrand Russell, um matemático britânico que em 1901 elaborou o paradoxo de Russell para demonstrar a natureza auto-contraditória da teoria de conjuntos de Georg Cantor. O paradoxo é também usado no teorema da incompletude de Gödel bem como na prova da indecidibilidade do problema de paragem de Alan Turing.