# Help showing that every subset of a countably infinite set is countable

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.

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

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

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

• 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 Commented Sep 30, 2020 at 9:32
• 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
– Ray
Commented Sep 30, 2020 at 10:24

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) 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) and then $$\{z\in Y:f(z); 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) maximising $$f(w)$$; since $$\{z\in Y:f(z) 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.

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.