# Proof of a Countability Theorem

1. Nov 28, 2007

### patfan7452

Hey all,

Can anyone prove this theorem?

Let N (natural numbers) ---> X be an onto function. Then X is countable.

I've been staring at it for 3 hours and really can't come up with anything. Any help?

2. Nov 28, 2007

### Coin

Wikipedia gives this definition for countable:
You have given us the opposite: a surjective function N --> S.

So, let "f" be your N --> X.

Now consider the inverse of f. It is an injective function X --> N. Because you have an injective function X --> N, you have proven X is countable.

If you want to get super fancy, you could even use f to define a countable ordering for the members of X, but this much shouldn't be necessary...

3. Nov 28, 2007

### HallsofIvy

Staff Emeritus
What do you mean by the "inverse" of f? If you are only given that f is surjective, it may not be injective and so may not have an inverse.

4. Nov 28, 2007

### Office_Shredder

Staff Emeritus
Let f be the function that maps N onto X

If f-1({x}) is the set of natural numbers s.t f(n)=x. Clearly these partition N, and all of them are non-empty. hence, for each x, there exists some n s.t. f(n)=x. Then, defining g(x) by g(x)=n for some n satisfying the f(n)=x, we can map X bijectively to some subset of N (if you want a more rigorous definition of g, let g(x) be the minimum element of f-1(x), which exists by well ordering). Hence X is countable

Last edited: Nov 28, 2007
5. Nov 28, 2007

### patfan7452

Thanks for the replies. Shredder,

Why does "f f-1({x}) is the set of natural numbers s.t f(n)=x" clearly partition N? Also, why is the map from X to some subset of N bijective?

6. Nov 28, 2007

### Office_Shredder

Staff Emeritus
$$f^{-1}( \{ x \} )$$ partitions N as for each n, f(n) maps to exactly one x. To be a bit more technical, it should be clear that $$f^{-1}(X)=N$$ i.e. the set of natural numbers that map to somewhere in the set X is all of N, but $$\bigcup_{x \epsilon X} f^{-1}( \{ x \} ) = f^{-1}( \bigcup_{x \epsilon X} \{ x \} ) = f^{-1}(X)=N$$ and for $$x_1, x_2 \epsilon X$$ if $$n \epsilon f^{-1}( \{ x_1 \} ), f^{-1}( \{ x_2 \} )$$ then by definition $$f(n)=x_1, x_2$$ that is $$x_1=x_2$$ Obviously this can't happen, so they have empty intersections.

Not all maps from X to a subset of N are bijective, just the one I described where you pick for each $$x \epsilon X$$ precisely ONE $$n_x$$ s.t. $$f(n_x)=x$$ then if this map is called g(x), g(x) is 1-1, and $$\{ n_x \epsilon N | x \epsilon X \}$$ is obviously a subset of N. So g is a bijection between X and this set

EDIT: I'm missing a lot of curly braces (which kind of makes sense, as they're supposed to indicate a block should be treated as an individual thing, and hence are invisible), but is there a way to make them show up? Alternatively, you'll have to imagine that where it looks like I'm describing a set, I am indeed

Last edited: Nov 28, 2007
7. Nov 28, 2007

### CRGreathouse

TeX for a brace is \{ or \}.

8. Nov 28, 2007

### Office_Shredder

Staff Emeritus

9. Nov 28, 2007

### Coin

There should be a partial inverse.

See here:

We're not really interested in reversing the surjection, what we're interested in is the existence of an injection from Y into X, which "g" from the quote provides.