◀ ▲ ▶Branches / Set-theory / Proof: By Induction

Proof: By Induction

(related to Corollary: Cartesian Products of Countable Sets Is Countable)

• By hypothesis, $A_1,\ldots,A_n$ are countable sets and $A=A_1\times\ldots\times A_n$ is their Cartesian product.
• We prove by induction that $A$ is countable.
• Base Case $n=2$
  • ... is correct, since $$A_1\times A_2=\bigcup_{a\in A_2}(A_1\times a)$$ and the union of countably many countable sets is countable.
• Induction step $n\to n+1$
  • Assume $A_{n+1}$ is countable.
  • Then, $$A_1\times \ldots\times A_n\times A_{n+1}=\left(\bigcup_{a\in A_{n+1}}(A_1\times \ldots\times A_n)\times a\right).$$
  • By induction hypothesis, $A_1\times \ldots\times A_n$ is countable.
  • Apply union of countably many countable sets is countable once again.
    ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Modler, F.; Kreh, M.: "Tutorium Analysis 1 und Lineare Algebra 1", Springer Spektrum, 2018, 4th Edition