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

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

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

Media som används på denna webbplats

Icke-injektiv-surjektiv.svg
Författare/Upphovsman: Svjo, Licens: CC BY-SA 3.0
Icke-injektiv-surjektiv avbildning
Injektiv-icke-surjektiv.svg
Författare/Upphovsman: Svjo, Licens: CC BY-SA 3.0
Injektiv-icke-surjektiv avbildning
Injektiv-surjektiv-funk.svg
Författare/Upphovsman: Svjo, Licens: CC BY-SA 3.0
Injektiv-surjektiv-funk avbildning