Aftelbare verzameling

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de wiskunde noemen we een verzameling aftelbaar als we de elementen ervan kunnen ‘aftellen’. Dat houdt in dat we de elementen op een rij kunnen zetten met een eerste element, een tweede element, enz., waarbij alle elementen aan de beurt komen. De eenvoudigste aftelbare verzamelingen zijn de eindige verzamelingen.

Een aftelbare verzameling is niet noodzakelijk eindig. Zo zijn ook de gehele getallen aftelbaar. We zetten ze als volgt in een rij om geteld te worden: 0, 1, -1, 2, -2, 3, -3, enz. Het tellen van de elementen stopt weliswaar nooit, maar elk element komt aan de beurt.

Er zijn ook verzamelingen die overaftelbaar zijn, dat wil zeggen niet aftelbaar. Een verzameling is dus eindig, aftelbaar oneindig, of overaftelbaar.

Definitie[bewerken]

S heet aftelbaar oneindig als er een bijectie f: \mathbb{N} \to S bestaat, of anders gezegd, als S gelijkmachtig is met \mathbb{N}.

Een verzameling S heet aftelbaar als (equivalente definities):

  • S eindig of aftelbaar oneindig is
  • er een surjectie f: \mathbb{N} \to S bestaat
  • er een injectie f: S \to \mathbb{N} bestaat
  • er een bijectie f: \mathbb{N} \to S bestaat, of voor zeker geheel getal n ≥ 0 een bijectie f: \{ 1, .. , n \} \to S
  • S gelijkmachtig is met \mathbb{N} of voor zeker geheel getal n ≥ 0 met \{ 1, .. , n \}

Eigenschappen[bewerken]

  • Als R aftelbaar is en er bestaat een surjectieve functie g tussen R en een bepaalde verzameling S, dan is S ook aftelbaar.
  • Een eindig product van aftelbare verzamelingen is aftelbaar. Dat kan men als volgt inzien:
Stel dat S_1 tot en met S_n aftelbaar zijn, met n een natuurlijk getal. Dan zijn er n surjectieve functies  f_i tussen de natuurlijke getallen en S_i. We kunnen die surjectieve functies combineren tot één surjectieve functie:
f: \mathbb{N}^{n} \to \prod_{i=1}^{n} S_i: (x_1,x_2, \ldots x_n) \to f((x_1,x_2, \ldots x_n)) = (f_1(x_1), f_2(x_2) \ldots f_n(x_n))

Daar  \mathbb{N}^{n} aftelbaar is voor elke natuurlijke n, zal ook  \prod_{i=1}^{n} S_i aftelbaar zijn.

Voorbeelden[bewerken]

  • De verzameling van de gehele getallen  \mathbb{Z} is aftelbaar. Een voor de hand liggende aftelling is de volgende:
 0,-1,1,-2,2,-3,3, \ldots
  • Een mogelijke aftelling van  \mathbb{N}^{2} is de volgende:
 (0,0),(0,1),(1,0),(2,0),(1,1)(0,2),(3,0),(2,1),\ldots
Eerst schrijven we dus de koppeltjes op met som 0, dan die met som 1, 2 enzovoort. Deze procedure kan men uitbreiden naar een willekeurig eindige macht van  \mathbb{N} .
  • De verzameling van de positieve rationale getallen  \mathbb{Q}^+ is aftelbaar, want met elk positief rationaal getal correspondeert een koppel natuurlijke getallen (teller, noemer). Voor de volledige verzameling rationale getallen, wordt het iets ingewikkelder:
  • Voor \mathbb{Q} kijken we naar alle getallen van de vorm a/b, met a een natuurlijk getal, en b een van nul verschillend natuurlijk getal. Deze getallen kunnen door een bijectie afgebeeld worden op een deelverzameling van de geordende tripletten (a,b,c), met a ≥ 0, b > 0, a en b copriem, en c = 0 als a/b > 0, anders is c = 1.
Zo wordt 0 afgebeeld op (0,1,0), 1 (= 1/1) op (1,1,0), -1 op (1,1,1), 1/2 op (1,2,0), -1/2 op (1,2,1), 2 op (2,1,0), enz...