Kapitel 1

Grundlagen

δoς μoι πoυ στω και κινησω την γην.

Gib mir einen Punkt, wo ich stehen kann, und ich werde die Erde aus den Angeln heben.

Archimedes von Syrakus (∼287–212 v.u.Z.), mathematisches Jahrtausendgenie und eines der ersten Opfer der Mathematik (”Noli perturbare circulos meos“).

Wir wollen in diesem Paragraphen einige Werkzeuge kennenlernen, die wir brauchen, um unsere Aussagen und Beweise so fassen zu können, daß sie den heutzutage üblichen wissenschaftlichen Standards genügen. Dabei geht es hier nur um ”Sprechweisen“ (Nomenklatur). Die Prinzipien des Schließens werden beileibe nicht erschöpfend dargestellt (das bleibt der Disziplin der mathematischen Logik überlassen und ist nichts für Anfänger!), die Probleme der Axiomatik der Mengenlehre werden nur angerissen.

Erst seit Mitte des vorigen Jahrhunderts bemühen sich die Mathematiker um eine exakte Grundlegung ihrer Wissenschaft (Boole, Frege, Hilbert, Russell, Gödel, …), wohl infolge der Erschütterungen, die die Entdeckung der Nichteuklidischen Geometrien nach sich zog. Seither hat die Mathematik auch ihren Charakter geändert. Aus einer Disziplin von Zahl und Raum wurde sie zur Theorie der Strukturen – zu einer Wissenschaft, die aus vorgegebenen Axiomen Folgerungen zieht.

Demgemäß wird heutzutage in mathematischen Vorlesungen der Stoff nach der axiomatischen Methode ( vgl. S. 12 ff ) präsentiert, wenn auch gewöhnlich nicht voll formalisiert. Ersteres fasziniert und verwirrt Anfänger bzw. -innen gleichermaßen. Daher sind einige Warnungen angebracht.

Das axiomatische Vorgehen erweckt den Eindruck, als ob jede mathematische Disziplin (z.B. die Lineare Algebra) eine Kette aus Definitionen und Sätzen sei und als ob die Mathematiker in ihren Schöpfungen weitestgehend ”frei“ seien. So gibt es die Meinung, daß die platonische Auffassung von Mathematik (wonach mathematische Gegebenheiten außerhalb der menschlichen Vorstellung existieren, also vom menschlichen Geist entdeckt werden und nicht von ihm erschaffen) durch die moderne Entwicklung obsolet geworden sei.

Wenn jedoch logisches Denken und mathematisches Schließen nichts anderes als unter dem Anpassungsdruck der Evolution erworbene Fähigkeiten der menschlichen Spezies sind, so löst sich der sonst so gerne unversöhnlich aufgebaute Gegensatz ”entdecken – schaffen“ (Platonismus – Nominalismus) auf und gleichzeitig löst sich das Rätsel, warum die vom Menschen ”geschaffene“ Mathematik sich so wundervoll zur Beschreibung der Welt eignet, warum Mathematik sich anwenden läßt.

Die immer wieder prinzipiell gestellte Frage nach der Anwendbarkeit moderner mathematischer Theorien erhält somit eine überraschend einfache Antwort: Der Selektionsdruck der Evolution hat der Spezies Mensch mit der Fähigkeit zu Logik und Mathematik offensichtlich ein sehr gut an die Realität angepaßtes Vermögen beschert, und mit dem Erschaffen mathematischer Realität erfolgt daher eben nichts anderes als das Wiederentdecken zugrundeliegender Realität.

Oft können wir den Realitätsbezug einer mathematischen Theorie erst relativ spät nach ihrer Ausformulierung erkennen (Die Geschichte zeigt uns viele interessante Beispiele: Nichteuklidische Geometrien, Gruppentheorie, Theorie der endlichen Körper, Tensorkalkül, Knotentheorie, Primzahltheorie). Die Beschäftigung mit Primzahlen zum Beispiel – insbesondere die Frage nach großen Primzahlen – galt lange Zeit als eine Disziplin für Sonderlinge, bis sie im letzten Viertel unseres Jahrhunderts große Relevanz erlangte: Abgesehen davon, daß man neue Generationen von Superrechnern gern auch insoweit testet, daß man den Rekord für die größte bekannte Primzahl zu brechen sucht^{1}, sind große Primzahlen heute in der Kryptologie für gewisse sehr sichere Verschlüsselungsverfahren wichtig – zur heutigen Zeit der Kommunikation in globalen Netzwerken von vitalem Interesse für die Wirtschaft.

Da es die Aufgabe der Informatiker ist, Prozesse des logischen Schließens, Algorithmen und Datenstrukturen auf Maschinen zu implementieren, ist für sie natürlich jegliche Art von Mathematik von Interesse. Dennoch gibt es einen Grundkanon dessen, was ein Naturwissenschaftler heutzutage an Mathematik kennengelernt haben sollte.

Was die Präsentation von Mathematik in Gestalt des Schemas ”Axiome, Definitionen, Theoreme, …“ angeht, so darf diese Darstellungsform nicht für das Ganze gehalten werden. Definieren heißt begrenzen, ausgrenzen, aussondern oder ”feststellen“ (letzteres durchaus in des Sinnes wörtlicher Bedeutung). Der Verstand setzt also – um einmal bei der platonischen Sichtweise zu bleiben – in der Welt mathematischer Sachverhalte Fixpunkte so, wie der Bergsteiger Eisen in den Fels schlägt. Die gesetzten Haltepunkte (Axiome, Definitionen, Theoreme, …) sind bis zu einem bestimmten Grade eine willkürliche Auswahl aus der Gesamtheit aller Möglichkeiten. Wo ich meine Eisen einschlage, ist in gewissem Sinne willkürlich, erfolgt aber angepaßt an die mathematische Topographie. Die Eindimensionalität der Zeit erweckt den Eindruck einer Kette. In Wirklichkeit entsteht ein (vieldimensionales) Netz von Fixpunkten (den Knotenpunkten) und Relationen (den Fäden des Netzes), das über das mathematische Substratum gelegt wird (relationaler Beziehungszusammenhang).

Das durch die axiomatische Methode gelieferte Bild ist also ein Teilbild der mathematischen Wirklichkeit, wie es durch das Netz mit seinen Knotenpunkten geliefert wird. Wir präsentieren einen historisch gewachsenen Kanon. Schließlich halten sich die Bergsteiger gewöhnlich auch an die von den Vorgängern eingeschlagenen Eisen. Wichtig ist es, möglichst viel in dem Netz herumzuwandern (das Bergsteigen zu üben!).

1Mersenne-Primzahl z.B. 2^{3021377} − 1.

Info http://www.utm.edu/research/primes/largest.html

1.1 Mathematische Logik

Die formale Logik befaßt sich mit Aussagen (das sind deklarierende, sinntragende Zeichenfolgen, die eine Bedeutung, den sog. Wahrheitswert, tragen) – mit ihrer Struktur und mit dem Umgang mit ihnen (Schlußregeln). In der zweiwertigen Logik kommt jeder Aussage entweder der Wahrheitswert W (wahr) oder F (falsch) zu (Kontradiktion, tertium non datur). Diese Auffassung entspricht auch der klassischen Logik, wie sie etwa im Organon des Aristoteles (384–322 v.u.Z.) oder – noch pointierter – in den Werken der megarisch-stoischen Schule niedergelegt ist.

Beispiele für Aussagen:

1. Jeder Vogel kann fliegen. F

2. 3^{2} + 4^{2} = 5^{2} W

3. 4^{2} + 5^{2} = 6^{2} F

4. Wenn n eine natürliche Zahl größer als 2 ist, so gibt es kein Tripel x, y, z ganzrationaler, von Null verschiedener Zahlen mit x^{n} + y^{n} = z^{n}. (Satz von Fermat-Wiles) ^{2} W

5. Jede von 2 verschiedene gerade natürliche Zahl ist Summe zweier Primzahlen. (Goldbachsche Vermutung) W?F?

Der Wahrheitswert der letzten Aussage ist nicht bekannt.^{3} Dennoch wird in der zweiwertigen Logik davon ausgegangen, daß ”im Grunde“ feststeht, ob die Aussage wahr oder falsch ist. Keine Aussagen sind z.B. Fragen oder Befehle.

Andrew Wiles

2

Diese (erst im Nachlaß gefundene) Aussage wurde von Pierre de Fer-

mat (1601-65) auf den Rand seines Diophant-Exemplars notiert mit

dem Zusatz, er habe einen wahrhaft wundervollen Beweis dafür ge-

