Surjektive Funktion - Surjective function

In der Mathematik ist eine surjektive Funktion (auch als Surjektion oder On-Funktion bekannt ) eine Funktion $f$ , die jedem Element $y$ ein Element $x$ $zuordnet$ ; Das heißt, für jeden $y$ , gibt es eine $x$ derart , dass $f (x) = y$ . Mit anderen Worten, jedes Element der Codomain der Funktion ist das Abbild von mindestens einem Element ihrer Domain . Es ist nicht erforderlich , dass $x$ sein einzigartig ; die Funktion $f$ kann ein oder mehrere Elemente von $X$ auf dasselbe Element von $Y$ abbilden.

Eine nicht-injektive surjektive Funktion (Surjektion, keine Bijektion)
Eine injektive surjektive Funktion (Bijektion)
Eine injektive nicht-surjektive Funktion (Injektion, keine Bijektion)
Eine nicht-injektive nicht-surjektive Funktion (auch keine Bijektion)

Der Begriff surjektiv und die damit verbundenen Begriffe injektiv und bijektiv wurden von eingeführt Nicolas Bourbaki , eine Gruppe von hauptsächlich Französisch der 20. Jahrhundert Mathematiker , die unter diesem Pseudonym, eine Reihe von Büchern schrieben eine Ausstellung moderner fortgeschrittener Mathematik präsentiert, beginnend im Jahr 1935. Das Französisch Wort sur bedeutet über oder über , und bezieht sich auf die Tatsache, dass das Bild des Bereichs einer surjektiven Funktion den Cobereich der Funktion vollständig bedeckt.

Jede Funktion induziert eine Surjektion durch Einschränkung seiner codomain auf das Bild von seiner Domäne. Jede surjektive Funktion hat eine Rechtsinverse und jede Funktion mit einer Rechtsinversen ist notwendigerweise eine Surjektion. Die Zusammensetzung surjektiver Funktionen ist immer surjektiv. Jede Funktion kann in eine Surjektion und eine Injektion zerlegt werden.

Definition

Eine surjektive Funktion ist eine Funktion, deren Bild gleich ihrem Kobereich ist . Äquivalent ist eine Funktion mit Domäne und Kodomäne surjektiv, wenn für jedes in mindestens ein in mit existiert . Surjektionen werden manchmal durch einen zweiköpfigen Pfeil nach rechts (bezeichnet U + 21A0 ↠ nach rechts Doppelköpfig ARROW ), wie in . $f$ $X$ $Y$ $y$ $Y$ $x$ $X$ $f(x)=y$ $f\colon X\twoheadrightarrow Y$

Symbolisch,

Wenn , dann heißt surjektiv, wenn

f\colon X\rightarrow Y

f

\forall y\in Y,\,\exists x\in X,\;\;f(x)=y

.

Beispiele

Eine nicht-surjektive Funktion von der Domäne X zur Kodomäne Y . Das kleinere gelbe Oval innerhalb von Y ist das Bild (auch Range genannt ) von f . Diese Funktion ist nicht surjektiv, da das Bild nicht die gesamte Co-Domäne ausfüllt. Mit anderen Worten, Y wird in einem zweistufigen Prozess gefärbt: Zuerst wird für jedes x in X der Punkt f ( x ) gelb gefärbt; Zweitens sind alle übrigen Punkte in Y , die nicht gelb sind, blau gefärbt. Die Funktion f wäre nur surjektiv, wenn es keine blauen Punkte gäbe.

