Subset of countable set is countable proof I'm self studying Understanding Analysis and there's an exercise that asks to prove that if $ A\subseteq B $ and $B$ is countable, then $A$ is either countable or finite. I want to be sure that my proof is not wrong or badly written.
Being finite is trivial, so let's suppose it's not.
In the exercise, we assume there exists $f:N \to B$ which is 1-1 and onto and $n_1=\min\{n\in N:f(n)\in A\}$. As a start to a definition of $g:N \to A$, we set $g(1)=f(n_1)$. These are given by the exercise and we're asked to continue the process inductively.
I construct sets $a_n=\{n_c \text{ for } c \le n\}$ for example $a_1=\{n_1\}$, $a_2=\{n_1, n_2\}$ etc.
Then I construct: $$n_c=\min\{n\in N:f(n)\in A\ and\ n\notin a_{n_{c-1}}\}$$
and thus $g(c)=f(n_c)$ for every $c\in N$ gives us a $1-1$ function from $N$ onto $A$.
I would love to hear any sort of feedback, thank you!
 A: It's clear that you have an effective solution in mind, but your proof doesn't accurately convey it. Informally, the crucial idea you have is to define $n_c$ to be the smallest $n$ so that $f(n)$ is in $A$ and was not yet enumerated - but the structure of your proof doesn't effectively communicate this.
A good way to start proofs is just to succinctly state your goal, introducing all variables necessary to do so. In this case, I'd begin with:

Let $B$ be a countable set and $A\subseteq B$ be some subset thereof. We claim that $A$ is either countable or finite.

You've started by writing, a bit confusingly, that "being finite is trivial" - but when you say something is trivial (which you usually shouldn't!), it means you have some statement in mind that you're leaving out the proof for. That's not what you're doing here. I think you mean to say is something along these lines:

We will prove this by showing that, if $A$ is not finite, then it is countable.

Where we note that proving "X or Y" is the same as proving "not X implies Y" - and we're not claiming that it's easy to prove that $A$ is finite, but rather that we're going to assume it's not - and that the form of the statement we're trying to show justifies a proof using this assumption. Also, note that the assumption we extract is that $A$ is not finite (i.e. $A$ is infinite) whereas you've written "suppose it's uncountable" (which means "neither finite nor countable") - although I suspect this is just a slip of language more than a conceptual inaccuracy.
Your next step is fine:

We assume there exists $f:N \to B$ which is 1-1...

Though, as a minor nitpick, I'd note that you should write "let" instead of "assume" or even "Since $B$ is countable, there exists..." since there is no assuming going on - you're just writing what it means to be countable.
Then, you sort of define a bunch of things a bit aimlessly - you should always tell your reader what you're doing and try to build things in steps. My inclination would be to write something like:

We will now define a sequence of values $n_i$ with the intention that $f(n_1),\,f(n_2),\ldots$ will enumerate $A$. We first define
$$n_1=\min\{n\in \mathbb N: f(n)\in A \}.$$
To describe further values,  we define the set $A_k=\{n_i : i \leq  k\}$ to be the set of prior values of the sequence and let
$$n_k = \min\{n\in\mathbb N : f(n)\in A\text{ and }n\not\in A_{k-1}\}.$$

This is more or less what you've written, but expanded out with set builder notation and with some minor changes to conventions (e.g. using capital letters for sets and using variables $i,j,k$ for indices). Your proof is missing something here, however: you need to show that the definition makes sense - in particular, that a minimum exists. This is where you use that $A$ was assumed infinite:

Note that the set $\{n\in\mathbb N : f(n)\in A\text{ and }n\not\in A_{k-1}\}$ must be non-empty since every element of $A$ can be written as $f(n)$ for some $n$ since $f$ is onto and, since we assumed $A$ is infinite, it cannot be the case that $n_1,n_2,\ldots,n_{k-1}$ are the only indices so that $f(n)\in A$.

This is a rather crucial step since otherwise you fail to use the assumption that $A$ is infinite - which is an immediate red flag. In more nitpicking terms, you might notice that you could avoid ever assuming $A$ is infinite by splitting into cases here; if that set were ever empty, we would have directly proved that $A$ is finite - and mathematicians often feel that a direct proof is preferable to proofs by contradiction*.
Only after defining this sequence would I define $g$ - and I would be sure to tell the reader the purpose of $g$ when introducing it. Note that saying somewhere that $g$ is 1-1 is really important since it's literally the whole point of constructing it!

We now define a 1-1 function $g:\mathbb N\rightarrow A$ by the following rule:
$$g(k)=f(n_k)$$

Your proof has a problem where you write $g(n_c)=f(n_c)$ - the input to $g$ needs to be the index in the sequence, not the value, but I assume this is a typo.
The proof you wrote ends there. This might be okay as long as everyone involved understands that there is a claim left unproven and agrees that it is trivial - but let me be pedantic: We never showed that $g$ is 1-1! We have a good definition, but a definition is not a proof. I won't spoil this for you, but there are basically three claims you should finish, which I'll list in order of how difficult they are to prove:

*

*$g(k)\in A$ for every $k\in\mathbb N$.


*$g$ is one-to-one (as in "injective"). A proof of this ought to start with:

Let $i,j\in\mathbb N$ be such that $g(i)=g(j)$. We will show that $i=j$.

and then proceed to some convincing argument that $i$ really does equal $j$.


*$g$ is onto. This proof is more difficult since you have to find a preimage for an arbitrary $a\in A$. The proof should begin:


Let $a\in A$. We will construct some $k\in\mathbb N$ such that $g(k)=a$.

If you haven't already thought this through, this is a somewhat interesting challenge. You'll need to use that $f$ is onto in proving this, and likely also that the sequence $n_1,n_2,\ldots$ is strictly increasing.
Fixing up the writing of the first half of the proof and filling in the proof that $g$ is 1-1 should give you a nice solution to the exercise.
(*Okay, strictly speaking, the form of the proof you have wouldn't usually be called a proof by contradiction - but it's also not a direct proof. Loosely speaking, some mathematicians find it objectionable or inelegant to assume that either "X or not X" and when you can avoid doing so, it's often wise to)
A: By definition, we have an injection $j:B\hookrightarrow\Bbb N$.  But if $A\subset B$, then $|A|\le |B|$.  That is, the inclusion $i:A\hookrightarrow B$ is an injection.  Then $j\circ i:A\hookrightarrow\Bbb N$ is injective.
