First, let me say that when I say countable set I mean a set whose cardinality is less than or equal to the cardinality of $\mathbb{N}$. A set whose cardinality is strictly equal to the cardinality of $\mathbb{N}$ will be called countably infinite.

Also, $\bigsqcup_{i \in I} X_i = \{ (i,x) \in I \times\bigcup_{i \in I} X_i \mid x \in X_i \}$. Of course, $|\bigcup_{i \in I} X_i| \leq |\bigsqcup_{i \in I} X_i|$.

Let $(X_i)_{i \in I}$ be an indexed family with the index set $I$.

It is widely known that if $I$ is countable (resp., countably infinite) and $\forall i \in I, X_i$ is countable (resp., countable infinite), then $\bigsqcup_{i \in I} X_i$ is itself countable (resp., countable infinite).

However, what if $I \neq \varnothing$ and

  • $(1)$ $I$ is countably infinite but each $X_i$ is only known to be countable? That is, there is a bijection $f\colon I\to\mathbb{N}$ and a family $(f_i)_{i \in I}$ of injections $X_i\to\mathbb{N}$.

  • $(2)$ And what if each $X_i$ is countably infinite while $I$ is just countable? That is, there is an injection $f\colon I\to\mathbb{N}$ and a family $(f_i)_{i \in I}$ of injections $X_i\to\mathbb{N}$.

The intuition tells me that in both cases $(1)$ and $(2)$ the disjoint union $\bigsqcup_{i \in I} X_i$ will be countably infinite. However, how to prove it rigorously is another question entirely.

Remark. To construct a family $(f_i)_{i \in I}$ of injections (resp., bijections) $X_i\to\mathbb{N}$ knowing only that each $X_i$ is countable (resp., countably infinite) we need the axiom schema of replacement to obtain a set of sets of injections $X_i\to\mathbb{N}$ (each for every $i \in I$) and the axiom of choice to obtain a choice function of such set.

P.S. I don't know whether I should tag this as elementary set theory or set theory. Sorry.


Since the empty set is countable, (1) is not necessarily infinite, and neither is (2) if $I=\emptyset$.

  • $\begingroup$ While I agree it's helpful, this seems more of an oversight on the original intention. If the OP edits now, what's the worth of your answer? $\endgroup$ – Asaf Karagila Sep 8 '18 at 7:32
  • $\begingroup$ Thanks! Edited. $\endgroup$ – Jxt921 Sep 8 '18 at 7:50

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.