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

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)

• Often proving a set has cardinality $c$ is most easily done by separating the implications of being at most cardinality $c$ and at least cardinality $c$. You've addressed the first implication with your point (1). For the other direction it suffices to work with a nice subset of the transitive relations, one that is clearly big enough to be uncountable. – hardmath Sep 23 '16 at 10:10
• You are right, and it is indeed easy to prove that the cardinality of this group is at most c. The other direction is always more difficult, and I can't figure out how to prove it – S. Peter Sep 23 '16 at 10:15
• My hint is to construct an uncountable number of equivalence relations. Equivalence relations are always transitive! – hardmath Sep 23 '16 at 10:17
• equivalence relations are always transitive and are uncountable but who says it's cardinal is c and not ℵ0? – S. Peter Sep 23 '16 at 10:23
• @S.Peter There are at least as many equivalence relations on $X$ as there are subsets of $X-\{x_0\}$ – Hagen von Eitzen Sep 23 '16 at 10:55

## 2 Answers

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}$.

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