4

Let $f: \Bbb N \to P(\Bbb N)$. Present 2 different sets of natural numbers A, B that are not in Im(f)

What I did:

First idea: I defined an injective function f that takes each n and returns it's singleton. Now each other member of $P(\Bbb N)$ which is not a singleton is not in $Im(f)$.

Does this "proof" suffice? Is there somehow a way to generalize it even more?

Second idea: I took the numbers 0 and 1 only, if I define a function from a set of {0,1} to P({0,1}) I'll always have 2 sets left out of the image (since P({0,1}) has 4 sets and {0,1} has only 2 members). I thought of somehow generalizing this by induction, but don't really have an idea how.

Thanks for your help.

Cameron Buie
  • 102,994
jreing
  • 3,297
  • 2
    Your first example doesn't work because it is a specific example. Just because you found one example where the statement is true doesn't imply the entire statement is true. The second statement is working a little bit better, but you aren't presenting $2$ different sets, only arguing that there are these sets. You'll also run into a problem when the set is infinite since induction only proves it for finitely many elements. – Clayton Mar 21 '13 at 14:28
  • Thanks. I think I found the solution: http://math.stackexchange.com/questions/214807/non-existence-of-a-surjective-function-from-a-set-to-its-subsets-cantors-theor?rq=1 ... The question is, using D from this guy's answer I have one set, does it suffice to say that any subset of that "D" is also a different set not in Im(f)? – jreing Mar 21 '13 at 14:29
  • 1
    That solution gives you one set of natural numbers not in the image. You'll still need to exhibit another. – Cameron Buie Mar 21 '13 at 14:33
  • hhh, I just noticed that now :-) – jreing Mar 21 '13 at 14:34

2 Answers2

1

Put $$\eqalign{ A&:=\bigl\{2j\ \bigm|\ j\geq 0,\ 2j\notin f(j)\bigr\}\ \cup\ \bigl(\{1\}\cap f(0)\bigr)\ ,\cr B&:=\bigl\{2j+1\ \bigm|\ j\geq 0,\ 2j+1\notin f(j)\bigr\}\ .\cr}$$ Then for each $j\geq0$ the set $A$ contains the number $2j$ iff $f(j)$ does not contain this number, and similarly the set $B$ contains the number $2j+1$ iff $f(j)$ does not contain this number. Therefore both $A$ and $B$ are different from all sets $f(j)$. In addition the set $A$ contains the number $1$ iff $1\in f(0)$, in which case $B$ does not contain $1$. It follows that $A\ne B$.

Christian Blatter
  • 226,825
0

Once you have one set $A$ which is not in $\text{Im}(f)$, you can construct a new function $g:\mathbb N \to \mathcal P(\mathbb N)$ whose image $\text{Im}(g)$ is equal to $\text{Im}(f) \cup A$ (can you see how?). Any set of naturals that doesn't belong to $\text{Im}(g)$ is not in the image of $f$, and is different from $A$ (can you see why?).

Erick Wong
  • 25,198
  • 3
  • 37
  • 91