I have to find the cardinality of the set of all relations over the natural numbers, without any limitations.
It seems to be א, but I can't find a function/other way to prove it.
help anyone?
thanxs.
[Math] cardinality: The cardinality of the set of all relations over the natural numbers.
cardinalselementary-set-theory
Best Answer
Recall that $R$ is a relation over $A$ if $R\subseteq A\times A$.
The definition above tells us that every subset of $\mathbb{N\times N}$ is a relation over $\mathbb N$, and vice versa - every relation over $\mathbb N$ is a subset of $\mathbb{N\times N}$.
Thus the set of all relations over $\mathbb N$ is exactly $\mathcal P(\mathbb{N\times N})$, that is the power of $\mathbb{N\times N}$.
We know that $\mathbb N$ and $\mathbb{N\times N}$ have the same cardinality, $\aleph_0$. So their power sets also have the same cardinality. Therefore $|\mathcal P(\mathbb{N\times N})|=\aleph=|\mathbb R|=2^{\aleph_0}$.
Note, however, that as a particular set, every relation in particular is a subset of a countable set and thus countable (or finite).