7
$\begingroup$

How is it proved that if $$A \subset B\ \text{with}\ B\ \text{countable} $$ then $A$ is either countable, finite, or empty? I think the proof involves a $1-1$ correspondence between $\mathbb{N}$ and $A$ but other than that I do not know how to proceed.

EDIT: I have checked the solution and it advises me to proceed as follows. " As a start to a definition of $$g: \mathbb{N} \rightarrow A$$ set $$g(1)=f(n_1) $$ Then show how to inductively continue this process to produce a $1-1$ function $g$ from $\mathbb{N}$ onto $A$."

So the proof according to my book involves induction.

$\endgroup$
  • $\begingroup$ Misleading title... What if you used a contradiction? $\endgroup$ – abiessu Nov 4 '13 at 15:03
  • 1
    $\begingroup$ Maybe you can use the well-order of the natural numbers. $\endgroup$ – Stefan Hamcke Nov 4 '13 at 15:03
  • $\begingroup$ Thank you for your responses but since I am a begginer, could you please be a little more specific? $\endgroup$ – JohnK Nov 4 '13 at 15:04
  • $\begingroup$ "countable finite or empty" There is something wrong in your question. $\endgroup$ – Michael Greinecker Nov 4 '13 at 15:06
  • 1
    $\begingroup$ The inclusion of $A$ in $B$ gives via the bijection $B\equiv\Bbb N$ an injection $i:A\to\Bbb N$. Now you can define a function $f: 1↦\min i[A],\ 2↦\min i[A]\setminus\{f(1)\},\ 3↦\min i[A]\setminus\{f(1),f(2)\},...$ $\endgroup$ – Stefan Hamcke Nov 4 '13 at 15:08
6
$\begingroup$

Via the bijection $\Bbb N\cong B$ we have an injection $i:A\to\Bbb N$.

Define $$f(n+1)=\min\{k∈i[A]∣k>f(n)\}$$ for $n≥1$ and $$f(1)=\min i[A]$$

We claim that for each $n$ we have $\{f(1)<f(2)<...<f(n)\}$ is a subset of $i[A]$ and contains each $i(a)$ less than $f(n)$.
Proof: Induction over $n$:
For $n=1$ clearly $f(1)∈i[A]$, and since there is no $i(a)<f(1)$, the claim is true.
Assume that the statement is true for $n$. Then by definition of $f$, the number $f(n+1)$ is larger than $f(n)$, so the set $\{f(1)<...<f(n)<f(n+1)\}$ is a subset of $i[A]$. Since $f(n+1)$ is the minimal element of $i[A]$ larger than $f(n)$, it must contain each $i(a)$ less than $f(n+1)$.

So we have shown that $f:\Bbb N↦i[A]$ is an injection. Now, for $a\in A$ we have the natural number $l=i(a)$. Since $l$ is less than $f(n)$ for some $n\in\Bbb N$, $f$ being strictly increasing, it must thus be one of $f(1),f(2),...,f(n-1)$.

$\endgroup$
8
$\begingroup$

Any subset of a countable set is countable.

Take $A\subset B$ where $B$ is countable. Then $|A|\leq|B|$ since $A\subset B$. By definition, $|A|\leq|B|$ if there is a one-to-one function from $A$ into $B$. We also see that $|B|\leq\aleph_0$ since $B$ is countable. Thus, $|A|\leq\aleph_0$.

$\endgroup$
  • 1
    $\begingroup$ Your response is very intuitive and thank you for it but I fear that I am required to produce a bisection for that exercise. $\endgroup$ – JohnK Nov 4 '13 at 20:17
2
$\begingroup$

Hint: Define an injection $f:B \to \mathbb{N}$ (this is possible as B is countable). Define the inclusion mapping $I:A \to B$. Consider $f\circ I:A \to \mathbb{N}.$ What can you say about $I$? What can you then say about $f \circ I$? What can you then conclude about $A$?

$\endgroup$
0
$\begingroup$

Hint: Suppose $f$ is the function that maps $B$ to $\mathbb{N}$, sort each item in $B$ by it's $f$ value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.