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).
Best Answer
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.