# Cardinality of relations set

I was thinking about cardinality of all symmetric relations, for example in $\mathbb{Z}$. I know, that if I have finite set (which contains $n$ elements), there are $2^{\frac{n(n+1)}{2}}$ symmetric relations. But what happens when we are talking about infinite sets ($\mathbb{Z}$ for example)? How many symmetric relations are in $\mathbb{Z}$ or $\mathbb{N}$? What about equivalence relation?

I just want to know, how to think about such problems. If You can, please show me some examples of similar problems (maybe with hints, how to solve them).

-

To see that the number of equivalence relations on an infinite set $A$ of size $\kappa$ is $2^{\kappa}=|{\mathcal P}(A)|$ (i.e., the largest possible size), recall that any set of size $\kappa$ can be split into $\kappa$ sets of size $\kappa$: $\kappa=\kappa\times\kappa$. Say $A$ has size $\kappa$. Fix a partition $A=\bigcup_{i\in I}A_i$, where $I$ is an index set of size $\kappa$, each $A_i$ has size $\kappa$, and $A_i\cap A_j=\emptyset$ if $i\ne j$. Also, for each $A_i$, find a partition $A_i=B_i\cup C_i$ where each $B_i,C_i$ is non-empty.

Given $D\subseteq I$, let $E_D$ be the equivalence relation on $A$ defined as follows:

If $i\in D$, then $B_i$ and $C_i$ are equivalence classes. If $i\in I$ is not in $D$, then the whole of $A_i$ is an equivalence class.

More precisely, in case the above description is not clear: $a E_D b$ for $a,b\in A$, iff both $a,b$ are in the same $A_i$ (for some -unique- $i\in I$) and (if $i\notin D$, then both $a,b$ are in $B_i$ or both are in $C_i$).

Then, from $E_D$, we can reconstruct $D$, so the map $f:{\mathcal P}(I)\to {\mathcal E}$, where ${\mathcal E}$ is the set of equivalence relations on $A$, given by $f(D)=E_D$ is injective, and $|{\mathcal E}|\ge 2^\kappa$.

(In fact, for this inequality to hold, all we needed is that $2\times\kappa=\kappa$: We could have taken each $A_i$ of size 2 and each $B_i,C_i$ a singleton. However, the argument below uses that $\kappa\times\kappa=\kappa$.)

Since each class is a subset of $A\times A$, and different classes are disjoint, each equivalence relation has at most $\kappa=|A|$ classes (cannot have more classes than elements of $A$), and each class is chosen from ${\mathcal P}(A\times A)$, so there are at most $\kappa\times 2^{|\kappa\times\kappa|}=2^\kappa$ equivalence relations.

It follows that the number of equivalence relations is $2^\kappa$, as claimed.

Since each equivalence relation is symmetric, this also shows that there are precisely $2^\kappa$ symmetric relations on $A$ if $|A|=\kappa$.

Let me close with a technical remark: If $A$ is countable (so $\kappa$ is usually denoted $\aleph_0=|{\mathbb N}|=|{\mathbb Z}|$), the equality $\kappa=\kappa\times\kappa$ and the equality $\kappa 2^\kappa=2^\kappa$ can be verified without using the axiom of choice. Same if $A$ has the size of the reals (so $\kappa$ is usually denoted ${\mathfrak c}$ or $2^{\aleph_0}=|{\mathcal P}({\mathbb N})|$).

However, for arbitrary infinite $A$, the equalities require the axiom of choice. I haven't checked what the number of equivalence relations for an arbitrary infinite $A$ is if choice fails. I do not think it is $2^{|A|}$ in general.

-
+1: I was wondering when you will post an answer! –  Aryabhata Jan 19 '11 at 1:21
Wow! Thank You for a great answer. –  exTyn Jan 19 '11 at 1:55

You can think of a symmetric relation as an undirected graph, with vertices being $\mathbb{Z}$.

Since there are a countable number of edges (an infinite subset of $\mathbb{Z} \times \mathbb{Z}$), of which you can pick any subset, the number of symmetric relations is $2^{\mathbb{N}}$.

An equivalence relation is a subset of $\mathbb{Z}\times\mathbb{Z}$ and hence the number of equivalence relations $\le 2^{\mathbb{N}}$. Since we have the partitions $\{S, \mathbb{Z} - S\}$ for any $S \subset \mathbb{Z}$, the number of equivalence relations is also $2^{\mathbb{N}}$.

-
Rather than ${\mathbb Z}\times{\mathbb Z}$, you want ${\mathbb Z}\cup[{\mathbb Z}]^2$, where the latter is the set of unordered pairs of integers. Otherwise, you are overcounting (for example, you count $\{(1,2),(2,1)\}$ twice). This overcounting does not matter at the end, but it requires an argument. –  Andres Caicedo Jan 19 '11 at 0:44
@Andres: Thanks. I have edited the answer. –  Aryabhata Jan 19 '11 at 0:53
and what, if we are talking about $\mathbb{N}$? Is there the same answer? –  exTyn Jan 19 '11 at 1:04
@exTyn: Yes, that is correct. –  Aryabhata Jan 19 '11 at 1:17
Thank's for help. –  exTyn Jan 19 '11 at 1:56