Stel \(X\) is een aftelbare verzameling en \(Y\subset X\). Als \(X\) of \(Y\) eindig is zijn we eigenlijk snel klaar. We bekijken dus enkel het geval dat \(X\) aftelbaar oneindig is en de deelverzameling niet eindig is. Stel \(X=\{x_0,x_1,x_2,\ldots\}\). Dan is er een kleinste \(i\), zeg \(i_0\), waarvoor \(x_i\in Y\) en we noteren \(x_{i_0}\) als \(y_0\). Voorts is er een kleinste \(i\), zeg \(i_1\), waarvoor \(x_{i_1}\in Y\backslash \{y_0\}\) en we noteren \(x_{i_1}\) als \(y_1\). Als \(y_0,y_1, \ldots y_n\) reeds gedefinieerd zijn, nemen we als \(y_{n+1}\) het element \(x_{i_{n+1}}\), waarbij \(i_{n+1}\) de kleinste index \(i\) is waarvoor \(x_i\in Y\backslash \{y_0,y_1,\ldots y_n\}\). Merk op dat elk element van \(Y\) voorkomt in de rij \(y_0,y_1,\ldots\) en dat deze rij niet eindigt, omdat \(Y\) niet eindig wordt verondersteld. \(Y\) is dus aftelbaar oneindig. Dus \(Y\) is in alle gevallen een aftelbare verzameling.

We bewijzen de aftelbaarheid van \(X\cup Y\) alleen voor twee verzamelingen die aftelbaar oneindig zijn, dus als \(X\cong \mathbb{N}\) en \(Y\cong \mathbb{N}\). Omdat \(\mathbb{N}\cong \{n\in \mathbb{N}\mid n\text{ is even}\}\) en \(\mathbb{N}\cong \{n\in \mathbb{N}\mid n\text{ is oneven}\}\) kunnen we een bijectieve functie maken van \(X\cup Y\) naar \(\mathbb{N}\) door \(X\) bijectief af te beelden op \( \mathbb{N}\mid n\text{ is even}\}\) en \(Y\) bijectief af te beelden op \( \mathbb{N}\mid n\text{ is oneven}\}\). Met andere woorden, \(X\cup Y\) is aftelbaar.

We bewijzen de aftelbaarheid van \(X\times Y\) alleen voor twee verzamelingen die aftelbaar oneindig zijn, dus als \(X\cong \mathbb{N}\) en \(Y\cong \mathbb{N}\). Er is dan een bijectie van \(X\times Y\) naar \(\mathbb{N}\times \mathbb{N}\). Dus: \(X\times Y\cong\mathbb{N}\times \mathbb{N}\). Omdat \(\mathbb{N}\times \mathbb{N}\cong (\mathbb{N}\), moet dan wel \(X\times Y\cong\mathbb{N}\). Met andere woorden, \(X\times Y\) is aftelbaar.

We tonen eerst aan dat de verzameling \(\mathbb{Q}^{+}\) van alle positieve rationale getallen aftelbaar oneindig is. Deze positieve rationale getallen kunnen beschouwd worden als \(p/q\) met \(p\) en \(q\) positieve natuurlijke getallen en \(p/q\) een onvereenvoudigbare breuk, d.w.z. \(\mathrm{ggd}(p,q)=1\). We kunnen nu de function \(f:\;\mathbb{Q}\rightarrow \mathbb{Z}\times \mathbb{Z}\backslash\{0\}\) definiëren door \(f(p/q)=(p,q)\). Dan is \(f\) een injectieve functie. Omdat \(\mathbb{N}\times \mathbb{N}\) aftelbaar oneindig is en \(f(\mathbb{Q}^{+}\) een oneindige deelverzameling hiervan is, is en dus \(f(\mathbb{Q}^{+})\) aftelbaar oneindig. Maar dan is \(\mathbb{Q}^{+}\) ook aftelbaar oneidig.

De verzameling \(\mathbb{Q}^{-}\) van alle negatieve rationale getallen is evident gelijkmachtig met \(\(\mathbb{Q}^{+}\) en dus ook aftelbaar oneindig. Maar dan is \(\mathbb{Q}=\mathbb{Q}^{-}\cup\{0\}\cup \mathbb{Q}^{+}\) als vereniging van aftelbare verzamelingen ook aftelbaar. Omdat de verzameling van rationale getallen niet eindig is, weten we dan dat deze verzameling oneindig aftelbaar is.