funden, aber der Rand sei dafür zu klein. Es war eine Sensation, als

Andrew Wiles (⋆1953) diese sog. große Fermatsche Vermutung end-

lich 1994 beweisen konnte (publiziert in Ann. of Math. 41 (1995)).

Die Akademie der Wissenschaften zu Göttingen verwaltete für einen

für die Lösung 1906 ausgesetzten Preis von 100000 Goldmark (3 Mio.

DM nach heutiger Kaufkraft), der nach Abwertungen jetzt noch mit

75000 DM valutierte und am 27.06.1997 überreicht wurde.

3Bisher bewiesen: … als Summe von höchstens 67 Primzahlen darstellbar.

Es gibt auch Bestrebungen, mehrwertige Logiken zu entwickeln.^{4} Versuche, diese Logiken praktisch anzuwenden, waren bisher haupsächlich im Falle der Fuzzy-Logik erfolgreich. (In der Fuzzy-Logik arbeitet man statt mit zwei diskreten Wahrheitswerten W, F mit einem ganzen Kontinuum gewichteter Wahrheitswerte.)^{5}

Für den konkret forschenden Mathematiker oder Naturwissenschaftler ist aber die Zweckmäßigkeit das entscheidende Kriterium. Daher wird Mathematik immer noch nahezu ausschließlich nach der zweiwertigen Logik betrieben.

Der einfachste Part der formalen Logik ist der sogenannte Aussagenkalkül.^{6} Hier werden neben den Aussagen auch Aussagenvariable behandelt. Die Aussagenvariablen sind Statthalter für beliebige Aussagen, die an Stelle der Variablen eingesetzt werden können; so, wie in

x^{2} − y^{2} = (x + y)(x − y)

für die arithmetischen Variablen x, y jede beliebige reelle Zahl eingesetzt werden kann. Aussagenvariable und/oder Aussagen können durch Verwendung von Junktoren zu Ausdrücken (Formeln, Aussagenverbindungen) kombiniert werden, welche ihrerseits mittels Junktoren weiter verknüpft weden können. Die Junktoren^{7} (Verknüpfungszeichen) werden folgendermaßen über Wahrheitstafeln eingeführt:

Seien A, B Formeln.

4Erste Versuche 1920 von Lukasiewicz. Vgl. J.B. Rosser - A.R. Turquette: Many valued logics. Amsterdam 1952. Anwendung der dreiwertigen Logik auf die Quantenmechanik zuerst 1944 durch Hermann Reichenbach, der die in der Quantentheorie auftretende Unbestimmtheit durch den Wahrheitswert ”unbestimmt“ zu beschreiben suchte. Jedoch scheint das nicht hinreichend allgemein, da die Wahrscheinlichkeitsrechnungen der Quantentheorie nicht zu 3 diskreten Wahrheitswerten passen. Wiederum vertrat U. Blau die Meinung, daß nur eine dreiwertige Logik unserem intuitiven Denken gerecht werden kann (Papiere zur Linguistik 4, 1973: Dreiwertige Sprachanalyse und Logik, 1974).

5Jedoch nutzt z.B. das Computeralgebra-System Maple die dreiwertige Logik mit dem dritten Wahrheitswert FAIL, der zurückgegeben wird, wenn eine Prozedur das Problem nicht vollständig lösen kann.

6Das Wort Kalkül rührt von ”calculi“ her, der lat. Bezeichnung für Rechensteinchen.

Ein Kalkül erfordert, daß die Zeichenfolgen eindeutig erkannt und gemäß den Regeln des Kalküls mechanisch verarbeitet werden können.

7Einige Junktoren treten in Programmiersprachen als Operatoren auf. Z.B. in C: ¬ als !, ∧ als &&, ∨ als ||.

Bezeichnung  Zeichen  Wahrheitstafel  Sprechweise

Negation ¬A \begin{matrix}A & ¬A \\ W & F \\ F & W \end{matrix} Non A; A gilt nicht; es ist nicht wahr, daß A gilt.

schwache Disjunktion; einschließendes (schwaches) Oder

A ∨ B \begin{matrix}A & B & A ∨ B \\ W & W & W \\ W & F & W \\ F & W & W \\ F & F & F \end{matrix} A gilt oder B gilt

oder beides gilt; A oder B oder beides.

Kurzform: \begin{matrix}∨ & W & F \\ W & W & W \\ F & W & F \end{matrix}

strenge Disjunktion; ausschließendes Oder

A ⊔ B \begin{matrix}⊔ & W & F \\ W & F & W \\ F & W & F \end{matrix} Entweder A oder

B.

Konjunktion A ∧ B \begin{matrix}∧ & W & F \\ W & W & F \\ F & F & F \end{matrix} A gilt und B gilt; A und B.

logische Äquivalenz A ↔ B \begin{matrix}↔ & W & F \\ W & W & F \\ F & F & W \end{matrix} Mit A gilt auch B und umgekehrt; genau wenn A, so B; A dann und nur dann, wenn B; A ist hinreichend und notwendig für B.

Implikation A → B \begin{matrix}→ & W & F \\ W & W & F \\ F & W & W \end{matrix} Wenn A, so B; mit A ist auch B wahr; A ist hinreichend für B; B ist notwendig für A; A höchstens dann, wenn B.

Achtung: Bei A → B braucht B nicht aus A ableitbar zu sein, wenn dies auch die oft benutzte Sprechweise ”Aus A folgt B“ zu suggerieren scheint!

Die Implikation ist auch sehr zu unterscheiden vom Kausalzusammenhang. Betrachten wir das Modell einer Klingel, die Aussagen A: ”Es fließt Strom.“, B: ”Der Magnet unterbricht durch Anziehung der Metallzunge den Stromkreis.“ sowie die durch das Modell offensichtlich als richtig erwiesenen Aussagen:

1. Wenn Strom fließt, so unterbricht der Magnet durch Anziehung der Metallzunge den Stromkreis.

2. Wenn der Magnet durch Anziehung der Metallzunge den Stromkreis unterbricht, so fließt kein Strom.

Also würde gelten A → B und B → ¬A und somit (siehe unten modus Barbara) A → ¬A. Demnach wäre die Aussage falsch, im Widerspruch zur Realität.

Sie haben den Fehler natürlich sofort bemerkt! Es handelt sich hier um Ursache und Wirkung. Diese beziehen sich auf Vorgänge, die in der Zeit ablaufen. Das ”wenn … so“ bedeutet also keine Gleichzeitigkeit wie bei der logischen Implikation.

In der Mathematik verwenden wir die Junktoren präzise so, wie oben definiert. Es gibt sicherlich Unterschiede zwischen dem Sprachgebrauch im täglichen Leben und dem in der mathematischen Logik. Einige Beispiele:

1. Jemand erbittet von seinem Freund, welcher jede Woche an genau einem Nachmittag in der Werkstatt seines Vaters mithilft, als Freundschaftsdienst die dringend nötige Behebung eines Defekts am Auto und fragt ihn: ”Wann bist Du wieder in der Werkstatt?“ Antwort: ”Ich bin heute oder morgen oder übermorgen dort.“ Wird diese Antwort im Alltagsleben als wahr angesehen werden, wenn der Antwortende im Augenblick der Antwort schon genau weiß, daß er zu keinem anderen Zeitpunkt als morgen in der Werkstatt sein wird?

2. Eine Erbengemeinschaft gab der Öffentlichkeit gegenüber folgende Stellungnahme ab:

”Als Kinder wie als Erben von Franz Josef Strauß wissen wir, daß es solche Geschäfte mit solchen Provisionen zu keiner Zeit und nirgendwo mit und ohne Schalck-Golodkowski gegeben hat.“ Zeugt diese Verlautbarung nun von logischem Unvermögen oder von bewußtem Mißbrauch der Sprache zum Zwecke der Verschleierung des Sinns der Aussage?

Ausriß aus Der Spiegel 34/1991, p.19

3. Es fällt ohne streng formale Betrachtungsweise schwer, die Aussage ”Wenn der Imperator nicht sterblich ist, so ist der Imperator sterblich.“ als wahr anzusehen.

Übrigens stand und steht die Definition der Implikation über die von uns abgedruckte Wahrheitstafel seit eh und je im Kreuzfeuer der Kritik von Philosophen und Logikern. Anlaß zur Kritik bildete unter anderem auch die Zeitabhängigkeit des Wahrheitswertes der folgenden Aussage: ”Wenn Daniela lustig ist, so ist sie nicht lustig.“ (Zu allen Zeiten, zu denen Daniela lustig ist, ist die Aussage falsch. Zu den Zeiten, zu denen Daniela nicht lustig ist, ist sie wahr!) Möglicherweise erlaubt es unser Implikationsbegriff auch nicht, gewisse Probleme adäquat zu behandeln. In einer zweiwertigen Logik muß die Implikation jedoch notwendig so definiert werden, denn von den 2^{4} kombinatorischen Möglichkeiten für die Wahrheitstafeln kommt unsere Wahl dem, was intuitiv als Implikation angesehen wird, am nächsten.

