Aftelbaarheid

[barrelhouse]

Beste,

Mag ik er van uit gaan dat als een verzameling aftelbaar is bv: de natuurlijke getallen N. Dat deze verzameling dan aftelbaar is in al haar dimensies nl.

N x N

N x N x N

N x N x N x N ...

Alvast bedankt!

[TD]

Wat bedoel je verder met die puntjes? Voor het cartesisch product van een eindig aantal aftelbare verzamelingen, zoals N, is dat inderdaad waar.

Voor een aftelbaar aantal gaat dit niet meer op; in tegenstelling tot bij unies (de unie van een aftelbaar aantal aftelbare verzamelingen, is weer aftelbaar).

[barrelhouse]

Inderdaad over een eindig aantal. Hoe zou je dat kunnen aantonen d.m.v. een bijectie? Bij N x N , kan je gebruik maken van een matrix, moet je bij meerdere dimensies dan een tabel doorlopen?

[Drieske]

Ik geef je een idee voor het cartesisch product van 2. Beschouw de functie:

\(f: \mathbb{N} \times \mathbb{N} \to: \mathbb{N}: (n, m) \mapsto 2^n 3^m\)

. Zie je dat dit een bijectie is? Kun je veralgemenen?

[TD]

Inderdaad over een eindig aantal. Hoe zou je dat kunnen aantonen d.m.v. een bijectie? Bij N x N , kan je gebruik maken van een matrix, moet je bij meerdere dimensies dan een tabel doorlopen?

Je zou dat bewijs kunnen proberen te veralgemenen. Een andere typisch bewijs maakt gebruik van de unieke priemontbinding.

[barrelhouse]

Inderdaad, bij elke dimensie kan je een nieuw priemgetal toevoegen tot een bepaalde macht, dit geeft telkens een uniek getal. Heb je hiermee dan ook bewezen dan het eindig cartesisch product van Q bestaat? Aangezien elk getal uit Q kan geschreven worden als een koppel gehele getallen. In Q x Q kan je dan een koppel van 4 getallen nemen waarvan je weet dat die verzameling aftelbaar is omdat N x N x N x N aftelbaar is?

[TD]

Ja, zelf meer algemeen: elk cartesisch product van een eindig aantal aftelbare verzamelingen, is aftelbaar. Elke aftelbare verzameling is immers bijectief met N, dus het volstaat om het te tonen voor N^k, zoals hierboven.

[barrelhouse]

Inderdaad! Hartelijk dank voor de snelle reacties!

[Drieske]

Het is inderdaad wat TD al zegt. Wil je toch een explicietere afbeelding, dan gaat dat zo: zeg X₁, ..., X_n allen aftelbaar. Definieer dan

\(f_i: X_i \to \mathbb{N}\)

voor alle i. Dan is

\(h: X_1 \times \cdots \times X_n \to \mathbb{N}: (a_1, \cdots, a_n) \mapsto p_1^{f_1(a_1)} \cdots p_n^{f_n(a_n)}\)

een bijectie.

[Rogier]

Ik geef je een idee voor het cartesisch product van 2. Beschouw de functie:

\(f: \mathbb{N} \times \mathbb{N} \to: \mathbb{N}: (n, m) \mapsto 2^n 3^m\)

. Zie je dat dit een bijectie is? Kun je veralgemenen?

Kanttekening: wel injectief, maar niet surjectief, dus ook niet bijectief.. 5 behoort bijvoorbeeld niet tot het beeld van f. Maar da's hier verder niet heel belangrijk, een injectieve functie volstaat reeds om de aftelbaarheid van

\(\nn\times\nn\)

aan te tonen.

[Rogier]

Nog een alternatieve benadering voor hogerdimensionale cartesische producten:

Als

\(\nn\times\nn\)

aftelbaar is, d.w.z. je hebt een injectieve functie

\(f:\nn\times\nn\rightarrow\nn\)

, dan is

\(\nn\times\nn\times\nn\)

ook aftelbaar, middels de functie

\(g(x,y,z) = f(f(x,y),z)\)

. Datzelfde kun je herhaaldelijk toepassen voor hogere dimensies.

[Drieske]

Inderdaad een terechte opmerking ! Te rap geweest in het typen.

-edit- aanvullend ter verduidelijking voor TS: injectief volstaat omdat dit gewoon betekent dat niet alles van N bereikt wordt, maar een deelverzameling. En een deelverzameling van iets aftelbaars is zelf ook aftelbaar.

[tempelier]

Beste,

Mag ik er van uit gaan dat als een verzameling aftelbaar is bv: de natuurlijke getallen N. Dat deze verzameling dan aftelbaar is in al haar dimensies nl.

N x N

N x N x N

N x N x N x N ...

Alvast bedankt!

Mij lijkt het gewoon aftelbaar via de diagonaal methode van Cantor net zoals de aftelbaarheid van Q wordt bewezen.

[tempelier]

Mij lijkt het gewoon aftelbaar via de diagonaal methode van Cantor net zoals de aftelbaarheid van Q wordt bewezen.

Het moet het late uur geweest zijn maar bovenstaande is niet goed bedenk ik me nu.

Het geldt wel voor een eindig aantal N*N*....*N, dan kan het herhaald worden toegepast maar niet persé voor een oneindig aantal.

[TD]

Meer nog: met een diagonaalargument à la Cantor kan je tonen dat het niet meer aftelbaar is, als je een aftelbaar aantal kopies van N in een cartesisch product neemt.