Calculate cardinality of a subset of all the relations above $\mathbb{N}$ This is my question:
Define $X$ to be set of all the relations $R$ over $\mathbb{N}$ such that $R^{*}=\mathbb{N\times\mathbb{N}}$, where $R^{*}$ is the transitive closure of R.
What is the cardinality of the set $X$?
What I've tried so far:
I notice that all the transitive relations besides $\mathbb{N}\times\mathbb{N}$ are not in $X$. And I know that the cardinality of all the transitive relations over $\mathbb{N}$ is $\mathfrak c$.
Thank you very much!
 A: As you noted, the transitive relations are not going to help you in this question. So the trick is to look at the non-transitive relations.
First note that $|X| \leq \mathfrak{c}$ because $|X| \leq |\mathcal{P}(\mathbb{N} \times \mathbb{N})| = \mathfrak{c}$, where $\mathcal{P}$ denotes the powerset. This is simply using the upper bound on the cardinality of all relations, see also this question.
Let's define
$$
P = \{(n, 0) : n \in \mathbb{N}\} \cup \{(0, n) : n \in \mathbb{N}\}.
$$
Then the transitive closure $P^*$ of $P$ is clearly $\mathbb{N} \times \mathbb{N}$. So any relation $R$ such that $P \subseteq R$ will satisfy $R^* = \mathbb{N} \times \mathbb{N}$ and hence $R \in X$ for any such relation.
Now for $A \subseteq \mathbb{N}_{>0}$ we define
$$
R_A = \{(1, a) : a \in A\} \cup P.
$$
Then by the above discussion $R_A \in X$ for any $A \subseteq \mathbb{N}_{>0}$. Furthermore, for distinct $A, B \subseteq \mathbb{N}_{> 0}$ we also have $R_A \neq R_B$. So the assignment $A \mapsto R_A$ is an injective function $\mathcal{P}(\mathbb{N}_{>0}) \to X$, and hence $\mathfrak{c} \leq |X|$. We conclude that $|X| = \mathfrak{c}$.
A: We show that the cardinality is $\frak c$. Since you've already noted that there are at most $\frak c$ many relations in all, it suffices to show that there are at least $\frak c$ many relations with the desired property.
First, let $\mathbf a = (a_n)_n$ be an arbitrary sequence of natural numbers with the property that $a_{n} \neq 1$ for all $n$. Define the relation $$R_{\mathbf a} := (\Bbb N \times \Bbb N) - \{(n, a_n) : n \in \Bbb N \setminus \{1\}\}.$$
Since there are $\frak c$ many such sequences, it suffices to show that $R_{\mathbf a}^* = \Bbb N \times \Bbb N$.
To do that, we need to show that $(n, a_n) \in R_{\mathbf a}^*$ for all $n \neq 1$.
Fix such an $n$. Then, note that $(n, 1)$ and $(1, a_n)$ are both in $R_{\mathbf{a}}$. Thus, by transitivity, so is $(n, a_{n})$ and we are done.
