12
$\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$
18
  • $\begingroup$ Misleading title... What if you used a contradiction? $\endgroup$
    – abiessu
    Nov 4, 2013 at 15:03
  • 1
    $\begingroup$ Maybe you can use the well-order of the natural numbers. $\endgroup$ Nov 4, 2013 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, 2013 at 15:04
  • $\begingroup$ "countable finite or empty" There is something wrong in your question. $\endgroup$ Nov 4, 2013 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$ Nov 4, 2013 at 15:08

5 Answers 5

9
$\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
  • 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, 2013 at 20:17
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$
0
3
$\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$
1
$\begingroup$

We start with a bijective mapping

$\tag 1 f: \Bbb N \cong B$

Using $f$ we define another function

$\tag 2 \Phi: \mathcal P(B) \setminus \emptyset \to B$ $\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad X \mapsto f\bigr(\,\text{min}(f^{-1}(X))\,\bigr)$

If $A \subset B$ and $A$ is not finite, we can recursively build another function $g: \Bbb N \to A$ by setting

$\quad g(1) = \Phi(A)$

and with $g(1), g(2), \dots, g(n)$ set, defining

$\quad g(n+1) = \Phi\bigr(A \setminus \{g(1), g(2), \dots, g(n)\}\bigr)$

Exercise 1: Show that $g$ is a well-defined (recursive) function.

Exercise 2: Show that $g$ is a bijective correspondence,

$\tag 3 g: \Bbb N \cong A$


Here is another proof.

A set $C$ is countable if there exist a surjection $h: \Bbb N \to C$. In fact, an explicit bijection $\Bbb N \cong C$ can be constructed using $h$ (see, for example, this).

Addressing the interesting situation, let $B$ be an infinite set contained in a countable set $A$. Let $f: \Bbb N \cong A$ exhibit the $\text{1:1}$ correspondence. Choose any element $b_0 \in B$ and define

$$ F(m) = \left\{\begin{array}{lr} f(m), & \text{for } m \in f^{-1}(B) \\ b_0 , & \text{for } m \in \mathbb N \setminus f^{-1}(B) \end{array}\right\} $$

The mapping $F: \Bbb N \to B$ is a surjection.

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