Öppna huvudmenyn
En surjektiv funktion, som inte är injektiv
En funktion som inte är surjektiv, men injektiv

En surjektiv funktion, eller en surjektion, är en funktion f från mängden X 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.

Innehåll

Surjektioner mellan två mängderRedigera

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.

ExempelRedigera

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

 .

BevisRedigera

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 ävenRedigera

KällorRedigera

  • 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

NoterRedigera

  1. ^ Karl-Johan Bäckström, Diskret matematik, Studentlitteratur, Lund 1986.
  Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.