Cardinalidad de las relaciones establecidas

Question

Estaba pensando acerca de la cardinalidad de todas las relaciones simétricas, por ejemplo, en $\mathbb{Z}$. Sé, que si he conjunto finito (que contiene a $n$ elementos), hay $2^{\frac{n(n+1)}{2}}$ relaciones simétricas. Pero, ¿qué sucede cuando estamos hablando de conjuntos infinitos ($\mathbb{Z}$ por ejemplo)? Cuántas relaciones simétricas son en $\mathbb{Z}$ o $\mathbb{N}$? ¿Qué acerca de la relación de equivalencia?

Sólo quiero saber, ¿cómo pensar acerca de tales problemas. Si puedes, por favor, muéstrame algunos ejemplos de problemas similares (tal vez con consejos, de cómo solucionarlos).

Answer 1

Para ver que el número de las relaciones de equivalencia en un conjunto infinito $A$ del tamaño de la $\kappa$ $2^{\kappa}=|{\mathcal P}(A)|$ (es decir, el tamaño más grande posible), recordemos que cualquier conjunto de tamaño $\kappa$ se puede dividir en $\kappa$ conjuntos de tamaño $\kappa$: $\kappa=\kappa\times\kappa$. Decir $A$ tiene el tamaño de $\kappa$. Fijar una partición $A=\bigcup_{i\in I}A_i$ donde $I$ es un conjunto de índices de tamaño de $\kappa$, cada una de las $A_i$ tiene el tamaño de $\kappa$, e $A_i\cap A_j=\emptyset$ si $i\ne j$. También, para cada una de las $A_i$, encontramos una partición $A_i=B_i\cup C_i$ donde cada una de las $B_i,C_i$ no está vacía.

Dado $D\subseteq I$, vamos a $E_D$ ser la relación de equivalencia en $A$ define de la siguiente manera:

Si $i\in D$, $B_i$ $C_i$ son clases de equivalencia. Si $i\in I$ no $D$, el total de $A_i$ es una clase de equivalencia.

Más precisamente, en el caso de que la descripción anterior no está claro: $a E_D b$$a,b\in A$, iff tanto $a,b$ están en el mismo $A_i$ (para algunos-y única- $i\in I$) y (si $i\notin D$, $a,b$ $B_i$ o ambos están en $C_i$).

Luego, a partir de $E_D$, podemos reconstruir $D$, por lo que el mapa de $f:{\mathcal P}(I)\to {\mathcal E}$ donde ${\mathcal E}$ es el conjunto de las relaciones de equivalencia en $A$, dado por $f(D)=E_D$ es inyectiva, y $|{\mathcal E}|\ge 2^\kappa$.

(De hecho, esta desigualdad para celebrar, todo lo que se necesita es que el $2\times\kappa=\kappa$: podríamos haber tomado cada una de las $A_i$ de tamaño 2 y cada una de las $B_i,C_i$ un singleton. Sin embargo, el argumento por debajo de los usos que $\kappa\times\kappa=\kappa$.)

Puesto que cada clase es un subconjunto de a $A\times A$, y las diferentes clases son disjuntos, cada uno de equivalencia de la relación tiene en la mayoría de las $\kappa=|A|$ clases (no puede tener más clases de elementos de $A$), y cada clase es elegido de ${\mathcal P}(A\times A)$, por lo que hay en la mayoría de las $\kappa\times 2^{|\kappa\times\kappa|}=2^\kappa$ las relaciones de equivalencia.

De ello se deduce que el número de las relaciones de equivalencia es $2^\kappa$, como se reivindica.

Desde cada uno de equivalencia de la relación es simétrica, esto también muestra que hay exactamente $2^\kappa$ relaciones simétricas en $A$ si $|A|=\kappa$.

---

Permítanme concluir con una técnica de observación: Si $A$ es contable (por lo $\kappa$ es generalmente denotado $\aleph_0=|{\mathbb N}|=|{\mathbb Z}|$), la igualdad de $\kappa=\kappa\times\kappa$ y la igualdad de $\kappa 2^\kappa=2^\kappa$ puede ser verificado sin usar el axioma de elección. Mismo si $A$ tiene el tamaño de los reales (por lo $\kappa$ es generalmente denotado ${\mathfrak c}$ o $2^{\aleph_0}=|{\mathcal P}({\mathbb N})|$).

Sin embargo, para arbitrario infinito $A$, la igualdad requiere el axioma de elección. No he comprobado lo que el número de las relaciones de equivalencia para una arbitraria infinito $A$ es si la elección de falla. Creo que no es $2^{|A|}$ en general.

Answer 2

Usted puede pensar en una relación simétrica como un grafo no dirigido, con vértices ser $\mathbb{Z}$.

Puesto que hay una contables número de aristas (un subconjunto infinito de $\mathbb{Z} \times \mathbb{Z}$), de los cuales usted puede escoger cualquier subconjunto, el número de relaciones simétricas es $2^{\mathbb{N}}$.

Una relación de equivalencia es un subconjunto de a $\mathbb{Z}\times\mathbb{Z}$ y por lo tanto el número de las relaciones de equivalencia $\le 2^{\mathbb{N}}$. Ya tenemos las particiones $\{S, \mathbb{Z} - S\}$ cualquier $S \subset \mathbb{Z}$, el número de las relaciones de equivalencia también es $2^{\mathbb{N}}$.