Countability proof.

Printable View

November 29th 2010, 08:01 AM
mathsohard

Countability proof.

I need help on proving

(1) prove that if B http://www.mathhelpforum.com/math-he...ab35a80a37.png A and A is countable, then B is countable

(2) prove that if B http://www.mathhelpforum.com/math-he...ab35a80a37.png A, A is infinite, and B is finite, then A\B is infinite

I don't even know where to start... THx
November 29th 2010, 08:07 AM
mathsohard

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....
November 29th 2010, 08:22 AM
FernandoRevilla

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
November 29th 2010, 08:33 AM
emakarov

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?
November 29th 2010, 08:40 AM
mathsohard

I get the (2) part , however could you explain more on (1) part please???
November 29th 2010, 09:14 AM
emakarov

Quote:

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.