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