Funció exhaustiva

Una funció exhaustiva.

Una altra 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'una altra manera, una funció f: X → 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

• Per a qualsevol conjunt X, la funció identitat id_X 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

En general, sigui f: X → 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 f: X → Y una funció injectiva existirà sempre una funció f^-1: f(X) → X tal que f^-1(f(x))=x per a tot element x de X.

Funcions invertibles per la dreta

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ó f: X → Y és exhaustiva si i només si hi ha una funció g: Y → 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 f∘g é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, g∘f, 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

• Si f i g són totes dues exhaustives, llavors f∘g és exhaustiva.
• Si f∘g és exhaustiva, llavors f és exhaustiva (però g pot no ser-ho).
• f: X → Y és exhaustiva si i només si, donades dues funcions qualsevol g,h:Y → Z, sempre que g∘f = h∘f, llavors g = h. En altres paraules, Les funcions exhaustives són precisament els epimorfismes de la categoria Conjunt de conjunts.
• Si f: X → Y és exhaustiva i B és un subconjunt de Y, llavors f(f ⁻¹(B)) = B. És a dir, B pot ser recuperat a partir de la seva antiimatge f ⁻¹(B).
• Per a qualsevol funció h: X → Z hi ha una funció exhaustiva f:X → Y i una funció injectiva g:Y → Z tals que h = g∘f. Per a veure-ho, es defineix Y els conjunts h ⁻¹(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. En conseqüència, f és exhaustiva donat que és una projecció, i g és injectiva per definició.
• Col·lapsant 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 : A → B pot ser descomposta en la composició d'una projecció amb una bijecció tal com segueix. Sia A/~ les classes d'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(~) : A → A/~ l'aplicació projecció la qual envia cada x de A a la seva classe d'equivalència [x]_~, i sia f_P : A/~ → B la funció donada per f_P([x]_~) = f(x). Llavors f = f_P ∘ P(~).
• Si f: X → 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é

• Espai revestiment
• Funció bijectiva
• Funció injectiva