Initially assume ZFC.

Let $\binom{\kappa}{\lambda}$ denotes $\left|[\kappa]^{\lambda}\right|$ where $[\kappa]^{\lambda}$ is the collection of all subsets of $\kappa$ with cardinality $\lambda$. That is, the number of subsets of $\kappa$ of size $\lambda$.

Let $\kappa$ be any infinite cardinal number. Then it is easy to see that

  1. $\binom{\kappa}0=1$
  2. $\binom{\kappa}n=\kappa$ for all positive natural number $n$.
  3. $\binom{\aleph_0}{\aleph_0}=\beth_1$
  4. $\binom{\kappa}{\lambda}\le \kappa^\lambda$ when $1\le \lambda \le \kappa$

3 is due to $\beth_1=\sum_{\lambda=0}^{\aleph_0}\binom{\aleph_0}{\lambda}$ and others besides $\binom{\aleph_0}{\aleph_0}$ sums $\aleph_0$(since countable infinite countable infinites sums to countable infinite)

$\left({}^{\kappa}_{\lambda}\right)\le \kappa^\lambda$ is due to an injection can be made from $[\kappa]^{\lambda}$ into $\kappa^{\lambda}$(maps $\{a_i|i<\lambda\}$ to $\langle a_i\rangle_{i<\lambda}$ where $a_j<a_k$ iff $j<k$)

I hypothesize that

$$\binom{\kappa}{\lambda}=\begin{cases} \kappa^\lambda,&\lambda \le \kappa \\ 0,& \lambda>\kappa \end{cases}$$

It holds when $\kappa=\aleph_0$, but hard to induct for larger cardinals without assuming GCH. So I need some helps.


Observe that if $1\leq\lambda\leq\kappa$ then $\lambda\cdot\kappa=\kappa$. That is we can take $\lambda$ disjoint subsets of $\kappa$ of size $\kappa$. Then, by picking one element of each such subset we form subsets of $\kappa$ of size $\lambda$. The number of such subsets is exactly $\kappa^\lambda$ which gives that $|[\kappa]^\lambda|\geq\kappa^\lambda$.

Edit: Here is the answer with a few more details: Let $\{A_\beta : \beta<\lambda\}$ be the disjoint subsets of $\kappa$ and let us pick an enumeration for each $A_\beta=\{a^\beta_\xi : \xi<\kappa\}$. Given $f\in\kappa^\lambda$ let $X_f=\{a^\beta_{f(\beta)} : \beta\in\lambda\}$. Given $f,g\in\kappa^\lambda$, if $f\neq g$ we have that $f(\alpha)\neq g(\alpha)$ for some $\alpha\in\lambda$, and hence $X_f\neq X_g$ since $a^\alpha_{f(\alpha)}\in X_f$ while $a^\alpha_{f(\alpha)}\notin X_g$ because the $A_\beta$ are disjoint (and hence $a^\alpha_{f(\alpha)}$ is not in $A_\beta$ for all $\beta\neq \alpha$). Hence the function $f\mapsto X_f$ is injective, and we have at least $\kappa^\lambda$ subsets of $\kappa$ of size $\lambda$.

  • $\begingroup$ Clean and to the point! $\endgroup$ – Asaf Karagila Feb 23 '13 at 12:57
  • $\begingroup$ I'm not clear that the number of such subsets is exactly $\kappa^\lambda$...Would you please show me a detail? $\endgroup$ – Popopo Feb 23 '13 at 14:56
  • $\begingroup$ @Popopo: I edited my answer to add more details. Let me know if there is anything unclear. $\endgroup$ – Apostolos Feb 23 '13 at 16:47
  • $\begingroup$ Right, that's all right. Thank you very much. $\endgroup$ – Popopo Feb 24 '13 at 2:50

For each $A\in [\kappa]^{\lambda}$, choose some $f_A\in \kappa^{\lambda}$ such that $Im(f_A)=A$,then the asssingment $A\longmapsto f_A$ is one-to-one, and hence $|[\kappa]^{\lambda}|\leq \kappa^{\lambda}$.

We have that $|\lambda\times \kappa|=\kappa$, but each function $f:\lambda\rightarrow \kappa$ is a subset of $\lambda\times \kappa$ of size $\lambda$, thus $\kappa^{\lambda}\leq |[\kappa]^{\lambda}|$.

  • $\begingroup$ A succinct and correct proof. Thank you. $\endgroup$ – Popopo Feb 24 '13 at 16:13
  • $\begingroup$ you're welcome :) $\endgroup$ – Camilo Arosemena-Serrato Feb 24 '13 at 16:25

This becomes easier if you regard functions as sets of ordered pairs. Then every function from $\lambda$ into $\kappa$ (the sort of thing counted by $\kappa^\lambda$) is a $\lambda$-element subset of $\kappa\times\kappa$. Since $\kappa\times\kappa$ has $\kappa$ elements, it has $\binom\kappa\lambda$ subsets of size $\lambda$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.