Für jede Menge X ist die Identitätsfunktion id _X auf X surjektiv.
Die Funktion $f : Z \to {0, 1}$ definiert durch f ( n ) = n mod 2 ( dh gerade ganze Zahlen werden auf 0 abgebildet und ungerade ganze Zahlen auf 1) ist surjektiv.
Die Funktion $f : R \to R$ , definiert durch f ( x ) = 2 x + 1 surjektiv (und sogar bijektive ), da für jede reelle Zahl y , wir haben x , so dass f ( x ) = y : Eine solche geeignete x ist ( y − 1)/2.
Die durch f ( x ) = x ³ − 3 x definierte Funktion $f : R \to R$ ist surjektiv, denn das Urbild jeder reellen Zahl y ist die Lösungsmenge der kubischen Polynomgleichung x ³ − 3 x − y = 0 , und jedes kubische Polynom mit reellen Koeffizienten hat mindestens eine reelle Wurzel. Diese Funktion ist jedoch nicht injektiv (und damit nicht bijektiv ), da beispielsweise das Urbild von y = 2 { x = −1, x = 2} ist. (Tatsächlich hat das Urbild dieser Funktion für jedes y , −2 ≤ y ≤ 2 mehr als ein Element.)
Die Funktion $g : R \to R$ , definiert durch g ( x ) = x ² ist nicht surjektiv, da es keine reelle Zahl x derart , dass x ² = -1 . Die durch $g$ $($ $x$ $) =$ $x$ $2$ (mit eingeschränktem $Kobereich)$ definierte Funktion $g : R \to R \geq0$ ist jedoch surjektiv, da es für jedes y im nichtnegativen reellen Kobereich Y mindestens ein x im reellen Bereich gibt X , derart , daß x ² = y .
Die natürliche Logarithmus - Funktion $ln: (0, + \infty) \to R$ ist eine surjektiv und sogar bijektive (Abbildung aus dem Satz von positiven reellen Zahlen in die Menge der reellen Zahlen). Ihre Umkehrung, die Exponentialfunktion , ist , wenn sie mit der Menge der reellen Zahlen als Bereich definiert ist, nicht surjektiv (da ihr Bereich die Menge der positiven reellen Zahlen ist).
Die Matrixexponentialfunktion ist nicht surjektiv, wenn sie als Abbildung aus dem Raum aller n × n Matrizen auf sich selbst betrachtet wird. Sie wird jedoch üblicherweise als Abbildung aus dem Raum aller n × n Matrizen auf die allgemeine lineare Gruppe vom Grad n (d. h. die Gruppe aller n × n invertierbaren Matrizen ) definiert. Nach dieser Definition ist die Matrixexponentialfunktion für komplexe Matrizen surjektiv, für reelle Matrizen jedoch immer noch nicht surjektiv.
Die Projektion von einem kartesischen Produkt $A \times B$ auf einen seiner Faktoren ist surjektiv, es sei denn, der andere Faktor ist leer.
In einem 3D-Videospiel werden Vektoren mittels einer surjektiven Funktion auf einen 2D-Flachbildschirm projiziert.

Interpretation für surjektive Funktionen in der kartesischen Ebene, definiert durch die Abbildung f : X → Y , wobei y = f ( x ), X = Funktionsbereich, Y = Funktionsumfang. Jedes Element im Bereich wird von einem Element in der Domäne nach der Regel f abgebildet . Es kann eine Anzahl von Domänenelementen geben, die demselben Bereichselement zugeordnet sind. Das heißt, jedes y in Y wird von einem Element x in X abgebildet , mehr als ein x kann auf dasselbe y abgebildet werden . Links: Es wird nur eine Domäne gezeigt, die f surjektiv macht . Rechts: Zwei mögliche Domänen X ₁ und X ₂ sind dargestellt.

Nicht-surjektive Funktionen in der kartesischen Ebene. Obwohl einige Teile der Funktion surjektiv sind, wobei Elemente y in Y einen Wert x in X haben, so dass y = f ( x ), sind es einige Teile nicht. Links: Es gibt y ₀ in Y , aber es gibt kein x ₀ in X, so dass y ₀ = f ( x ₀ ). Rechts: Es gibt y ₁ , y ₂ und y ₃ in Y , aber es gibt keine x ₁ , x ₂ und x ₃ in X so dass y ₁ = f ( x ₁ ), y ₂ = f ( x ₂ ), und y ₃ = f ( x ₃ ).

