Prove that If $A \subseteq B$ and $B$ is countable, then $A$ is either countable or finite. I would like a verification of my attempt. I'm open minded to any suggestions that you may have for me.
Proof.
Assume that $B$ is a countable set. Thus, by definition $\exists f: \mathbb{N} \to B$ such that $f$ is bijective. Let $A \subseteq B$ be an infinite subset of $B$. We must show that $A$ is countable. Let $n_1 = \min \{n \in \mathbb{N}: f(n) \in A \}$. As a start to a definition of $g: \mathbb{N} \to A$, set $g(1) = f(n_1)$. Take $n_k \in \{n \in \mathbb{N}: f(n) \in A\}$ for some arbitrary $k \in \mathbb{N}$. Then, set $g(k) = f(n_k)$. Now define $n_{k+1} = \min\{n \in \mathbb{N}: f(n) \in A \big/ \{f(1), f(2), ..., f(k)\}\}$ and set $g(k+1) = f(n_{k+1})$. That way, by induction, $g: \mathbb{N} \to A$ is defined for all natural numbers and thus $A$ is countable. Now if $A$ were a finite subset of $B$ then clearly, $A$ is finite. $\quad$ QED.
Thank you in advance!
 A: I decided to go ahead and write up an answer so that I am not limited by characters.
The idea behind this sort of approach is to define a bijection between $A$ and $\mathbb{N}$ by first taking the minimum of
$$f^{-1}(A) = \{n\in \mathbb{N}: f(n)\in A\},$$ then the second smallest element, and so on. You can do this by defining a sequence $(n_k)$ recursively.
$$n_1 := \min f^{-1}(A)$$ is the smallest element of $f^{-1}(A)$, which exists by well-ordering of $\mathbb{N}$
Then for each $k>1$, you can define
$$n_k := \min \left(f^{-1}(A)\setminus \{n_1,\ldots,n_{k-1}\}\right),$$
which also exists by well-ordering. You should be able to verify that
$$f^{-1}(A)\setminus \{n_1,\ldots,n_{k-1}\} = \{n \in \mathbb{N}: f(n) \in A\setminus\{f(n_1),\ldots,f(n_{k-1})\}\}$$
using that $f$ is a bijection.
The definition of $n_k$ you gave does not preclude that $n_k=n_1$ because you didn't remove $f(n_1)$ from the set under consideration.
Once you have the sequence $(n_k)$, you can define $g:\mathbb{N} \to A$ just as you did and prove that it's both well-defined and a bijection.
A: Without going too deeply into the details, allow me to present a hopefully instructive way to establish this result. To organise the formal framework of our approach, let us use the name induction triplet to refer to any object of the form $(A, a, f)$ where $A$ is an arbitrary set, $a \in A$ is a certain element and $f \colon A \to A$ is a certain self-map of $A$. Furthermore, given two such triplets $(A, a, f)$ respectively $(B, b , g)$, let us call a morphism of inductive triplets any map $\varphi \colon A \to B$ such that $\varphi(a)=b$ and $\varphi \circ f=g \circ \varphi$.
Agreeing once and for all to denote by:
$$\begin{align} 
\varsigma \colon \mathbb{N} &\to \mathbb{N} \\
\varsigma(n)&=n+1
\end{align}$$
the successor function on the naturals, it is clear that $(\mathbb{N}, 0, \varsigma)$ is an induction triplet, which we shall refer to as the fundamental triplet (for we shall indeed see later on that it plays a remarkable role in the theory of such triplets).
Before we move on, let us introduce a particular class of induction triplets, to which we shall refer as Peano triplets (this - by the way - is merely ad-hoc terminology I am proposing in order to convey ideas in this setting): we will call triplet $(A, a, f)$ Peano if it satisfies the following two axioms:

*

*$f$ is an injection and $a \notin f[A]$

*any subset $M \subseteq A$ such that $a \in M$ and $f[M] \subseteq M$ (i.e. $M$ is stable or closed with respect to $f$) is necessarily $A$ itself.

