TU Wien:Mathematik 1 UE (diverse)/Theorie WS05/22.11.2005

Intention

Diese Präsentationsgrundlage ist nicht darauf ausgerichtet, die Gebiete

• Mengen
• Relationen
• Funktionen von Mengen

zu erläutern, sondern wurde konzipiert als Grundgerüst für die theoretische Grundlage der Beispiele, die am 23.11.2005 in den Übungsgruppen vorbereitet sein müssen. --Mnemetz 17. Nov 2005 11:03 (CET)

Mengen

Alle Bezeichnungen der Mengenlehre tauchen in der einen oder anderen Form als Hilfsmittel in allen Teilbereichen der Mathematik auf, da sie eine kurze und übersichtliche Darstellung von Sachverhalten ermöglichen.

Definition von Mengen

Ein Kleinkind bekommt eine Schachtel voller Duplo-Steine in verschiedenen Farben. Das Kind sortiert nun alle roten Steine aus und bildet damit die "Menge der roten Steine".

Was lernen wir daraus Allgemeines bezüglich Mengenbildung? Bei dieser werden Objekte

• ausgesondert
• und zusammengefasst.

Naive Mengenlehre

Georg CANTOR (1845-1918) definiert "Menge" folgendermaßen:

---

Definition: Unter einer Menge ist die Zusammenfassung von bestimmten, wohlunterscheidbaren Objekten zu einem Ganzen zu verstehen. Die Objekte, die zu einer Menge zusammengefasst werden, heißen Elemente dieser Menge.

---

Die Elemente müssen also einem Auswahlkriterium standhalten. Ebenso muss das Auswahlkriterium entsprechend gewählt werden.

Mit der Wohlunterscheidbarkeit geht die Forderung einher, dass die Elemente der Menge klar trennbar sein müssen! Beispiel: Menge aller Buchstaben von "glatt" entspricht "M = {g,l,a,t} ".

Ob ein Element zu einer Menge gehört beschreibt man kurz als $x\in M$; gehört es nicht dazu, dann als $x\notin M$

Russels' Paradoxon

Die Formulierungen der naiven Mengenlehre führen jedoch in gewissen Fällen zu Paradoxien!

Die Russellsche Antinomie ist ein von Bertrand Russell formuliertes Paradoxon auf der Grundlage der naiven Mengenlehre. Die Menge M ist definiert als die "Menge aller Mengen, die sich nicht selbst enthalten".

$M=\{X|X\notin X\}$

Diese Definition führt zu einem Widerspruch, da sich demzufolge M sowohl selbst enthält als auch nicht selbst enthält.

Es gibt zahlreiche populäre Formulierungen der Russellschen Antinomie. Bekannt ist der Barbier, der alle Männer im Ort rasiert, die sich nicht selbst rasieren. Die Frage, ob sich der Barbier selbst rasiert oder nicht, führt ebenfalls zu einem Widerspruch (Barbier-Paradoxon).

Durch den axiomatischen Aufbau der Mengenlehre lassen sich Antinomien vermeiden. Er zeigt, dass die Zusammenfassung aller Mengen, die sich nicht selbst enthalten, keine Menge sein kann, sondern eine Klasse bildet - eben weil das sonst zu einem Widerspruch führt. Die Klassendefinition dieser Mengenzusammenfassung ist jedoch in sich widerspruchsfrei und bildet die leere Klasse.

Mengenangaben

Beschreibende Mengenangabe

Auch deskriptive Mengenangabe genannt.

$A=\{x|x{\text{ hat die Eigenschaft(en) }}P\}$

Die Menge A besteht also aus allen Elementen x, die die Eigenschaften P besitzen.

Statt dem | wird manchmal auch : geschrieben.

Aufzählende Mengenangabe

Auch enumerative Mengenangabe genannt: Dabei werden die Elemente der Menge explizit angegeben:

$B=\{1,2,3,4,5,6\}$

Z.B. alle Elemente eines Würfels.

Veranschaulichung durch Venn-Diagramme

Mengen werden sehr oft durch VENN-Diagramme veranschaulicht.

Der von dr Kurve umschlossene Bereich smybolisiert die Elemente der Menge A.

Spezielle Relationen zwischen Mengen

Betrachten wir nun einige spezielle Beziehungen zwischen zwei Mengen A und B und einige Operationen, bei denen den Mengen A und B eine Menge C zugeorndet wird.

Teilmenge

Die Menge B heißt Teilmenge von A

$B\subseteq A$

wenn jedes Element von B auch in A ist, d.h.

$x\in B\Rightarrow x\in A$

Als Venn-Diagramm dargestellt:

Gleichheit

Die Mengen A und B heißen gleich (A = B), wenn jedes Element von A auch in B ist und umgekehrt. D.h. A ist eine Teilmenge von B und B eine Teilmenge von A:

$A=B\Leftrightarrow (A\subseteq B\wedge B\subseteq A)$

echte Teilmenge

Eine echte Teilmenge ist die Menge B dann von A ($B\subset A$), wenn B eine Teilmenge von A ist aber B ungleich A is. d.h.:

$B\subset A\Leftrightarrow (B\subseteq A\wedge B\neq A)$

Manchmal wird auch das Symbol $\subsetneq$ verwendet.

Durchschnitt

Die Menge C heißt Durchschnitt der Mengen A und B (sprich folgende symbolische Darstellung als "C ist A geschnitten B"),

$C=A\cap B$

wenn C die Menge aller Elemente ist, die sowohl in a als auch in B liegen, d.h.:

$C=A\cap B=\{x|x\in A\wedge x\in B\}$

Als VENN-Diagramm dargestellt:

Die Definition des Durchschnittes auf ein beliebiges System von Mengen $A_{i},i\in I$ erweitert bedeutet:

$\bigcap _{i\in I}A_{i}=\{x|x\in A_{i}\qquad \forall i\in I\}$

(Der Durchschnitt dieser Mengen ist die Menge aller Elemente ...)

Disjunktivität

Die Mengen A und B heißen disjunkt, wenn gilt:

$A\cap B=\varnothing$

$\varnothing$ symbolisiert eine leere Menge.

Als VENN-Diagramm dargestellt:

Vereinigung

C ist dann die Vereinigungsmenge vn A und B

$C=A\cup B$

wenn C die Menge aller Elemente ist, die in A oder in B oder in beiden Mengen liegen, d.h.:

$C=A\cup B=\{x|x\in A\vee x\in B\}$

$\vee$ steht für "oder".

VENN-Diagramm:

Die Definition der Vereinigung auf ein beliebiges System von Mengen $A_{i},i\in I$ erweitert bedeutet:

$\bigcup _{i\in I}A_{i}=\{x|{\text{ Es existiert ein }}i\in I{\text{ mit }}x\in A_{i}\}$

Differenz

Die Differenzmenge C = A - B (manchmal auch c = A\B besteht aus den Elementen von A, die nicht in B liegen, d.h.:

$C=A-B=\{x|x\in A\wedge x\notin B\}$

C = B - A als VENN-Diagramm:

Wenn $B\subseteq A$, so gilt: $B-A=\varnothing$.

"Universum"

Der Begriff Universum steht in der (diskreten) Mathematik für das so genannte Mengenuniversum U. Es fasst beliebige bekannte und unbekannte, über Axiome definierte Objekte zusammen, auch Mengen von Objekten.

Symmetrische Differenz

C heißt symmetrische Differenz der Mengen A und B,

$C=A\triangle B$,

wenn C alle Elemente aus A enthält, die nicht zu B gehören und alle Elemente aus B, die nicht zu A gehören, d.h.:

$A\triangle B=(A-B)\cup (B-A)$

VENN-Diagramm:

Cartesisches Produkt

C ist ein cartesisches Produkt der Mengen A und B,

$C=A\times B$,

wenn C die Menge aller geordneten Paare $\langle x,y\rangle$ von den Elementen $x\in A$ und $x\in B$ ist, d.h.:

$C=A\times B=\{\langle x,y\rangle |x\in A,y\in B\}$.

$\langle \rangle$ symbolisieren geordnete Paare, n-Tupel, etc.

Cartesische Koordinaten

Beispiel:

A = {0,1}, B = {0,1,2}

$\Rightarrow A\times B=\{\langle 0,0\rangle ,\langle 0,1\rangle ,\langle 0,2\rangle ,\langle 1,0\rangle ,\langle 1,1\rangle ,\langle 1,2\rangle ,\}$

Darstellung der Elemente als "Koordinatensystem:

Operationen zwischen Mengen

Kommutativgesetze

Vertauschungsgesetze - möglich ist:

• $A\cap B=B\cap A$
• $A\cup B=B\cup A$
• $A\triangle B=B\triangle A$

Assoziativgesetze

Verknüpfungsgesetze, möglich sind:

• $(A\cap B)\cap C=A\cap (B\cap C)$

• $(A\cup B)\cup C=A\cup (B\cup C)$
• $(A\triangle B)\triangle =A\triangle (B\triangle C)$

Distributivgesetze

Auch Verteilungsgesetze genannt.

• $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

• $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Allgemeiner mit Mengen:

$A\cup (\bigcup _{i\in I}B_{i})=\bigcup _{i\in I}(A\cup B_{i})$

$A\cup (\bigcap _{i\in I}B_{i})=\bigcup _{i\in I}(A\cap B_{i})$

De Morgan'sche Gesetze

Diese Gesetze behandeln die Relationen zwischen Komplement-Mengen (d.h. "umgekehrten" Mengen").

$A,B\subseteq M=C_{M}(A\cap B)=C_{M}(A)\cup C_{m}(B)$

Potenzmenge

Die Potenzmenge der Menge A (${\mathfrak {P}}$), ist die Menge, deren Elemente alle Teilmengen der Menge A sind, d.h.:

${\mathfrak {P}}=\{U|U\subseteq A\}$

Relationen

Definition

Eine allgtemeine Beschreibung der Beziehung $U\subseteq V$ für Teilmengen U,V einer vorgegebenen Menge M. d.h.

$U,V\in {\mathfrak {P}}(M)$

kann z.B. so vorgenommen werden, daß die Teilmenge

$R=\{\langle U,V\rangle |U,V\in {\mathfrak {P}}(M)\wedge U\subseteq V\}$

des cartesischen Produktes ${\mathfrak {P}}(M)\times {\mathfrak {P}}(M)$ vorgegeben wird.

U und V stehen genau dann in der Relation "$\subseteq$", wenn das geordnete Paar $\langle U,V\rangle$ in R liegt.

Betrachten wir die Menge M={0,1}, d.h.:

${\mathfrak {P}}=\{\varnothing ,\{0\},\{1\},\{0,1\}\}$ - in der folgenden Grafix die mit x markiertten Punkte:

Eine allgemeine Definition: Die zweistellige Relation R auf einer Menge A ist eine Teilmenge des cartesischen Produktes $A\times A$. Sind a,b $\in$ A, so steht A in Relation zu B genau dann, wenn $\langle A,B\rangle \in R$ gilt. Die übliche Schreibweise ist aRb.

Gerichtete Graphen

Relationen können als gerichtete Graphen symbolisch dargestellt werden. Dieser besteht aus einer Menge von "Knoten", und zwar den Elementen der Menge A, sowie einer Menge von gerichteten Kanten (durch Pfeile dargestellt), die von einem "Knoten" U genau dann zu einem Knoten V führen, wenn das geodnete Paar $\langle U,V\rangle$ in R liegt.

Beispiel eines gerichteten Graphen der Relation "$\subseteq$" auf A = ${\mathfrak {P}}$({0,1}):

Äquivalenzrelation

Bei einer Äquivalenzrelation müssen Reflexivität, Symmetrie und Transitivität gemeinsam vorliegen.

Reflexivität

Reflexivität heißt, dass jedes Element in Relation zu sich selbst steht:

$\forall {\text{ a }}\in {\text{ A }}:{\text{ (a,a) }}\in {\text{ R }}$

Symmetrie

Symmetrie heißt, wenn für alle a,b mit aRb auch bRa folgt.

$\forall {\text{ a,b }}\in {\text{ }}A^{2}:{\text{ (a,b) }}\in {\text{ R }}\qquad \Rightarrow \qquad {\text{ (b,a) }}\in {\text{ R }}$

Transitivität

Eine Relation R transitiv, wenn stets gilt: (a,b) aus R UND (b,c) aus R FOLGT (a,c) aus R

$\forall {\text{ a,b }}\in {\text{ R }}:{\text{ (a,b) }}\in {\text{ R }}\wedge {\text{ (b,c) }}\in {\text{ R }}\qquad \Rightarrow \qquad {\text{ (a,c) }}\in {\text{ R }}$

Klasseneinteilung

Eine Zerlegung einer Menge A in leere, paarweise disjunkte Teilmengen $A_{i},i\in I$ heißt Klasseneinteilung oder Partitionierung der Menge.

In der Mengenlehre heißen zwei Mengen A und B disjunkt oder elementfremd, falls sie kein gemeinsames Element besitzen.

Gleichbedeutend dazu ist folgende formale Definition:

Zwei Mengen A und B heißen disjunkt, wenn A geschnitten mit B leer ist:

$A\cap B=\emptyset$

Mehrere Mengen heißen paarweise disjunkt, wenn je zwei von ihnen disjunkt sind.

Eine disjunkte Mengenfamilie

$M_{i},\quad i\in \Lambda$

ist eine Familie von paarweise disjunkten Mengen. Es gilt also

$M_{i}\cap M_{j}=\emptyset$ für $i\neq j$.

Die Vereinigung M eines disjunkten Mengensystems bezeichnet man als disjunkte Vereinigung und schreibt sie als

$M={\dot {\bigcup _{i\in \Lambda }}}M_{i}\ .$

Ein Mengensystem U von Teilmengen einer Menge X heißt Partition von X, wenn gilt:

• die Vereinigung aller Mengen in U ist wieder ganz X,
• U ist eine disjunkte Mengenfamilie,
• die leere Menge ist nicht Element von U.

Vgl. auch Einteilung in Restklassen bei modulo-Beispielen.

Halbordnungsrelation

Eine Relation R auf die Menge A heißt Halbordnungsrelation, wenn folgende Bedingungen erfüllt sind:

Reflexivität

Reflexivität heißt, dass jedes Element in Relation zu sich selbst steht:

$\forall {\text{ a }}\in {\text{ A }}:{\text{ (a,a) }}\in {\text{ R }}$

Identität

$(aRb\wedge bRA)\Rightarrow a=b\qquad \forall a,b\in A$

Transitivität

Eine Relation R transitiv, wenn stets gilt: (a,b) aus R UND (b,c) aus R FOLGT (a,c) aus R

$\forall {\text{ a,b }}\in {\text{ R }}:{\text{ (a,b) }}\in {\text{ R }}\wedge {\text{ (b,c) }}\in {\text{ R }}\qquad \Rightarrow \qquad {\text{ (a,c) }}\in {\text{ R }}$

Hasse-Diaramm

Betrachten wir die Halbordnung "$\subseteq$" auf ${\mathfrak {P}}(\{0,1,2\})$ - als gerichteten Graphen ergibt sich:

Die Darstellung kann man vereinfachen, wenn man die vorliegende Halbordnung berücksichtigt:

1. Wegen der Refexivität kann man alle Schlingen $\circlearrowleft$ weglassen.
2. Wegen der Transitivität genügt es, nur die gerichteten Kanten zum "direkten" Nachfolger zu zeichnen.

Ergibt folgende Vereinfachung:

Wenn man nun vereinbart, dass die Kanten stets als nach oben gerichtet zu betrachten sind, ergibt sih als weietre Vereinfachung:

Dies ist dann das Hasse-Diagramm.

Funktionen, Kardinalzahl von Mengen

Funktion (Abbildung)

Definition der Funktion

A und B seien zwei nichtleere Mengen. Unter einer Funktion (oder Abbildung) f von A in B versteht man dann eine Vorschrift, die jedem $a\in A$ ein eindeutig bestimmbares $b\in B$ zuordnet,

b wird dann das Bild von a unter f genannt, b = f(a).

A ist dann der Definitionsbereich, B der Wertevorrat von f.

Injektivität

Eine Funktion $f:{\text{ }}A\rightarrow B$ ist dann injektiv, wenn jedes Element $b\in B$ höchstens einmal als Bild des Elementes $a\in A$ auftritt, d.h.:

$f(a_{1})=b,f(a_{2})=b\Rightarrow a_{1}=a_{2}\qquad \forall a_{1},a_{2}\in A,b\in B$

oder

$a_{1}\neq a_{2}\Rightarrow f(a_{1})\neq f(a_{2})\qquad \forall a_{1},a_{2}\in A$.

Man sagt auch eineindeutige Abbildung von A in B oder 1-1 Abbildung von A in B).

Surjektivität

Eine Funktion $f:{\text{ }}A\rightarrow B$ ist dann surjektiv, wenn jedes $b\in B$ mindestens einmal als Bild eines Elementes $a\in A$ unter f auftritt, d.h.:

Zu jedem $b\in B$ existiert ein $a\in A$ mit f(a)=b.

Man sagt auch: Abbildung von A auf B.

Bijektivität

Eine Funktion $f:{\text{ }}A\rightarrow B$ ist dann bijektiv, wenn f injektiv und surjektiv ist.

Man sagt auch umkehrbar eindeutig oder eindeutige Abbildung von A auf B ider 1-1 Abbildung von A auf B.

Kardinalität

Für die Kardinalzahl (Kardinalität, Mächtigkeit), einer Menge A schreibt man |A| oder #A und für sie gilt:

1. hat eine Menge A nur eindlich viele Elemente (eine endliche Menge), so bezechnet |A| die Anzahl der Elemente von A,
2. Allen gleichmächtigen, unendlichen Mengen ordnet man als Kardinalzahl das Symbol "Aleph" zu: $\aleph$