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)

  • $\begingroup$ 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. $\endgroup$ – hardmath Sep 23 '16 at 10:10
  • $\begingroup$ 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 $\endgroup$ – S. Peter Sep 23 '16 at 10:15
  • $\begingroup$ My hint is to construct an uncountable number of equivalence relations. Equivalence relations are always transitive! $\endgroup$ – hardmath Sep 23 '16 at 10:17
  • $\begingroup$ equivalence relations are always transitive and are uncountable but who says it's cardinal is c and not ℵ0? $\endgroup$ – S. Peter Sep 23 '16 at 10:23
  • 1
    $\begingroup$ @S.Peter There are at least as many equivalence relations on $X$ as there are subsets of $X-\{x_0\}$ $\endgroup$ – Hagen von Eitzen Sep 23 '16 at 10:55

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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