Wie oft darf ein Objekt in einer Menge vorkommen?

In diesem ersten Abschnitt befassen wir uns mit der Sprache der Mathematik. Die nat�rlichen Sprachen wie deutsch, englisch, etc. mangelt es leider an der n�tigen Pr�zision, insbesonders dann, wenn es darum geht unendliche Objekte und Prozesse zu beschreiben. Um die dadurch entstehenden Vieldeutigkeiten zu vermeiden wurde von Georg Cantor die Mengenlehre entwickelt.

1.1 Definition.
Unter einer Menge verstehen wir wie Cantor eine Zusammenfassung wohlunterschiedener Objekte unserer Anschauung oder unseres Denkens zu einem neuen Ganzen. Es mu� dabei im Prinzip feststellbar sein, ob ein gegebenes Objekt zur Menge geh�rt oder nicht. Jene Objekte die zur Menge geh�ren hei�en Elemente der Menge. Wenneine Menge undein Objekt ist, dann schreiben wirfallsein Element der Mengeist undandernfalls. Dies folgt der allgemeinen Methode in der Mathematik die Negation einer Beziehung zweier Objekte durch Durchstreichen des Relationssymbols zu bezeichnen, alsobedeutet es ist nicht, sowiebedeutetist ungleich (nicht gleich)undbedeutet, da�nicht kleiner alsist.

Wir haben zwei M�glichkeiten Mengenzu beschreiben:

• Aufz�hlend: Durch Angabe einer Listealler Elemente der Menge. Man schreibt dann. Das Symbol `' bedeutet `definitionsgem�� ist die linke Seite gleich der rechten' oder kurz `ist definitionsgem�� gleich'. Alsoist definitionsgem�� gleich der Menge bestehend aus den Elementen,, ...,. Man schreibt auch k�rzer ``'' anstelle von ``,,...,''. Wir wollen dabei auch denn Fall zulassen, da� gewisse dergleich sind. Ist z.B.so ist. Dies hat den Nachteil, da� wir nicht sofort erkennen, wieviel Elemente die Mengehat (h�chstens jedenfallsviele), aber den ungemeinen Vorteil, da� wir die Menge hinschreiben k�nnen ohne die genauen Werte von,, ...,bestimmen zu m�ssen: Z.B.
  
  Dies wird bisweilen auch bei unendlichen Mengen verwendet. Z.B.. Hierbei gibt es aber nat�rlich viele v�llig verschiedene Interpretationen wie die weiteren Elemente dieser Menge nun wirklich aussehen:
  • ist die Menge der positiven ganzen Zahlen.
  • ist die Menge der Primzahlen, d.h. nur jener ganzen Zahlen, die keine anderen Teiler als 1 und sich selbst besitzen. Ein etwas l�ngerer Abschnitt w�re somit.
  • besteht aus den Gliedern der Fibonacci-Folge, d.h. jedes Element ist die Summe seiner beiden unmittelbaren Vorg�nger. Ein etwas l�ngerer Abschnitt w�re somit.
• Beschreibend: Durch Angabe einer Eigenschaft, welche die Elemente der Menge charakterisiert. Man schreibt dannund liest dies alsist per Definition die Menge alle (Objekte)welche die Eigenschaftbesitzen. Also z.B.ist positive ganze Zahloderist Primzahl. Nat�rlich darf man an Stelle vonauch jeden anderen Buchstaben verwenden.

Insbesonders nennt man die Mengedie kein einziges Element hat die leere Menge. Beschreibend kann man sie auch durch Angabe einer Eigenschaft die f�r keinerf�llt ist, wie z.B.angeben, d.h..

Ein analoger Ausdruck, n�mlichf�hrt allerdings auf einen fatalen Widerspruch, denn die Untersuchung der Frage ``Istein Element von sich selbst oder nicht?'' kann nur eine der beiden Antworten:oderhaben. Im ersten Fall mu� alsodie definierende Eigenschaft vonbesitzen, alsoerf�llen im Widerspruch zur Annahme. Im anderen Fall darfdie definierende Eigenschaft vonnicht besitzen, es darf also nichtgelten, und (wegen dem Satz vom ausgeschlossenen Dritten) mu�gelten, ebenfalls ein Widerspruch zur Annahme.

Auswege aus dem Widerspruch, den die Russel'sche Mengeliefert, wurden viele ersonnen. Grundidee dabei ist nicht alle Konstruktionen von Mengen zuzulassen.

Die erste recht technische und heute �berholte Methode wurde von Russel und Whitehead in der Principia Mathematica pr�sentiert und bestand darin Buchzuf�hren wie tief verschachtelt die Mengenklammern einer Menge sind und jeweils nur solche eine Elemente einer Menge von Tiefezuzulassen, die selbst Tiefehaben. Dies ist aber sehr umst�ndlich, und wollen wir ``Buchhaltern'' �berlassen.

Zermelo, Fraenkel und Skolem sind ihrerseits so vorgegangen, da� nur mehr ganz bestimmte Konstruktionen, die wir in der Folge alle besprechen werden (wie z.B. Potenzmenge, Vereinigung, Durschnitt, etc.), verwendet werden d�rfen um aus gegebenen Mengen neue zu definieren.

Eleganter ist der Zugang von G�del, Bernays und Neumann, die in der Beschreibunghat die Eigenschaft wieder alle Eigenschaftenzulassen, aber die so erhaltenen Objektenun Klassen oder Unmengen nennen, und nur deren Elemente als Mengen bezeichnen. Ein Menge in ihren Sinn ist also eine Klasse, die in mindestens einer Klasse als Element enthalten ist.

Morse, Kelley und Tarski haben dies noch insofern modifiziert, da� die Einschr�nkung, da� alle Variablen in den bei der Klassenbildung betrachteten Aussagen nur Mengen durchlaufen d�rfen, fallengelassen wurde. F�r genauere Details dazu sei auf eine Vorlesung �ber Mengenlehre oder entsprechende B�cher verwiesen.

Zwei Mengenundsind genau dann gleich, wenn sie genau die selben Elemente besitzen, d.h. jedes beliebige Objektgenau dann zugeh�rt, wenn es zugeh�rt. Um dies k�rzer symbolisieren zu k�nnen schreiben wir ``'' statt ``f�r alle''. Und wenn eine Aussagegenau dann wahr ist wenn es eine Aussageist, so schreiben wirund sagen daf�rist �quivalent zu. Wir k�nnen aus den Wahrheitswerten TRUE und FALSE der beiden Teilaussagenundjene der (logischen) �quivalenzbestimmen:

TRUETRUETRUEFALSEFALSETRUEFALSETRUEFALSETRUEFALSEFALSE

Wenn schlu�endlich ``:'' als ``(f�r die) gilt'' gelesen wird, dann sind zwei Mengenundgenau dann gleich (d.h.) wenn, also

Eine schw�chere M�glichkeit Mengen miteinander zu vergleichen ist folgende: Eine Mengehei�t Teilmenge einer Menge(und wir schreiben dann, oder sagen auchist Obermenge von), genau dann, wenn jedes Element vonauch Element vonist. Wenn eine Aussageeine Aussagezur Folge hat, so schreibt man f�r diesen Sachverhaltund sagt auchimpliziert. Es ist alsoselbst eine Aussage, die nur dann falsch sein kann, wenn zwarerf�llt ist, nicht aber. Die Wahrheitstafel f�r ``'' ist somit die folgende:

TRUETRUETRUEFALSEFALSETRUEFALSETRUETRUETRUEFALSEFALSE

Beachte, da�genau dann gilt, wenn sowohlals auch(auch alsgeschrieben) gilt, d.h. die beiden Aussagenundsich gegenseitig implizieren.

Wir k�nnen obige Definition nun kurz wie folgt schreiben:

Graphisch k�nnen wir das durch folgendes sogenanntes Venn-Diagramm veranschaulichen:

Beachte, da� analog zubei Zahlen f�r alle Mengendie Aussagegilt. Will man nur echte Teilmengenbetrachten, d.h. welcheerf�llen, so schreiben wir daf�r(und sagtist eine echte Teilmenge von), d.h.

F�r das Teilmengesein wird oft auch das Symbolanstelle vonverwendet, da diese Situation in der Mathematik viel �fter auftaucht als jene der echten Teilmenge (f�r die man dann allerdings soetwas schreckliches wieB oder

Offensichtlich istund. Diese Eigenschaft vonhei�t Antisymmetrie.

Weiters folgt ausunddie Aussage. Mann nennt diese Eigenschaft die Transitivit�t von.

Nat�rlich k�nnen Mengen selbst wieder Elemente einer Menge sein. Z.B. k�nnen wir die Mengealler Teilmengen einer Menge betrachten, also

Beachte, da� sehr deutlich zu unterscheiden ist zwischen,und. Wenn,,bezeichnet (Wer meint schon zu wissen, was die Zahlensind, der m�ge andere Symbole f�r die 3 eben definierten Mengen verwenden), so ist

• (Die leere Menge ist Teilmenge jeder Menge), aber nicht(denn) und auch nicht(denn die leere Menge hat kein einziges Elemente).
• , aber nicht(daaber nicht), und somit auch nicht.
• (denn das einzige Element 0 vonist auch Element der Menge) und somitaber auch.

1.2 Definition. Mengenoperationen.
Aus je zwei Mengenundk�nnen wir neue Mengen bilden:
Der Durchschnittvonundist die Menge aller Objekte die sowohl Elemente vonals auch vonsind. Salopp k�nnte man auch sagen: Der Durchschnitt besteht aus den Elementen die in beiden Mengen liegen. Dies k�nnte allerdings zu Verwechslung mit der weiter unten definierten Vereinigungsmenge f�hren, z.B. wenn wir die Menge aller Studentinnen, die in beide parallel-Klassen gehen, betrachten.

Wennundzwei Aussagen sind, dann bezeichnet man mit ``'' oderdie Aussage, da� beide Aussagen zutreffen. In vielen Computersprachen wird `&&' anstelle des auf der Tastatur nicht vorhandenenverwendet. Man lie�t dies als ``und''. Die Wahrheitstafel des (logischen) Undsist also folgende:

TRUETRUETRUEFALSEFALSEFALSEFALSETRUEFALSETRUEFALSEFALSE

Es ist also

Dies kan man durch ein Venn-Diagramm veranschaulichen:

Man sagt zwei Mengenundseien Element-fremd oder auch disjunkt, wenn, d.h. sie kein einziges gemeinsames Element besitzen.

Beachte, da�die gr��te gemeinsame Teilmenge vonundist, siehe auch (1.5).

Sei nuneine weitere gemeinsame Teilmenge vonund. Dann ist(alsodie gr��te gemeinsame Teilmenge), denn ausfolgtundalsound somit.     []

Es ist.

Die Vereinigungvonundist die Menge aller Objekte die Element mindestens einer der beiden Mengenbzw.sind. Wennundzwei Aussagen sind, dann bezeichnet man mitdie Aussage, da� zumindestens eine der beiden Aussagen zutrifft. In vielen Computersprachen wirdanstelle von. Man liest dies als ``oder'', mu� dabei aber beachten, da� dies ein nicht ausschlie�endes oder ist, also auch den Fall, da�undgelten, inkludiert. Interpretiere z.B. den Satz `Jack liebt Jill oder (Jack liebt) Jane''. D.h. die Wahrheitstafel des (logischen) Odersist folgende:

TRUETRUETRUEFALSEFALSEFALSEFALSETRUETRUETRUEFALSETRUE

Es ist also

Auch dies kan man durch ein Venn-Diagramm veranschaulichen:

Wir wollen nun die wichtigsten Rechenregeln f�r Durchschnitt und Vereinigung aufstellen:

1.3 Lemma.
Es seien,undMengen. Dann gilt:

1. Kommutativit�t:,.
2. Assoziativit�t:,.
3. Distributivit�t:

Assoziativit�t besagt also, da� es ist egal ist, wie wir bei mehrfachen Vereinigungen oder mehrfachen Durchschnitten Klammern setzen (in welcher Reihenfolge wir sie also ausrechnen), und wir k�nnen sie auch ganz weglassen, alsooderschreiben, ohne irgendwelche Mi�verst�ndnisse zu provozieren.

Distributivit�t zeigt, da� wenn sich Durchschnitts- und Vereinigungsbildung abwechseln, so darf man nicht mehr Klammern vertauschen, aber kann``hineinmultiplizieren''. Vergleiche dies mit dem Distributivgesetz f�r das Rechnen mit Zahlen:aber nicht.

1. Durch Zeichnung (Venn-Diagramme). Wichtig dabei ist, da� die drei Mengen,undin allgemeiner Lage gezeichnet werden, d.h. alle m�glichen F�lle f�r Punkte zu den einzelnen Mengen zu geh�ren oder nicht wirklich vorkommen. F�r vier Mengen w�re das schon nicht mehr ganz einfach erreichbar.
   

2. Durch Wahrheitstafel. D.h. man betrachtet alle F�lle daf�r, da�oder nicht,oder nicht undoder nicht, und �berpr�ft ob in allen F�llengenau dann ein Element der linken Seite ist, wenn es auch eines der rechten Seite ist.
   

3. Durch Umwandeln mittels der Definitionen in Aussagenlogik:Wir haben das distributiv-Gesetz f�r Durchschnitt und Vereinigung von Mengen also auf das distributiv-Gesetz f�r `und' und `oder' von Aussagen zur�ckgef�hrt. Die G�ltigkeit des letzteren sagt uns der gesunde Hausverstand oder wir (als Logiker) beweisen es mittels Wahrheitstafel so wie zuvor.

1.4 Definition.
Wenn man anstelle zweier Mengenundendlich viele Mengen,, ...,gegeben hat, so kann man rekursiv (siehe (3.4)) Durchschnitt und Vereinigung als

Man schreibt k�rzer und eindeutiger unter Vermeidung von ``'' auch

Will man das nun auf unendlich viele Mengen �bertragen, also den Durchschnittoder die Vereinigungeiner beliebigen Mengevon Mengendefinieren, dann sollte wohl der Durchschnittdie Menge all jener Objekte sein, die gleichzeitig in jeder der Mengenals Element enthalten sind, d.h.

Wenneine Eigenschaft f�r Mengen ist, so benutzt man auch die Schreibweise

Wie f�r zweifache Vereinigung und Durchschnitt erhalten wir auch in dieser allgemeinen Situation:

1.5 Lemma.
Es seieine nicht-leere Menge von Mengen. Dann istdie kleinste (im Sinne von ``Teilmenge sein'') Menge, die alleals Teilmengen enth�lt.
Ebenso istdie gr��te (im Sinne von ``Teilmenge sein'') Menge, die in allenenthalten ist.

Sei nuneine Menge mitf�r alle. Dann ist, denn ausfolgtmitund wegenist somit.

Sei andererseitseine Menge mitf�r alle. Dann ist, denn ausfolgtf�r alle, also.

    []

1.6 Definition.
Unter der Differenzmengezweier Mengenund(man sagt daf�r auch:vermindert um) versteht man die Menge aller Objektedie zwar Elemente vonnicht aber vonsind, d.h.

Das entsprechenden Venn-Diagramm ist:

Wenn die Mengeklar ist, d.h. sich alles in einer fixen Grundmengeabspielt, dann schreibt man auch k�rzerf�rund nennt dies das Komplement von(in).

1.7 Proposition.
Seieine Menge von Mengenundeine weitere Menge. Dann gelten:

Verallgemeinerte distributiv Gesetze:

Eine graphische Darstellung der De Morgan'schen Gesetze ist:

Eine verbale Formulierung ist: Ein Objekt ist genau dann kein Element der Vereinigung, wenn es in keinen derliegt. Und ein Objekt ist genau dann kein Element des Durchschnitts, wenn es in einen dernicht enthalten ist.

Um Beziehungen zwischen Objekten behandeln zu k�nnen, ben�tigen wir eine M�glichkeit diese paarweise zusammenzufassen. Nat�rlich k�nnten wir zuunddie Mengebetrachten. Wegenist das aber f�r Vergleiche nicht geeignet, und wir brauchen den Begriff des geordneten Paares, der gew�hrleistet, da�

Um also z.B. die Beziehung des Elternseins zu beschreiben m��te man eine Tabelle, wo f�r jeden Menschen seine Eltern angef�hrt sind, aufstellen, oder eine solche, wo f�r jeden Menschen alle seine Kinder angef�hrt sind, oder f�r je zwei Menschenundangeben, obein Kind von(bzw.ein Elternteil von) ist. D.h. insind alle Punkteentsprechend mit den Werten TRUE oder FALSE zu belegen. Es gen�gt nat�rlich dabei alle mit den Wert TRUE anzugeben, also eine Teilmenge vonauszuzeichnen. Dies f�hrt zu folgender

1.8 Definition.
Eine Relationaufist eine Teilmenge von. Man schreibt k�rzeranstelle von, und sagt daf�rsteht in Relationzu. Istso spricht man k�rzer (aber nicht ganz sauber) von einer Relation auf.

Z.B. haben wir die Relationen,,,,,f�r Mengen, also auch auf der Potenzmengejeder fix vorgegebenen Menge.

Wir k�nnen eine Relation auch mittels gerichteten Graph veranschaulichen, z.B. f�r die Teilmengenrelation aufwobei wir Pfeile die sich aus der Reflexivit�t ergeben nicht eingezeichnet sind:

Auf folgende wichtige Eigenschaften k�nnen wir Relationenaufuntersuchen

• Reflexivit�t::.
• Symmetrie::.
• Transitivit�t::,.

�quivalenzrelationen sind zumeist dadurch gegeben, da� man Objekte �quivalent nennt, wenn sie eine gewisse Eigenschaft gemein haben. Z.B. ist f�rdie Relation ``gleicher Rest bei Division durch'' alsoteilt, d.h.:, eine �quivalenzrelation auf. Ebenso sind ``gleicher Geburtstag'', ``gleiches Sternzeichen'', ``gleich viele Kinder'', ``gleiches Gewicht'', ``gleicher Vornamen'', ``in die gleiche Klasse gehen'' u.s.w. �quivalenzrelationen auf der Menge aller Menschen.

Beim letzten Beispiel, der in gleiche Klassen gehenden Sch�ler einer Schule, steckt offensichtlich dahinter, da� die Schule (oder auch deren Sch�ler) in Klassen eingeteilt sind. Wir wollen eine analoge Beschreibung nun f�r jede �quivalenzrelationauf Mengenerhalten. Dazu bezeichnen wir Mengen, die bez�glich ``'' so gro� wie m�glich (man sagt maximal) unter allen Teilmengensind welche nur paarweise �quivalente Elemente enthalten, als �quivalenzklassen der �quivalenzrelation. Wir verwenden dabei die Sprechweise ``paarweise �quivalenter'' anstelle ``�quivalenter'' Elemente, denn wir k�nnen ja jeweils nur 2 Elemente miteinander vergleichen um ihre �quivalenz zu �berpr�fen und nicht alle Elemente der Mengeauf einmal. Wir k�nnen auch nicht von der gr��ten Teilmenge mit obiger Eigenschaft sprechen, denn man denke nur an die Klassen einer Schule, welche mehrere maximale Mengen mit obiger Eigenschaft sind.

Wie kann man nun �quivalenzklassen finden? Man beginnt mit einen Elementund betrachtet die Menge

Diese Menge besteht offensichtlich aus paarweise �quivalenten Elementen, denn wegen der Transitivit�t und Symmetrie sind je zwei Elementezueinander �quivalent. Es kann auch keine echte Obermengemit dieser Eigenschaft geben, denn deren Elemente m��ten dann zu�quivalent sein. Also isteine �quivalenzklasse von, die einzige Klasse in derals Element liegt, die sogenannte vonerzeugte �quivalenzklasse.

Umgekehrt ist jede �quivalenzklassevon dieser Form, denn kannnicht leer sein, andernfalls w�hlen wir irgend einund erhalten eine gr��ere Menge, einen Widerspruch zur Maximalit�t. Somit existiert einund wir w�hlen ein solches. Dann ist, da jedeszu�quivalent ist und wegen der Maximalit�t vonist.

Es ist alsogerade die Menge aller �quivalenzklassen von.

Die �quivalenzklassen zur Teilbarkeit durchhei�en Restklassen modulo, und man schreibtf�r die Mengeder Restklassen ganzer Zahlen modulo.

Beachte, da� sich hier unsere Vereinbarung, da� in der aufz�hlenden Beschreibung einer Menge gleiche Elemente mehrfach auftreten d�rfen bezahlt macht, denn z.B. ist, denn als Reste bei Division durch 2 kann ja nur 0 undauftreten.

1.9 Definition.
Eine Klasseneinteilungeiner Mengeist eine Mengevon nicht-leeren Teilmengendie paarweise disjunkt sind (d.h.mit) und deren Vereinigungist, d.h..

1.10 Proposition.
Es seieine nicht-leere Menge. Dann entsprechen den �quivalenzrelationaufgenau den Klasseneinteilungenvon.

Sei weitersund. Dann istnach obigen.

() Umgekehrt seieine Klasseneinteilung von. Wir definieren:. Dies beschreibt eine �quivalenzrelationauf:
Die Relation ist reflexiv, denn f�rexistiert einemit, also. Sie ist offensichtlich symmetrisch. Nun zur Transitivit�t. Sei, d.h.mit,. Also istund somit, d.h., also.

Bleibt zu zeigen, da� das hin und her zwischen �quivalenzrelationenund Klasseneinteilungenzusammenpa�t.

Sei alsodie Menge der �quivalenzklassen einer �quivalenzrelationunddie ausgewonnene �quivalenzrelation. Wir behaupten, da� diese mit der urspr�nglichen �bereinstimmt. Wir m�ssen alsozeigen.
Sei zuerst, dann liegt, also ist auchnach Definition. Umgekehrt sei, d.h. es existiert einmit. Daaber aus bez�glichpaarweise �quivalenten Elementen bestehen mu�, ist.

Sei nun andererseitsirgend eine Klasseneinteilung vonunddie zugeh�rige �quivalenzrelation, d.h.. Wir m�ssen zeigen, da�gerade aus den �quivalenzklassenvonbesteht.
Es ist, denn f�rist, also existiert einmit. Verschiedeneliefern das gleiche, denn diesind nach Voraussetzung paarweise disjunkt. Also ist. Sei umgekehrt. Dann ist, alsound damit.
Sei nun. Nach Voraussetzung ist, also k�nnen wir einw�hlen. Dann ist aber wie zuvor, dennimpliziertund somit. Wegen der paarweisen Disjunktheit ist somit.     []

1.11 Definition. Ordnungsrelationen.
Eine weitere wichtige Eigenschaft, auf die wir Relationenauf einer Mengeuntersuchen k�nnen, ist die Antisymmetrie, d.h.:.

Eine Relation die reflexiv, antisymmetrisch und transitiv ist hei�t Ordnungsrelation (oder auch partielle Ordnung).

Ein Beispiel daf�r ist die Relationf�r Mengen.

Gilt zus�tzlich die Dichothomie, d.h. je zwei Elemente sind miteinander vergleichbar, so hei�t die Ordnung linear oder auch totale Ordnung.

Ein Beispiel daf�r ist die Relationf�r Zahlen.

Mittels solcher Relationen, k�nnen wir die Elemente einer Menge in eine Reihenfolge bringen.

Ordnungsrelationen auf einer endlichen Menge k�nnen wir mittels sogenannten Hasse-Diagramm veranschaulichen, wobei gr��ere Elemente weiter oben stehen und Verbindungen die sich aus Reflexivit�t oder Transitivit�t ergeben nicht eingezeichnet werden. Z.B. f�r die Teilmengenrelation auf:

1.12 Definition. Funktionen.
Unter einer Abbildung (oder Funktion)vonnach(man schreibtund nenntden Definitionsbereich undden Wertebereich von) versteht man eine Relationmit der Eigenschaft, da� f�r jedesgenau einexistiert mit(und man schreibt dannf�r diesesoder auchund nennt es den Funktionswert vonbez�glich der Funktion). Wir k�nnen uns eine Abbildungals Programm (oder besser als eine blackbox) vorstellen, welches f�r jeden Inputeinen wohldefinierten Outputliefert.

Wir schreibenf�r die Menge aller Abbildungen. Die Motivation f�r diese Bezeichnungsweise ist, da�

F�r Abbildungenundundist das Bild vonunterdefiniert durch

und das Urbild vonunterdefiniert durch

Man kann Abbildungenundzusammensetzen zu einer Abbildung, die definiert ist durch. Lies dies als ``g ring f'' oder ``g zusammengesetzt mit f''. Als Teilmengebedeutet dies

Wichtige Eigenschaften, auf die hin man Abbildungenuntersuchen kann, sind:

• hei�t injektiv, wenn aus, oder �quivalent wenn, d.h. jedestritt h�chstens f�r einals Output unterauf. Nicht Injektivit�t l��t sich graphisch wie folgt darstellen:
  

• hei�t surjektiv, wennist, also f�r jedeseinmitexistiert, d.h. jedestritt mindestens f�r einals Output unterauf. Nicht Surjektivit�t l��t sich graphisch wie folgt darstellen:
  

• hei�t bijektiv, wennsowohl injektiv als auch surjektiv ist, d.h. zu jedemgenau einexistiert mit.

Beispiel.
Wir betrachten die Funktion

• ist weder injektiv noch surjektiv.
• 
  ist injektiv aber nicht surjektiv.
• 
  ist nicht injektiv aber surjektiv.
• 
  ist bijektiv.

1.13 Bemerkung.
Die Notationf�r die Zusammensetzung vonmitist keineswegs gl�cklich gew�hlt, denn dabei wirkt ja zuerstund dannauf einen Input. W�rde man hier allerdings die Reihenfolge umdrehen, so w�re es wegen der definierenden Formelzweckm��ig auch die rechte Seite besser alszu schreiben, d.h. den Wert vonbzgl. der Abbildungalsund nicht. Dies w�rde auch durchwegs der Idee entsprechen, da� jagenommen wird und darauf dann die Vorschriftangewandt wird, was auch der Schreibweise

Auch die Bezeichnungf�r die Bildmenge und

Die grundlegenden Eigenschaften von Bild und Urbild fa�t folgende Proposition zusammen:

1.14 Proposition.
Es seieine Abbildung,,,und. Dann gilt:

Verbale Formulierungen sind z.B.:

(1)

(2) Sei,, d.h.. Somit istund damit.

(3)

(4)

(5')

Beachte, da� in (3) nicht Gleichheit gilt: Es seidie Funktion

Der Grund warum der Beweis f�r Gleichheit nicht funktioniert ist, da� zwar ``es gibt ein, soda� f�r alleeine Aussage gilt'' zur Folge hat, da� ``f�r jedeseinexistiert, soda� dieselbe Aussage gilt'' jedoch nicht umgekehrt. Man vergleiche z.B. ``Jeder Mensch besitzt eine Mutter'' mit ``Es gibt eine Frau die Mutter von jedem Menschen ist''. Oder auch ``jeder wird von jemanden geliebt'' im Gegensatz zu ``Es gibt jemanden der jeden liebt''.

1.16 Proposition.
Es seieine Abbildung und. Dann gilt:

• ist injektiv:.
• ist surjektiv:.
• ist bijektivmitund.

() Umgekehrt seiund. Dann ist, alsoinjektiv.

(2) () Sei nunsurjektiv. F�r jedesw�hlen wir ein zugeh�riges

() Umgekehrt seiund. Es istund, d.h.ist surjektiv.

(3) () Entweder man definiert

() Dies folgt sofort aus (1) und (2).     []

1.15 Bemerkung.
Die eindeutige Abbildungmitund, die f�r bijektiveexistiert, hei�t Umkehrfunktion vonoder auch inverse Funktion zuund wird auch alsbezeichnet.

Fallsbijektiv ist, so ist das Urbild

1.17 Definition.
Es seieine Abbildung undeine Teilmenge. Unter der Einschr�nkungverstehen wir die Abbildung, die aufmit�bereinstimmt, also durchgegeben ist. Als Teilmenge vonist also.

1.18 Um Mengen der Gr��e nach miteinander vergleichen zu k�nnen, k�nnen wir f�r endliche Mengen nat�rlich die Anzahlen der Elemente bestimmen und diese dann vergleichen. Ohne wirklich z�hlen zu k�nnen gibt es aber auch eine andere M�glichkeit: Um z.B. festzustellen, ob gleichviele H�hrerInnen wie Sitzpl�tze vorhanden sind, bittet man darum, da� sich alle setzten und falls weder leere Sitze �berbleiben noch Personen stehenbleiben, dann sind es gleich viele. Mathematisch kann man das so beschreiben, da� versucht wird jeder Personeinen Platzso zuzuordnen, da� keine zwei Personen den gleichen Platz angewiesen bekommen und auch kein Platz �brigbleibt, d.h. diese Zuordnungvon der Menge aller Personen in die Menge aller Pl�tze bijektiv ist. Dieses Verfahren k�nnen wir auch bei unendlichen Mengen durchf�hren und geben dazu folgende

Definition.
Wir schreiben(oder auch), fallsundgleichm�chtig sind, d.h. eine bijektive Abbildungexistiert. Eine Mengehei�t abz�hlbar (unendlich) falls sich gleichm�chtig mit der Mengeder nat�rlichen Zahlen ist.

Eine Menge hei�t endlich, falls sie nur endlich viele Elemente besitzt, also gleichm�chtig zu einer nat�rlichen Zahlist.

1.19 Bemerkung.
Im Unterschied zu endlichen Mengen, kann eine unendliche Menge durchaus gleichm�chtig mit einer echten Teilmenge sein. Z.B. definierteine bijektive Abbildung.

Veranschaulichen kann man sich dies wie folgt: Man betrachtet Hilbert's Hotel, ein Hotel mit abz�hlbar unendlich vielen Zimmern, die mit den nat�rlichen Zahlen 0,1,2,...durchnumeriert sind. Diese Hotel sei voll belegt und es kommt ein neuer Gast, welcher dadurch untergebracht werden kann, da� man die bereits einquartierten G�ste bittet jeweils in das Zimmer mit der n�chst h�heren Nummer zu wechseln und somit Zimmer 0 freibekommt.

Man kann sogar eine unendliche Teilmenge entfernen ohne die Gleichm�chtigkeit zu st�ren: Betrachte die Mengeder gerade Zahlen. Dann definierteine bijektive Abbildung. Und f�r die Mengeder ungeraden Zahlen gilt ebenfallsverm�ge. Es ist alsodie disjunkte Vereinigungund beide Teilmengen sind gleichm�chtig mit.

Ebenso ist, dennundsowie, alsonach �bungsaufgabe (43).

Veranschaulichen kann man sich das wieder durch Hilbert's Hotel. Diesmal kommt ein Reisebus mit abz�hlbar unendlich vielen Passagieren die alle untergebracht werden sollen. Diesmal werden die bereits einquartierten G�ste gebeten jeweils in das Zimmer mit der doppelt so gro�en Nummer zu wechseln. Dann werden alle Zimmer mit ungerader Nummer frei und wir k�nnen die Passagiere des Reisebusses in diesen abz�hlbar unendlich vielen Zimmern unterbringen.

Aber auch

Das bedeutet also, da� selbst wenn auf abz�hlbar unendlich vielen Welten jeweils ein voll belegtes Hotel von Hilbert steht und aus Einsparungsgr�nden alle bis auf ein Hotel aufgel�st werden sollen, dann kann man den G�sten, die durch Hotelnummer und Zimmernummer beschrieben werden k�nnen (also durch Punkte in), auf eindeutige Weise neue Zimmernummern indes verbleibenden Hotels zuweisen.

In �bungsaufgabe (44) werden wird zeigen, da� die Menge aller endlichen Folgen nat�rlicher Zahlen ebenfalls abz�hlbar ist, und somit auch die Menge der Polynome mit rationalen Koeffizienten und ebenso die Menge der algebraischen Zahlen, d.h. Nullstellen solcher Polynome. Aus dem gleichen Argument ist auch die Menge aller m�glichen (endlich langen) Worte (die mittels Buchstaben aus einen abz�hlbaren Alphabet gebildet werden k�nnen) abz�hlbar und ebenfalls die Menge aller m�gliche (endlichen) S�tze und genauso aller (endlichen) B�cher.

Da� es aber auch echt m�chtigere unendliche Mengen (sogenannte �berabz�hlbare Mengen) gibt, war eine von Cantor's wesentlichen Erkenntnissen:

Wie oft kommt ein Element in einer Menge vor?

Kann eine Menge ein Element einer anderen Menge sein?

Wie viele Elemente hat eine Menge?

Sind unendliche Mengen gleichmächtig?