Surjektiv funktion

Från Wikipedia
Hoppa till: navigering, sök
En surjektiv funktion, men som inte är injektiv
En funktion som är injektiv, men inte surjektiv

En surjektiv funktion, eller en surjektion, är en funktion f från mängden X mängden Y, det vill säga sådan att f:s definitionsmängd Df = X och f:s värdemängd Vf = Y. Varje funktion är en surjektion av Df på Vf.

Alternativ definition: Låt X och Y vara två mängder och f en funktion f: XY. Då sägs f 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 värde i en surjektiv funktions målmängd motsvaras av minst ett värde i dess definitionsmängd, det vill säga att funktionens värdemängd är lika med dess målmängd.

Surjektioner mellan två mängder[redigera | redigera wikitext]

Låt S beteckna mängden surjektioner från en n-mängd X till en k-mängd Y, då gäller

|S|=k! \cdot s(n, k)

där s(n, k) är ett stirlingtal av andra slaget.

Exempel[redigera | redigera wikitext]

Antalet surjektioner från \mathbb{N}_6 till \mathbb{N}_7 är

7! \cdot s(6, 7)=7! \cdot 0=0 \; .

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 \mathbb{N}_4 till \mathbb{N}_2 är

2! \cdot s(4, 2)=2 \cdot 7=14.

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
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.