Surjektiv funktion

Från Wikipedia
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 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: XY. 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]

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

Externa länkar[redigera | redigera wikitext]