Proof of a Countability Theorem

[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?

 

[Coin]

Wikipedia gives this definition for countable:

A set X is called countable if there exists an injective function
X --> N

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

 

[HallsofIvy]

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.

 

[Office_Shredder]

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

 

[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?

 

[Office_Shredder]

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

 

[CRGreathouse]

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

TeX for a brace is \{ or \}.

 

[Office_Shredder]

Thanks. I added them in

 

[Coin]

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.

There should be a partial inverse.

See here:

Every function with a right inverse is a surjection... assuming [the axiom of] choice, a function f: X → Y is surjective if and only if there exists a function g: Y → X such that, for every y in Y

f(g(y)) = y , (g can be undone by f)

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.