2
$\begingroup$

I think this set is uncountable, but I don't really know how to prove this. Maybe somehow find an injection from $\mathcal{P}( \mathbb{N} \times \mathbb{N}) \rightarrow A$?

$\endgroup$
0

3 Answers 3

0
$\begingroup$

For any $X\subseteq \mathbb N$, the relation $R_X = \{(x,x) | x \in X\}$ is anti-symmetric.

$\endgroup$
0
$\begingroup$

Alternatively you can count such antisymmetric relations on a set having $n$ elements, which are

$2^n 3^{\frac{n^2-n}{2}}$

Set $n=\aleph_0$ for set of natural numbers, so that

$2^{\aleph_0} 3^{\frac{\aleph_0^2-\aleph_0}{2}}>2^{\aleph_0}=c(\text{cardinality of real numbers }\mathbb R)$

$\endgroup$
-1
$\begingroup$

For any $S \subset \mathbb{N}$ take $\mathcal{R}_S = \bigcup_{s \in S} \{(s,s+1)\}$. It is clear that $\mathcal{R}$ is anti-symmetric, as it's a subset of anti-symmetric relation $\mathcal{R}=\{(x,y):x<y\}$, and that this transformation is injective, so there are at least $\# \mathcal{P}(\mathbb{N})$ anti-symmetric relations on $\mathbb{N}$, thus their number is uncountable.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.