Contar las relaciones de equivalencia

Question

Soy consciente de que en un conjunto finito el número de relaciones de equivalencia es el n-ésimo El número de Bell . Por otro lado, la única referencia que pude encontrar en la web para conjuntos infinitos fue esta: Al contar las relaciones de equivalencia por D.J. Baylis, en el que prueba que el conjunto de relaciones de equivalencia en $ \mathbb {N}$ es incontable. Estoy interesado en cualquier tipo de teorema que dé alguna regla sobre el conteo de las relaciones de equivalencia en un conjunto infinito - algo como $ \beth_0 = \aleph_0 $ y $ \beth_n = 2^{ \beth_ {n-1}}$ - si es que hay alguno.

Answer 1

Asumiré que el axioma de la elección se mantiene: esto puede no ser necesario, pero no estoy seguro.

Comienza observando que las relaciones de equivalencia en un conjunto $S$ son "lo mismo" que las particiones de $S$ (recuerde que una partición de $S$ es un conjunto $B$ de subconjuntos de $S$ con las propiedades que

1) $ \cup_ {b \in B}b = S$ y

2) para todos $b,b' \in B$ tenemos $b \cap b'= \emptyset $ ).

Deje que $S$ sea un conjunto infinito, que $B(S)$ denotan el conjunto de particiones de $S$ y $P(S)$ el conjunto de energía de $S$ (a saber, el conjunto de todos los subconjuntos de $S$ ). Voy a mostrar que $|B(S)| = |P(S)|$ y note que $|P(S)| = 2^{|S|}$ .

Primero que nada, usa el axioma de elección para fijar, para cada subconjunto no vacío $A$ de $S$ un elemento $c(A) \in A$ .

A cualquier función $f \colon S \to S$ asociamos una partición $B_f$ de $S$ dejando que $B_f = \{ f^{-1}(s) | s \in f(S) \}$ en palabras, $B_f$ es la partición cuyos elementos son las fibras no vacías de la función $f$ . Cualquier partición $B$ se obtiene por esta construcción: definimos una función $f_B \colon S \to S$ dejando que $f_B(s) = c(b_s)$ donde $b_s$ es la parte de $B$ que contiene $s$ . Claramente, la partición $B_{f_B}$ coincide con la partición $B$ . Deducimos que hay una suposición del conjunto de todas las funciones $S \to S$ al conjunto de particiones; por lo que concluimos que $|B(S)| \leq |S^S| = |P(S)| = |2^S|$ .

Para la otra desigualdad, que $P'(S)$ denotan el conjunto de pares no ordenados de subconjuntos de $S$ de la forma $\{ A , S \setminus A \}$ donde $A \subset S$ es un subconjunto adecuado no vacío de $S$ . Cada pareja no ordenada en $P'(S)$ determina de manera única una partición de $S$ con dos partes, para que haya una inyección $P'(S) \to B(S)$ . Deducimos que $|B(S)| \geq |P'(S)|$ . Para concluir, basta con mostrar que $|P'(S)| \geq |P(S)|$ . Esto es fácil, ya que hay una suposición natural $P(S) \setminus \{ S , \{ \emptyset\ } \} \to P'(S)$ cuyas fibras consisten exactamente en dos elementos, y $P(S)$ es un conjunto infinito.

Answer 2

En primer lugar, para abordar los números de Beth (como has notado, el marcado matemático no funciona con ellos. Usaré palabras en su lugar)

$ \beth $ Los números (Beth) son números cardinales definidos como sigue:

1. $ \beth_0 = \aleph_0 $ ,
2. $ \beth_ { \alpha +1} = 2^{ \beth_n }$ ,
3. $ \beth_\delta = \sup_ { \gamma < \delta } \beth_\gamma $ para un límite ordinal $ \delta $ .

Ahora, dado un conjunto infinito $X$ y asumiendo el axioma de la elección, tenemos que $|X \times X|=|X|$ Por lo tanto $|P(X \times X)| = |P(X)|$ . Defina $R(X)$ como el conjunto de todas las relaciones de equivalencia en $X$ entonces claramente $R(X) \subset P(X \times X)$ y por lo tanto $|R(X)| \le |P(X)|$ .

Por otra parte, hay $2^{|X|}$ particiones de $X$ en dos conjuntos (un fácil ejercicio de aritmética cardinal), así que para cada partición como tal $\{X', X \setminus X'\}$ podemos definir una relación de equivalencia con dos clases de equivalencia, a saber $X'$ y su complemento en $X$ . Por lo tanto $|R(X)| \ge |P(X)|$ .

En general, tenemos que el número de relaciones de equivalencia en $X$ es $2^{|X|}$ .

Answer 3

Deje que $X$ ser un conjunto infinito. Cualquier función $f : X \to X$ determina una relación de equivalencia en $X$ : $$ x_1 \equiv x_2 \iff f(x_1) = f(x_2). $$ De ello se deduce que hay al menos $2^{|X|}$ relaciones de equivalencia en $X$ (véanse las observaciones que figuran a continuación). Por otra parte, cualquier relación de equivalencia define una función de $X$ a $X,$ tomar un juego completo $S$ de representantes, enviar cada elemento de una clase determinada a su representante en $S.$ Por lo tanto, no hay más que $|X|^{|X|}$ relaciones de equivalencia en $X.$ Por lo tanto, hay exactamente $|X|^{|X|}=2^{|X|}$ relaciones de equivalencia en $X.$