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 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. 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 : 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