Prove that the cardinality of the set of all transitive relation on $\Bbb N$ is $\mathfrak c$

Question

How do I prove the following statement? I have an idea of how to go here, but need a further explanation -

Firstly, I'll define the set of all transitive relation on $\Bbb N$ as $T$.

1. First of all, prove that the cardinal number of the set $\mathcal P(\Bbb N\times \Bbb N) = \mathfrak c$. That is easily done.
2. Define a function : $f\colon \mathcal P(\Bbb N\times\Bbb N) \to T$, as follows: $R$ is in $\mathcal P(\Bbb N\times \Bbb N)$. If $R$ is transitive, $f(R) = R$, otherwise $f(R) =$ the closest transitive relation that contains $R$.
3. That function splits $\mathcal P(\Bbb N\times \Bbb N)$ into different departs, according to the result $f$ sends them to. I need to prove that the cardinal number of those results is $\mathfrak c$.
4. There is a $1\leftrightarrow1$ function between $T$ and the group of results of $F$. therefore, cardinal number of $T$ is equal and is $\mathfrak c$.

I can't figure out how to prove point number 3.

(Sorry for my english)

Answer 1

For each $A\in\mathcal P(\Bbb N)$ we can define the map $1_A\colon \Bbb N\to\{0,1\}$, $n\mapsto\begin{cases}1&n\in A\\0&n\notin A\end{cases}$ and then the transitive relation $R_A$ by $n\mathop{R_A}m\iff 1_A(n)<1_A(m)$. Note that $R_A\ne R_B$ for $A\ne B$, except that $R_\emptyset=R_{\Bbb N}$.

Answer 2

You already know that there are only $\mathfrak{c}$ binary relations on $\Bbb N$ and hence that there at most $\mathfrak{c}$ of them that are transitive. The hard part is finding $\mathfrak{c}$ different transitive relations on $\Bbb N$.

HINT: Every linear order is transitive. If $f:\Bbb N\to\Bbb N$ is a bijection, define a relation $\preceq_f$ on $\Bbb N$ by setting $m\preceq_fn$ if and only if $f(m)\le f(n)$.