First note that the natural numbers in your definition are transitive sets. So if $m\in m$ then $m\subseteq n$, and furthermore $m\neq n$, otherwise you would have $n\in n$ in contradiction to the axiom of regularity.
Use this fact to deduce that $m<n$ if and only if whenever $M,N$ are sets of cardinality $m,n$ respectively, there is an injection from $M$ into $N$, but there is no injection from $N$ into $M$. The latter may be easier to prove by using the pigeonhole principle (which you can prove independently by induction, see [1]).
First note that if $m=0$ then this follows from the above directly regardless to the value of $k$. So we may assume that $m\neq 0$.
We next prove by induction on $k$. For $k=0$ this is obvious. Assume that for $k-1$ it is true that $m+(k-1)<n+(k-1)$ whenever $m<n$.
Now suppose that $M\subsetneqq N$, and $K$ are sets of cardinality $m,n,k$ respectively, and $K$ is disjoint from $N$ (and so from $M$ as well). By the above it suffices to show that that there is no injection from $N\cup K$ into $M\cup K$ in order to show that $m+k<n+k$.
Suppose that there was an injection $g\colon N\cup K\to M\cup K$, restrict $g$ to $N$, since $M$ is a proper subset there has to be some $x\in N$ such that $g(x)\in K$, otherwise $g\upharpoonright N$ is an injection from $N$ into $M$. It follows that there exists some $u\in K$ such that $g(u)\in M$, otherwise $g\upharpoonright K$ would be an injection into $K\setminus\{g(x)\}$, which is impossible.
Define $f$ to be $(g\setminus\{\langle x,g(x)\rangle,\langle y,g(y)\rangle\})\cup\{\langle x,g(y)\rangle\}$. This is an injection from $N\cup K\setminus\{y\}$ into $M\cup K\setminus\{g(x)\}$. That is, an injection from a set of cardinality $n+(k-1)$ into a set of cardinality $m+(k-1)$. But the induction hypothesis tells us that this is a contradiction.
More:
- Subset of a finite set is finite
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.
Best Answer
The set of non-negative numbers: I assume you talk of non-negative integers. The set would be $\{0,1,2,3...\}$.
Every element of the set can be associated with a natural number as $n-1$ where $n$ is the natural number.
That means: $0$ is associated with $1$, $1$ is associated with $2$ and so on. When every element of the given set can be associated with a natural number, It is denumerable (countably infinite).