proof that countable unions are countable


Let C be a countable set of countable sets. We will show that C is countableMathworldPlanetmath.

Let P be the set of positive primes (http://planetmath.org/Prime). P is countably infiniteMathworldPlanetmath, so there is a bijection between P and . Since there is a bijection between C and a subset of , there must in turn be a one-to-one function f:CP.

Each SC is countable, so there exists a bijection between S and some subset of . Call this function g, and define a new function hS:S such that for all xS,

hS(x)=f(S)g(x)

Note that hS is one-to-one. Also note that for any distinct pair S,TC, the range of hS and the range of hT are disjoint due to the fundamental theorem of arithmeticMathworldPlanetmath.

We may now define a one-to-one function h:C, where, for each xC, h(x)=hS(x) for some SC where xS (the choice of S is irrelevant, so long as it contains x). Since the range of h is a subset of , h is a bijection into that set and hence C is countable.

Title proof that countable unions are countable
Canonical name ProofThatCountableUnionsAreCountable
Date of creation 2013-03-22 12:00:01
Last modified on 2013-03-22 12:00:01
Owner Koro (127)
Last modified by Koro (127)
Numerical id 9
Author Koro (127)
Entry type Proof
Classification msc 03E10