Springen naar inhoud

Bewijzen aftelbaar oneindige verzamelingen


  • Log in om te kunnen reageren

#1

Fruitschaal

    Fruitschaal


  • >250 berichten
  • 524 berichten
  • Ervaren gebruiker

Geplaatst op 21 oktober 2010 - 09:58

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!

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 21 oktober 2010 - 10:21

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 LaTeX naar A kunt maken. (*
Verborgen inhoud
een functie naar A is een surjectie als ieder element van A bereikt wordt, oftewel als er voor ieder element a ∈ A een x bestaat zodat f(x)=a
)

Tip voor vraag a: bewijs eerst dat LaTeX aftelbaar is.

Vraag b: weet je hoe je moet bewijzen dat LaTeX aftelbaar is? Iets soortgelijks kun je hier ook doen.

Vraag c: denk eens aan hoe getallen genoteerd worden in een 3-tallig stelsel.

Veranderd door Rogier, 21 oktober 2010 - 10:21

In theory, there's no difference between theory and practice. In practice, there is.

#3

Fruitschaal

    Fruitschaal


  • >250 berichten
  • 524 berichten
  • Ervaren gebruiker

Geplaatst op 03 november 2010 - 18:56

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 LaTeX

naar A kunt maken. (*
Verborgen inhoud
een functie naar A is een surjectie als ieder element van A bereikt wordt, oftewel als er voor ieder element a ∈ A een x bestaat zodat f(x)=a
)

Tip voor vraag a: bewijs eerst dat LaTeX aftelbaar is.

Vraag b: weet je hoe je moet bewijzen dat LaTeX aftelbaar is? Iets soortgelijks kun je hier ook doen.

Vraag c: denk eens aan hoe getallen genoteerd worden in een 3-tallig stelsel.

a) Het is dus de bedoeling dat je bewijst dat LaTeX een surjectie is? Zo ja, hoe moet ik dit gaan aanpakken?

b) Waarom moet je bewijzen dat LaTeX aftelbaar is? Het gaat hier toch om LaTeX ?

c) Hoe getallen genoteerd worden? Je bedoelt dat {1,2,3} = {3,2,1} of gaat het hier om {123}?

#4

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 03 november 2010 - 19:17

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.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#5

Fruitschaal

    Fruitschaal


  • >250 berichten
  • 524 berichten
  • Ervaren gebruiker

Geplaatst op 03 november 2010 - 19:41

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) 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.

b) Het gaat hier toch om een vermenigvuldiging, geen breuk?

#6

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 03 november 2010 - 19:46

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 LaTeX , 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)

#7

Fruitschaal

    Fruitschaal


  • >250 berichten
  • 524 berichten
  • Ervaren gebruiker

Geplaatst op 03 november 2010 - 19:48

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 LaTeX

, 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) Wat houdt het begrip 'bijectie' nou eigenlijk in?

b) Ik bedoel inderdaad LaTeX .

#8

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 03 november 2010 - 19:51

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)

#9

Fruitschaal

    Fruitschaal


  • >250 berichten
  • 524 berichten
  • Ervaren gebruiker

Geplaatst op 03 november 2010 - 20:23

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?

#10

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 03 november 2010 - 20:39

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?

Op wikipedia staan duidelijke plaatjes: injectie en surjectie. En een bijectie is dus een functie die zowel injectief als surjectief is.
In theory, there's no difference between theory and practice. In practice, there is.

#11

Fruitschaal

    Fruitschaal


  • >250 berichten
  • 524 berichten
  • Ervaren gebruiker

Geplaatst op 03 november 2010 - 20:42

Op wikipedia staan duidelijke plaatjes: injectie en surjectie. En een bijectie is dus een functie die zowel injectief als surjectief is.

Injectie begrijp ik, maar surjectie vind ik nogal vaag.
Geplaatste afbeelding
Dit moet surjectie voorstellen, maar van C gaat er toch een lijn naar 3 én naar 4? Dan is het toch niet surjectief?

#12

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 03 november 2010 - 21:09

Dit moet surjectie voorstellen, maar van C gaat er toch een lijn naar 3 én naar 4? Dan is het toch niet surjectief?

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.

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:

Geplaatste afbeelding

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.

#13

Fruitschaal

    Fruitschaal


  • >250 berichten
  • 524 berichten
  • Ervaren gebruiker

Geplaatst op 03 november 2010 - 21:15

Erg bedankt! Dat snap ik dan nu tenminste.

Maar goed, wat voor nut heeft een bijectie voor deze opgave?

#14

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 03 november 2010 - 21:43

Maar goed, wat voor nut heeft een bijectie voor deze opgave?

"Bewijs dat X aftelbaar oneindig is" komt neer op "bewijs dat er een bijectie bestaat tussen LaTeX en X".
In theory, there's no difference between theory and practice. In practice, there is.

#15

Fruitschaal

    Fruitschaal


  • >250 berichten
  • 524 berichten
  • Ervaren gebruiker

Geplaatst op 03 november 2010 - 21:49

"Bewijs dat X aftelbaar oneindig is" komt neer op "bewijs dat er een bijectie bestaat tussen LaTeX

en X".

Oké, dat begrijp ik. Je moet dus bewijzen dat er voor elk element in X één en alleen één element in LaTeX is. Maar hoe doe je dat?





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures