Surjektiv funktion

En surjektiv funktion, eller en surjektion, är en funktion f från mängden X på mängden Y, det vill säga en funktion f från X till Y, sådan att dess värdemängd V_f = Y. För varje funktion f finns en surjektiv funktion med samma funktionsgraf, som går från definitionsmängden D_f på värdemängden V_f.

En surjektiv funktion, som inte är injektiv

En surjektiv och injektiv funktion

En funktion som inte är surjektiv, men injektiv

Definitionen kan även formuleras så: Låt X och Y vara två mängder och f en funktion f: X→Y. f sägs då vara surjektiv, eller en surjektion, om det för varje y i Y finns ett x i X sådant att f(x) = y. Detta innebär således att varje element i en surjektiv funktions målmängd är ett funktionsvärde.

Surjektioner mellan två mängder

Låt $S$ beteckna mängden surjektioner från en n-mängd X till en k-mängd Y, då gäller

$|S|=k!\cdot s(n,k)$

där s(n, k) är ett stirlingtal av andra slaget.

Exempel

Antalet surjektioner från $\mathbb {N} _{6}$ till $\mathbb {N} _{7}$ är

$7!\cdot s(6,7)=7!\cdot 0=0\;.$

s(6, 7)=0 eftersom en mängd av 6 element inte kan delas upp i 7 icke-tomma delmängder. Vidare finns inga surjektioner f: X→Y så att |X|<|Y| när mängderna är ändliga.

Antalet surjektioner från $\mathbb {N} _{4}$ till $\mathbb {N} _{2}$ är

$2!\cdot s(4,2)=2\cdot 7=14$.

Bevis

Varje surjektion f: X→Y medför en partition av X i k delar. Om vi har en partition i k delar finns det k! surjektioner som åstadkommer partitionen. Eftersom de k delmängderna kan bli tilldelade till de k elementen i Y på vilket bijektivt sätt som helst blir antalet surjektioner k!*s(n, k).

Se även

• Bijektiv
• Injektiv

Källor

• R. Creighton Buck, Advanced Calculus, McGraw-Hill Book Company, New York 1956.
• C. Hyltén-Cavallius och Sandgren, Matematisk Analys, Håkan Ohlssons Boktryckeri, Lund 1958.
• Norman L. Biggs, Discrete Mathematics, Oxford University Press, USA 2009

Externa länkar

• Wikimedia Commons har media som rör Surjektiv funktion.
  Bilder & media