Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


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.