Let $f:\mathbb N\to \mathbb P(\mathbb N)$ be given by the following expression: $$f(n)=\{m\in\mathbb N\mid 3m-10>n\}$$ Find a set $A$ such that $A \notin \mathrm{Rng}{f}$.

I came up with $A=\{n\in\mathbb N\mid n\notin f(n)\}$, but I don't believe that it works because $6\in f(6)$.

  • 1
    $\begingroup$ Where's the contradiction? Does that mean $A=f(6)$? No. It means that $6\notin A$ and therefore that $A\neq f(6)$. $\endgroup$ – Thomas Andrews Apr 19 '15 at 22:50
  • $\begingroup$ Of course, you could just take $A=\{1\}$. Since $1\notin f(n)$ for any $n$, so this would mean that $A\cap f(n)=\emptyset$ for all $A$. Or you could take $A$ any finite set, since $f(n)$ is always infinite. Or you could take $A$ to be the set of all primes, since if $m\in f(n)$ then $m+1\in f(n)$, so $f(n)$ contains all numbers larger than its least element. $\endgroup$ – Thomas Andrews Apr 19 '15 at 22:54

The set $A=\{n\in\mathbb N\mid n\notin f(n)\}$ should work for every application $f$, for instance in your application it's clear that $n\in f(n)$ if and only if $3n-10> n$ which means that: $$A=\{0,1,2,3,4,5\} \tag 1$$ now assume that there exists some $x$ such that $f(x)=A$ then $A$ is infinte because always $f(x)$ is infinite for any $x$, this contradicts $(1)$.

Note that the set $A$ always works without any restriction on $f$, and it's a part of Cantor's argument that $\mathbb N$ and $\mathbb P(\mathbb N)$ don't have the same cardinal.


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.