# Thread:

1. ## Countability proof.

I need help on proving

(1) prove that if B A and A is countable, then B is countable

(2) prove that if B A, A is infinite, and B is finite, then A\B is infinite

I don't even know where to start... THx

2. I have a theorem which says
Suppose A is a set. The following statements are equivalent:
1. A is countable
2. Either A = empty or there is a function f:z+ -> A that is onto.
3. There is a function f:A -> z+ that is one-to-one

I am supposed to use those however I am stuck....

3. If $A$ is denumerable then $A=\{a_1,a_2,\ldots\}$ . If $B=\emptyset$ then, $B$ is finite . If $B\neq \emptyset$ let $n_1$ be the least positive integer such that $a_{n_1}\in B$, let $n_2$ be the least positive integer such that $n_2>n_1$ and $a_{n_2}\in B$ ...

Could you continue?

Regards.

Fernando Revilla

4. You can use the equivalent condition #3 to show (1). Namely, suppose $B\subseteq A$ and there exists a one-to-one function $f:A\to\mathbb{Z}^+$. Consider the restriction of f on B, i.e., the function whose domain is B and that acts just like f on any $x\in B$. Is this restriction still one-to-one?

For (2), note that $A = B\cup(A\setminus B)$. What happens when $A\setminus B$ is finite?

5. I get the (2) part , however could you explain more on (1) part please???

6. could you explain more on (1) part please???
Whom are you asking? Fernando suggests using condition #2 to prove (1), i.e., that B is countable. Going with #2, let's assume that there is an onto function $f:\mathbb{Z}^+\to A$ and that B is nonempty, i.e., there exists some fixed $x_0\in B$. I think it is easier to construct another function $g:\mathbb{Z}^+\to B$ as follows:

$g(n)=<br /> \begin{cases}<br /> x_0 & f(n)\notin B\\<br /> f(n) & \text{otherwise}<br /> \end{cases}$

You have to check that indeed $g:\mathbb{Z}^+\to B$ and that g is onto.

If you are going ti use #3 to show (1), then assume that there exists an $f:A\to\mathbb{Z}^+$. Consider $g(x)$ such that $g(x)=f(x)$ for $x\in B$ and $g(x)$ is undefined otherwise. You need to show that $g:B\to\mathbb{Z}^+$ and that g is one-to-one.
{"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": 26, "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": true}, "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.9442981481552124, "perplexity_flag": "head"}