10
$\begingroup$

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.

$\endgroup$

3 Answers 3

13
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Clean and to the point! $\endgroup$
    – Asaf Karagila
    Commented Feb 23, 2013 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
    Commented Feb 23, 2013 at 14:56
  • $\begingroup$ @Popopo: I edited my answer to add more details. Let me know if there is anything unclear. $\endgroup$
    – Apostolos
    Commented Feb 23, 2013 at 16:47
  • $\begingroup$ Right, that's all right. Thank you very much. $\endgroup$
    – Popopo
    Commented Feb 24, 2013 at 2:50
7
+50
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ A succinct and correct proof. Thank you. $\endgroup$
    – Popopo
    Commented Feb 24, 2013 at 16:13
  • $\begingroup$ you're welcome :) $\endgroup$ Commented Feb 24, 2013 at 16:25
5
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .