Bewijzen aftelbaar oneindige verzamelingen
Moderators: ArcherBarry, Fuzzwood
- Berichten: 524
Bewijzen aftelbaar oneindige verzamelingen
Hallo,
Hopelijk kunnen jullie me met deze opgaven op weg helpen, want ik weet niet goed hoe ik moet beginnen.
-----
Bewijs dat de volgende verzamelingen aftelbaar oneindig zijn:
a) { 3n | n is element van Z } (Z = alle gehele getallen).
b) Z * Z
c) De verzameling van alle woorden bestaande uit de letters {a,b,c} d.w.z.:
{ ∅, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, ... }
Hier betekent ∅ het lege woord bestaande uit 0 letters.
-----
Alvast bedankt!
Hopelijk kunnen jullie me met deze opgaven op weg helpen, want ik weet niet goed hoe ik moet beginnen.
-----
Bewijs dat de volgende verzamelingen aftelbaar oneindig zijn:
a) { 3n | n is element van Z } (Z = alle gehele getallen).
b) Z * Z
c) De verzameling van alle woorden bestaande uit de letters {a,b,c} d.w.z.:
{ ∅, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, ... }
Hier betekent ∅ het lege woord bestaande uit 0 letters.
-----
Alvast bedankt!
- Berichten: 5.679
Re: Bewijzen aftelbaar oneindige verzamelingen
Een oneindige verzameling A is aftelbaar als je alle elementen kunt nummeren, dus zodanig dat ieder element een keer aan de beurt komt. Of anders gezegd, als je een surjectie* van
Tip voor vraag a: bewijs eerst dat
Vraag b: weet je hoe je moet bewijzen dat
Vraag c: denk eens aan hoe getallen genoteerd worden in een 3-tallig stelsel.
\(\nn\)
naar A kunt maken. (*Verborgen inhoud
)Tip voor vraag a: bewijs eerst dat
\(\zz\)
aftelbaar is.Vraag b: weet je hoe je moet bewijzen dat
\(\qq\)
aftelbaar is? Iets soortgelijks kun je hier ook doen.Vraag c: denk eens aan hoe getallen genoteerd worden in een 3-tallig stelsel.
In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 524
Re: Bewijzen aftelbaar oneindige verzamelingen
a) Het is dus de bedoeling dat je bewijst datRogier schreef:Een oneindige verzameling A is aftelbaar als je alle elementen kunt nummeren, dus zodanig dat ieder element een keer aan de beurt komt. Of anders gezegd, als je een surjectie* van\(\nn\)naar A kunt maken. (*Verborgen inhoud)
Tip voor vraag a: bewijs eerst dat\(\zz\)aftelbaar is.
Vraag b: weet je hoe je moet bewijzen dat\(\qq\)aftelbaar is? Iets soortgelijks kun je hier ook doen.
Vraag c: denk eens aan hoe getallen genoteerd worden in een 3-tallig stelsel.
\(\zz\)
een surjectie is? Zo ja, hoe moet ik dit gaan aanpakken?b) Waarom moet je bewijzen dat
\(\qq\)
aftelbaar is? Het gaat hier toch om \(\zz\)
?c) Hoe getallen genoteerd worden? Je bedoelt dat {1,2,3} = {3,2,1} of gaat het hier om {123}?
- Berichten: 24.578
Re: Bewijzen aftelbaar oneindige verzamelingen
Misschien niet alles tegelijk doen. Kies alvast een opgave om eerst uit te werken, bijvoorbeeld:
a) Een verzameling kan geen surjectie zijn... Je kan een bijectie tussen N en Z maken, verder is z -> 3z duidelijk een bijectie.
b) Nee, om Z x Z (vermoed ik), dat zijn koppels gehele getallen. Bovendien kan je een breuk q = a/b uit Q zien als (a,b); met b niet-nul.
a) Een verzameling kan geen surjectie zijn... Je kan een bijectie tussen N en Z maken, verder is z -> 3z duidelijk een bijectie.
b) Nee, om Z x Z (vermoed ik), dat zijn koppels gehele getallen. Bovendien kan je een breuk q = a/b uit Q zien als (a,b); met b niet-nul.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)
- Berichten: 524
Re: Bewijzen aftelbaar oneindige verzamelingen
a) Oké. Maar hoe bewijs je dat n --> 3n een bijectie is? Dan moest hij toch injectief en surjectief zijn? Dus f(a) = f(a'), a = a' en surjectief ben ik even kwijt.TD schreef:Misschien niet alles tegelijk doen. Kies alvast een opgave om eerst uit te werken, bijvoorbeeld:
a) Een verzameling kan geen surjectie zijn... Je kan een bijectie tussen N en Z maken, verder is z -> 3z duidelijk een bijectie.
b) Nee, om Z x Z (vermoed ik), dat zijn koppels gehele getallen. Bovendien kan je een breuk q = a/b uit Q zien als (a,b); met b niet-nul.
b) Het gaat hier toch om een vermenigvuldiging, geen breuk?
- Berichten: 24.578
Re: Bewijzen aftelbaar oneindige verzamelingen
Het lijkt me toch handiger om een opgave per keer te doen. Hier een reactie op beide, maar probeer misschien eerst eentje verder uit te werken.
a) Als n verschilt van m, dan 3n ook van 3m; verder wordt elke k bereikt want n -> 3n zorgt ervoor dat k het beeld is van k/3. Veel eenvoudiger dan schalingen zullen de bijecties niet komen... .
b) Dat ligt eraan wat je met "Z * Z" in je opgave bedoelt. Ik vermoed \(\zz \times \zz\), het "cartesisch product" van Z met Z en dat is precies de verzameling van koppels (p,q) met p en q in Z. Die kan je dan weer in verband brengen met Q, want p/q kan je in bijectie brengen met (p,q).
a) Als n verschilt van m, dan 3n ook van 3m; verder wordt elke k bereikt want n -> 3n zorgt ervoor dat k het beeld is van k/3. Veel eenvoudiger dan schalingen zullen de bijecties niet komen... .
b) Dat ligt eraan wat je met "Z * Z" in je opgave bedoelt. Ik vermoed \(\zz \times \zz\), het "cartesisch product" van Z met Z en dat is precies de verzameling van koppels (p,q) met p en q in Z. Die kan je dan weer in verband brengen met Q, want p/q kan je in bijectie brengen met (p,q).
"Malgré moi, l'infini me tourmente." (Alfred de Musset)
- Berichten: 524
Re: Bewijzen aftelbaar oneindige verzamelingen
a) Wat houdt het begrip 'bijectie' nou eigenlijk in?TD schreef:Het lijkt me toch handiger om een opgave per keer te doen. Antwoord op beide, maar probeer misschien eerst eentje verder uit te werken.
a) Als n verschilt van m, dan 3n ook van 3m; verder wordt elke k bereikt want n -> 3n zorgt ervoor dat k het beeld is van k/3. Veel eenvoudiger dan schalingen zullen de bijecties niet komen... .
b) Dat ligt eraan wat je met "Z * Z" in je opgave bedoelt. Ik vermoed \(\zz \times \zz\), het "cartesisch product" van Z met Z en dat is precies de verzameling van koppels (p,q) met p en q in Z. Die kan je dan weer in verband brengen met Q, want p/q kan je in bijectie brengen met (p,q).
b) Ik bedoel inderdaad \(\zz \times \zz\).
- Berichten: 24.578
Re: Bewijzen aftelbaar oneindige verzamelingen
Een afbeelding van A naar B heet "bijectie" als de afbeelding injectief en surjectief is; met andere woorden als de afbeelding met elk element a uit A precies één element b uit B associeert en omgekeerd. Een bijectie is met andere woorden een "een-op-een verband" tussen twee verzamelingen; het koppelt op unieke wijze paren van elementen uit de twee verzamelingen.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)
- Berichten: 524
Re: Bewijzen aftelbaar oneindige verzamelingen
Oké, dus als alleen element a uit A is verbonden met bijvoorbeeld b en c uit B. Dan is de functie injectief?
Als element a en d uit A verbonden zijn met alleen b uit B. Dan is de functie surjectief?
Bijectief is dan als a uit A allen met b uit B verbonden is?
Als element a en d uit A verbonden zijn met alleen b uit B. Dan is de functie surjectief?
Bijectief is dan als a uit A allen met b uit B verbonden is?
- Berichten: 5.679
Re: Bewijzen aftelbaar oneindige verzamelingen
Op wikipedia staan duidelijke plaatjes: injectie en surjectie. En een bijectie is dus een functie die zowel injectief als surjectief is.Fruitschaal schreef:Oké, dus als alleen element a uit A is verbonden met bijvoorbeeld b en c uit B. Dan is de functie injectief?
Als element a en d uit A verbonden zijn met alleen b uit B. Dan is de functie surjectief?
Bijectief is dan als a uit A allen met b uit B verbonden is?
In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 524
Re: Bewijzen aftelbaar oneindige verzamelingen
Injectie begrijp ik, maar surjectie vind ik nogal vaag.
Dit moet surjectie voorstellen, maar van C gaat er toch een lijn naar 3 én naar 4? Dan is het toch niet surjectief?
- Berichten: 5.679
Re: Bewijzen aftelbaar oneindige verzamelingen
Let op, het is een functie van verzameling X naar verzameling Y, niet andersom. Dus de pijlen gaan in dit geval van 3 naar C en van 4 naar C. Niet van C naar 3 en 4.Dit moet surjectie voorstellen, maar van C gaat er toch een lijn naar 3 én naar 4? Dan is het toch niet surjectief?
Dat wil zeggen: f(3)=C en f(4)=C (waarbij f de functie van X naar Y is).
Het is een surjectie omdat er voor ieder element y uit Y, er minstens één x in X bestaat zodat f(x)=y (en in het geval y=C zijn er zelfs twee x'en, namelijk x=3 en x=4). Anders uitgedrukt: als alle elementen uit Y worden bereikt door f.
Als de situatie als volgt was zou het geen surjectie zijn:
Want er is nu geen x ∈ X zodat f(x)=A.
Nog even voor de volledigheid, misschien helpt dit:
Een functie f:X→Y heet een surjectie als er voor ieder element y in Y, er minstens één x in X bestaat zodat f(x)=y.
Een functie f:X→Y heet een injectie als er voor ieder element y in Y, er hoogstens één x in X bestaat zodat f(x)=y.
En een bijectie combineert deze twee eigenschappen:
Een functie f:X→Y heet een bijectie als er voor ieder element y in Y, er precies één x in X bestaat zodat f(x)=y.
In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 524
Re: Bewijzen aftelbaar oneindige verzamelingen
Erg bedankt! Dat snap ik dan nu tenminste.
Maar goed, wat voor nut heeft een bijectie voor deze opgave?
Maar goed, wat voor nut heeft een bijectie voor deze opgave?
- Berichten: 5.679
Re: Bewijzen aftelbaar oneindige verzamelingen
"Bewijs dat X aftelbaar oneindig is" komt neer op "bewijs dat er een bijectie bestaat tussenMaar goed, wat voor nut heeft een bijectie voor deze opgave?
\(\nn\)
en X".In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 524
Re: Bewijzen aftelbaar oneindige verzamelingen
Oké, dat begrijp ik. Je moet dus bewijzen dat er voor elk element in X één en alleen één element in"Bewijs dat X aftelbaar oneindig is" komt neer op "bewijs dat er een bijectie bestaat tussen\(\nn\)en X".
\(\nn\)
is. Maar hoe doe je dat?