Proof that injections from $[1],[2],[3].,,,.$ into $S$ implies $S$ is infinite Let $S$ be a set and for $n \in \mathbb{N}$ let $[n]$ be the set of all natural numbers less than $n$.
Suppose that for each nonzero $n \in \mathbb{N}$ there is an injection from $[n]$ to $S$. Show that there is an injection from $\mathbb{N}$ to S.
I am not sure if the above claim is true. It seems true, but I am unsure how to prove it (or to find a counterexample for that matter).
If possible, I'd prefer a proof that doesn't use the axiom of choice, or any of its equivalences.
 A: As mentioned in comments, this depends essentially of having the axiom of choice available at least in some variant. If you don't have choice then it is possible that there may exist an "infinite Dedekind-finite set", which would exactly be a counterexample to your claim.
(A set $S$ is called Dedekind-infinite if there exists an bijection between $S$ and a proper subset of $S$. It is easily proved -- in ZF -- that this is the case exactly when there is an injection $\mathbb N\to S$). 
If you have at least the axiom of countable choice, it is easy enough. Use the axiom to select simultaneously for each $n$ a particular injection $f_n: [n]\to S$. Then construct the function $g:\mathbb N\to S$ recursively by the rule:


*

*$g(n) = f_{n+1}(i)$ where $i$ is the smallest number in $[n+1]$ such that $f_{n+1}(i) \notin \{g(0),\ldots,g(n-1)\}$.


It ought to be clear enough that there is always such an $i$ and that $g$ becomes injective. The work of writing down the proof then amounts to finding an appropriate recursion theorem and showing that it applies. (You'll need as a lemma something like there is no surjection $[n]\to[n+1]$, but that's just finite reasoning).