Eigenschaften

Eine Funktion ist genau dann bijektiv, wenn sie sowohl surjektiv als auch injektiv ist .

Wenn (wie es oft geschieht) eine Funktion mit ihrem Graphen identifiziert wird , dann ist die Surjektivität keine Eigenschaft der Funktion selbst, sondern eine Eigenschaft der Abbildung . Dies ist die Funktion zusammen mit ihrer Codomäne. Im Gegensatz zur Injektivität lässt sich die Surjektivität nicht allein aus dem Graphen der Funktion ablesen.

Surjektionen als rechtsumkehrbare Funktionen

Die Funktion g : Y → X heißt eine Rechtsinverse der Funktion f : X → Y, wenn f ( g ( y )) = y für jedes y in Y ( g kann durch f rückgängig gemacht werden ). Mit anderen Worten, g ist eine rechte Inverse von f, wenn die Zusammensetzung f o g von g und f in dieser Reihenfolge die Identitätsfunktion auf dem Gebiet Y von g ist . Die Funktion g muss keine vollständige Umkehrung von f sein, da die Zusammensetzung in der anderen Ordnung, g o f , möglicherweise nicht die Identitätsfunktion auf dem Gebiet X von f ist . Mit anderen Worten, f kann g rückgängig machen oder " umkehren " , aber nicht notwendigerweise dadurch umgekehrt werden.

Jede Funktion mit einer Rechtsinversen ist notwendigerweise eine Surjektion. Der Satz, dass jede surjektive Funktion eine Rechtsinverse hat, ist äquivalent zum Auswahlaxiom .

Wenn f : X → Y surjektiv und B eine Teilmenge von Y ist , dann ist f ( f ⁻¹ ( B )) = B . Somit kann B aus seinem Urbild f ⁻¹ ( B ) wiederhergestellt werden .

Zum Beispiel in der ersten Abbildung oben, gibt es eine gewisse Funktion g , so dass g ( C ) = 4. Es gibt auch eine Funktion f , so daß f (4) = C . Es spielt keine Rolle, dass g ( C ) auch gleich 3 sein kann; es ist nur wichtig, dass f g "umkehrt" .

Surjektive Zusammensetzung: Die erste Funktion muss nicht surjektiv sein.
Eine weitere surjektive Funktion. (Dieser ist zufällig eine Bijektion )
Eine nicht- surjektive Funktion. (Dies ist zufällig eine Injektion )

Surjektionen als Epimorphismen

Eine Funktion f : X → Y ist genau dann surjektiv, wenn sie rechtsaufhebend ist : gegebene beliebige Funktionen g , h : Y → Z , immer wenn g o f = h o f , dann g = h . Diese Eigenschaft wird in Form von Funktionen und ihrer Zusammensetzung formuliert und kann auf den allgemeineren Begriff der Morphismen einer Kategorie und ihrer Zusammensetzung verallgemeinert werden . Rechts-auslöschende Morphismen werden Epimorphismen genannt . Insbesondere sind surjektive Funktionen genau die Epimorphismen in der Kategorie der Mengen . Die Vorsilbe epi leitet sich von der griechischen Präposition ἐπί ab und bedeutet über , über , auf .

Jeder Morphismus mit einer rechten Inversen ist ein Epimorphismus, aber die Umkehrung gilt im Allgemeinen nicht. Eine Rechtsinverse g eines Morphismus f heißt Abschnitt von f . Ein rechtsinverser Morphismus wird als gespaltener Epimorphismus bezeichnet .

Surjektionen als binäre Relationen

Jede Funktion mit Domäne X und Kodomäne Y kann als links-gesamte und rechts-eindeutige binäre Relation zwischen X und Y angesehen werden, indem sie mit ihrem Funktionsgraphen identifiziert wird . Eine surjektive Funktion mit Domäne X und Kodomäne Y ist dann eine binäre Relation zwischen X und Y , die rechts-eindeutig und sowohl links-total als auch rechts-total ist .

