Surjektiv funktion
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/8/81/Icke-injektiv-surjektiv.svg/150px-Icke-injektiv-surjektiv.svg.png)
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Injektiv-surjektiv-funk.svg/150px-Injektiv-surjektiv-funk.svg.png)
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/5/5a/Injektiv-icke-surjektiv.svg/150px-Injektiv-icke-surjektiv.svg.png)
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 Vf = Y. För varje funktion f finns en surjektiv funktion med samma funktionsgraf, som går från definitionsmängden Df på värdemängden Vf.[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
[redigera | redigera wikitext]Låt beteckna mängden surjektioner från en n-mängd X till en k-mängd Y, då gäller
där s(n, k) är ett stirlingtal av andra slaget.
Exempel
[redigera | redigera wikitext]Antalet surjektioner från till är
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 till är
- .
Bevis
[redigera | redigera wikitext]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
[redigera | redigera wikitext]Källor
[redigera | redigera wikitext]- 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
[redigera | redigera wikitext]- ^ Karl-Johan Bäckström, Diskret matematik, Studentlitteratur, Lund 1986.
Externa länkar
[redigera | redigera wikitext]Wikimedia Commons har media som rör Surjektiv funktion.