# The cardinality of the set all symmetric relations on the set of natural numbers is $\mathfrak{c} = | \mathbb{R} | = 2^{\aleph_0}$

Prove that a set of all symmetric relations on the set of natural numbers has cardinality $\mathfrak{c} = | \mathbb{R} | = 2^{\aleph_0}$.

Here I think that the $(a,b)b$ - will be every number there is in $\mathbb N$ and hence we will never get pass ordered pair that contain $a$ as first number. If it's true can you please tell me how to write it?

• Here i think that the (a,b)b - will be every number there is in N and hence we will never get pass ordered pair that contain ′a′ as first number. What does this mean?
– anon
Commented Aug 22, 2015 at 6:14
• i am new at this so maybe i write here something totally wrong. i though about relation set {(1,1),(1,2),(1,3),(1,4)...} since the 1 , 2 , 3 , 4 are part of Natural numbers set (which is infinite) we will never get to relation of ordered pair which will be {...(2,1),(2,2)....}. This what i though is the way of thinking needed to solve this question.
– Mor
Commented Aug 22, 2015 at 6:19
• Sets are not bounded by our ability to write things in lists. Anyway, do you know what a relation is?
– anon
Commented Aug 22, 2015 at 6:21
• Relation R of A-{1,2,3} set is a subset of {AXA}. For example: R = {(1,1),(2,3)}.
– Mor
Commented Aug 22, 2015 at 6:23
• A relation $R$ on a set $X$ is a subset $R\subseteq X\times X$, yes. For instance, consider the divisibility relation on $\Bbb N$. This relation $R\subseteq\Bbb N\times\Bbb N$ includes all ordered pairs $(a,b)$ in which $b$ is a multiple of $a$. In particular it includes $(1,1)$, $(1,2)$, $(1,3)$, $(1,4)$, etc. but it also includes $(2,2)$, $(2,4)$, and so on. Just because the first list I wrote down that had $1$s in the first coordinate didn't have all the elements of the relation doesn't mean the relation isn't well-defined.
– anon
Commented Aug 22, 2015 at 6:24

Hint: symmetric relations on $\Bbb N$ are in bijection with subsets of $\{(a,b)\in\Bbb N^2:a\le b\}$.
Alt route: any subset of $\{(c,c)\in\Bbb N^2:c\in\Bbb N\}$ is a symmetric relation.