Springen naar inhoud

[wiskunde] injectie en surjectie


  • Log in om te kunnen reageren

#1

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 06 oktober 2009 - 22:39

Hoe bewijs je dat een injectie links invers is en dat een surjectie rechtsinvers is?

Bedankt!
"C++ : Where friends have access to your private members." — Gavin Russell Baker.

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

#2

TD

    TD


  • >5k berichten
  • 24051 berichten
  • VIP

Geplaatst op 06 oktober 2009 - 23:39

Zorgvuldiger formuleren: als een functie injectief is, heeft die functie een linker inverse (en omgekeerd); analoog voor de surjectie met een rechter inverse.

Neem een f:X->Y en beschouw y = f(x) met x in X en y in Y. Definieer g zodat g(y) = x. Omdat f injectief is, is die x uniek. Eventueel bestaat x niet, als y niet behoort tot het beeld van f. Het volstaat dan g(y) willekeurig te definiŽren, zodat g toch bestaat voor elk element uit Y. Op die manier is g:Y->X een functie die per constructie voldoet aan g(f(x)) = x, dus een linkerinverse is voor f.

De andere richting is eenvoudiger, probeer dat zelf en zo ook voor de surjectie.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#3

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 31 oktober 2009 - 21:46

De andere richting heb ik gevonden voor het deeltje over injectie:
f(a)=f(a') => g(f(a))=g(f(a'))=>a=a' en we hebben het criterium voor injectie bewezen door gebruik te maken van de definitie van de links inverse in de laatste stap: afgebeeld op de identiteit op A.
=> klopt dit?


Voor surjectief geldt:

g(y)=x en deze x bestaat altijd wegens de surjectiviteit
fįg=f(g(y))=f(x)=y= identiteit op B, dus er bestaat een rechts inverse
=> klopt dit?

Andere richting:
fįg=identiteit op B
=> hoe bewijs je hier de surjectiviteit?

Nogmaals bedankt voor uw moeite!
"C++ : Where friends have access to your private members." — Gavin Russell Baker.

#4

Phys

    Phys


  • >5k berichten
  • 7556 berichten
  • VIP

Geplaatst op 31 oktober 2009 - 21:56

De andere richting heb ik gevonden voor het deeltje over injectie:
f(a)=f(a') => g(f(a))=g(f(a'))=>a=a' en we hebben het criterium voor injectie bewezen door gebruik te maken van de definitie van de links inverse in de laatste stap: afgebeeld op de identiteit op A.
=> klopt dit?

Je hebt hier (correct) aangetoond dat als f een linksinverse g heeft, dan is f injectief.

Voor surjectief geldt:

g(y)=x en deze x bestaat altijd wegens de surjectiviteit
fįg=f(g(y))=f(x)=y= identiteit op B, dus er bestaat een rechts inverse
=> klopt dit?

Dit is volg ik niet, bovendien is het erg slordig opgeschreven. Blijkbaar neem je aan dat g surjectief is. Je gaat vervolgens aantonen dat er een rechtsinverse bestaat? Iets duidelijker zijn graag.

Andere richting:
fįg=identiteit op B
=> hoe bewijs je hier de surjectiviteit?

Ook dit is onzorgvuldig opgeschreven. Wat zijn f en g? Mogelijk wil je aantonen dat als er voor de (gegeven) functie f een rechtsinverse g is (zodat f o g=id), dan is f surjectief. Neem daartoe een y in het codomein van f. Je wilt een x in het domein van f vinden zodat f(x)=y. Maar uit de aanname volgt al direct y=f(g(y)). Dus...?
Never express yourself more clearly than you think.
- Niels Bohr -

#5

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 03 november 2009 - 21:30

Ik denk dat het zo zit voor het laatste puntje, (wiskundig correct genoteerd):

f:X :eusa_whistle: Y : f(x)=y

Definieer nu een functie g(y)=x
Laat de functie f inwerken op beide leden, dan bekomt men:
f(g(y))=f(x)
Het linkerlid is, wegens het gegeven dat fįg de identiteit op Y is, gelijk aan y. Men bekomt dan:
y=f(x).

Het enige wat nog wringt, is of je de functie g(y)=x mag definiŽren (en of ze steeds bestaat).
Kan u daar nogmaals een antwoord opgeven? Bedankt!
"C++ : Where friends have access to your private members." — Gavin Russell Baker.

#6

Phys

    Phys


  • >5k berichten
  • 7556 berichten
  • VIP

Geplaatst op 03 november 2009 - 22:20

Het enige wat nog wringt, is of je de functie g(y)=x mag definiŽren (en of ze steeds bestaat).
Kan u daar nogmaals een antwoord opgeven? Bedankt!

Je moet toch echt iets duidelijker zijn over wŠt je nu precies wilt bewijzen. Als ik het goed begrijp, wil je aantonen:
Als er voor de (gegeven) functie f:X->Y een functie g:Y->X bestaat zodat f o g=id, dan is f surjectief.
Jij moet g dus niet gaan definiŽren, gegeven is dat f o g =id. Dat betekent precies dat f(g(y))=y voor alle y in Y. Aantonen dat f surjectief is, betekent aantonen dat voor iedere y in Y er een x in X bestaat zodat f(x)=y.

Begrijp je dit allemaal, en zie je waar ik heen wil?

