Selv om begge begrepene beskriver hvordan elementer mellom to sett kartlegges, adresserer de forskjellige sider av ligningen. En-til-en (injeksjon) funksjoner fokuserer på hvor unikt inngangene er, og sikrer at ingen to stier fører til samme destinasjon, mens onto (surjektiv) funksjoner sikrer at alle mulige destinasjoner faktisk nås.
Høydepunkter
En-til-en sikrer tydelighet; videre sikrer fullstendighet.
En funksjon som både er én-til-én og på kalles en bijeksjon.
Den horisontale linjetesten identifiserer én-til-én-funksjoner med et raskt blikk.
Onto-funksjoner krever at rekkevidden og kodomenet er identiske.
Hva er En-til-en (injeksjon)?
En kartlegging der hver unike input produserer en distinkt, unik output.
Formelt kalt en injeksjonsfunksjon i mengdelære.
Den består den horisontale linjetesten når den plottes på et koordinatplan.
Ingen to forskjellige elementer i domenet deler det samme bildet i kodomenet.
Antall elementer i domenet kan ikke overstige antallet i kodomenet.
Viktig for å lage inverse funksjoner fordi avbildningen kan reverseres uten tvetydighet.
Hva er På (Surjektiv)?
En kartlegging der hvert element i målsettet dekkes av minst én inngang.
Formelt kjent som en surjektiv funksjon.
Funksjonens rekkevidde er nøyaktig lik dens kodomene.
Flere innganger kan peke til samme utgang så lenge ingenting utelates.
Størrelsen på domenet må være større enn eller lik størrelsen på kodomenet.
Garanterer at hver verdi i utdatasettet har minst ett «forhåndsbilde».
Sammenligningstabell
Funksjon
En-til-en (injeksjon)
På (Surjektiv)
Formelt navn
Injeksjonsmiddel
Surjektiv
Kjernekrav
Unike utganger for unike innganger
Total dekning av målsettet
Horisontal linjetest
Må bestås (skjæres maksimalt én gang)
Må krysses minst én gang
Relasjonsfokus
Eksklusivitet
Inkludering
Angi størrelsesbegrensning
Domene ≤ Kodomene
Domene ≥ Kodomene
Delte utganger?
Strengt forbudt
Tillatt og vanlig
Detaljert sammenligning
Eksklusivitetsbegrepet
En én-til-én-funksjon er som en eksklusiv restaurant der hvert bord er reservert for nøyaktig én gruppe; du vil aldri se to forskjellige grupper som deler samme sete. Matematisk sett, hvis $f(a) = f(b)$, må $a$ være lik $b$. Denne eksklusiviteten er det som gjør at disse funksjonene kan «angres» eller inverteres.
Konseptet med dekning
En onto-funksjon er mer opptatt av å snu hver stein i målsettet. Tenk deg en buss der hvert eneste sete må være okkupert av minst én person. Det spiller ingen rolle om to personer må sitte på samme benk (mange-til-en), så lenge det ikke er et eneste ledig sete igjen på bussen.
Visualisering med kartleggingsdiagrammer
et avbildningsdiagram identifiseres én-til-én-forholdet med enkle piler som peker mot enkeltpunkter – ingen piler konvergerer noen gang. For en onto-funksjon må hver prikk i den andre sirkelen ha minst én pil som peker mot seg. En funksjon kan være begge deler, noe matematikere kaller en bijeksjon.
Grafiske forskjeller
På en standard graf tester du for én-til-én-status ved å skyve en horisontal linje opp og ned. Hvis den treffer kurven mer enn én gang, er ikke funksjonen én-til-én. Testing for 'på' krever at man ser på grafens vertikale spenn for å sikre at den dekker hele det tiltenkte området uten mellomrom.
Fordeler og ulemper
En-til-en
Fordeler
+Tillater inverse funksjoner
+Ingen datakollisjoner
+Bevarer særpreg
+Enklere å reversere
Lagret
−Kan la utgangene være ubrukte
−Krever større kodomene
−Strenge inndataregler
−Vanskeligere å oppnå
På
Fordeler
+Dekker hele målsettet
+Ingen bortkastet utdataplass
+Enklere å få plass til små sett
+Utnytter alle ressurser
Lagret
−Tap av unikhet
−Kan ikke alltid inverteres
−Kollisjoner er vanlige
−Vanskeligere å spore tilbake
Vanlige misforståelser
Myt
Alle funksjoner er enten én-til-én eller på.
Virkelighet
Mange funksjoner er ingen av delene. For eksempel er $f(x) = x^2$ (fra alle reelle tall til alle reelle tall) ikke én-til-én fordi både $2$ og $-2$ resulterer i $4$, og den er ikke på fordi den aldri produserer negative tall.
Myt
En-til-en betyr det samme som en funksjon.
Virkelighet
En funksjon krever bare at hver inngang har én utgang. Én-til-én er et ekstra lag med «strenghet» som forhindrer at to innganger deler den utgangen.
Myt
Onto avhenger kun av formelen.
Virkelighet
Til avhenger i stor grad av hvordan du definerer målsettet. Funksjonen $f(x) = x^2$ er til hvis du definerer målet som 'alle ikke-negative tall', men mislykkes hvis målet er 'alle reelle tall'.
Myt
Hvis en funksjon er onto, må den være reversibel.
Virkelighet
Reversibilitet krever én-til-én-status. Hvis en funksjon er på, men ikke én-til-én, vet du kanskje hvilken utdata du har, men du vet ikke hvilken av de flere inngangene som opprettet den.
Ofte stilte spørsmål
Hva er et enkelt eksempel på en én-til-én-funksjon?
Den lineære funksjonen $f(x) = x + 1$ er et klassisk eksempel. Hvert tall du setter inn vil gi deg et unikt resultat som ingen andre tall kan produsere. Hvis du får et resultat på 5, vet du med sikkerhet at inputen var 4.
Hva er et enkelt eksempel på en onto-funksjon?
Tenk deg en funksjon som knytter alle innbyggere i en by til bygningen de bor i. Hvis hver bygning har minst én person inni, er funksjonen «på» settet med bygninger. Den er imidlertid ikke én-til-én, fordi mange mennesker deler den samme bygningen.
Hvordan fungerer den horisontale linjetesten?
Se for deg en horisontal linje som beveger seg opp og ned over grafen din. Hvis den linjen noen gang berører funksjonen på to eller flere steder samtidig, betyr det at disse forskjellige x-verdiene deler en y-verdi, noe som beviser at den ikke er én-til-én.
Hvorfor er disse konseptene viktige i informatikk?
De er viktige for datakryptering og hashing. En god krypteringsalgoritme må være én-til-én, slik at du kan dekryptere meldingen tilbake til sin opprinnelige unike form uten å miste data eller få blandede resultater.
Hva skjer når en funksjon er både én-til-én og på?
Dette er en «bijeksjon» eller en «én-til-én-korrespondanse». Det skaper en perfekt paring mellom to mengder der hvert element har nøyaktig én partner på den andre siden. Dette er gullstandarden for å sammenligne størrelsene på uendelige mengder.
Kan en funksjon være på, men ikke én-til-én?
Ja, det skjer ofte. $f(x) = x^3 - x$ er på alle reelle tall fordi det går fra negativ uendelighet til positiv uendelighet, men det er ikke én-til-én fordi det krysser x-aksen på tre forskjellige punkter (-1, 0 og 1).
Hva er forskjellen mellom rekkevidde og kodomene?
Kodomenet er «målsettet» du annonserer i starten (som «alle reelle tall»). Verdiene er verdiene funksjonen faktisk treffer. En funksjon er bare på når verdiområdet og kodomenet er identiske.
Er $f(x) = \sin(x)$ én-til-én?
Nei, sinusfunksjonen er ikke en-til-en-funksjonen fordi den gjentar verdiene sine hver 2 π radian. For eksempel er π sin(0) π, π sin(π) π og π sin(2 π) π alle lik 0.
Vurdering
Bruk en én-til-én-kartlegging når du må sikre at alle resultater kan spores tilbake til et spesifikt, unikt utgangspunkt. Velg en onto-kartlegging når målet ditt er å sikre at alle mulige utgangsverdier i et system utnyttes eller oppnås.