Kardinalität des Bereichs einer Surjektion

Die Kardinalität des Definitionsbereichs einer surjektiven Funktion ist größer oder gleich der Kardinalität ihres Kobereichs: Wenn f : X → Y eine surjektive Funktion ist, dann hat X im Sinne von Kardinalzahlen mindestens so viele Elemente wie Y . (Der Beweis Appelle an das Axiom der Wahl zeigen , dass eine Funktion g : Y → X erfüllt f ( g ( y )) = y für alle y in Y . Existiert g leicht injektiv, also die sein gesehen formale Definition von | Y | ≤ | X | ist erfüllt.)

Insbesondere dann , wenn beide X und Y ist finite mit der gleichen Anzahl von Elementen, dann f : X → Y surjektiv ist, wenn und nur wenn f ist injektiv .

Bei zwei Mengen X und Y wird die Notation X ≤ ^* Y verwendet, um zu sagen, dass entweder X leer ist oder dass es eine Surjektion von Y auf X gibt . Mit dem Auswahlaxiom kann man zeigen, dass X ≤ ^* Y und Y ≤ ^* X zusammen implizieren, dass | Y | = | X |, eine Variante des Schröder-Bernstein-Theorems .

Zusammensetzung und Zersetzung

Die Zusammensetzung surjektiver Funktionen ist immer surjektiv: Wenn f und g beide surjektiv sind und der Kobereich von g gleich dem Bereich von f ist , dann ist f o g surjektiv. Wenn umgekehrt f o g surjektiv, dann f surjektiv (aber g , die Funktion zuerst angewandt, muss nicht sein). Diese Eigenschaften verallgemeinern sich von Surjektionen in der Kategorie der Mengen zu beliebigen Epimorphismen in jeder Kategorie .

Jede Funktion kann in eine Surjektion und ein zerlegt werden Injektion : für jede Funktion h : X → Z gibt es eine Surjektion f : X → Y und eine Injektions g : Y → Z , so daß h = g o f . Um dies zu sehen, definieren Sie Y als die Menge der Urbilder h ⁻¹ ( z ) wobei z in h ( X ) ist . Diese Urbilder sind disjunkt und partitionieren X . Dann trägt f jedes x zu dem Element von Y, das es enthält, und g trägt jedes Element von Y zu dem Punkt in Z, an den h seine Punkte sendet. Dann ist f surjektiv, da es eine Projektionsabbildung ist, und g ist per Definition injektiv.

Induzierte Surjektion und induzierte Bijektion

Jede Funktion induziert eine Surjektion, indem sie ihre Codomäne auf ihren Bereich beschränkt. Jede surjektive Funktion induziert eine Bijektion, die auf einem Quotienten ihrer Domäne definiert ist, indem sie alle Argumente, die einem gegebenen festen Bild zugeordnet sind, zusammenbricht. Genauer gesagt kann jede Surjektion f : A → B wie folgt als Projektion gefolgt von einer Bijektion faktorisiert werden. Seien A /~ die Äquivalenzklassen von A unter der folgenden Äquivalenzrelation : x ~ y genau dann, wenn f ( x ) = f ( y ). Äquivalent ist A /~ die Menge aller Urbilder unter f . Sei P (~) : A → A /~ die Projektionsabbildung, die jedes x in A in seine Äquivalenzklasse [ x ] _~ schickt , und sei f _P : A /~ → B die wohldefinierte Funktion von f _P ([ x ] _~ ) = f ( x ). Dann ist f = f _P o P (~).

Siehe auch

Verweise

Weiterlesen

Bourbaki, N. (2004) [1968]. Theorie der Mengen . Elemente der Mathematik . 1 . Springer. doi : 10.1007/978-3-642-59309-3 . ISBN 978-3-540-22525-6. LCCN 2004110815 .

Languages

In other projects