Infinite subset contains finite subset of any size Is it true in ZF that given any infinite set $X$ and any natural number $n$, there is a subset of $X$ with cardinality $n$ (i.e. equinumerous with $n$)?
Here, $X$ is defined to be an infinite set if $X$ is not equinumerous to any natural number $n$.
This may turn out to be quite trivial, but I can't think of an argument to show this.
 A: Here is a slight variant on the answer by Alex. It assumes that you already proved some basic things about finite sets and their cardinality.
Given an infinite set $S$, we prove by induction that for every $n$, there exists $S_n\subseteq S$ of size $n$.
For $n=0$, the only set of size $0$ is $\varnothing$, and since $\varnothing$ is a subset of any other set, in particular it is a subset of $S$.
Suppose that there is a subset $S_n\subseteq S$ of size $n$, since $S$ is not finite it cannot be that $S_n=S$; therefore there exists $s\in S\setminus S_n$, and now $S_n\cup\{s\}$ is a set of size $n+1$ as wanted.

Now let me leave you with something to contemplate on: The above proof is not enough to conclude that $S$ has a countably infinite subset. Why?
A: We proceed by induction:
Let $S$ be an infinite set. Let $a\in S$. By the axiom of subsets, there exists a subset $A\subset S$ such that $x\in A\Rightarrow x=a$. By the axiom of extensionality, $A=\{a\}$. Thus, we can get a subset of size $1$.
Now suppose that we can get a subset $K$ of size $n$, meaning we have a bijection from $\{1,...,n\}$ to $K$. By the axiom of subsets, there is a subset $K^C$ of $S$ satisfying $x\in K^C\Leftrightarrow x\not\in K$. If $K^C$ is empty, then $K$ and $S$ have the same elements. By the axiom of extensionality, $K=S$, so there is a bijection from $\{1,...,n\}$ to $S$, a contradiction. Therefore there exists $b\in K^C$. By the argument above, there exists a set $B=\{b\}$. By the axiom of unordered pairs, there exists a set $\{K,B\}$. By the axiom of the sum set, there exists a set $K'$ containing all the elements of $K$ and $B$. Let $g:\{1,...,n+1\}to K'$ be defined by $g(x)=f(x)$ if $x\in K$ and $g(x)=b$ is $x\in B$. This is clearly a bijection, so $K'$ has size $n+1$.
