Funció exhaustiva

De Viquipèdia
Dreceres ràpides: navegació, cerca
Una funció exhaustiva.
Un altre funció exhaustiva.
Una funció que no és exhaustiva.
Composició exhaustiva: la primera funció no cal que sigui exhaustiva.

En matemàtiques, es diu que una funció f entre dos conjunts és exhaustiva (també dita epijectiva, suprajectiva o surjectiva) quan tot element del conjunt d'arribada és imatge d'almenys un element del domini. És a dir, els valors de la funció abasten completament el codomini; això és: per a cada element y del codomini, hi ha almenys un x del domini tal que f(x) = y.

Dit d'un altre forma, una funció fX → Y és exhaustiva si i només si el seu recorregut f(X) és igual al seu codomini Y.

Les funcions exhaustives que també són injectives s'anomenen funcions bijectives.

Exemples[modifica | modifica el codi]

  • Per a qualsevol conjunt X, la funció identitat idX de X és exhaustiva.
  • La funció f: ℝ → ℝ definida per f(x) = 2x + 1 és exhaustiva, perquè per a cada nombre real y es té f(x) = y on x és (y - 1)/2.
  • La funció logaritme natural ln: (0,+∞) → ℝ és exhaustiva.
  • La funció f: ℤ → {0,1,2,3} definida per f(x) = x mòdul 4 és exhaustiva.
  • En general, sigui ~ una relació d'equivalència dins el conjunt A, és exhaustiva la projecció canònica de pas al quocient π : A → A/~ que fa π(a) = [a]~ (la seva classe d'equivalència).
  • La funció g: ℝ → ℝ definida per g(x) = x² no és exhaustiva, perquè (per exemple) no hi ha cap nombre real x tal que x² = −1. Ara bé, si el codomini es defineix com [0,+∞), llavors g és exhaustiva.

Obtenció de funcions exhaustives[modifica | modifica el codi]

En general, sigui fX → Y una funció no necessàriament exhaustiva sempre podem definir la funció g : X → f(X) amb g(x)=f(x) per a tot x de X que sí que serà exhaustiva, ja que haurem definit com a conjunt d'arribada de g el seu recorregut.

Aquest procés s'utilitza per a invertir les funcions injectives que no són exhaustives, convertint-les així en bijeccions. El procés és: sigui fX → Y una funció injectiva existirà sempre una funció f-1f(X) → X tal que f-1(f(x))=x per a tot element x de X.

Funcions invertibles per la dreta[modifica | modifica el codi]

Cada funció amb inversa per la dreta és una funció exhaustiva. El recíproc és equivalent a l'axioma d'elecció. És a dir, acceptant l'elecció, una funció fX → Y és exhaustiva si i només si hi ha una funció gY → X tal que, per cada y \in Y

f(g(y)) = y \, (g pot ser desfeta per f)

És a dir, una funció g tal que fg és igual a la funció identitat de Y (d'acord amb la definició de funció inversa).

Fixeu-vos que pot ser que g no sigui una inversa completa de f perquè la composició en l'altre ordre, gf, pot no ser la identitat de X. En altres paraules, f pot desfer o "revertir" g, però no necessàriament pot ser revertida per aquesta. Les funcions exhaustives no sempre són invertibles (bijectives).

Per exemple, a la il·lustració, hi ha alguna funció g tal que g(C) = 4. També hi ha alguna funció f tal que f(4) = C. No importa que g(C) també pugui ser igual a 3; només importa que f "reverteix" g.

Altres propietats[modifica | modifica el codi]

  • Si f i g són totes dues exhaustives, llavors fg és exhaustiva.
  • Si fg és exhaustiva, llavors f és exhaustiva (però g pot no ser-ho).
  • fX → Y és exhaustiva si i només si, donades dues funcions qualsevol g,h:Y → Z, sempre que gf = hf, llavors g = h. En altres paraules, Les funcions exhaustives són precisament els epimorfismes de la categoria Conjunt de conjunts.
  • Si fX → Y és exhaustiva i B és un subconjunt de Y, llavors f(f −1(B)) = B. És a dir, B pot ser recuperat a partir de la seva antiimatge f −1(B).
  • Per a qualsevol funció hX → Z hi ha una funció exhaustiva f:X → Y i una funció injectiva g:Y → Z tals que h = gf. Per veure-ho, es defineix Y els conjunts h −1(z) on z és de Z. Aquests conjunts són disjunts i parteixen X. Per tant f porta cada x cap a l'element de Y que el conté, i g porta cada element de Y cap al punt de Z al qual h envia els seus punts. Per tant f és exhaustiva donat que és una projecció, i g és injectiva per definició.
  • A base de col·lapsar tots els arguments que donen la mateixa imatge, tota funció exhaustiva indueix una bijecció definida sobre el quocient del seu domini. De forma més precisa, cada funció exhaustiva f : AB pot ser descomposta en la composició d'una projecció amb una bijecció tal com segueix. Sia A/~ les classes de equivalència de A baix la següent relació d'equivalència: x ~ y si i només si f(x) = f(y). De forma equivalent, A/~ és el conjunt de totes les antiimatges a través de f. Sia P(~) : AA/~ l'aplicació projecció la qual envia cada x de A a la seva classe d'equivalència [x]~, i sia fP : A/~ → B la funció donada per fP([x]~) = f(x). Llavors f = fPP(~).
  • Si fX → Y és una funció exhaustiva, llavors X té com a mínim tants elements com Y, en el sentit del nombre cardinal.
  • Si tots dos X i Y són finits amb el mateix nombre d'elements, llavors f : X → Y és exhaustiva si i només si f és injectiva.


Vegeu també[modifica | modifica el codi]