# Thread: Countability of Subsets proof

1. ## 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!

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

3. 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)$.

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

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

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

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