Countability of Subsets proof

**jstarks44444** · December 9th 2010, 03:00 PM

Prove: A subset of a countable set is countable.

I began the proof saying we will assume a set B which is a subset of A where A is countable. By the following proposition, which says,

" the nonempty set A is countable if and only if there exists a surjection N --> A ",

there exists a surjection N --> A

Then I think there exists a surjection from N --> B, which would mean B is countable as well, but I am not sure how to justify this statement. Any help with this proof would be appreciated!

**dwsmith** · December 9th 2010, 03:09 PM

Here is my thought.

Let A be the set. Then since A is countable, $|A|=n$ .

Let $B\subseteq A$ . $|B|$ can, at most, be equal to set A.

Therefore, $|B|\leq n$ .

**Plato** · December 9th 2010, 03:28 PM

Originally Posted by dwsmith

Let A be the set. Then since A is countable, $|A|=n$ .

That statement is false. The set $A$ could be infinite.
Perhaps you are confused as to what countable means.

There is a surjection $\Phi:N\to A$ . Consider $\Phi\left(\Phi^{-1}(B)\right)$ .

**dwsmith** · December 9th 2010, 03:31 PM

In my books, when we discuss countable infinite, we say countable infinite not countable. So I was under the impression we were dealing with a finite set A.

**Plato** · December 9th 2010, 03:58 PM

Originally Posted by dwsmith

In my books, when we discuss countable infinite, we say countable infinite not countable. So I was under the impression we were dealing with a finite set A.

It appears that you have the misfortune of having a non-standard textbook.
COUNTABLE.

**HallsofIvy** · December 10th 2010, 04:13 AM

A "surjection" From N to X is a function such that, for all x in X, there exist n such that f(n)= x.

Let x be a member of B. Since B is a subset of A, x is a member of A. Since A is countable, there exist a surjection, f, from N to A, so there exist some n such that f(n)= x. Since this is true for all x in B, there exist a surjection from N to B.

**Also sprach Zarathustra** · December 10th 2010, 07:19 AM

Originally Posted by jstarks44444

Prove: A subset of a countable set is countable.

I began the proof saying we will assume a set B which is a subset of A where A is countable. By the following proposition, which says,

" the nonempty set A is countable if and only if there exists a surjection N --> A ",

there exists a surjection N --> A

Then I think there exists a surjection from N --> B, which would mean B is countable as well, but I am not sure how to justify this statement. Any help with this proof would be appreciated!

Lemma:

Every subset of $\mathbb{N}$ is countable.

Proof of the lemma:

Let $B\subset\mathbb{N}$ . If $B$ is finite, it is obvious that $B$ is countable.
If $B$ is infinite, we will find bijection $f:B\to\mathbb{N}$ , with that we will show that $B$ is countable.

For every $x\inB$ , set of elements of $B$ that are smaller than $x$ is finite.
Let us now define the function $f:B\to\mathbb{N}$ :

For every $x\inB$ , $f(x)$ will be the number of elements that are smaller than $x$ .

$f$ is one-to-one.

(Proof) If $a$ and $b$ are elements of $B$ and $a<b$ , each element of $B$ that smaller than $a$ is smaller also than $b$ , and $a$ himself isn't smaller that $a$ , but smaller that $b$ . Hence $f(b)\geq f(a)+1$ , so that $f(a) \neq f(b)$ .

$f$ is onto.

(Proof) We will prove that for every $n\in\mathbb{N}$ have an origin.
Proving by induction on $n$ .

$B$ is infinite, hence $B$ isn't empty, therefor $B$ has first element- $a_0$ , it's obvious that $f(a_0)=0$ .
Suppose that there is origin for $n$ , and we prove that there is origin to $n+1$ , let $a$ be origin for $n$ . $B$ is infinite, set of elements of $B$ that less than $a$ is finite, hence set of elements of $B$ that greater from $a$ is not empty. Let $b$ the first such element. Elements of $B$ that are smaller than $b$ they are elements of $B$ that are smaller than $a$ adding $a$ , so we get that $f(b)=n+1$ , hence $n+1$ has an origin. We proved that $f$ is onto.

$f$ is bijective, therefor $B\sim\mathbb{N}$ , hence $B$ countable.

Noe back to the original theorem:

Subset of a countable set is countable.

Proof:

Let $A$ be countable set. If A is finite, every subset of $A$ is also finite, and therefor countable.
If $A$ is infinite, $A\sim\mathbb{N}$ . Let $B$ be a subset of $A$ , and we will prove that $B$ is countable. Let $f:A\to \mathbb{N}$ be a bijection, so $f {[ B ]} \subseteq \mathbb{N}$ , and therefor it countable.
The function $g:B\to f{[B]}$ , so that for all $x\in B$ $g(x)=f(x)$ , is bijection, therefor $B\sim f{[B]}$ , the conclusion is that $B$ countable.

Thread: Countability of Subsets proof

LinkBack

Thread Tools

Display

Countability of Subsets proof

Similar Math Help Forum Discussions

Interval Countability proof

Countability proof.

Inductive Proof of Countability of Algebraic Numbers

Countability Proof

Proof of countability

Search Tags