I believe I have these all correct, but if I made an error could you lend a hand and possibly explain why I was mistaken? Thanks in advance.

Consider the following sets:





$X_{5}=\{R|R$ is a relation on $\{1,2,3,4,5\}\}$

$X_{6}=\{R|R$ is a relation on $\mathbb{N}\}$

$X_{7}=\{R|R$ is a relation on $\mathbb{R}\}$







a) Which sets above are finite?


b) For the sets which are finite, order then by ascending cardinality.


c) Which sets above are countable?


d) Which sets above are countably infinite?


e) Which sets above are uncountable?


f) Which sets have cardinality greater than c = |R|?


  • 2
    $\begingroup$ This is gonna take very long to answer, but just glancing, you are missing $X_4$ for finiteness. The question asks for the particular set, not the objects. $\endgroup$ – IAmNoOne Jun 21 '16 at 1:26
  • 1
    $\begingroup$ $X_{12}$ is finite too, for similar reasons. $\endgroup$ – lulu Jun 21 '16 at 1:29
  • 1
    $\begingroup$ $X_{6}$ isn't finite. Let $f : \mathbb{N} \to \mathbb{N}$ be a bijection, and let $R_f$ be defined on $\mathbb{N}$ be defined by $(a R_f b) \iff \left( f^{-1}(a) \leq f^{-1}(b) \right)$. You should be able to construct infinitely many such bijections without much difficulty. $\endgroup$ – AJY Jun 21 '16 at 1:47
  • 1
    $\begingroup$ Part $f$ is wrong. $X_8$ has the same cardinality as $\mathbb R$. $\endgroup$ – Matt Samuel Jun 21 '16 at 2:08
  • 3
    $\begingroup$ @shai Since your comment got an upvote I think it's important to point out that what you say is not true. $\mathbb N^{\{0,1\}}$ is the set of all functions from a two element set into the natural numbers and hence is countable. $\endgroup$ – Matt Samuel Jun 21 '16 at 2:34

Your Answer

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

Browse other questions tagged or ask your own question.