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