Bijektion

In der Mathematik , eine Bijektion ist die Anwendung bijektiv . Eine Anwendung ist bijektiv, wenn jedes Element ihres Ankunftssatzes einen und nur einen Vorgänger hat , d. H. Ein Bild von genau einem Element (seiner Definitionsdomäne ) ist, oder wenn es injektiv und surjektiv ist . Bijektionen werden manchmal auch als Eins-zu-Eins-Übereinstimmungen bezeichnet .

Das kann man in dieser Definition bemerkt, eine erlegt keine Bedingung für die Elemente des Ausgangssatzes , andere als die , die eine Anwendung definiert: Jedes Element hat ein Bild und nur einer.

Wenn es eine Bijektion f von einer Menge E in eine Menge F gibt, dann existiert eine von F nach E : die reziproke Bijektion von f , die jedem Element von F seinen Vorgänger durch f zuordnet . Wir können dann sagen, dass diese Mengen bijektiv oder äquipotent sind .

Cantor hat zunächst gezeigt, dass bei einer Injektion von E nach F und einer Injektion von F nach E (nicht unbedingt surjektiv) E und F äquipotent sind (dies ist der Cantor-Bernstein-Satz ).

Wenn zwei endliche Mengen äquipotent sind, haben sie die gleiche Anzahl von Elementen. Die Erweiterung dieser Äquivalenz auf unendliche Mengen führte zum Konzept des Kardinals einer Menge und unterschied verschiedene Größen von unendlichen Mengen, die Klassenäquipotenz sind. So können wir zum Beispiel zeigen, dass die Menge der natürlichen Zahlen dieselbe Größe hat wie die Menge der rationalen Zahlen , aber eine Größe, die streng kleiner ist als die Menge der reellen Zahlen . Tatsächlich von in , gibt es Injektionen aber keine overjection. $\ mathbb {N}$ $\ mathbb {R}$

Formale Definitionen

Funktionsdefinition

Eine Karte ist bijektiv, wenn jedes Element des Ankunftssatzes genau einen Vorgänger (in ) von hat , der formal geschrieben ist: $f: E \ bis F.$ $F.$ $E.$ $f$

{\ displaystyle \ forall y \ in F, \ \ existiert! \ x \ in E, \ quad f (x) = y}

oder, was äquivalent ist, wenn es eine Anwendung ist , die zusammengesetzt auf der linken oder auf der rechten Seite durch , die gibt Anwendungsidentität : ${\ displaystyle g: F \ bis E}$ $f$

{\ displaystyle g \ circ f = \ operatorname {id} _ {E}}

und ,

{\ displaystyle f \ circ g = \ operatorname {id} _ {F}}

das heißt:

{\ displaystyle \ forall x \ in E, \ \ forall y \ in F, \ quad f (x) = y \ Longleftrightarrow g (y) = x}

Eine solche Anwendung wird dann eindeutig bestimmt durch . Wir nennen es die wechselseitige Bijektion von und schreiben es auf . Es ist auch eine Bijektion, und ihre Umkehrung ist . $G$ $f$ $f$ $f ^ {- 1}$ $f$

Relationale Definition

Eine Bijektion der in ein binäres Verhältnis von in dem eine Anwendung und deren wechselseitige Beziehung ist auch eine Anwendung. Im Detail müssen die folgenden vier Eigenschaften haben: $E.$ $F.$ $R.$ $E.$ $F.$ $R ^ {- 1}$ $R.$

Funktionalität : Jedes Element von hat höchstens ein Bild pro , d.h. $E.$ $R.$

{\ displaystyle \ forall x \ in E, \ \ forall y, y '\ in F, \ quad [(xRy {\ text {und}} xRy') \ Rightarrow y = y ']}

;;

Anwendbarkeit : Jedes Element von hat mindestens ein Bild von , das heißt $E.$ $R.$

{\ displaystyle \ forall x \ in E, \ \ existiert y \ in F, \ quad xRy}

;;

Injektivität : Jedes Element von hat höchstens eine Vorgeschichte von , das heißt $F.$ $R.$

{\ displaystyle \ forall x, x '\ in E, \ \ forall y \ in F, \ quad [(xRy {\ text {und}} x'Ry) \ Rightarrow x = x']}

Surjektivität : Jedes Element von hat mindestens einen Vorgänger von , das heißt $F.$ $R.$