Eine Formel, die stets den Wahrheitswert W hat, heißt eine Tautologie. Durch Einsetzen aller möglichen Wahrheitswerte für A, B, C sind die folgenden Ausdrücke leicht als Tautologien zu verifizieren:

(Dabei gilt folgende Rangfolge der Junktoren: ¬ bindet stärker als ∨, ∧, und letztere binden stärker als →, ↔. Von dieser Konvention abweichende Bindungen werden durch Klammern realisiert.)

1. A ∨ ¬A (Tertium non datur. Schlechter Name, der erst mit der folgenden Tautologie Sinn macht.)

2. ¬(A ∧ ¬A) (Gesetz vom Widerspruch, Kontradiktion)

3. (A → B) ∧ (B → C) → (A → C) (Syllogismus, Modus Barbara)

4. A ↔ ¬(¬A) (Gesetz der doppelten Negation)

5. (A → B) ↔ (¬B → ¬A) (Gesetz der Kontraposition)

6. A ∧ (A → B) → B (Modus ponendo ponens)

7. A ∧ ¬A → B (Ex falso quodlibet, Duns-Scotus-Regel)

8. (A → A ∧ ¬A) → ¬A (Reductio ad absurdum)

9. ¬(A ∨ B) ↔ ¬A ∧ ¬B (De Morgansche Gesetze)

10. ¬(A ∧ B) ↔ ¬A ∨ ¬B

Übung: Welche der folgenden drei Formeln sind Tautologien?

A ∧ (B ∨ C) ↔ (A ∧ B) ∨ (A ∧ C) ,
(¬B → A ∧ ¬A) → B ,
(A ∧ ¬B → C ∧ ¬C) ↔ (A → B) .

Die beiden folgenden Tautologien zeigen, daß wir eigentlich nur die beiden Junktoren ¬ und ∨ benötigen:

(A → B) ↔ ¬A ∨ B ,
A ∧ B ↔ ¬(¬A ∨ ¬B) .

Bemerkung: Definitionen erfolgen mit Hilfe der logischen Äquivalenz nach dem Schema Definiendium (Das neu zu Definierende) :↔ Definiens (Die definierende Aussage). Der Doppelpunkt wird auf die Seite des Definiendums geschrieben ( Beispiel: Definitionen 1.1, S.17 ). Steht jedoch ausdrücklich ”Definition:“ davor, so wird auch öfter salopper ”… heißt …, wenn …“ statt ”… heißt …, genau wenn …“ formuliert.

Der Aussagenkalkül ist noch sehr grob; denn er regelt nur die Verknüpfung von Aussagen zu Formeln. Er befaßt sich aber überhaupt nicht mit der Feinstruktur der Aussagen, wie es sogar schon in der Aristotelischen Logik zu finden ist. Typische ”Aussagen“ sind doch: ”Alle Menschen sind sterblich.“, ”7 ist eine Primzahl.“, ”π < 5“, aber auch ”Für alle x ∈ ℝ, x > 0, existiert y ∈ ℝ mit x = y^{2} “.

Daher wird der Aussagenkalkül zum sog. (engeren) Prädikatenkalkül erweitert, der den Umgang mit speziellen sprachlichen Gebilden regelt.

Aussageformen oder Aussagefunktionen sind Gebilde vom Typ ”x ist ein Rabe“, kurz geschrieben als R(x), ”x ist schwarz“, kurz geschrieben als S(x). (Das sind keine Aussagen, da es keinen Sinn macht, von Wahr oder Falsch zu reden.) x heißt eine Individualvariable, R heißt eine Prädikatsvariable.

Zu den Verknüpfungen des Aussagenkalküls kommen noch zwei Quantoren hinzu: ⋁ und ⋀ (oft auch als ∃

bzw. ∀ geschrieben). ⋁_{x} R(x) ist eine

Schreibweise für ”Es gibt ein x mit dem Prädikat R“, also für ”Es gibt ein x so, daß gilt: x ist ein Rabe.“ ⋁ (bzw. ∃) heißt Partikularisator. Analog wird der Generalisator ⋀ (bzw. ∀) ”für alle “ gebraucht.

⋀_{x}[R(x) → S(x)] ???

Drei wichtige gültige Formeln des Prädikatenkalküls sind:

¬⋀_{x}P (x) ↔ ⋁_{x}¬P (x) ,

¬⋁_{x}P (x) ↔ ⋀_{x}¬P (x) ,

⋁_{x} ⋀_{y}P (x, y) → ⋀_{y} ⋁_{x}P (x, y) .

Übung: Machen Sie sich die Formeln anhand von Beispielen klar, insbesondere auch, daß die letzte Formel keine Äquivalenz ist (Wichtig später für das Verständnis des Unterschiedes zwischen Konvergenz und gleichmäßiger Konvergenz).

Vielbenutzte Quantoren der Sprache, wie ”für fast alle“, ”für die meisten“, …, werden hingegen in der klassischen mathematischen Logik nicht verwandt. Die bei den Quantoren stehenden Individualvariablen heißen gebundene Variablen, während die anderen Individualvariablen freie Variablen heißen.^{8} Prädikate können natürlich mehrere Individualvariablen aufweisen, geschrieben dann als P (x_{1}, x_{2}, …, x_{n}). Beispiel: K(x, y) für ”x ist kleiner als y“.

8Der engere Prädikatenkalkül wird oft erweitert, indem auch gebundene Prädikatsvariablen zugelassen werden, z.B. zwecks Definition der Gleichheit a = b :↔ ⋀_{x}F (a) = F (b)

(Gleichheit im Sinne universeller Vertretbarkeit). Jedoch hat Bernays eine für die Zwecke der Mathematiker hinreichende axiomatische Einführung der Zermelo-Fraenkelschen Mengenlehre auf der Basis des engeren Prädikatenkalküls mit ι-Symbol gegeben.

Ein Problem des Prädikatenkalküls liegt darin, daß ein entsprechendes Universum von Individuen vorausgesetzt wird, auf die sich die Aussagenvariablen beziehen. Wenn das Universum aus endlich vielen Individuen besteht, geht der Prädikatenkalkül nicht über die Aussagenlogik hinaus.

1.2 Die axiomatische Methode

Eine formale mathematische Theorie ist ein geeigneter logischer Kalkül (meist der engere Prädikatenkalkül mit dem Begriff der Identität (d.i. Gleichheit im Sinne universeller Vertretbarkeit), eventuell noch mit dem ι-Symbol^{9}), der durch spezielle Symbole für besondere Individuen, Prädikate oder Aussageformen erweitert ist^{10}, zusammen mit sogenannten Axiomen, in denen diese Symbole vorkommen. (Vgl. G.T. Kneebone: Mathematical Logic and the foundations of mathematics. London 1963.) Ferner muß festgelegt werden, welche Formeln einschlägig (wohlgebildet) sind und welche Ableitungsregeln angewendet werden dürfen.

Seien P_{1}, P_{2}, …, P_{n} einschlägige Aussagen der formalen Theorie, die sog. Prämissen oder Voraussetzungen, und sei B eine zu beweisende Behauptung.

(i) Ein formaler (direkter) Beweis für das Theorem:

”Mit P_{1}, P_{2}, …, P_{n} gilt auch B“ besteht aus einer Folge (gewöhnlich untereinander geschriebener) einschlägiger Formeln F_{1}, F_{2}, …, F_{k} mit F_{k} = B, wobei jede Formel F_{i} eine Prämisse oder ein Axiom ist oder aus vorhergehenden Formeln F_{j} (j < i) durch Anwendung einer der Ableitungsregeln entstanden ist.

(ii) Ein formaler indirekter Beweis für den obigen Satz beginnt mit n Zeilen mit den Prämissen P_{1}, P_{2}, …, P_{n}. In der (n + 1)-ten Zeile steht ¬B. Dann folgen weitere Beweiszeilen, die wie bei einem formalen direkten Beweis, also eventuell unter Verwendung vorheriger Zeilen, entstanden sind. Sobald einmal zwei Zeilen mit den Formeln Z und ¬Z aufgetreten sind (Widerspruch), ist der indirekte Beweis vollendet (¬B kann nicht wahr sein).

9Wenn eine Eigenschaft E durch ein Prädikat P (x) dargestellt wird, so bedeutet ι_{x}P (x)

”das Individuum mit der Eigenschaft E“

10Im Axiomensystem der Mengenlehre sind zum Beispiel ∈ und { : } solche Symbole.

Beispiel (für einen indirekten Beweis): Behauptung: \sqrt{2} ist nicht rational (Aussage B). Annahme: \sqrt{2} = \frac{a}{b} (a, b ganzrational; Bruch sei durchgekürzt). Dann ist a^{2} = 2b^{2}, a also gerade, d.h. a = 2c. Mithin ist 4c^{2} = 2b^{2}, also auch b gerade. Also ist \frac{a}{b} nicht durchgekürzt. Widerspruch! □

Als Beispiel für eine formale mathematische Theorie führen wir 4 Axiome und 2 Ableitungsregeln ein, mit denen Hilbert und Ackermann den Aussagenkalkül formalisierten.

Axiome:

(i) ¬(A ∨ A) ∨ A

(ii) ¬A ∨ (A ∨ B)

(iii) ¬(A ∨ B) ∨ (B ∨ A)

(iv) ¬(¬A ∨ B) ∨ (¬(C ∨ A) ∨ (C ∨ B))

Ableitungsregeln:

(I) Von zwei Formeln F_{1} und F_{1} → F_{2} darf zur Formel F_{2} übergegangen werden, symbolisch geschrieben: F_{1} \underline{F_{1} → F_{2}} F_{2} (Modus ponendo ponens)

(II) Für jede Variable, die in einer gegebenen Formel auftritt, ist folgende Substitution zulässig: X wird überall, wo es auftritt, durch eine beliebige, aber festgewählte, einschlägige Formel F ersetzt, geschrieben: F |X. (Substitutionsregel)

Zunächst ist es sicher nützlich, die Implikation mittels der Definition (A → B) :↔ ¬A ∨ B einzuführen und die Formeln der Axiome in einer ”anschaulicheren“ Version zu schreiben: (i) A ∨ A → A, (ii) A → A ∨ B, (iii) A ∨ B → B ∨ A, (iv) (A → B) → (C ∨ A → C ∨ B). Die Substitution ¬C|C in (iv) zeigt die Gültigkeit von (A → B) → ((C → A) → (C → B)) und (I) zweimal hierauf angewendet liefert die so formal deduzierte Ableitungsregel C → A \underline{A → B} C → B (Modus Barbara)

Als Beispiele für formale Beweise mögen die Deduktion des ”tertium non datur“ und des Satzes von der doppelten Negation dienen:

Satz: A ∨ ¬A Beweis:

1. A → A ∨ A (ii) und A|B 2. A ∨ A → A (i)

3. A → A Modus Barbara 4. ¬A ∨ A Definition von → 5. ¬A ∨ A → A ∨ ¬A (iii) und (II)

6. A ∨ ¬A (I) bezügl. 4. und 5. Satz: A ↔ ¬¬A

Beweis:

1. Ann.: ¬((A → ¬¬A) ∧ (¬¬A → A))

2. ¬¬(¬(A → ¬¬A) ∨ ¬(¬¬A → A)) (Definition von ∧)

3. A ∨ ¬A voriger Satz 4. ¬A ∨ ¬¬A ¬A|A in voriger Zeile 5. A → ¬¬A Definition von → 6. ¬A → ¬¬¬A ¬A|A in voriger Zeile 7. (A ∨ ¬A) → (A ∨ ¬¬¬A ¬A|A, ¬¬¬A|B, A|C in (iv) und (I)

8. A ∨ ¬¬¬A (I)

9. ¬¬¬A ∨ A (iii) mit Substitution und (I)

10. ¬¬A → A Definition von → 11. ¬(A → ¬¬A) ∨ ¬(¬¬A → A) (I) bezogen auf 2. Zeile

und letzte Zeile mit entsprechender Substitution

12. (A → ¬¬A) → ¬(¬¬A → A) Definition von → 13. ¬(¬¬A → A) (I)

14. Widerspruch zur Aussage 3 Zeilen höher! □

Während die Beweisführung im ersten Satz voll formalisiert ist, sind beim Beweis des zweiten Satzes für die Etablierung einer neuen Zeile bisweilen mehrere Beweisschritte zusammengefaßt. Formale Beweise zu führen ist schrecklich umständlich und mühsam, auch werden sie für unseren menschlichen Verstand eher undurchsichtig. Die Situation erinnert an die Unterschiede, die zwischen der korrekten Beschreibung eines Algorithmus in freier Sprache (erster Schritt beim Programmieren) und dem vollständigen Quell-Code eines Computerprogramms bestehen. Bei formalen Beweisen muß im Prinzip ein Computer prüfen können, ob die Beweise richtig sind. Die praktizierenden Mathematiker begnügen sich mit einer teilweisen Formalisierung – weit weniger als in unserem zweiten Beispiel. Es wird zwar gefordert, daß die mathematische Theorie voll formalisierbar ist, um die Verwendung der Anschauung und die darin liegenden Gefahren auszuschalten, jedoch werden meistens die Ableitungsregeln nicht vollständig formuliert und auch unbewußt angewandt.

Der Stand der Dinge auf dem Gebiet der Computerbeweise ist folgender: Zwar können Computer aus den Prämissen mit Hilfe der Ableitungsregeln neue gültige Formeln in Hülle und Fülle produzieren, aber zu der behaupteten Formel zu gelangen ist nicht so einfach, da Computer ja keine Intuition besitzen. Jedoch ist es dem Computerprogramm EQP (equational power) von Mc Cune in Argonne (Illinois, USA) 1997 gelungen zu beweisen, daß eine Menge, auf der folgende Axiome für die beiden Verknüpfungen ∨ und ¬ gelten

(i) A ∨ B ↔ B ∨ A ,

(ii) (A ∨ B) ∨ C ↔ A ∨ (B ∨ C) ,

(iii) ¬(¬(A ∨ B) ∨ ¬(A ∨ ¬B)) ↔ A (sog. Robbins-Äquivalenz).

bereits eine Boolesche Algebra ist, ein Beweis, den die Mathematiker seit 60 Jahren vergeblich zu führen suchten.^{11}

Die moderne axiomatische Methode mit ihrem Verzicht auf Anschauung gab den MathematikerINNEn sehr viel Bewegungsfreiheit. Es geht nicht um die Frage, ob die Axiome selbst wahr sind, sondern es geht um die Ableitung von Sätzen aus den Axiomen. So ist auch der Ausspruch von Bertrand Russell zu verstehen: ”Die reine Mathematik ist jene Disziplin, bei der man weder weiß, worüber man spricht, noch ob das, was man sagt, wahr ist.“ Da unser Text hier für Menschen geschrieben ist, verzichten wir natürlich auf eine vollständig formalisierte Darstellung, eingedenk der Worte von A. Tarski: ”Was eine (ergänze: voll formalisierte) Darstellung an Strenge und methodologischer Korrektheit gewinnt, verliert sie an Faßlichkeit und Durchsichtigkeit“. Es ist ”nicht vernünftig zu fordern, daß die Beweise in einem gewöhnlichen Lehrbuch in vollständiger Gestalt angegeben werden“.

11Der EQP-Beweis, den die Maschine in 8 Tagen schaffte, ist für Menschen schwierig nachvollziehbar, da viele unintuitive, aber sehr komplexe Substitutionen durchgeführt werden. Informationen unter http://www.mcs.anl.gov/home/mccune/ar/robbins/.

Ein Preprint des Mc-Cune-Papiers ist unter ftp://info.mcs.anl.gov/pub/Otter/wwwmisc/robbins-jar-final.ps.gz erhältlich.

Der berühmte ”weiße Rabe “(corvus albus) kommt in den antiken Logik-Lehrbüchern oft vor. Hier aus Aristoteles, Anal.

Prior. IV, 16

1.3 Mengen, Relationen, Abbildungen

Die Objekte der Mengenlehre heißen Klassen. Es wird ferner mit einer Elementbeziehung ∈ gearbeitet. Wenn a, A Klassen sind, so sagen wir im Falle der Schreibweise a ∈ A ”a ist Element von A“ oder ”a ist in A“ oder ”a gehört zu A“. Klasse und Elementbeziehung bleiben unerklärte Bausteine des Axiomensystems der Mengenlehre. In diesem Abschnitt bedeuten A, B, C, …, a, b, c, … stets Bezeichnungen für Klassen. Wir treffen die Übereinkunft, daß kleine Buchstaben ausschließlich für Elemente reserviert seien.

Bei der Entwicklung der Mengenlehre stellte sich bald heraus, daß die Cantorsche Definition ”Eine Menge ist die Zusammenfassung von wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens zu einem Ganzen“ leider nicht brauchbar ist. Denn diese Definition führte in verschiedene Antinomien, zum Beispiel in die Russellsche Antinomie:

Sei M die ”Menge“ (im Cantorschen Sinne) aller Mengen, die sich nicht selbst als Element enthalten. Kurzes Nachdenken über die Frage, ob dann M sich selbst als Element enthält, führt zu der Erkenntnis, daß sowohl M ∈ M als auch ¬(M ∈ M) gelten muß, was unmöglich sein kann.

B. Russell (1872 - 1970)

Also mußte der Cantorsche Mengenbegriff aufgegeben werden. Heutzutage werden Mengen als spezielle Klassen definiert ( vgl. Def. 1.6 ].

1.1 Definitionen :

A = B :↔ ⋀_{x}(x ∈ A ↔ x ∈ B)

A ⊂ B :↔ ⋀_{x}(x ∈ A → x ∈ B)

A heißt im letzteren Fall eine Teilklasse von B.

1.2 Extensionalitätsaxiom : x = y ∧ x ∈ A → y ∈ A

1.3 Bemerkungen : Es gelten

(i) A = A (Reflexivität der Gleichheit)

(ii) A = B → B = A (Symmetrie der Gleichheit)

(iii) A = B ∧ B = C → A = C (Transitivität der Gleichheit)

(iv) A ⊂ B ∧ B ⊂ A → A = B

(v) A ⊂ B ∧ B ⊂ C → A ⊂ C

Beweis: Definitionen 1.1 und Extensionalitätsaxiom 1.2

1.4 Komprehensionsaxiom : Sei P (x) eine Aussageform, die vollständig durch ∈, ∨, ¬, ⋁, ⋀, Klammern und Variable ausgedrückt werden kann. Dann existiert eine Klasse, die aus allen Elementen x besteht, für die P (x) gilt, geschrieben: {x : P (x)}.

Warum werden in 1.4 nur Elemente zugelassen? Um nicht in Antinomien zu geraten; denn {A : ¬(A ∈ A)} wäre genau die Bildung, die zur Russellschen Antinomie führt. Wohl aber ist die Bildung {x : ¬(x ∈ x)} zulässig!

1.5 Satz : Die Klasse U := {x : ¬(x ∈ x)} ist nicht Element einer Klasse. Beweis: Indirekte Annahme: U ist Element einer Klasse. Es ist entweder U ∈ U oder ¬(U ∈ U). Wenn U ∈ U, so ist nach Definition von U aber ¬(U ∈ U), und wenn ¬(U ∈ U) gilt, so ist, da U als Element angenommen ist, nach Definition gerade U ∈ U. In jedem Fall ergibt sich also ein Widerspruch. (Wir haben uns also praktisch die Argumentation der Russellschen Antinomie für einen Widerspruchsbeweis von Satz 1.5 zunutze gemacht.)

1.6 Definitionen : Eine Klasse, die Element einer Klasse ist, heißt eine Menge. Eine Klasse, die nicht Menge ist, heißt eine eigentliche Klasse, echte Klasse oder Unmenge.

Nach Satz 1.5 ist {x : ¬(x ∈ x)} keine Menge. Also gibt es echte Klassen. Aber gibt es Mengen? Das wird sichergestellt durch:

1.7 Axiom über die leere Menge : Die leere Klasse Ø := {x : x ≠ x} ist eine Menge. Es gilt Ø ⊂ A für alle Klassen A; denn die Aussage x ∈ Ø → x ∈ A ist wahr für jedes x.

1.8 Axiom der Paarung : Wenn a, b Mengen sind, so ist {a, b} := {x : x = a ∨ x = b} eine Menge.

Wenn a eine Menge ist, so ist auch {a} := {x : x = a} eine Menge; denn es ist offensichtlich {a} = {a, a}, und letzteres ist nach 1.8 eine Menge. Wegen {a} = {a, a} kommen wir überein, gleiche Elemente zwischen geschweiften Klammern jeweils nur einmal aufzuführen.

1.9 Definitionen : Seien A, B Klassen.

1) A ∪ B := {x : x ∈ A ∨ x ∈ B} heißt die Vereinigung von A und B.

2) A ∩ B := {x : x ∈ A ∧ x ∈ B} heißt der Durchschnitt von A und B.

3) A \ B := {x : x ∈ A ∧ ¬(x ∈ B)} heißt die Differenz von A und B.

4) Ist B ⊂ A, so heißt A \ B das Komplement von B in A, geschrieben C_{A}B.

5) A, B heißen disjunkt oder zueinander fremd, wenn A ∩ B = Ø gilt.

Analog werden Vereinigung und Durchschnitt über eine Klasse M von Men-

gen definiert: ⋃_{A∈M}A := {x : ⋁_{A∈M}x ∈ A}; ⋂_{A∈M}A := {x : ⋀_{A∈M}x ∈ A} .

Für die Begriffe von 1.9 können nun zahlreiche Regeln abgeleitet werden. Zwei oft verwendete sind die Distributivgesetze:

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) ,
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) .

Letzteres folgt zum Beispiel nach Def 1.1 und 1.9 unter Verwendung der 1. Tautologie auf Seite 8.. . .

1.10 Definitionen : (a, b) := {{a}, {a, b}} heißt ein geordnetes Paar. A × B := {(a, b) : a ∈ A ∧ b ∈ B} heißt das Cartesische Produkt der Klassen A und B. Ist A = Ø oder B = Ø, so definieren wir A × B = Ø. Allgemein: M_{1} × M_{2} × … × M_{n} =: X_{j=1}^{n}M_{j} (=: M^{n}, wenn M_{1} = … = M_{n} = M).

Beispiel: ℝ^{2} = ℝ × ℝ kann als Menge der Punkte der euklidischen Ebene aufgefaßt werden.

Zusammen mit weiteren Axiomen läßt sich so die Mengenlehre axiomatisch aufbauen. Wer sich dafür interessiert, ziehe dazu Literatur zu Rate. Ein wichtiges Buch auf diesem Feld ist A.A. Fraenkel: Abstract set theory, Amsterdam 1953.

Wahrscheinlich reichen für den Tagesgebrauch in der Mathematik zusätzlich die folgenden Axiome aus:

1) Axiom der Teilmenge: Jede Teilklasse einer Menge ist eine Menge.

2) Axiom der Vereinigung: Ist M eine Menge von Mengen, so ist ⋃_{A∈M}A

eine Menge.

3) Axiom der Potenzmenge: Zu jeder gegebenen Menge A existiert die Menge P(A) aller Teilmengen von A, die sogenannte Potenzmenge.

4) Unendlichkeitsaxiom: Es existiert eine Nachfolger-Menge, d.h. eine Menge, die mit jedem Element A auch ihren Nachfolger A^{+} := A ∪ {A} enthält. Dieses Axiom sichert die Existenz der Menge ℕ der natürlichen Zahlen.

5) Auswahlaxiom: Darüber jedoch später Näheres.

Wir arbeiten im Folgenden nur mit Mengen! Uns interessiert also der Unterschied zwischen Mengen und Klassen nicht weiter!

Wir wollen nun noch ausführen, wie die wichtigen Begriffe der Abbildung und der Relation mit Hilfe der Mengentheorie eingeführt werden können:

1.11 Definitionen : Eine Abbildung oder Funktion f von A nach B ist ein geordnetes Tripel (f, A, B), wobei A, B Klassen sind und f ⊂ A × B ist mit folgenden Eigenschaften

(i) ⋀_{x∈A} ⋁_{y∈B}(x, y) ∈ f (Existenz des Bildes)

(ii) (x, y) ∈ f ∧ (x, z) ∈ f → y = z (Eindeutigkeit des Bildes)

1) x heißt ein Urbild von y, y heißt das Bild von x. Es ist üblich, f : A → B statt (f, A, B) und y = f(x) bzw. f : x ↦ y statt (x, y) ∈ f zu schreiben. Wir sagen auch: f bildet x auf y ab.

2) A heißt der Definitionsbereich von f.

3) Bild f := f(A) := ⋃_{x∈A}f(x) heißt der Bildbereich oder der Wertevorrat

von f.

4) Sei M ⊂ B. f^{−1}(M) := {x : x ∈ A ∧ f(x) ∈ M} heißt das (volle) Urbild von M. f^{−1}(y) heißt Faser.

