2
$\begingroup$

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.

  • 5
    To all the commentators, $\aleph$ is used in some parts of the world to denote $2^{\aleph_0}$. In fact this is Cantor's original notation.2012-06-30

2 Answers 2

4

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

  • 0
    @Benedict, of course. At least in the course I took, and in most contexts "relation" means binary relation, otherwise the arity is specified.2012-06-30
2

All relations from $\Bbb N\to\Bbb N$ are the subsets of $\Bbb N \times \Bbb N $ which is of same cardinality as $\Bbb Q$(set of rationals) as you can consider a rational $p/q$ ($q\neq 0$) as tuple $(p,q)$ of $\Bbb N \times \Bbb N$ and Cardinality of Rationals is same as of $\Bbb N$.Hence, $|\Bbb N \times \Bbb N|=|\Bbb N|=\aleph_0$ and therefore $2^{\aleph_0}$ is the required cardinality.

  • 0
    @Asaf: Thanks, done :) (have to adm$it$, I think that particular restriction somewhat silly).2012-06-30