Se nos pide demostrar que siendo A un conjunto de conjuntos, el conjunto { x ∈ A | x ∉ x } ∉ A. Es interesante y por eso lo blogueo porque es una aplicación de la paradoja de Russell.

Demostración

Llamemos B al conjunto { x ∈ A | x ∉ x }. Supongamos que B ∈ A y consideremos a B con respecto a si mismo desde la relación ∈, o bien B ∈ B o bien B∉ B.

Supongamos que B ∈ B entonces por la propia definición de B, B ∉ B, lo cual es una contradicción. Ahora si B ∉ B también por la definición de B sigue que B ∈ B, lo cual también es una contradicción.

Dado que nuestra premisa original nos lleva siempre a una contradicción, debe ser falsa, por consiguiente B ∉ A.

Es interesante también como este ejercicio sirve de introducción a los tipos y clases de Haskell.