5) f heißt injektiv, wenn ⋀_{x,y∈A}(f(x) = f(y) → x = y).

6) f heißt surjektiv, wenn ⋀_{y∈B} ⋁_{x∈A}f(x) = y.

7) f heißt bijektiv, wenn f injektiv und surjektiv ist.

8) Die Komposition der Abbildungen f : A → B und g : B → C ist die durch g ∘ f(x) := g(f(x)) definierte Abbildung g ∘ f : A → C.

9) Die durch id_{A}(x) := x definierte Abbildung id_{A} : A → A heißt die (auf A) identische Abbildung.

10) f : A → B, g : A → B heißen gleich, wenn f(x) = g(x) für alle x aus A gilt.

Slogans: Injektivität bedeutet Eindeutigkeit des Urbildes! Surjektivität ist Abbildung ”auf“, bedeutet also Existenz des Urbildes!

Keine Abbildung ( Bild nicht eindeutig )

Keine inj. Abb. ( Urbild nicht eindeutig )

1.12 Bemerkungen :

(i) Die Komposition von Abbildungen ähnelt der Multiplikation (reeller Zahlen) und wird daher entsprechend geschrieben: g ∘ f – nur wird hier von rechts nach links gelesen; denn zuerst wird f und dann g ausgeführt. Die Bezeichnung ”Linksinverses“ rührt ebenfalls von der Multiplikation her. Es gilt doch: ⋀_{a∈ℝ\\{0\}} ⋁_{b∈ℝ}ba = 1, nämlich b = \frac{1}{a} = a^{−1}, also ”b ist

Linksinverses zu a“.

(ii) Eine Abbildung f : A → B schreiben wir auch als A ⟶_{f} B. Seien

nun f, g, h Abbildungen mit A ⟶_{f} B ⟶_{g} C ⟶_{h} D. Dann gilt:

(f ∘ g) ∘ h = f ∘ (g ∘ h). Beweis: Es gilt h ∘ (g ∘ f)(x) = h((g ∘ f)(x)) = h(g(f(x))) und ebenso (h ∘ g) ∘ f(x) = (h ∘ g)(f(x)) = h(g(f(x))) für alle x ∈ A, also sind beide linke Seiten gleich.

(iii) Seien f : A → B und g : B → C surjektive (injektive bzw. bijektive) Abbildungen. Dann ist g ∘ f surjektiv (injektiv bzw. bijektiv). Beweis als Übung.

1.13 Satz : Sei f : A → B eine Abbildung. Dann gelten:

(i) f ist genau dann injektiv, wenn ein g : B → A existiert mit g ∘f = id_{A}. g heißt dann ein Linksinverses zu f.

(ii) f ist genau dann surjektiv, wenn ein h : B → A existiert mit f ∘h = id_{B}. h heißt dann ein Rechtsinverses zu f.

(iii) f ist genau dann bijektiv, wenn es genau ein g : B → A gibt mit g ∘ f = id_{A} und f ∘ g = id_{B}. Dieses eindeutig bestimmte g heißt dann die Umkehrabbildung oder die inverse Abbildung zu f, oft auch mit f^{−1} bezeichnet.

Achtung: Die inverse Abbildung f^{−1} nicht mit der Faser f^{−1}(y) verwechseln! Beweis:

I) Sei die rechte Seite der Behauptung (i) gültig. Wenn f(x) = f(y) ist, so ist g ∘ f(x) = g ∘ f(y), also id_{A}(x) = id_{A}(y), also x = y, also f injektiv. Sei nun f injektiv. Dann gibt es zu jedem b ∈ f(A) genau ein a_{b} ∈ A mit f(a_{b}) = b. Wenn wir dann die Abbildung g : B → A mittels g(b) = a_{b} für b ∈ f(A) und = a (a ∈ A, beliebig) für die übrigen b definieren, so ist g ein Linksinverses zu f. Also ist (i) bewiesen.

II) Führen Sie den Beweis von (ii) selber analog zu I.

III) Die ”Wenn-Richtung“ von (iii) folgt direkt aus (i) und (ii). Sei nun f als bijektiv vorausgesetzt. Wir nehmen dann die nach (i) und (ii) zu f existierenden Abbildungen g und h. Es gilt h = id_{A} ∘h = (g ∘ f) ∘ h = g ∘ (h ∘ f) = g ∘ id_{B} = g, also sind auch alle Linksinversen zu f gleich. Ebenso alle Rechtsinversen, und daher existiert die (eindeutig bestimmte) inverse Abbildung zu f.

1.14 Folgerung : Sei f eine Bijektion. Dann gilt (f^{−1})^{−1} = f. Beweis: Es gilt sowohl (f^{−1})^{−1} ∘ f^{−1} = id_{B} als auch f ∘ f^{−1} = id_{B}, also wegen der Eindeutigkeit der Inversen zu f nach Satz 1.13 (f^{−1})^{−1} = f.

AnfängerInnen müssen sich daran gewöhnen, nichts als selbstverständlich vorauszusetzen. Wir werden bald wichtige Strukturen kennenlernen, in denen die Existenz des Inversen keineswegs gesichert ist.

1.15 Definitionen : Sei M eine Menge. Eine Teilmenge R von M × M heißt eine Relation ρ auf M. Wir sagen: x steht in Relation zu y, geschrieben x ρ y, wenn (x, y) ∈ R gilt.

(i) Ist a ρ a für alle a ∈ M, so heißt ρ reflexiv.

(ii) Gilt (a ρ b → b ρ a), so heißt ρ symmetrisch.

(iii) Gilt (a ρ b ∧ b ρ c → a ρ c), so heißt ρ transitiv.

(iv) Eine Relation, die reflexiv, symmetrisch und transitiv ist, nennen wir eine Äquivalenzrelation, oft mit ∼ bezeichnet.

1.16 Beispiele :

(i) Die Gleichheit ist die bekannteste Äquivalenzrelation. Eine weitere Äquivalenzrelation ist die Ähnlichkeitsrelation auf der Menge aller Dreiecke.

(ii) Die Relation ”ist ein Teiler von“ auf der Menge der natürlichen Zahlen ist reflexiv und transitiv, aber nicht symmetrisch.

(iii) Sei n eine natürliche Zahl. Die kleinsten nichtnegativen Reste, die bei Division von ganzrationalen Zahlen durch n auftreten können, sind 0, 1, 2, …, n − 1. Seien a, b ganzrational. Wir sagen: a ≡ b mod n, wenn a und b bei Division durch n den gleichen kleinsten nichtnegativen Rest lassen, gesprochen: a kongruent zu b modulo n. Die Kongruenzrelation ist eine Äquivalenzrelation (Selbst überlegen!). Äquivalent mit a ≡ b mod n ist die Aussage: n ist ein Teiler von a − b.^{12}

1.17 Satz : Sei ∼ eine Äquivalenzrelation auf M. Dann ist M disjunkte Vereinigung (oder Partition) von (bzw. in) Teilmengen M_{ν} von M, geschrieben als M = ⋃_{ν} ; .M_{ν}, so daß gilt:

⋀_{a,b∈M_{ν}}a ∼ b ∧ [(a ∈ M_{ν}, b ∈ M_{μ}, μ ≠ ν) → a ≁ b] .

Die Mengen M_{ν} heißen die Äquivalenzklassen von M bezüglich ∼. Also: M zerfällt in disjunkte Äquivalenzklassen. Beweis: Aufgabe 1, 2. Übungsblatt.

12Die Bedeutung der Kongruenzrelation wird daraus ersichtlich, daß heutige Programmiersprachen wie Pascal, Modula, Lisp, Prolog einen Operator bzw. eine Funktion mod bereitstellen. In C/C++ wird das Zeichen % genommen: a%b ist der kleinste nichtnegative Rest von a modulo b.

1.18 Beispiele :

(i) Die Menge ℤ der ganzrationalen Zahlen zerfällt bezüglich der Kongruenz mod 8 in 8 Äquivalenzklassen, sog. Restklassen, nämlich

ˆ0 = {0, ±8, ±16, …} ,

ˆ1 = {…, −15, −7, 1, 9, 17, …} ,

…,

ˆ7 = {…, −9, −1, 7, 15, 23, …} .

(ii) Zentralprojektion bedeutet eine Partition des gesamten Raumes (ohne Projektionspunkt) in die Projektionsstrahlen (Äquivalenzklassen) ( siehe nachfolgendes Bild ).

Dürer : Der Zeichner des liegenden Weibes

1.4 Elementare Kombinatorik