Ik gaf eigenlijk het antwoord al weg:

Neem daartoe een y in het codomein van f. Je wilt een x in het domein van f vinden zodat f(x)=y. Maar uit de aanname volgt al direct y=f(g(y)). Dus...?

Never express yourself more clearly than you think.
- Niels Bohr -

#7

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 03 november 2009 - 22:45

Ik begin het te begrijpen (denk ik).
Aangezien je vertrekt van het gegeven y=f(g(y)) en dit voor iedere y in Y, is de surjectiviteit feitelijk bewezen aangezien je net moet bewijzen dat er voor iedere y in het beeld een x bestaat in X zodat f(x)=y.

Voor iedere y geldt:
y=f(g(y))
en dus ook:
y=f(x)
omdat g(y)=x voor iedere y.

Is het nu wel correct of doe ik het nog steeds verkeerd?
Bedankt voor uw uitgebreid antwoord!
"C++ : Where friends have access to your private members." — Gavin Russell Baker.

#8

Phys

    Phys


  • >5k berichten
  • 7556 berichten
  • VIP

Geplaatst op 03 november 2009 - 23:01

Ik begin het te begrijpen (denk ik).
Aangezien je vertrekt van het gegeven y=f(g(y)) en dit voor iedere y in Y, is de surjectiviteit feitelijk bewezen aangezien je net moet bewijzen dat er voor iedere y in het beeld een x bestaat in X zodat f(x)=y.

Voor iedere y geldt:
y=f(g(y))
en dus ook:
y=f(x)
omdat g(y)=x voor iedere y.

Is het nu wel correct of doe ik het nog steeds verkeerd?
Bedankt voor uw uitgebreid antwoord!

Ik denk dat je nog wat moeite hebt met begrijpen wat je gegevens betekenen en wat je moet bewijzen; het bewijs zelf stel namelijk niets voor. Daarom een wat uitgebreidere uitleg.

Gegeven is een functie f:X->Y, en gegeven is het bestaan van een g:Y->X met de eigenschap dat f o g = id_Y. Het enige dat we weten is dat zo'n g bestaat, verder hebben we er helemaal geen informatie over; we hebben ook geen andere informatie nodig dan dat f o g = id_Y geldt. De identiteit is de functie die ieder element op zichzelf afbeeldt, dus id_Y:Y->Y voldoet aan id_Y(y)=y voor alle y in Y. Als we zeggen dat f o g gelijk is aan id_Y, zeggen we dus de samenstelling (f o g):Y->Y voldoet aan (f o g)(y)=y voor alle y in Y. Oftewel, f(g(y))=y voor alle y in Y.

We willen aantonen dat f:X->Y surjectief is. Dat betekent, we moeten aantonen dat voor iedere y in Y een x in X bestaat zodat f(x)=y. Dus, we nemen een willekeurige y0 in Y. We weten dat f(g(y))=y voor alle y in Y. Dus dit geldt voor y0: f(g(y0))=y0. We moesten een x in X vinden zodat f(x)=y0. Maar we hebben dus aangetoond dat x=g(y0) hieraan voldoet! QED

Je opmerking "omdat g(y)=x voor iedere y" is vreemd, want je neemt een willekeurige y in Y (die is vast), en definieert dan x=g(y). Je zegt dus dat g(y), een element uit X, voldoet, en je noemt dit gewoon x.
Never express yourself more clearly than you think.
- Niels Bohr -

#9

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 03 november 2009 - 23:12

Dat verduidelijkt de zaak veel. Het bestaan van zo'n identiteit op Y betekent dus dat er voor elke y een pijl van een functie g aankomt in Y, net daar waar de pijl van de oorspronkelijke functie f vertrokken was?
"C++ : Where friends have access to your private members." — Gavin Russell Baker.

#10

Phys

    Phys


  • >5k berichten
  • 7556 berichten
  • VIP

Geplaatst op 04 november 2009 - 00:27

Het bestaan van zo'n identiteit op Y

Let op je formulering: op iedere verzameling A bestaat de identiteit, namelijk de functie die iedere a in A naar zichzelf (a) stuurt. Je bedoelt: het bestaan van een g:Y->X zodat f o g gelijk is aan de identiteit op Y.

betekent dus dat er voor elke y een pijl van een functie g aankomt in Y, net daar waar de pijl van de oorspronkelijke functie f vertrokken was?

Wat je precies met 'een pijl' bedoelt weet ik niet (ik ken geen definitie van 'een pijl van een functie').

g stuurt ieder punt y in Y naar dat punt x=g(y) waarvoor geldt f(x)=y. Dus g stuurt y naar dŪe x, die f naar y stuurt. Dat is precies de betekenis van een rechtsinverse: f(g(y))=y voor alle y in Y.
Never express yourself more clearly than you think.
- Niels Bohr -

#11

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 04 november 2009 - 19:11

Het was de gewoonte om het 'pad' van een functie te volgen met een pijl. Als er slechts ťťn pijl toekomt in elk punt van Y, spreken we van een injectie, als in elk punt van Y een pijl aankomt spreken we van een surjectie.

Het begrip 'pijl' werd idd niet gedefinieerd, maar wel gebruikt ter illustratie.
"C++ : Where friends have access to your private members." — Gavin Russell Baker.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures