Para ver que el número de relaciones de equivalencia en un conjunto infinito A de tamaño κ es 2κ=|P(A)| (es decir, el mayor tamaño posible), recordemos que cualquier conjunto de tamaño κ puede dividirse en κ conjuntos de tamaño κ : κ=κ×κ . Diga A tiene tamaño κ . Fijar una partición A=⋃i∈IAi , donde I es un conjunto de índices de tamaño κ Cada uno de ellos Ai tiene tamaño κ y Ai∩Aj=∅ si i≠j . Además, para cada Ai , encontrar una partición Ai=Bi∪Ci donde cada Bi,Ci no está vacío.
Dado D⊆I , dejemos que ED sea la relación de equivalencia en A definidos de la siguiente manera:
Si i∈D entonces Bi y Ci son clases de equivalencia. Si i∈I no está en D entonces el conjunto de Ai es una clase de equivalencia.
Más concretamente, en caso de que la descripción anterior no esté clara: aEDb para a,b∈A si ambos a,b están en el mismo Ai (para algunos -únicos- i∈I ) y (si i∉D entonces ambos a,b están en Bi o ambos están en Ci ).
Entonces, desde ED podemos reconstruir D , por lo que el mapa f:P(I)→E , donde E es el conjunto de relaciones de equivalencia en A dado por f(D)=ED es inyectiva, y |E|≥2κ .
(De hecho, para que esta desigualdad se cumpla, lo único que necesitamos es que 2×κ=κ : Podríamos haber tomado cada Ai de tamaño 2 y cada Bi,Ci un único individuo. Sin embargo, el argumento siguiente utiliza ese κ×κ=κ .)
Como cada clase es un subconjunto de A×A y las diferentes clases son disjuntas, cada relación de equivalencia tiene como máximo κ=|A| (no puede tener más clases que elementos de A ), y cada clase se elige entre P(A×A) por lo que hay como máximo κ×2|κ×κ|=2κ relaciones de equivalencia.
Se deduce que el número de relaciones de equivalencia es 2κ como se ha reclamado.
Como cada relación de equivalencia es simétrica, esto también demuestra que hay precisamente 2κ relaciones simétricas en A si |A|=κ .
Permítanme terminar con una observación técnica: Si A es contable (por lo que κ se suele denominar ℵ0=|N|=|Z| ), la igualdad κ=κ×κ y la igualdad κ2κ=2κ puede verificarse sin utilizar el axioma de elección. Lo mismo si A tiene el tamaño de los reales (así que κ se suele denominar c o 2ℵ0=|P(N)| ).
Sin embargo, para un infinito arbitrario A las igualdades requieren el axioma de elección. No he comprobado cuál es el número de relaciones de equivalencia para un infinito arbitrario A es si la elección falla. No creo que sea 2|A| en general.