Eines der Axiome für die Menge ℕ := {1, 2, 3, …} der natürlichen Zahlen lautet:^{13}

1.19 Induktionsaxiom : Sei A(n) eine Aussage über die natürliche Zahl n mit den Eigenschaften (i) A(n) ist wahr für ein n = n_{0} (Induktionsanfang) und

13Wir wollen die Axiomatik der Zahlensysteme auch später nur insoweit behandeln, als es die reellen und komplexen Zahlen betrifft ( Kapitel 2, 3 ). Das bekannteste Axiomensystem für die Menge ℕ der natürlichen Zahlen stammt von Guiseppe Peano. Aus ℕ lassen sich leicht die Bereiche ℤ der ganzrationalen Zahlen und ℚ der rationalen Zahlen entwickeln ( siehe z. B. E. Landau: Grundlagen der Analysis ).

(ii) ∀n ≥ n_{0} : A(n) → A(n + 1).

Dann gilt A(n) für alle n ≥ n_{0}.

Eine zweite, äquivalente Fassung des Induktionsaxioms lautet: Wenn A(n_{0}) für ein n_{0} ∈ ℕ und ⋀_{{n∈ℕ \atop n_{0}≤n<k}}A(n) → A(k), dann gilt A(n) für alle n ≥ n_{0}.

Ein Beweis für die Aussage ⋀_{{n∈ℕ \atop n≥n_{0}}} A(n) mit Hilfe des Induktionsaxioms heißt

ein Beweis durch vollständige Induktion. In einem solchen Beweis beweisen wir also (i) die Behauptung für ein festes n_{0} und zeigen z.B. (ii): Sobald die Behauptung für ein n richtig ist, so ist sie es auch für den Nachfolger n + 1 (sog. Schluß von n auf n + 1). Es ist klar, daß dann die behauptete Aussage für jedes n ≥ n_{0} bewiesen ist, da wir uns ja von n_{0} mit dem Induktionsschluß (ii) zu seinem Nachfolger n_{0} + 1, von dem Nachfolger zu dessen Nachfolger etc. zu jedem n ≥ n_{0} ”hochhangeln“ können. Beispiele für solche Induktionsbeweise sind die Beweise der beiden folgenden Sätze.

1.20 Definition : Für n ∈ ℕ heißt die Zahl n! := 1·2·3···n n-Fakultät. Wir verabreden: 0! = 1.

1.21 Satz : Es seien A = {a_{1}, a_{2}, …, a_{n}} und B = {b_{1}, b_{2}, …, b_{n}} zwei Mengen mit genau n Elementen (Mengen der Mächtigkeit n, Schreibweise: |A| = |B| = n). Dann gilt für die Anzahl |S_{n}| der Bijektionen f : A → B: |S_{n}| = n!. Beweis: Durch vollständige Induktion.

(i) Induktionsanfang: Die Behauptung ist richtig für n = 1; denn zwischen {a_{1}} und {b_{1}} gibt es genau eine Bijektion. Also gilt |S_{1}| = 1.

(ii) Induktions-Annahme: Die Aussage sei richtig für n.

(iii) Induktions-Schluß: Wir zählen die Bijektionen zwischen {a_{1}, a_{2}, …, a_{n+1}} und {b_{1}, b_{2}, …, b_{n+1}}. Da es für das Bild von a_{1} genau n Möglichkeiten gibt (nämlich j = 1, 2, …, n), gibt es also (n + 1) · (n!) Möglichkeiten für eine bijektive Abbildung zwischen A und B.

1.22 Definitionen : Eine Bijektion f : A → A heißt Permutation oder Transformation von A. Die Menge aller Permutationen einer n-elementigen Menge wird mit S_{n} bezeichnet. Eine Anordnung mit Berücksichtigung der Reihenfolge von n Elementen, unter denen n_{1} gleiche seien, etwa alle gleich a_{1}; n_{2} gleiche, etwa gleich a_{2}; … und n_{r} gleiche, die gleich a_{r} seien, heißt Permutation mit Wiederholungen.

1.23 Bemerkung : Die Anzahl dieser Permutationen mit Wiederholungen beträgt \frac{n!}{n_{1}!n_{2}!...n_{r}!}. Überlege die Richtigkeit dieser Formel!

1.24 Binomischer Satz : Für a, b ∈ ℝ und n ∈ ℕ gilt

(a + b)^{n} = ∑_{k=0}^{n} \frac{n!}{k!(n − k)!}a^{k}b^{n−k}.

. Dabei gilt die Schreibweise ∑_{k=0}^{n}c_{k} := c_{0} + c_{1} + … + c_{n} .

Beweis: Durch vollständige Induktion.

(i) Induktionsanfang: Offensichtlich gilt a + b = \frac{1!}{0!1!}a^{0}b^{1} + \frac{1!}{1!0!}a^{1}b^{0}.

(ii) Induktionsschluß: Es gilt

(a + b)^{n+1} = (a + b)(a + b)^{n}
= (a + b) ∑_{k=0}^{n} \frac{n!}{k!(n − k)!}a^{k}b^{n−k}

= ∑_{k=0}^{n} \frac{n!}{k!(n − k)!}a^{k+1}b^{n−k} + ∑_{k=0}^{n} \frac{n!}{k!(n − k)!}a^{k}b^{n−k+1}

= ∑_{k=1}^{n+1} \frac{n!}{(k − 1)!(n − k + 1)!}a^{k}b^{n−k+1} + ∑_{k=0}^{n} \frac{n!}{k!(n − k)!}a^{k}b^{n−k+1} .

Die Veränderung in der ersten Summe bei der letzten Umformung wird auch Überschieben des Index genannt.

Slogan: Bei Erhöhung der Indexgrenzen um j ersetze den laufenden Index k durch k − j.

Ferner gilt doch die Beziehung (*)

\frac{n!}{(k − 1)!(n − k + 1)!} + \frac{n!}{k!(n − k)!} = \frac{k · n! + (n − k + 1) · n!}{k!(n − k + 1)!}
= \frac{(n + 1)!}{k!(n − k + 1)!} , also

(a + b)^{n+1} = ∑_{k=1}^{n} \frac{(n + 1)!}{k!(n − k + 1)!}a^{k}b^{n−k+1} + a^{n+1} + b^{n+1}

= ∑_{k=0}^{n+1} \frac{(n + 1)!}{k!(n − k + 1)!}a^{k}b^{n−k+1} .

Übung: Überlege direkten Beweis mittels Permut. mit Wdhg.

1.25 Definitionen : Die Koeffizienten der Binomischen Formel werden Binomialkoeffizienten genannt und mit \binom{n}{k} := \frac{n!}{k!(n−k)!} bezeichnet (definiert für 0 ≤ k ≤ n).

(*) aus 1.24 \binom{n}{k−1} + \binom{n}{k} = \binom{n + 1}{k} ist Grundlage für das Pascalsche Dreieck der Binomialkoeffizienten:

1

1  1
1  2  1
1  3  3  1
1  4  6  4  1
· · · · · · · · · · · · · · · · · · · · · · · · · · ·

Binom. Satz und Pascal-Dreieck waren in China lange vor Pascal bekannt.

Aus Chu Shi-Chieh : Kostbarer Spiegel der 4 Elemente ( 13. Jh. )

Blaise Pascal (1623 - 1663)

Pascal war Mathematiker, Physiker, Philosoph, Theologe und Ingenieur. Er erfand die hydraulische Presse und baute eine Addiermaschine.

Pascals Rechenmaschine

1.26 Definitionen : Seien k, n ∈ ℕ und k ≤ n.

(i) Eine k-elementige Teilmenge einer n-elementigen Menge heißt eine Kombination (ohne Wiederholung) von n Elementen zur k-ten Klasse. Die Anzahl dieser Kombinationen sei mit C(k, n) bezeichnet.

(ii) Entsprechend wird eine k Objekte umfassende Multimenge^{14} , die mit Hilfe einer Teilmenge einer n-elementigen Menge gebildet wurde, Kombination von n Elementen zur k-ten Klasse mit Wiederholung genannt. Ihre Anzahl sei mit C_{W} (k, n) bezeichnet.

(iii) Eine k-elementige Permutation, gebildet aus Elementen einer n-elementigen Menge, heißt Variation (ohne Wiederholung) von n Elementen zur k-ten Klasse. Ihre Anzahl: V (k, n).

(iv) Analog können auch Variationen mit Wiederholung definiert werden. Ihre Anzahl: V_{W} (k, n).

1.27 Bemerkungen : Es gelten

(i) C(k, n) = \binom{n}{k} ,

