Prove that if $1 < \kappa_i \leq \lambda_i$ for all $i \in I$ then $\sum_{i \in I} \kappa_i \leq \prod_{i \in I} \lambda_i$ where $\kappa_i$ and $\lambda_i$ (for all $i \in I$) are cardinal numbers.

I am trying to prove this, which is similar to König's Theorem, but the technique to prove that does not work here because it could be that $\kappa_i = \lambda_i$ for any or all $i \in I$.

Suppose $\langle A_i \,|\, i \in I \rangle$ are mutually disjoint sets where $|A_i| = \kappa_i$ for all $i \in I$. Likewise suppose that $\langle B_i \,|\, i \in I \rangle$ are sets such that $|B_i| = \lambda_i$ for all $i \in I$. Since $\kappa_i \leq \lambda_i$ we can assume that $A_i \subseteq B_i$ for all $i \in I$. We can then show the result by constructing an injection from $\bigcup_{i \in I} A_i$ to $\prod_{i \in I} B_i$ by the definition of cardinal sums and products.

I have found the determination of a general rule for such a mapping such that it is injective to be very difficult. I believe that I am able to come up with a mapping but it must treat the cases where $|I| = 0$ (so $I = \emptyset$, which is the trivial case), $0 < |I| < 3$, and $|I| \geq 3$ separately, which is messy, and the rules for mapping within the cases is also pretty messy.

Is there a simple way to construct this injective mapping that I am missing? Presumably it will depend on the fact that both $A_i$ and $B_i$ have at least two distinct elements for every $i \in I$.

NOTE: I found this question: Cardinality of the Union is less than the cardinality of the Cartesian product, and I actually came up with the mapping that Asaf gives in his answer. However, it seems that this mapping is not actually injective if $|I| = 2$, and I note that his mapping does not depend on the fact that $\kappa_i$ is strictly less than $\lambda_i$ (not here but in the actual König's Theorem), which is needed for a correct proof of König's Theorem.

To see how this fails suppose that $I = 2 =\{0, 1\}$ and $$ A_0 = B_0 = \{0, 1\} \\ A_1 = B_1 = \{0', 1'\} \,. $$ In his notation, if we let $\langle b_i \,|\, i \in I \rangle = \langle 0, 0' \rangle$, then it has to be that $\langle c_i \,|\, i \in I \rangle = \langle 1, 1' \rangle$. His mapping $f$ then becomes $$ f(0) = \langle 0, 1' \rangle \\ f(1) = \langle 1, 0' \rangle \\ f(0') = \langle 1, 0' \rangle \\ f(1') = \langle 0, 1' \rangle \,. $$ Unless I am misunderstanding his mapping, this is clearly not injective, and I don't think that we have violated any of the assumption used to build the mapping. I was able to come up with a slightly different mapping that works when $|I| = 2$ but, again, having to treat these cases separately is messy.

  • $\begingroup$ Uhh, your counterexample doesn't have that $|A_i|<|B_i|$. And since $2+2=2\times 2$, you would have literally found a counterexample to the lemma itself. $\endgroup$ – Asaf Karagila Apr 2 '18 at 8:41
  • $\begingroup$ But also let me share that a couple of years ago, I was teaching the proof of König's lemma, and someone noticed that there is an edge case where the proof doesn't work, which was something like two finite sets, or something like that. $\endgroup$ – Asaf Karagila Apr 2 '18 at 8:42
  • $\begingroup$ (In my second comment, I don't remember if it was the same injection as in the answer you refer to, but it just goes to show that there might be some minor edge case missing.) $\endgroup$ – Asaf Karagila Apr 2 '18 at 8:51
  • $\begingroup$ Thanks for your response! The construction of the injection in your answer also does not use the fact that $|A_i| < |B_i|$, unless I misread something. I'm not claiming to have found a counterexample to the lemma, just that this particular method of constructing a mapping is not injective in all cases. Since posting, I've tried to prove that the mapping is injective, and have seen how it gets stuck and also how you can get out of it if $|I| > 2$. I can post details if it would help to illustrate the issue. $\endgroup$ – kyp4 Apr 2 '18 at 17:26

After working through the details, I was mistaken about needing to treat the cases on $|I|$ separately. We only need two cases.

First, if $I = \varnothing$, then we have the trivial case of $$ \sum_{i \in I} \kappa_i = 0 \leq 1 = \prod_{i \in I} \lambda_i \,. $$ If $I \neq \varnothing$, then there is an $i_0 \in I$. We also have distinct $\alpha_i$ and $\beta_i$ in $B_i$ (for any $i \in I$) since we have $1 < \kappa_i \leq \lambda_i = |B_i|$ so that $2 \leq |B_i|$. Note that choosing these elements requires the Axiom of Choice.

Then, for an $x \in \bigcup_{i \in I} A_i$ there is an $i_x \in I$ where $x \in A_{i_x}$. So, for any $i \in I$, define $$ a_i = \begin{cases} x & i = i_x \\ \alpha_i & i \neq i_x \text{ and } i = i_0 \text{ and } x = \alpha_{i_x} \\ \beta_i & i \neq i_x \text{ and } i = i_0 \text{ and } x \neq \alpha_{i_x} \\ \beta_i & i \neq i_x \text{ and } i \neq i_0 \text{ and } x = \alpha_{i_x} \\ \alpha_i & i \neq i_x \text{ and } i \neq i_0 \text{ and } x \neq \alpha_{i_x} \,. \end{cases} $$ Then define $f(x) = \langle a_i \,|\, i \in I \rangle$. It is then easy but tedious (involving a lot of messy case work) to show that $f$ is an injective mapping from $\bigcup_{i \in I} A_i$ to $\prod_{i \in I} B_i$, which shows the result.


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.