- - - - - Diese Seite braucht webEQ! Klicken Sie auf das Logo. - - - - -
4.8. Gleichmächtige Mengen

Bijektive Funktionen spielen in der Mengenlehre eine ungemein wichtige Rolle. Mit ihnen kann man u.a. präzise beschreiben, wann zwei Mengen gleichviele Elemente enthalten, so daß schließlich die Mengen hinsichtlich ihrer Elementanzahl klassifiziert werden können.

Definition: Zwei Mengen M und N heißen gleichmächtig (in Zeichen M ~ N), falls es eine bijektive Funktion  f : M ® N gibt.

Bemerkung:  N ~ Æ  Û  N = Æ M ~ M M ~ N   Þ  N ~ M M ~ N   Ù  N ~ L   Þ  N ~ L Beweis: Zu 1.: Sei  N ~ Æ, dann gibt es eine bijektive Funktion von  N  ® Æ. Falls N ¹ Æ, gibt es überhaupt keine Funktion von N® Æ. Also hat man: N = Æ. Falls N = Æ, ergibt sich die Behauptung aus 2. Zu 2.: XM ist eine umkehrbare Funktion von M ® M. Zu 3.: Ist  f : M ® N  bijektiv, so ist   f -1 : N ® M  ebenfalls bijektiv. Zu 4.: Sind   g : M ® N  und  f : N ® L  bijektiv, so ist auch $f\circ g$ : M ® L  bijektiv.

Das Konzept der Gleichmächtigkeit ist ein unentbehrliches Hilfsmittel bei der Untersuchung unendlicher Mengen. Einige "Mengensorten" zeichnen wir durch einen Namen aus:

Definition: Eine Menge M heißt endlich, falls M = Æ oder falls es eine natürliche Zahl n gibt, so daß {1,....,n} ~ M. Eine Menge M heißt abzählbar, falls N ~ M . Jede Bijektion  f : N ® M  heißt eine Abzählung von M. Eine Menge M heißt unendlich, falls sie nicht endlich ist. Unendliche Mengen, die nicht abzählbar sind, nennen wir überabzählbar.

Beispiel: Jede Menge der Form {a1,....,an} ist endlich. Jede abzählbare Menge M ist unendlich. Æ ist nicht abzählbar. M   $~/$  P(M). Beweis: Zu 1.: Offensichtlich ist {(1,a1),....,(n,an)} eine bijektive Funktion von {1,....,n} ® {a1,....,an}. Zu 2.: Sei  f : N ® M  eine Abzählung von M. Insbesondere ist damit M ¹ Æ. Wäre nun M endlich, so gäbe es ein n Î N und eine Bijektion g : {1,....,n} ® M . Damit ist aber $h:=g\circ f^{-1}$ eine umkehrbare Funktion von {1,....,n} ® N . h kann nicht bijektiv sein, denn z.B. hat die natürliche Zahl  max{h(1),....,h(n)} + 1  kein h-Urbild. Widerspruch. Zu 3.: Ergibt sich sofort aus 2. Zu 4.: Der sehr elegante Beweis geht auf Cantor zurück. Wir müssen zeigen: keine Funktion von M nach P(M) ist umkehrbar. Sei dazu  f : M ® P(M) irgendeine Funktion. Wir betrachten die Menge A :=  {x Î M | x Ï f(x)}Ì M. A hat kein Urbild, denn die Gleichung  f(y) = A für ein y ΠM erzeugt den Widerspruch y Î f(y)   Û   y Î A    Û   y Ï f(y). Also ist  f nicht bijektiv.

Bei den klassischen Zahlenmengen N, Z, Q  und R  sind die Unendlichkeitssorten bekannt. Zunächst stellen wir dies für N  und Z  dar.

