This problem is from Spivak. Give another proof that $\binom{n}{k}$ is a natural number by showing that $\binom{n}{k}$ is the number of sets of exactly $k$ integers each chosen from $1, \ldots,n$.

I went ahead and argued that since, by the multiplication principle, the number of ways to choose $k$ integers from $n$ with order is $n(n-1)(n-2)\cdots(n-k+1)$ or $\frac{n!}{(n-k)!}$ and the number of ways to arrange any $k$ integers is $k!$, that the number of ways to choose $k$ integers from $1,\cdots,n$ without order has to be $\frac{n!}{k!(n-k)!}=\binom{n}{k}$. Somehow though, in a chapter on induction, I doubt this is what Spivak was looking for. 

I just don't know how to rigorously define the idea of "the number of subsets of $1, \ldots, n$ with cardinality $k$."