mini|upright=0.6|En surjektiv funktion, som inte är injektiv mini|upright=0.6|En surjektiv och injektiv funktion mini|upright=0.6|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 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.Karl-Johan Bäckström, Diskret matematik, Studentlitteratur, Lund 1986.
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 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 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 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
Externa länkar
Kategori:Matematisk terminologi