# Countability of Subsets proof

• Dec 9th 2010, 03:00 PM
jstarks44444
Countability of Subsets proof
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!
• Dec 9th 2010, 03:09 PM
dwsmith
Here is my thought.

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

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

Therefore, $\displaystyle |B|\leq n$.
• Dec 9th 2010, 03:28 PM
Plato
Quote:

Originally Posted by dwsmith
Let A be the set. Then since A is countable, $\displaystyle |A|=n$.

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

There is a surjection $\displaystyle \Phi:N\to A$. Consider $\displaystyle \Phi\left(\Phi^{-1}(B)\right)$.
• Dec 9th 2010, 03:31 PM
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.
• Dec 9th 2010, 03:58 PM
Plato
Quote:

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.
• Dec 10th 2010, 04:13 AM
HallsofIvy
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.
• Dec 10th 2010, 07:19 AM
Also sprach Zarathustra
Quote:

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 $\displaystyle \mathbb{N}$ is countable.

Proof of the lemma:

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

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

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

$\displaystyle f$ is one-to-one.

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

$\displaystyle f$ is onto.

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

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

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

Noe back to the original theorem:

Subset of a countable set is countable.

Proof:

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