# Thread:

1. ## Finite function question

Suppose that f : X --> Y is given.

If X is finite, show that f(X) is also finite. Similarly, if X is countable,
show that f(X) is also countable.

2. Hello,
Originally Posted by flaming
Suppose that f : X --> Y is given.

If X is finite, show that f(X) is also finite. Similarly, if X is countable,
show that f(X) is also countable.
(talking about Y is an extraneous information)

The solution lies in the definition of $f(X)$

$f(X)=\{f(x) ~:~ x \in X\}$

For any $x \in X$, there is at least one element $y \in f(X)$ such that $y=f(x)$

It also means that for any $y \in f(X)$, there is at least one $x \in X$ such that $y=f(x)$
You can see that this sentence is exactly the definition of a surjection.

Hence $f ~:~ X \to f(X)$ is a surjection. By Cantor-Bernstein theorem (I think it's this one), we have $\text{Card}(X) \ge \text{Card}(f(X))$

If X is finite, then $\text{Card}(X) < \text{Card}(\mathbb{N})$. So we have ${\color{red}\text{Card}(f(X))} \le \text{Card}(X) < {\color{red}\text{Card}(\mathbb{N})}$. Thus f(X) is finite.

If X is countable, then $\text{Card}(X) \le \text{Card}(\mathbb{N})$, etc...

If you see any mistake, tell me, I'm learning this stuff too

3. Here are some remarks to clear up some questions raised by the above posts.
DEFINITION: $card(A) \leqslant card(B) \Leftrightarrow \,\exists \, g:A \mapsto B$ is an injection

Here is a most important theorem in many texts that deal with this material.
There is an injection $F:A \mapsto B$ if and only if there exists a surjection $<br /> G:B \mapsto A$.
As noted above there is a surjection $f:X \mapsto f(X)$.
So by that theorem we must have an injection $g:f(X) \mapsto X$
Now apply the definition.

BTW: I do not see how the Cantor-Schroder-Bernstein theorem applies

Also recall that a function $f:A \mapsto B$ is simply a subset of $A \times B$.
Where $A$ is the set of all first terms of the pairs and $f(A)$ is the set of second terms in the pairs.
So there is a natural expectation that the $card(f(A)) \leqslant card(A)$.

#### Search Tags

View Tag Cloud

Copyright © 2005-2013 Math Help Forum. All rights reserved.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 23, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9602869153022766, "perplexity_flag": "head"}