Beispiel: N  ist abzählbar. Z  ist abzählbar. Beweis: Zu 1.: XN  ist eine Bijektion von N ® N . Zu 2.: Die Aufgabe besteht darin, die Elemente von Z , d.h. .....,-2,-1,0,1,2,..... mit natürlichen Zahlen durchzunummerieren. Dies scheint schwierig zu sein, da Z  keinen "Anfang" hat; die folgende Umsortierung aber räumt dieses Hindernis aus dem Weg: 0,1,-1,2,-2,...... Mit Hilfe der Gaußfunktion können wir diese Nummerierung durch eine Funktion erzeugen: Die Funktion f : N ® Z ,  gegeben durch   $f(n):={(-1)}^n[\frac{n}{2}]$ ist bijektiv; g : Z ® N  mit   $g(n):=\{\begin{array}{c}2n,\text{\&quad;falls\&quad;}n>0\hfill \\ -(2n-1),\text{\&quad;falls\&quad;}n\&LessEqual;0\hfill \end{array}$ ist die Umkehrfunktion. Zum Beweis zeigen wir, daß sich  f und g in ihrer Wirkung gegenseitig aufheben: Für n ΠZ >0 ist    $f(g(n))=f(2n)={(-1)}^{2n}[n]=n$ . Für n ΠZ £0 ist    $f(g(n))=f(-(2n-1))={(-1)}^{-(2n-1)}[-n+\frac{1}{2}]=(-1)(-n)=n$ . Für ein gerades n ÎN  ist    $g(f(n))=g({(-1)}^n[\frac{n}{2}])=g(\frac{n}{2})=2\frac{n}{2}=n$ . Für ein ungerades n ÎN ,  etwa n = 2k-1, ist    $\begin{array}{ccc}g(f(n))\hfill & =\hfill & g({(-1)}^n[\frac{n}{2}])\hfill \\ \hfill & =\hfill & g(-[k-\frac{1}{2}])=g(-(k-1))=2(k-1)+1=2k-1=n.\hfill \end{array}$

Bei den verbliebenen Mengen Q  und R  sind die Überlegungen ein wenig aufwendiger. Es ist übersichtllicher, zunächst einige allgemeine, auch für sich interessante Sachverhalte zu klären.

In einigen Bereichen besitzen die Teilmengen von N  eine gewisse Schlüsselrolle. Daher benötigen wir einen vollständigen Überblick über ihre Mächtigkeiten. Wenngleich die folgenden Aussagen anschaulich sehr klar sind, die Beweise müssen streng geführt werden! Überdies sind sie technisch aufwendig. Wir benutzen gelegentlich eine wichtige Grundeigenschaft der natürlichen Zahlen: Jede nicht-leere Teilmenge von N  besitzt ein kleinstes Element.

Bemerkung: Es sei n ÎN, dann ist jede Teilmenge A von {1,....,n} endlich. Jede Teilmenge A von N ist endlich oder abzählbar. Beweis: Zu 1.: Falls A = Æ, ist nichts weiter zu zeigen. Sei also A ¹ Æ. Wir müssen A bijektiv auf ein "fortlaufendes Stück" {1,....,k} abbilden, wobei wir zunächst die Länge k dieses Stücks benötigen. Dazu "zählen" wir die Elemente von A mit Hilfe ihrer Indikatorfunktion cA und setzen k := cA(1) + .... + cA(n). Ist z.B. A = {2,4} Ì {1,2,3,4}, so  ist  k  =   cA(1) + cA(2) + cA(3) + cA(4)   =  0 + 1 + 0 + 1   =  2. Mit dem gleichen Trick definieren wir nun die Funktion   g : A ® {1,....,k} durch  g(i) := cA(1) + .... + cA(i). Da A ¹ Æ, besitzt A ein kleinstes Element: minA. Offensichtlich ist g(minA) = 1; ferner hat man: g(i +1) =  g(i) + cA(i + 1), also entsteht g(i + 1) aus g(i) durch Addition von 1 oder 0, d.h. insbesondere ist g(i) £ g(i+1).  Außerdem ist g(i) £  k, also sind alleWerte von g natürliche Zahlen zwischen 1 und k; sie liegen also tatsächlich im angegebenen Bildbereich. g ist bijektiv und damit A endlich, denn: verschiedene Elemente aus A haben verschiedene Bilder (also besitzt jedes Bild auch höchstens ein Urbild): sind i und j zwei verschiedene Elemente aus A, etwa i < j, so ist g(i) = cA(1) + .... + cA(i) < cA(1) + .... + cA(i) + cA(i + 1) + .... + cA(j) = g(j), denn cA(j) = 1. jedes j Î{1,....,k} hat auch mindestens ein Urbild. Sei anderenfalls j das kleinste Element von {1,....,k}ohne Urbild; dann ist j >1 (denn 1 hat ein Urbild!), also ist j - 1 Î{1,....,k - 1} und j - 1 hat ein Urbild, etwa j - 1 = g(r). Wäre nun A Ì {1,....,r}, so hätte man k = cA(1) + .... + cA(m) = cA(1) + .... + cA(r) = j - 1 £ k - 1. Widerspruch. Also ist A\{1,....,r} ¹ Æ und für die Zahl s := min(A\{1,....,r}) Î A hat man g(s)  =   cA(1) + .... + cA(r) + cA(r + 1) + .... + cA(s)         =   cA(1) + .... + cA(r) + 1         =  g(r) + 1         =  j - 1 + 1  =  j. Also hat j doch ein Urbild! Zu 2.: Sei A eine nicht-endliche Teilmenge von N. Wir müssen zeigen: A ist abzählbar. Dazu setzen wir wieder den "Indikatorfunktionentrick" ein und definieren noch einmal eine Funktion g : A ® N  durch  g(i) := cA(1) + .... + cA(i) Genau wie in Teil 1 zeigt man: jedes j ÎN hat höchstens ein Urbild. g ist also bijektiv, wenn wir nachweisen können, daß jedes j ÎN auch mindestens ein Urbild hat. Auch hier gehen wir i.w. wie in Teil 1 vor: Zunächst hat 1 ein Urbild, denn da A nicht endlich ist, also insbesondere A ¹ Æ, existiert minA und g(minA) = 1. Sei jetzt angenommen, es gibt ein j ÎN ohne Urbild. O.E. sei j das kleinste Element dieser Art, dann ist j >1 und j - 1 ÎN besitzt ein Urbild, etwa j - 1 = g(r). Wäre nun A Ì {1,....,r}, so müßte nach Punkt 1 A endlich sein! Also ist wieder A\{1,....,r} ¹ Æ und min(A\{1,....,r}) ein Urbild zu j. Widerspruch.

Es ist nun ein Leichtes, sich von den natürlichen Zahlen zu lösen und die gerade bewiesenen Zusammenhänge auf beliebige Mengen zu übertragen:

Bemerkung: Ist M endlich, so ist jede Teilmenge von M endlich. Ist M abzählbar, so ist jede Teilmenge von M endlich oder abzählbar. Beweis: Es reicht das Übertragungsverfahren einmal zu demonstrieren. Wir machen dies für Punkt 1: 1 ist trivial falls M leer ist; sei daher o.E. M ¹ Æ. Da M endlich, gibt es ein n ÎN und eine Bijektion  f : {1,....,n} ® M. Ist nun A Ì M und A ¹ Æ, so ist nach dem gerade Bewiesenen B := {f -1(x) | x Î A} eine nicht-leere, endliche Teilmenge von {1,....,n}. Es gibt also ein k ÎN und eine Bijektion h : {1,....,k} ® B. Dann ist aber $f^{-1}\circ h$ eine Bijektion von {1,....,k} nach A.

Eine letzte allgemeine Aussage:

Bemerkung: Abzählbare Vereinigungen endlicher Mengen sind abzählbar. Präzise gefaßt lautet die Aussage: Für jedes i ÎN sei Ai eine endliche, nicht-leere Menge. Sind die Ai paarweise disjunkt, so ist A := ÈAi = {x| es gibt (genau) ein i mit  x Î Ai} abzählbar. Beweis: Zunächst gibt es nach Voraussetzung zu jedem i ÎN  ein ni ÎN  und eine Bijektion gi : {1,...,ni} ® Ai . Wir konstruieren nun eine Funktion  f : A ® N : Ist x Î A, also x Î Ai für genau ein i, so sei f(x) := n1 + .... + ni-1 + gi -1(x).  f ist umkehrbar; die Funktion  g : N ® A, gegeben durch   g(n) := gi*(n - (n1 + .... + ni*-1)) (Î Ai*) ist die Umkehrfunktion zu  f; mit i* sei dabei die Zahl max{i| n1 + .... + ni-1 < n}bezeichnet. (Hier ist auf die Konvention n1 + .... + n0 = 0 zu achten, so ist z.B. i* = 1, falls n = 1 ist!) Wir zeigen wieder:  f und g heben sich in ihrer Wirkung gegenseitig auf: Für n ÎN ist f(g(n)) = n1 + .... + ni*-1 + gi*-1(gi*(n - (n1 + .... + ni*-1))) = n1 + .... + ni*-1 + n - (n1 + .... + ni*-1) = n Für x Î A, etwa x Î Ai, beachte man zuvor: n1 + .... + ni-1 <  n1 + .... + ni-1 + gi -1(x) £ n1 + .... + ni, denn gi -1(x) Π{1,...,ni} (*) Um nun g(f(x)) = g(n1 + .... + ni-1 + gi -1(x)) zu ermitteln, muß zunächst man das zu n1 + .... + ni-1 + gi -1(x) gehörige i* kennen; nach der Vorüberlegung (*) ist dies aber gerade i selbst. Also ergibt sich weiter: g(f(x)) =  gi(n1 + .... + ni-1 + gi -1(x) - (n1 + .... + ni-1)) =  gi(gi -1(x)) =  x.

Mit dieser Bemerkung könnte man als Beispiel noch einmal die Abzählbarkeit von Z nachweisen:
Setzt man nämlich A₁ := {0}, A₂ := {-1,1}, A₃ := {-2,2},..., so sind alle A_i endlich, nicht-leer, paarweise disjunkt und ÈA_i = Z !

Wir setzen jetzt dieses Verfahren ein, um die Abzählbarkeit vonQ  sicherzustellen:

Bemerkung: Q  ist abzählbar. Beweis: Wir müssenQ  in abzählbar viele endliche Mengen zerlegen. Bei der Darstellung von Brüchen darf man o.E. annehmen, daß alle Nenner positiv sind und nur maximal gekürzte Bruchdarstellungen vorkommen, also: Q  =  { $\frac{n}{m}$ | nÎZ  Ù  m ÎN  Ù  n und m  sind teilerfremd}. Wenn wir für den Augenblick den Bruch $\frac{n}{m}$ als Zahlenpaar (n,m) ÎZ ´N schreiben, haben wir die Möglichkeit, ihn als Gitterpunkt der Zeichenebene zu sehen. So sind etwa die auf den roten Diagonalen liegenden Brüche durch die Paare (-4,1), (-3,2), (-2,3), (-1,4), (0,5), (1,4), (2,3), (3,2) und (4,1) gegeben. Addiert man nun bei diesen Paaren die Beträge der Koordinaten, also z.B. ½-4½ + ½1½, so erhält man in allen Fällen den Wert 5! (Die genannten neun Paare sind übrigens die einzigen, die auf diese Weise den Wert 5 liefern.) Für einen Bruch $x=\frac{n}{m}$ setzen wir jetzt  b(x) := ½n½ + ½m½. Da wir nur maximal gekürzte Darstellungen zulassen, gehört zu jeder rationalen Zahl x genau eine Zahl  b(x) ÎN. Außerdem haben nur endlich viele Zahlen x denselben Wert b(x). Die Mengen  Ai := {x ÎQ | b(x) = i }, i ÎN , sind daher endlich, nicht-leer und paarweise disjunkt. Ihre Vereinigung ist Q . Nach dem Satz über abzählbare Vereinigungen ist Q  also abzählbar. Die Zerlegungsmengen Ai enthalten offensichtlich genau diejenigen Brüche, die auf dem i-ten Diagonalenpaar liegen. Diese Art der Aufteilung heißt Cantor'sches Diagonalverfahren.

Die letzte unserer Zahlenmengen, die MengeR der reellen Zahlen gehört nicht mehr zur Klasse der abzählbaren Mengen:

Bemerkung: R  ist überabzählbar. Beweis: Es reicht zu zeigen, daß R  eine überabzählbare Teilmenge enthält. Wir betrachten dazu die Menge R := {0,x1x2..... ÎR | xi = 0  Ú  xi = 1}, also die Menge aller Dezimalzahlen zwischen 0 und 1, deren Nachkommastellen nur mit 0 oder 1 besetzt sind. Die Elemente von R stehen in einem direkten Verhältnis zu den Teilmengen von N, denn bezeichnet man für eine solche Teilmenge A Ì N mit xA diejenige Zahl 0,x1x2... Î R bei der xi = 1 ist, genau dann wenn i Î A (Also z.B. x{2,3,5} = 0,01101 oder xÆ = 0 oder xN = 0,111111....), so ist die Funktion f : P(N) ® R gegeben durch  f(A) := xA bijektiv. Jede Zahl 0,x1x2..... Î R nämlich besitzt genau ein Urbild, und zwar die Menge derjenigen i mit xi = 1. R ist damit nicht abzählbar, denn anderenfalls wäre auch die zu R gleichmächtige Menge P(N) abzählbar. Dies aber ist nach einem unserer Beispiele nicht wahr. Schließlich kann R auch nicht endlich sein, denn R enthält eine abzählbare, und somit unendliche Menge, etwa die Menge ÈRi, wobei Ri := {10-i} = {0,0...01}, i ÎN . Die Ri sind Einermengen, z.B.R1 = {0,1}, R2 = {0,01}, R3 = {0,001} usw.