Your proof for the first statement is on the right track: you are on your way to showing that any denumerable set $A$, finite or not, is a subset of an infinite set $S$, by constructing a set $A$ containing only but not necessarily all of the elements of $S$.
- For a denumerable set $S$, it may be that $A$ is
- a proper finite subset of a denumerable set $S$,
- a denumerable subset of a denumerable set $S$ (think of denumerable $\mathbb N \subset \mathbb Z \subset \mathbb Q$, all denumerable sets.
- is equal to $S$, in which case it would be a nonproper subset $S$.
- If $S$ is infinite but not denumerable (i.e. if S is uncountable), then any denumerable set A, finite or otherwise, which contains only elements of $S$, will be a proper subset of $S$. Since we are investigating only the existence of a denumerable subset $A$ of an infinite set $S$, if $S$ is uncountable, then $A$ would necessarily be a proper subset whose elements do not contain all elements of $S$.
For the second statement - there's no "proof" for it because it is not true for all infinite sets.
E.g., consider $\mathbb R$: it is certainly an infinite set, but it is uncountable, and hence not denumerable, so it cannot be the subset of any denumerable set. If it were a subset of a denumerable set $S$, then as a subset of $S$, it would contain only, and at most all, elements of $S$ . Which means it would contain at most a countable number of elements, which contradicts the fact that $\mathbb R$ is uncountable.
You could do it all at once, but there’s nothing wrong with the idea of first proving that $X=A\cup B$ is countably infinite and then going on to prove that $X\cup C$ is as well. However, you’re off on the wrong foot in trying to prove that $X$ is countably infinite. Pairing up $A$ and $B$ isn’t going to help: what you need to do is pair up $A\cup B$ and $\Bbb Z^+$.
Writing $A=\{a_1,a_2,a_3,\dots\}=\{a_n:n\in\Bbb Z^+\}$ and $B=\{b_1,b_2,b_3,\dots\}=\{b_n:n\in\Bbb Z^+\}$ is a good start. Now let $X=A\cup B$. Informally you have $X=\{a_1,b_1,a_2,b_2,a_3,b_3\dots\}$, and it’s intuitive clear that this can be paired up with $\Bbb Z^+$:
$$\begin{array}{cc}
1&2&3&4&5&6&7&8&9&10&\dots\\
a_1&b_1&a_2&b_2&a_3&b_3&a_4&b_4&a_5&b_5&\dots
\end{array}$$
The problem is to express this clearly enough so that if someone asks what $55$ corresponds to, you can actually answer. If you examine the table above closely enough, it’s apparent that even numbers in the top line match up with $b$’s, and odd numbers with $a$’s, and a little more examination reveals the rule: $2n$ matches up with $b_n$, and $2n-1$ matches up with $a_n$. You can now express this as a bijection from $\Bbb Z^+$ to $X$:
$$f(n)=\begin{cases}
a_{\frac{n+1}2},&\text{if }n\text{ is odd}\\\\
b_{\frac{n}2},&\text{if }n\text{ is even}\;.
\end{cases}$$
Added: There is just one possible problem here: if the sets $A$ and $B$ are disjoint, all is well, but this $f$ will not be a bijection if some $a_i$ is equal to some $b_k$, i.e., if $A\cap B\ne\varnothing$. To get around this, you should replace $B$ by $B\,'=B\setminus A$. If $B\,'$ is finite, let $C'=B\,'\cup C$, and use the argument below to show that $A\cup C'$ is countably infinite. And if $B\,'$ is countably infinite, use it instead of $B$ in the argument above.
Now you need to prove that $X\cup C$ is countably infinite. Since we now know that $X$ is countably infinite, there’s no need to keep the notational baggage of $a_n$’s and $b_n$’s: let $X=\{x_n:n\in\Bbb Z^+\}$ (or, more informally, $\{x_1,x_2,x_3,\dots\}$). If $C=\varnothing$, then $X\cup C=X$ is certainly countably infinite, so we can assume that $C$ is non-empty, say $C=\{c_1,\dots,c_m\}$. Now the easiest way to list $X\cup C$ systematically is $\{c_1,c_2,\dots,c_m,x_1,x_2,x_3,\dots\}$. Lay out the correspondence with $\Bbb Z^+$ as we did above:
$$\begin{array}{cc}
1&2&3&\dots&m&m+1&m+2&m+3&\dots\\
c_1&c_2&c_3&\dots&c_m&x_1&x_2&x_3&\dots
\end{array}$$
It’s not too hard not to write down a bijection $g$ from $\Bbb Z^+$ to $X\cup C$:
$$g(n)=\begin{cases}
c_n,&\text{if }1\le n\le m\\\\
x_{n-m},&\text{if }n>m\;.
\end{cases}$$
Best Answer
Consider the set $\mathbb{N}_p = \{p\in\mathbb{N}: p\ is\ prime\}$. We know that $\mathbb{N}_p$ is countably infinite. So, we now notice that $x \in \{ n^2 : n \in\mathbb{N}\} \implies x \not\in \mathbb{N}_p$.
Hence, $\mathbb{N}_p \subset \mathbb{N} \setminus \{ n^2 : n \in \mathbb{N}\}$. So, we must conclude our set has infinite cardinality.