Surjektiv funktion

En surjektiv funktion, som inte är injektiv

En surjektiv och injektiv funktion

En funktion som inte är surjektiv, men injektiv

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]

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