Countability proof.

**mathsohard** · November 29th 2010, 08:01 AM

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

**mathsohard** · November 29th 2010, 08:07 AM

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

**FernandoRevilla** · November 29th 2010, 08:22 AM

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

**emakarov** · November 29th 2010, 08:33 AM

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?

**mathsohard** · November 29th 2010, 08:40 AM

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

**emakarov** · November 29th 2010, 09:14 AM

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.

Thread: Countability proof.

LinkBack

Thread Tools

Display

Countability proof.

Similar Math Help Forum Discussions

Interval Countability proof

Countability of Subsets proof

Inductive Proof of Countability of Algebraic Numbers

Countability Proof

Proof of countability

Search Tags