Let us remark at this stage that the fundamental triplet is in particular a Peano triplet (this is nothing else than a reformulation of the induction principle).
So far the expound might have seemed arid and abstract, but this is whence the matter starts to become interesting. The technical deductive details of the ensuing proposition will of course depend on the axiomatic system one uses to formalise set theory, but nevertheless any decent axiomatic system for set theory should admit as a theorem (i.e., in plain terms, should make it possible for one to demonstrate within the given deductive system) the following:

Fundamental theorem of induction (recursion). Given any induction triplet $(A, a, f)$ there exists a unique morphism of triplets $\varphi \colon \mathbb{N} \to A$ between the fundamental triplet and the given one. Furthermore, we have the following additional implications:


*

*if the triplet $(A, a, f)$ satisfies the first axiom of Peano triplets, then the unique morphism $\varphi$ is injective

*if the triplet $(A, a, f)$ satisfies the second axiom of Peano triplets, then the unique morphism $\varphi$ is surjective (lovely duality, isn't it!)

*therefore, if the given triplet $(A, a, f)$ is Peano, the unique morphism $\varphi$ is bijective.

To break down the meaning of this fundamental theorem, what it claims is the intuitively clear fact of the existence of a unique sequence $x \in A^{\mathbb{N}}$ (given by $x=\left(\varphi(n)\right)_{n \in \mathbb{N}}$) satisfying at the same time the initial condition $x_0=a$ as well as the recurrence relation $x_{n+1}=f(x_n)$ for any $n \in \mathbb{N}$.
Let us apply this theory of triplets to the deduction of the following result:

Proposition. Let $(A, R)$ be a well-ordered set ($R$ being therefore an order relation on the support-set $A$, which it well-orders) subject to the following hypotheses: $1^{\circ}.$ $A$ is infinite and $2^{\circ}.$ for any $x \in A$ the interval $\left(\leftarrow, x\right]_{R}\colon=\left\{t \mid t \leqslant_{R} x\right\}$ is finite. Under these conditions, $A$ is equipotent to $\mathbb{N}$.

Proof. $A$ being infinite it is nonempty and since it is well-ordered (by $R$) it has a minimum (with respect to $R$), which we will denote by $0_A \colon=\mathrm{min}_R A$. Furthermore, in view of the infinity of $A$ we gather from condition $2^{\circ}$ that $A$ cannot have a maximum. Since well-ordered sets are totally ordered, this means that for any given $x \in A$ the interval $\left(x, \rightarrow\right)_R \colon=\left\{y \mid y>_R x\right\} \neq \varnothing$ is nonempty (otherwise $x$ would be the maximum of $A$), which allows us to consider the map:
$$\begin{align}
\sigma \colon A &\to A \\
\sigma(x)&=\mathrm{min}_R \left(x, \rightarrow\right)_R,
\end{align}$$
none other than the successor map on $A$ with respect to $R$; by this we mean precisely that $\sigma(x)$ is the successor of $x$ for each $x \in A$, which can be also described by the relations $x<_R \sigma(x)$ and $\left(x, \sigma(x)\right)_R=\varnothing$ (no element strictly in between $x$ and $\sigma(x)$).
It is easy to see that the induction triplet $(A, 0_A, \sigma)$ satisfies the first axiom of Peano triplets (since the minimum $0_A$ cannot be the successor of any element and $\sigma$ is strictly increasing on a totally ordered set, hence injective), fact by virtue of which we infer from the fundamental induction theorem that the unique morphism of triplets $\varphi$ between the fundamental triplet and $(A, 0_A, \sigma)$ is injective.
To establish our claim it suffices to show that $\varphi$ is also surjective. We proceed by contradiction, assuming that $\varphi\left[\mathbb{N}\right] \subset A$ and therefore that $A \setminus \varphi\left[\mathbb{N}\right] \neq \varnothing$. Since we are working in a well-ordered set, there exists $a \colon=\mathrm{min}_R \left(A \setminus \varphi\left[\mathbb{N}\right]\right)$. We will succeed to end in a contradiction if we show that $\varphi\left[\mathbb{N}\right] \subseteq \left(\leftarrow, a\right)_R$, for indeed the right-hand term must on the one hand be finite, as a subset of the finite interval $\left(\leftarrow, a\right]_R$ (condition $2^{\circ}$), whereas the left-hand term $\varphi\left[\mathbb{N}\right]$ must be on the other hand infinite, since by virtue of $\varphi$'s injectivity it is a bijective copy of the infinite set $\mathbb{N}$.
In order to show the desired inclusion $\varphi\left[\mathbb{N}\right] \subseteq \left(\leftarrow, a\right)_R$, it suffices to establish that: $$\left[0_A, \varphi(n)\right]_R=\varphi\left[\left[0, n\right]_{\mathrm{O}}\right] \tag{*}$$
for any $n \in \mathbb{N}$, where by $\mathrm{O}$ I have taken the liberty to denote the standard order on the naturals. Indeed, having succeeded to establish relation ($*$), we either have $\varphi(n)<_R a$ for all $n \in \mathbb{N}$ or - since $R$ is a total order - there must exist $k \in \mathbb{N}$ such that $a \leqslant_R \varphi(k)$; the latter option would signify that $a \in \left[0_A, \varphi(k)\right]_R=\varphi\left[\left[0, k\right]_{\mathrm{O}}\right]$ and would entail $a \in \varphi\left[\mathbb{N}\right]$, which is impossible by definition of $a$.
Finally, the desired relation ($*$) is easily established by induction, the base case being trivial and the induction step relying on the crucial relation $\left[0_A, \sigma(x)\right]_R=\left[0_A, x\right]_R \cup \{\sigma(x)\}$, valid for any $x \in A$. More explicitly, if for given $n \in \mathbb{N}$ the relation ($*$) is assumed to hold, we immediately infer that:
$$\begin{align}
\left[0_A, \varphi(n+1)\right]_R&=\left[0_A, \sigma(\varphi(n))\right]_R \\
&=\left[0_A, \varphi(n)\right]_R \cup \{\varphi(n+1)\} \\
&=\varphi\left[\left[0, n\right]_{\mathrm{O}}\right] \cup \{\varphi(n+1)\} \\
&=\varphi\left[\left[0, n\right]_{\mathrm{O}} \cup \{n+1\}\right] \\
&=\varphi\left[\left[0, n+1\right]_{\mathrm{O}}\right],
\end{align}$$
which is none other than relation ($*$) for $n+1$. This concludes the proof. $\Box$
In passing, let us also remark that (preserving the notation used in the proof above) since $\varphi(n+1)=\sigma(\varphi(n))>_R \varphi(n)$ for any $n \in \mathbb{N}$, $\varphi$ is actually a strictly increasing bijection and as it is defined on a totally ordered set it moreover is an order isomorphism (in other words, its inverse is also increasing). Thus, the proposition above completely classifies any and all the well-ordered sets satisfying conditions $1^{\circ}$ and $2^{\circ}$ as being isomorphic to the well-ordered set $(\mathbb{N}, \mathrm{O})$.
The above proposition can in particular be applied to the end of producing the result you seek to prove, namely that:

Corollary. If $M \subseteq \mathbb{N}$ is infinite then $|M|=|\mathbb{N}|$.

Proof. Denoting as above the standard order on naturals by $\mathrm{O}$ we consider the well-ordered set $(M, \mathrm{O}_{|M})$ (where $\mathrm{O}_{|M} \colon=\mathrm{O} \cap (M \times M)$ is the restriction of $\mathrm{O}$ to $M$) and we notice that it satisfies the two conditions of the above proposition: it is infinite by hypothesis and for any $m \in M$ we have $\left(\leftarrow, m\right]_{\mathrm{O}_{|M}}=[0, m]_{\mathrm{O}} \cap M$, a subset of the finite interval $[0, m]_{\mathrm{O}}$ and hence itself finite. The intended claim follows by an immediate application of the proposition above. $\Box$
