Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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$.

share|cite|improve this answer
Clean and to the point! – Asaf Karagila Feb 23 '13 at 12:57
I'm not clear that the number of such subsets is exactly $\kappa^\lambda$...Would you please show me a detail? – Popopo Feb 23 '13 at 14:56
@Popopo: I edited my answer to add more details. Let me know if there is anything unclear. – Apostolos Feb 23 '13 at 16:47
Right, that's all right. Thank you very much. – 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}|$.

share|cite|improve this answer
A succinct and correct proof. Thank you. – Popopo Feb 24 '13 at 16:13
you're welcome :) – Camilo Arosemena 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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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