2
$\begingroup$

Here is the definition I am using for a set to be countable:

A set is $X$ is said to be finite provided that there exists a bijection $f:\mathbb{N}_n\to X$ for some $n\in\mathbb{N}$.

A set $X$ is said to be countably infinite provided that there exists a bijection $f:\mathbb{N}\to X$.

A set is said to be countable provided that it is either finite or countably infinite.

I have already shown that any subset of a finite set is finite using strong induction.

Claim: Let $X$ be a countably infinite set. Then every set $Y$ such that $Y\subseteq X$ is countable.

So I have broken down the question into quantifiers like so. Let $\leftrightarrow$ denote a bijection.

$$\forall X|\exists f|\,f:\mathbb{N}\leftrightarrow X \Longrightarrow \forall Y|Y\subseteq X\,\exists h,g\exists n\in\mathbb{N}|\big((h:\mathbb{N}_n\leftrightarrow Y)\vee (g:\mathbb{N}\leftrightarrow Y)\big)$$

I have had a lot of trouble trying to prove this claim, and I think that breaking it down into quantifiers is even worse however, I got the thought to proceed by contradiction because I cannot see how to prove this directly. I begin by supposing $X$ is a countably infinite set. Then there exists a bijection $f:\mathbb{N}\leftrightarrow X$. Suppose $Y\subseteq X$. If $Y=X$ we are done. Now, suppose that every function $h:\mathbb{N}_n\to Y$ and $g:\mathbb{N}\to Y$ is not bijective.

This is as far as I got with this line of thought. I wanted to show that if a function $f:A\to B$ is bijective, then the function $f':A'\to f(A')$ is also bijective, where $A'\subseteq A$ and $f(A')$ is the image of $f$ restricted to $A'$. I was wondering if that even made sense as well. Then, I would immediately reach a contradiction if everything I have is correct.

I don't necessarily want an answer, but I really do want a nudge in the right direction or some other hints for writing this proof.

Edit: I cannot use any notions of cardinality or sequences.

$\endgroup$
1
  • $\begingroup$ What do you mean you can't use any notions of sequences? Sequences are just functions from $\mathbb{N}$ to some random set. $\endgroup$ Commented Sep 30, 2020 at 10:29

4 Answers 4

3
$\begingroup$

Here is a third variation, with some details left for you.

First, to solve your problem, it is enough to show that any subset of $\mathbb{N}$ is countable.

So fix a subset $Y$ of $\mathbb{N}$. You know that $\mathbb{N}_n$ is countable for all $n$, and you have already shown that any subset of a finite set is finite, hence countable. So you may assume that $Y$ is not a subset of $\mathbb{N}_n$ for any $n$, i.e., $Y$ is has no upper bound in $\mathbb{N}$.

Now define $g\colon \mathbb{N}\to Y$ inductively as follows. Let $g(0)=\min Y$. Suppose $g(0),\ldots,g(n)$ have already been defined. Define $g(n+1)=\min(Y\setminus\{g(0),\ldots,g(n)\})$. This minimum exists since $Y$ is not contained in $\{g(0),\ldots,g(n)\}$.

We claim that $g$ is a bijection. First, $g$ is injective by construction, since we always choose $g(n+1)$ distinct from $g(0),\ldots,g(n)$. Suppose $g$ is not surjective. Define $$ k=\min \{y\in Y:\text{$y$ is not in the image of $g$}\}. $$ Let $Z=Y\cap\mathbb{N}_{k-1}$ (i.e., $Z$ is all elements of $Y$ strictly less than $k$). Since $Z$ is finite and all of its elements are in the image of $g$, we can choose some $n$ such that $Z\subseteq\{g(0),\ldots,g(n)\}$. Then $k=\min (Y\setminus\{g(0),\ldots,g(n)\})$. So $k=g(n+1)$ by definition, which contradicts our assumption that $k$ is not in the image of $g$.

$\endgroup$
2
$\begingroup$

When $Y$ is finite, the proof is straightforward. Now suppose $Y$ is infinite. Since $X$ is countable, there is a bijection $f:\mathbb{N}\to X$. Write $X=\{x_1,x_2,x_3,\cdots\}$ where $x_i=f(i)$. Since $Y\subseteq X$, there is a subsequence $(i_1,i_2,i_3,\cdots)$ of $(1,2,3,\cdots)$ such that $Y=\{x_{i_1},x_{i_2},x_{i_3},\cdots\}$. Define $g:\mathbb{N}\to Y$ by $g(j)=x_{i_j}$. This gives the desired bijection.

$\textbf{Edit}$: Here is a rephrasing which use no notion of sequence. We have described the subset $Y$ as some subcollection of elements in $X$. Suppose elements in $Y\subseteq X$ have indexs $i_1,i_2,i_3,\cdots$ (all of them are just some natural numbers, $i$ is just some sort of 'placeholder variable' which is irrelavent). Define a function $h:\mathbb{N}\to\mathbb{N}$ by $h(j)=i_j$. Then our $g:\mathbb{N}\to Y$ is simply the composition $f\circ h$

$\endgroup$
2
  • $\begingroup$ How do you show that $g$ is bijective? Also, could you elaborate on the double index? It is kind of confusing right now. Also, I cannot use anything related to sequences $\endgroup$
    – C Squared
    Commented Sep 30, 2020 at 9:32
  • $\begingroup$ I have edited the solution to avoid 'sequence'. I have also added some explanation to the index $i_j$ and hope it is good enough to understand $\endgroup$
    – Ray
    Commented Sep 30, 2020 at 10:24
1
$\begingroup$

Perhaps a simpler way to think of it, but essentially the same as what Ray said.

We have a bijection $f:X\to \mathbb N$. (I assume $\mathbb N$ includes $0$; what follows can be easily modified if it needs to start at $1$.) Now define a function $g:Y\to\mathbb N$ as follows: $$g(y):=|\{z\in Y:f(z)<f(y)\}|.$$ Since $f$ is an injection, $g(y)\leq f(y)$ for each $y$, and in particular it is finite. Also $g$ is an injection, since if $y_1,y_2\in Y$ are different then without loss of generality $f(y_1)<f(y_2)$ and then $\{z\in Y:f(z)<f(y_1)\}\subset\{z\in Y:f(z)<f(y_1)\}$; the inclusion is strict since the second set includes $y_1$ and the first does not.

Suppose $g(y)=k>0$. Choose $w\in Y$ with $f(w)<f(y)$ maximising $f(w)$; since $\{z\in Y:f(z)<f(w)\}=\{z\in Y:f(z)<f(y),z\neq w\}$ we have $g(w)=k-1$. Thus the range $g$ is an initial segment of $\mathbb N$, so it is either the whole of $\mathbb N$ or it is $\mathbb N_n$ for some $n$. Since $g$ is injective it is a bijection onto its range, as desired.

$\endgroup$
1
$\begingroup$

Let $A\subseteq B$ with $B$ being countable. Consider an identity mapping from a set $A$ to a set $B$ such that $f(a)=a$ an injection, where $a\in A$ because $A$ is contained in $B$ so any identical mapping from $A$ to $A$ is also a mapping from $A$ to $B$. We have that $B$ is countable, then $A$ is countable.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .