On page 95 of Halmos' Naive Set Theory, we get the exercise

If $\{a_i\}$ and $\{b_i\}$ are families of cardinal numbers such that $a_i< b_i$, then $$\sum_i a_i<\prod_ib_i$$

I know that we get $\le$ easily (one can create an injection from the LHS to RHS). The real task is to prove a bijection cannot happen. I tried doing a diagonalization argument like in Cantor's theorem, but it didn't pan out. The arbitrary index $I$ makes it tough to do something like that. Even if we replace it with an ordinal, because it could be uncountable.

I'm thinking maybe one must use transfinite induction on the ordinals (on the index)?

Any tips/solutions?


Before the proof, I notice that the sum $\sum_{i\in I} a_i$ is identified to the disjoint union $\bigcup_{i\in I} a_i\times\{i\}$ for convenience.

You can prove the inequality is strict by diagonal argument. Remember that $|A|\le |B|$ if and only if there is an injection from $A$ to $B$. If every function from $A$ to $B$ is not onto, then $|A|<|B|$. From this, we should prove: if $f:\sum_{i\in I} a_i \to \prod_{i\in I} b_i$ is an injective function then there is a function $c\in \prod_{i\in I} b_i$ which is not an element of the range of $f$ (so $f$ should not be an bijection.)

Consider $f\upharpoonright a_i$, function $f$ whose domain is restricted from $a_i$. Since $a_i<b_i$, the cardinality of the range of $f\upharpoonright a_i$ is less than $b_i$. Also, the range of $f\upharpoonright a_i$ consists of functions $x$ from $I$ with $x(i)\in b_i$ for all $i\in I$. From above facts we get $$|\{x(i)\in b_i : x\in \text{range of }f\upharpoonright a_i\}|\le a_i<b_i$$ so we can choose $c_i\in b_i$, with $c_i\neq x(i)$ for all $x\in (\text{range of }f\upharpoonright a_i)$.

Let define $c\in\prod_{i\in I}b_i$ with $c(i)=c_i$. You can check that $c_i\in b_i$ for each $i$, and $c\neq f(x)$ for all $x\in \sum_i a_i$.

  • $\begingroup$ I like your answer. One question: given the collection of functions $\mathrm{ran}\left( f\upharpoonright (\{i\}\times a_i) \right)$, is there a way to "replace" each one with its value at $i$ without using the axiom of replacement? (I ask this because otherwise I must figure out as a lemma that replacement of sets can only decrease the cardinal number... I can see an injection argument, but I'm interested either way) $\endgroup$ – Alberto Takase Mar 4 '15 at 13:48
  • $\begingroup$ @AlbertoTakase I think about your answer but I don't understand it :( I do not know the reason - maybe my poor English is a reason why I don't comprehend your asking. Can you explain about your additional question? $\endgroup$ – Hanul Jeon Mar 5 '15 at 4:44
  • $\begingroup$ math.stackexchange.com/questions/1175130/… I posted another question that asks this exact same question (more generally). I will also post how I found your solution helpful for others to see. $\endgroup$ – Alberto Takase Mar 5 '15 at 4:53

Thanks to tetori, I know how the diagonalization argument works. I'm posting the formal proof for others who may have this same question.

enter image description here

The trick is to project the collection of functions $\mathrm{ran} f\upharpoonright (\{i\}\times k_i)$ onto $i$ which (by the axiom of choice) has cardinal number less than or equal the collection.


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.