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.^[1]

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 ${\displaystyle S}$ beteckna mängden surjektioner från en n-mängd X till en k-mängd Y, då gäller

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

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

Exempel

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

${\displaystyle 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 ${\displaystyle \mathbb {N} _{4}}$ till ${\displaystyle \mathbb {N} _{2}}$ är

${\displaystyle 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

Noter

1. Karl-Johan Bäckström, Diskret matematik, Studentlitteratur, Lund 1986.

Externa länkar

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