# cardinality: The cardinality of the set of all relations over the natural numbers.

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.

-
Relations are (or are in correspondence with) subsets of $\Bbb N\times\Bbb N$, and the latter is equinumerous with $\Bbb N$ itself, so... – anon Jun 30 '12 at 12:42
@anon You claim that it's cardinality is א0? There can be infinite number of subsets, so it seemed to me like a equinumerous to N^N – adamco Jun 30 '12 at 12:49
Sorry, I meant $\Bbb N\times\Bbb N$ has cardinality $\aleph_0$, not that $\mathcal{P}(\Bbb N\times\Bbb N)$ does. – anon Jun 30 '12 at 12:53
This question asks about symmetric relations and equivalence relations: Cardinality of relations set‌​. – Martin Sleziak Jun 30 '12 at 12:55
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. – Asaf Karagila Jun 30 '12 at 13:09

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

-
You only consider binary relations here, but of course your proof generalises to $n$-ary relations as $|\mathbb{N}^n| = |\mathbb{N}| = \aleph_0$. – Benedict Eastaugh Jun 30 '12 at 15:03
@Benedict, of course. At least in the course I took, and in most contexts "relation" means binary relation, otherwise the arity is specified. – Asaf Karagila Jun 30 '12 at 15:26

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.

-
You can write $\aleph_0$ as \aleph_0. But you want cardinality of $\mathcal P(\mathbb N\times\mathbb N)$, not the cardinality of $\mathbb N\times\mathbb N$. So the final result should be $2^{\aleph_0}=\mathfrak c$. (TeX: $2^{\aleph_0}=\mathfrak c$) – Martin Sleziak Jun 30 '12 at 12:58
Actually, @Martin, there is some usage of $\aleph$ as the cardinality of the continuum. – Asaf Karagila Jun 30 '12 at 13:08
@Martin: Cantor's original, as I remarked in the comments to the question. It is much less common nowadays, though. – Asaf Karagila Jun 30 '12 at 13:14
Okay, per Asaf's clarification (thanks!) I think this answer is correct, but I can't immediately revoke my downvote (the system won't let me). anon's comment is a legitimate concern (what about negative rationals? why can we assert the result that $|\mathbb Q| = |\mathbb N|$, which I would normally prove after proving $|\mathbb{N \times N}| = |\mathbb N|$?) – Ben Millwood Jun 30 '12 at 13:15
@Ben: I edited the $\aleph$ symbol. Now you should be able to revoke your downvote. – Asaf Karagila Jun 30 '12 at 13:21