Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
+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}}$.

share|improve this answer
1  
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
1  
@exTyn: Yes, that is correct. –  Aryabhata Jan 19 '11 at 1:17
    
Thank's for help. –  exTyn Jan 19 '11 at 1:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.