{\ displaystyle \ forall y \ in F, \ \ existiert x \ in E, \ quad xRy}

Die Injektivität von entspricht der Funktionalität von und die Surjektivität von entspricht der Anwendbarkeit von . $R.$ $R ^ {- 1}$ $R.$ $R ^ {- 1}$

Es ist üblich, eine funktionale binäre Beziehung durch eine Funktion durch Posieren darzustellen $R.$ $f$

{\ displaystyle \ forall x \ in E, \ \ forall y \ in F, \ quad f (x) = y \ Longleftrightarrow xRy}

Wenn wir angeben, dass es sich um eine Anwendung handelt , gehen wir davon aus, dass diese funktional und anwendbar ist (siehe Anwendung_ (Mathematik) #Funktion_und_Anwendung für die Unterschiede zwischen Anwendung und Funktion , die je nach Autor variieren können). $f$ $R.$

Die Symmetrie zwischen Funktionalität und Injektivität einerseits und zwischen Anwendbarkeit und Surjektivität andererseits ergibt, dass wenn es sich um eine bijektive Beziehung handelt, dies auch der Fall ist. $R.$ $R ^ {- 1}$

Konkretes Beispiel

Nehmen wir den Fall eines Ferienortes, in dem eine Gruppe von Touristen in einem Hotel untergebracht werden soll. Jede Art der Verteilung dieser Touristen in den Zimmern des Hotels kann durch Anwenden des Satzes X der Touristen auf den Satz Y der Räume dargestellt werden (jeder Tourist ist einem Raum zugeordnet).

Der Hotelier möchte , dass die Anwendung surjektiv ist, dh dass jedes Zimmer belegt ist . Dies ist nur möglich, wenn mindestens so viele Touristen wie Zimmer vorhanden sind.
Touristen möchten , dass die Anwendung injektiv ist, dh jeder von ihnen hat ein individuelles Zimmer . Dies ist nur möglich, wenn die Anzahl der Touristen die Anzahl der Zimmer nicht überschreitet.
Diese Wünsche sind unvereinbar, wenn sich die Anzahl der Touristen von der Anzahl der Zimmer unterscheidet. Andernfalls ist es möglich, die Touristen so zu verteilen, dass nur einer pro Raum vorhanden ist und alle Räume belegt sind. Wir werden dann sagen, dass die Anwendung sowohl injektiv als auch surjektiv ist. es ist bijektiv .

Beispiele und Gegenbeispiele

Die durch $f$ $($ $x$ $) = 2$ $x$ $+ 1$ definierte affine Funktion ist bijektiv, da für jedes reelle $y$ genau eine reelle Lösung der Gleichung $y$ $= 2$ $x$ $+ 1$ von unbekanntem $x existiert$ , nämlich: $x$ $= ($ $y$ $- 1 ) / 2$ . $f: \ mathbb {R} \ bis \ mathbb {R}$
Die durch $g$ $($ $x$ $) =$ $x$ $2$ definierte Quadratfunktion ist aus zwei Gründen nicht bijektiv. Das erste ist, dass wir (zum Beispiel) $g$ $(1) = 1 =$ $g$ $(-1)$ haben und daher $g$ nicht injektiv ist; Das zweite ist, dass es (zum Beispiel) kein reales $x gibt,$ so dass $x$ $2$ $= -1 ist$ , und daher ist $g auch$ nicht surjektiv. Jede dieser Beobachtungen reicht aus, um festzustellen, dass $g$ nicht bijektiv ist. Andererseits ist die Anwendung eins zu eins . Die Erklärung ist, dass es für jedes positive reelle $y$ genau eine positive reelle Lösung für die Gleichung $y = x$ $2 gibt$ , nämlich $x$ $=$ $\sqrt$ $y$ . Die Quadratwurzelfunktion ist daher die reziproke Bijektion der Quadratfunktion auf diesen Mengen. ${\ displaystyle g: \ mathbb {R} \ to \ mathbb {R}}$
${\ displaystyle \ mathbb {R} _ {+} \ to \ mathbb {R} _ {+}, \, x \ mapsto x ^ {2}}$
Ebenso ist die Sinusfunktion , die als Anwendung von in angesehen wird , weder injektiv noch surjektiv und daher nicht bijektiv; R.{\ displaystyle \ mathbb {R}} $\ mathbb {R}$ R.{\ displaystyle \ mathbb {R}} $\ mathbb {R}$
- seine Einschränkung ist surjektiv, aber nicht injektiv (zum Beispiel und hat das gleiche Bild), daher nicht bijektiv; ${\ displaystyle \ sin: \ mathbb {R} \ bis [-1,1]}$ ${\ displaystyle 0}$ $\ pi$
- seine Einschränkung ist injektiv, aber nicht surjektiv (zum Beispiel ist das Bild ohne Wert), daher nicht bijektiv; ${\ displaystyle \ sin: [- {\ pi / 2}, {\ pi / 2}] \ to \ mathbb {R}}$ $2$
- seine Restriktionsbeschränkung ist bijektiv (wie auch eine Unendlichkeit anderer seiner Restriktionsbeschränkungen); ${\ displaystyle \ sin: [- {\ pi / 2}, {\ pi / 2}] \ bis [-1,1]}$
- seine inverse Bijektion ist dann $arcsin$ : ; ${\ displaystyle [-1,1] \ to [- {\ pi / 2}, {\ pi / 2}]}$
- Die Sinus-Sinus-Funktion, die dieselben Werte annimmt, aber als Anwendung von in angesehen wird , ist injektiv, aber nicht surjektiv (z. B. ist sie nicht das Bild eines Wertes) und daher nicht bijektiv. $[-1.1]$ $\ mathbb {R}$ $\ pi$
Die durch definierte Sigmoidfunktion ist bijektiv und wird in der Informatik häufig verwendet, insbesondere in neuronalen Netzen . ${\ displaystyle f: \ mathbb {R} \ to] 0.1 [}$ $f (x) = \ frac {1} {1 + e ^ {- x}}$

Eigenschaften

Bijektionen sind Isomorphismen in der Kategorie der Mengen .
Lass und . f::E.→F.{\ displaystyle f: E \ bis F} $f: E \ bis F.$ h::F.→G{\ displaystyle h: F \ bis G} ${\ displaystyle h: F \ bis G}$
- Wenn und bijektiv sind, dann ist bijektiv und . $f$ $h$ ${\ displaystyle h \ circ f}$ ${\ displaystyle (h \ circ f) ^ {- 1} = f ^ {- 1} \ circ h ^ {- 1}}$
- Wenn es bijektiv ist, ist es injektiv und surjektiv. ${\ displaystyle h \ circ f}$ $f$ $h$
Für jede Menge E werden Bijektionen von E auf sich selbst Permutationen von E genannt . Sie bilden mit der Operation ∘ der Zusammensetzung der Karten eine Gruppe , die als symmetrische Gruppe von E bezeichnet und mit S ( E ) oder bezeichnet wird . ${\ displaystyle {\ mathfrak {S}} (E)}$
Die Anzahl der Bijektionen zwischen zwei endlichen Mengen mit derselben Kardinalität n ist n ! .
Eine Karte von ℝ nach ℝ ist genau dann bijektiv, wenn ihr Graph eine horizontale Linie an genau einem Punkt schneidet.
Damit eine Anwendung einer endlichen Menge an sich bijektiv ist, reicht es aus, wenn sie injektiv oder surjektiv ist (dann ist es beides). Es kann als Anwendung des Schubladenprinzips angesehen werden . NB: Es kann eine Bijektion zwischen zwei unendlichen Mengen geben, von denen eine streng in der anderen enthalten ist. Es gibt viele Beispiele dafür im zählbaren Fall .

Anmerkungen und Referenzen

In N. Bourbaki , Elemente der Mathematik : Mengenlehre [ Detail der Ausgaben ](Ausgabe 1970 oder 2006 ), c. II, § 3, n o 7, nach def. 10, p. II. 17 lesen wir: „Anstatt zu sagen , dass f injektiv ist, wir sagen auch , dass f ist eine Eins-zu-eins . […] Wenn f [Abbildung von A nach B ] eins zu eins ist, sagen wir auch, dass f A und B in eine Eins-zu-Eins-Entsprechung bringt . " Aber in den" Spezifikationsergebnissen "am Ende des gleichen Bandes, p. ER9, "Eins-zu-Eins" wird nur im zweiten Sinne verwendet.

In Verbindung stehender Artikel

Satz der Bijektion