teoria de conjuntsfuncionsàlgebramatemàtiques discretes
Funcions un a un vs. funcions sobre un
Tot i que ambdós termes descriuen com es mapegen els elements entre dos conjunts, aborden diferents costats de l'equació. Les funcions un a un (injectives) se centren en la singularitat de les entrades, garantint que no hi hagi dos camins que portin a la mateixa destinació, mentre que les funcions surjectives (surjectives) asseguren que realment s'arribi a totes les destinacions possibles.
Destacats
Un a un assegura la distinció; onto assegura la completesa.
Una funció que és alhora bijectiva i sobreposada s'anomena bijecció.
La prova de línia horitzontal identifica funcions biunívoques d'un cop d'ull.
Les funcions onto requereixen que el rang i el codomini siguin idèntics.
Què és Un a un (injectiu)?
Un mapatge on cada entrada única produeix una sortida diferent i única.
Formalment anomenada funció injectiva en teoria de conjunts.
Supera la prova de la línia horitzontal quan es representa en un pla de coordenades.
Cap dos elements diferents del domini comparteix la mateixa imatge al codomini.
El nombre d'elements del domini no pot superar el nombre del codomini.
Essencial per crear funcions inverses perquè la funció es pot invertir sense ambigüitat.
Què és Sobre (surjectiu)?
Un mapatge on cada element del conjunt de destinacions està cobert per almenys una entrada.
Formalment coneguda com a funció surjectiva.
El rang de la funció és exactament igual al seu codomini.
Es permet que diverses entrades apuntin a la mateixa sortida sempre que no es deixi res de banda.
La mida del domini ha de ser major o igual que la mida del codomini.
Garanteix que cada valor del conjunt de sortida tingui com a mínim una "preimatge".
Taula comparativa
Funcionalitat
Un a un (injectiu)
Sobre (surjectiu)
Nom formal
Injectiu
Sobrejectiu
Requisit bàsic
Sortides úniques per a entrades úniques
Cobertura total de l'objectiu establert
Prova de línia horitzontal
Ha de passar (es creua com a màxim una vegada)
S'ha d'intersectar almenys una vegada
Enfocament en la relació
Exclusivitat
Inclusió
Estableix la restricció de mida
Domini ≤ Codomini
Domini ≥ Codomini
Sortides compartides?
Estrictament prohibit
Permès i comú
Comparació detallada
El concepte d'exclusivitat
Una funció individual és com un restaurant de luxe on cada taula està reservada per a exactament una persona; mai no veureu dos grups diferents compartint el mateix seient. Matemàticament, si $f(a) = f(b)$, aleshores $a$ ha de ser igual a $b$. Aquesta exclusivitat és el que permet que aquestes funcions es puguin "desfer" o invertir.
El concepte de cobertura
Una funció onto es preocupa més de no deixar pedra sense moure en l'objectiu establert. Imagineu-vos un autobús on tots els seients han d'estar ocupats per almenys una persona. No importa si dues persones han de seure al mateix banc (molts a un), sempre que no quedi ni un sol seient buit a l'autobús.
Visualització amb diagrames de mapatge
En un diagrama de mapatge, l'un a un s'identifica mitjançant fletxes individuals que apunten a punts individuals; mai no hi ha dues fletxes que convergeixin. Per a una funció onto, cada punt del segon cercle ha de tenir almenys una fletxa que hi apunti. Una funció pot ser ambdues coses, cosa que els matemàtics anomenen bijecció.
Diferències gràfiques
En un gràfic estàndard, es comprova l'estat biunívoc fent lliscar una línia horitzontal amunt i avall; si toca la corba més d'una vegada, la funció no és biunívoca. Per comprovar si hi ha "onto", cal mirar l'extensió vertical del gràfic per assegurar-se que cobreix tot el rang previst sense buits.
Avantatges i Inconvenients
Un a un
Avantatges
+Permet funcions inverses
+Sense col·lisions de dades
+Conserva la distinció
+Més fàcil de revertir
Consumit
−Pot deixar les sortides sense utilitzar
−Requereix un codomini més gran
−Normes d'entrada estrictes
−Més difícil d'aconseguir
A
Avantatges
+Cobreix tot el conjunt d'objectius
+Sense espai de sortida malgastat
+Més fàcil d'adaptar a conjunts petits
+Utilitza tots els recursos
Consumit
−Pèrdua d'unicitat
−No sempre es pot invertir
−Les col·lisions són habituals
−Més difícil de rastrejar
Conceptes errònies habituals
Mite
Totes les funcions són o bé una a una o bé interaccionants.
Realitat
Moltes funcions no són cap de les dues coses. Per exemple, $f(x) = x^2$ (de tots els nombres reals a tots els nombres reals) no és uniuntiva perquè $2$ i $-2$ donen com a resultat $4$, i no és uniuntiva perquè mai produeix nombres negatius.
Mite
Un a un significa el mateix que una funció.
Realitat
Una funció només requereix que cada entrada tingui una sortida. L'un a un és una capa addicional de "rigurositat" que impedeix que dues entrades comparteixin aquesta sortida.
Mite
Onto només depèn de la fórmula.
Realitat
Onto depèn en gran mesura de com definiu el conjunt d'objectius. La funció $f(x) = x^2$ és onto si definiu l'objectiu com "tots els nombres no negatius", però falla si l'objectiu són "tots els nombres reals".
Mite
Si una funció és sobre, ha de ser reversible.
Realitat
La reversibilitat requereix un estat biunívoc. Si una funció està activa però no és biunívoca, és possible que sàpigues quina sortida tens, però no sabràs quina de les múltiples entrades l'ha creada.
Preguntes freqüents
Quin és un exemple senzill d'una funció uniuniva?
La funció lineal $f(x) = x + 1$ és un exemple clàssic. Cada nombre que introduïu us donarà un resultat únic que cap altre nombre pot produir. Si obteniu una sortida de 5, sabeu del cert que l'entrada era 4.
Quin és un exemple senzill d'una funció onto?
Considerem una funció que assigna cada resident d'una ciutat a l'edifici on viuen. Si cada edifici té almenys una persona a dins, la funció és "sobre" el conjunt d'edificis. Tanmateix, no és uniunívoca, perquè molta gent comparteix el mateix edifici.
Com funciona la prova de la línia horitzontal?
Visualitza una línia horitzontal que es mou amunt i avall pel gràfic. Si aquesta línia toca la funció en dos o més llocs alhora, vol dir que aquests valors x diferents comparteixen un valor y, cosa que demostra que no és unidireccional.
Per què són importants aquests conceptes en informàtica?
Són vitals per al xifratge de dades i el resum. Un bon algorisme de xifratge ha de ser un a un per poder desxifrar el missatge a la seva forma original i única sense perdre dades ni obtenir resultats contradictoris.
Què passa quan una funció és alhora unitiva i sobreinversible?
Això és una "bijecció" o una "correspondència biunívoca". Crea un aparellament perfecte entre dos conjunts on cada element té exactament una parella a l'altre costat. Aquest és l'estàndard d'or per comparar les mides de conjunts infinits.
Pot una funció ser sobre però no biunívoca?
Sí, passa sovint. $f(x) = x^3 - x$ és aplicable a tots els nombres reals perquè abasta des de l'infinit negatiu fins a l'infinit positiu, però no és unidireccional perquè creua l'eix x en tres punts diferents (-1, 0 i 1).
Quina diferència hi ha entre rang i codomini?
El codomini és el conjunt "objectiu" que anuncies al principi (com ara "tots els nombres reals"). El rang és el conjunt de valors que realment arriba a la funció. Una funció només entra en joc quan el rang i el codomini són idèntics.
És $f(x) = \sin(x)$ un a un?
No, la funció sinusoidal no és en absolut biunívoca perquè repeteix els seus valors cada $2\pi$ radians. Per exemple, $\sin(0)$, $\sin(\pi)$ i $\sin(2\pi)$ són totes iguals a 0.
Veredicte
Feu servir un mapatge un a un quan necessiteu assegurar-vos que cada resultat es pugui rastrejar fins a un punt de partida específic i únic. Trieu un mapatge onto quan el vostre objectiu sigui garantir que tots els valors de sortida possibles d'un sistema s'utilitzin o es puguin assolir.