(ii) C_{W} (k, n) = \binom{n + k − 1}{k} ,

14Als Multimenge bezeichnet man in der Kombinatorik bisweilen ein Aggregat vom Typ {…, m, m, …}, in dem also Elemente auch mehrfach auftreten.

(iii) V (k, n) = \frac{n!}{(n−k)!} ,

(iv) V_{W} (k, n) = n^{k} .

Beweise: Für C(k, n) ist stets k ≤ n. Es gilt C(n, n) = 1. Zu zeigen bleibt also die Behauptung für k < n. Vollständige Induktion nach n: Die Formel ist richtig für n = 1, da C(0, 1) = 1 ist. Die Formel sei für n als richtig angenommen. Gesucht ist C(k, n + 1) mit k < n + 1. Sei M_{1} (M_{2}) die Menge der Kombinationen der Ziffern a_{1}, a_{2}, …, a_{n+1} zur k-ten Klasse, die a_{n+1} (nicht) enthalten. Nach Induktionsannahme ist |M_{1}| = C(k − 1, n) = \binom{n}{k−1} und |M_{2}| = C(k, n) = \binom{n}{k}. Also gilt nach (*) von 1.24 C(k, n + 1) = |M_{1}| +

|M_{2}| = \binom{n + 1}{k}.

Die Formel für V (k, n) folgt aus der Tatsache, daß es sich bei Variationen von n Elementen zur k-ten Klasse um Permutationen mit Wiederholungen handelt: Die n − k nichtauftretenden Ziffern werden als gleich angesehen!

Eine Variation von n Elementen zur k-ten Klasse zu bilden bedeutet, n Ziffern auf k Speicherzellen zu verteilen, also gibt es insgesamt V_{W} (k, n) = n^{k} Möglichkeiten.^{15}

Die Formel für C_{W} (k, n) sei als Aufgabe (z.B. mittels vollständiger Induktion) gelassen.

1.28 Definitionen :

(i) Zwei Mengen M, N heißen gleichmächtig, geschrieben |M| = |N| oder M ≅ N, wenn es eine Bijektion von M auf N gibt.

(ii) M heißt abzählbar, wenn M ≅ ℕ oder ∃n ∈ ℕ : M ≅ {1, 2, …, n}.

(iii) Im letzteren Fall ist M eine endliche Menge der Kardinalzahl |M| = n < ∞.

(iv) Der Menge ℕ der natürlichen Zahlen wird die Kardinalzahl ℵ_{0} (Aleph Null) zugeordnet.

Slogans: Gleichmächtig bedeutet ”gleichviele Elemente“.

Die Kardinalzahl einer Menge bedeutet die ”Anzahl“ ihrer Elemente.

15So vermag also ein Byte 2^{8} = 256 Bitmuster zu speichern, daher erfaßt der ASCII-Code nur 256 Zeichen.

1.29 Bemerkungen :

(i) ≅ ist eine Äquivalenzrelation.

(ii) Für unendliche Mengen ist es möglich, daß N ⊂_{≠} M mit M ≅ N

existiert. Z.B. ist 2ℤ := {0, ±2, ±4, …} ⊂_{≠} ℤ := {0, ±1, ±2, …} und

f(x) := 2x vermittelt eine Bijektion von ℤ auf 2ℤ.

Ja, es gilt sogar das sog. Dedekindsche Kriterium:

(iii) M unendlich ↔ M besitzt eine zu M gleichmächtige echte Teilmenge. (ohne Beweis)

1.30 Satz : Es seien A, B Mengen mit Ø ≠ A ⊂ B, B abzählbar. Dann ist A abzählbar. Beweis: Wenn B endlich ist, so ist natürlich auch A endlich. Wenn B abzählbar unendlich ist, so können wir B = {b_{1}, b_{2}, …} schreiben. Jedes Element von B hat also einen natürlichen Index. Sei b_{n_{1}} das erste in der natürlichen Reihenfolge der Indizes auftauchende Element, das zu A gehört, b_{n_{2}} das zweite etc. Dann erhalten wir A = {b_{n_{1}}, b_{n_{2}}, …}, und mithin ist A abzählbar.

1.31 Satz : Wenn M, N abzählbare Mengen sind, so ist M × N abzählbar. Beweis: Wegen 1.30 genügt es, die Aussage für abzählbar unendliche A, B zu beweisen. Seien also A = {a_{1}, a_{2}, …, a_{i}, …} und B = {b_{1}, b_{2}, …, b_{j}, …}. Die Elemente von A × B erfassen wir nach dem sog. Cantor’schen Diagonalverfahren: (a_{1}, b_{1}), (a_{1}, b_{2}), (a_{1}, b_{3}), (a_{1}, b_{4}), … (a_{2}, b_{1}), (a_{2}, b_{2}), (a_{2}, b_{3}), (a_{2}, b_{4}), … (a_{3}, b_{1}), (a_{3}, b_{2}), (a_{3}, b_{3}), (a_{3}, b_{4}), … (a_{4}, b_{1}), (a_{4}, b_{2}), …

⋮ \frac{(i+j−1)(i+j−2)}{2} +j gibt den Index des Paares (a_{i}, b_{j}) an. Somit ist A×B abzählbar unendlich.

1.32 Folgerung : Die Menge ℚ der rationalen Zahlen ist abzählbar. Denn: Die Menge der positiven rationalen Zahlen ist eine Teilmenge von ℕ × ℕ, also abzählbar (Jede positive rationale Zahl läßt sich als \frac{a}{b} darstellen mit a, b ∈ ℕ). Der Rest der Aussage folgt aus dem nächsten Satz.

1.33 Satz : Wenn M_{n} abzählbar für alle n ∈ ℕ ist, so ist ⋃_{n∈ℕ}M_{n} abzähl-

bar. Beweis: Schreibe M_{1} = {m_{11}, m_{12}, m_{13}, …}, M_{2} = {m_{21}, m_{22}, m_{23}, …}, M_{3} = {m_{31}, m_{32}, m_{33}, …},

⋮ und stelle die Menge ⋃ M_{n} gemäß dem Cantor’schen Diagonalverfahren als abzählbare Folge m_{11}, m_{12}, m_{21}, m_{13}, m_{22}, m_{31}, m_{14}, m_{23}, m_{32}, m_{41}, … dar.

1.34 Satz : M :=]0, 1] := {x ∈ ℝ : 0 < x ≤ 1} ist nicht abzählbar. Beweis: Schreibe jedes m ∈ M als nichtabbrechenden Dezimalbruch, also z.B. 0,5 als 0,499… 9…. Diese Darstellung der Elemente von M ist eindeutig. Annahme: M ist abzählbar. Dann können wir die Elemente von M als ”durchnumeriert“ ansehen: m_{1} = 0, a_{11}a_{12}a_{13} … m_{2} = 0, a_{21}a_{22}a_{23} …

⋮  mit a_{ij} ∈ ℕ für alle i, j.

Betrachte die Zahl r = 0, b_{1}b_{2}b_{3} … mit b_{i} ∈ {1, 2, …, 8}, b_{i} ≠ a_{ii} ∀i = 1, 2, …, n. Es ist r ∈ M. Aber r unterscheidet sich von jedem m_{i} an der i-ten Nachkommastelle, und das ist ein Widerspruch zu der Annahme, daß r in der Abzählung auftauchen muß.

1.35 Folgerungen : Die Menge der irrationalen Zahlen in ]0, 1] ist nicht abzählbar. Die Menge ℝ der reellen Zahlen ist nicht abzählbar.

Übung: Überlegen Sie sich, daß gilt: Wenn M eine endliche Menge ist, so ist |P(M)| = 2^{|M|}.

1.36 Bemerkung : Die Kardinalzahl der Potenzmenge einer Menge M ist stets größer als die Kardinalzahl von M, also erhalten wir auch eine ganze Hierarchie von sog. transfiniten Zahlen 2^{ℵ_{0}}, 2^{2^{ℵ_{0}}}, …. Natürlich gilt 𝔠 := |ℝ| = 2^{ℵ_{0}}. Eine viel diskutierte These lautet: Es gibt keine Kardinalzahl 𝔞 mit ℵ_{0} < 𝔞 < 𝔠. (Die sogenannte Kontinuumshypothese). K. Gödel und P.J. Cohen bewiesen die Unabhängigkeit der Kontinuumshypothese von den anderen Axiomen der Mengenlehre.

Bronzetafel in Halle-Neustadt mit Cantorschem Diagonalverfahren

Marmorbüste Cantors in der Martin-Luther-Universität, Halle a. d. S.