% -*- TeX:DE -*- %%% ==================================================================== %%% @LaTeX-file qedeq_set_theory_v1_1.00.00.tex %%% Generated at 2005-12-29 19:35:56,890 %%% ==================================================================== %%% Permission is granted to copy, distribute and/or modify this document %%% under the terms of the GNU Free Documentation License, Version 1.2 %%% or any later version published by the Free Software Foundation; %%% with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. \documentclass[a4paper,german,10pt,twoside]{book} \usepackage[german]{babel} \usepackage{makeidx} \usepackage{amsmath,amsthm,amssymb} \usepackage{color} \usepackage[bookmarks,bookmarksnumbered,bookmarksopen, colorlinks,linkcolor=webgreen,pagebackref]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \usepackage{graphicx} \usepackage{xr} \usepackage{epsfig,longtable} \usepackage{tabularx} \newtheorem{thm}{Theorem}[chapter] \newtheorem{cor}[thm]{Korollar} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{ax}{Axiom} \newtheorem{rul}{Regel} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \newtheorem{idefn}[thm]{Initiale Definition} \theoremstyle{remark} \newtheorem{rem}[thm]{Bemerkung} \newtheorem*{notation}{Notation} \addtolength{\textheight}{7\baselineskip} \addtolength{\topmargin}{-5\baselineskip} \setlength{\parindent}{0pt} \frenchspacing \sloppy \makeindex \title{Axiomatische Mengenlehre} \author{ Michael Meyling } \begin{document} \maketitle \setlength{\parskip}{0pt} \tableofcontents \setlength{\parskip}{5pt plus 2pt minus 1pt} \chapter*{Vorwort\label{ch:preface}} \label{chapter0} \addcontentsline{toc}{chapter}{Vorwort\label{ch:preface}} Mathematik ist eine Wissenschaft mit einer Struktur, die im Laufe der Zeit riesige Dimensionen erreicht hat. Diese unglaublich hohe Burg besitzt nur ein ganz schmales Fundament und ihre Festigkeit liegt an einfachen pr{\"a}dikatenlogischen M{\"o}rtel. Im Prinzip kann der Aufbau von jeder Mathematikerin verstanden werden. Von dem neuesten Gipfel mathematischer Erkenntnis kann jeder Pfad logisch folgerichtig bis in die mengentheoretischen Wurzeln nachvollzogen werden. \par Bei diesem Unternehmen will dieses Dokument Hilfestellung geben. Ziel ist eine Pr{\"a}sentation der mengentheoretischen Wurzeln in verst{\"a}ndlicher Weise. Bei aller Verst{\"a}ndlichkeit soll es jedoch jederzeit m{\"o}glich sein, tief in die Details einzusteigen. Ja sogar bis auf die Ebene eines formal korrekten Beweises hinab. Dazu gibt es dieses Dokument in verschiedenen Detailierungen. F{\"u}r alle aber gilt, dass die Formeln in Axiomen, Definitionen und Propositionen in formal korrekter Form vorliegen. \par Wir wollen bei den Wurzeln anfangen\ldots \par Dieses Dokument ist noch im Entstehen und wird von Zeit zu Zeit aktualisiert. Insbesondere werden an den durch {\glqq+++\grqq} gekennzeichneten Stellen noch Erg{\"a}nzungen oder {\"A}nderungen vorgenommen. \par Besondere Dank geht an meine Frau \emph{Gesine~Dr{\"a}ger} und unseren Sohn \emph{Lennart} f{\"u}r ihre Unterst{\"u}tzung und ihr Verst{\"a}ndnis f{\"u}r ihnen fehlende Zeit. \par \vspace*{1cm} Hamburg, Dezember 2005 \\ \hspace*{\fill} Michael Meyling %% end of chapter Vorwort\label{ch:preface} \chapter*{Einleitung\label{ch:introduction}} \label{chapter1} \addcontentsline{toc}{chapter}{Einleitung\label{ch:introduction}} Am Anfang steht die Logik. Sie stellt das R{\"u}stzeug zur Argumentation bereit. Sie hilft beim Gewinnen von neuen Aussagen aus bereits vorhandenen. Sie ist universell anwendbar, liefert aber selbst keine Grundaussagen {\"u}ber mathematische Objekte. Erst in der Mengenlehre wird durch die Axiome eine mathematische Struktur definiert. Besonders interessant ist die Mengenlehre dadurch, dass sie zum einen von eigentlich allen mathematischen Disziplinen verwendet wird. Zum anderen l{\"a}sst sich jede mathematische Disziplin innerhalb der Mengenlehre definieren. Zahlentheorie, Algebra, Analysis und alle weiteren Gebiete lassen sich darauf aufbauen. \par Dieses Dokument beschreibt die mathematischen Grundlagen der Mengenlehre. Ziel ist dabei die Bereitstellung von elementaren Ergebnissen der Mengenlehre, die in anderen mathematischen Disziplinen ben{\"o}tigt werden. Nach den Grundlagen wird die Boolsche Algebra der Klassen betrachtet. Es schliessen sich Betrachtungen {\"u}ber Relationen und Funktionen an. Ein weiteres wichtiges Ergebnis sind die Definition der nat{\"u}rlichen Zahlen und die Erf{\"u}llung der Peano-Axiome durch diese, auch auf den Begriff der Rekursion wird eingegangen. \par Die Darstellung erfolgt in axiomatischer Weise soll aber im Ergebnis der mathematischen Praxis entsprechen. Daher wird auch das Axiomensystem der Mengenlehre von \emph{A.~P.~Morse} und \emph{J.~L.~Kelley} (MK\index{MK}) verwendet. %% end of chapter Einleitung\label{ch:introduction} \chapter{Anfangsgr{\"u}nde} \label{chapter2} In diesem Kapitel beginnen wir mit den ganz elementaren Axiomen und Definitionen der Mengenlehre. Wir versuchen nicht eine formale Sprache einzuf{\"u}hren und setzen das Wissen um den Gebrauch von logischen Symbolen voraus. Noch genauer formuliert: wir arbeiten mit einer Pr{\"a}dikatenlogik erster Stufe mit Gleichheit. \par\index{Cantor}\index{Menge!Definition} \emph{G.~Cantor}, der als Begr{\"u}nder der Mengenlehre gilt, hat in einer Ver{\"o}ffentlichung im Jahre 1895 eine Beschreibung des Begriffs \emph{Menge} gegeben. \begin{quote} Unter einer {\glqq Menge\grqq} verstehen wir jede Zusammenfassung $M$ von bestimmten wohlunterscheidbaren Objekten $m$ unserer Anschauung oder unseres Denkens (welche die {\glqq Elemente\grqq} von $M$ genannt werden) zu einem Ganzen. \end{quote} \par Diese Zusammenfassung kann {\"u}ber die Angabe einer Eigenschaft dieser Elemente erfolgen. Um 1900 wurden verschiedene Widerspr{\"u}che dieser naiven Mengenlehre entdeckt. Diese Widerspr{\"u}che lassen sich auf trickreich gew{\"a}hlte Eigenschaften zur{\"u}ckf{\"u}hren. \par Es gibt verschiedene M{\"o}glichkeiten diese Widerspr{\"u}che zu verhindern. In diesem Text schr{\"a}nken wir zwar die Angabe von Eigenschaften in keiner Weise ein, aber wir nennen das Ergebnis der Zusammenfassung zun{\"a}chst einmal \emph{Klasse}. Zus{\"a}tzliche Axiome regeln dann, wann eine bestimmte Klasse auch eine Menge ist. Alle Mengen sind Klassen, aber nicht alle Klassen sind Mengen. Eine Menge ist eine Klasse, die selbst Element einer anderen Klasse ist. Eine Klasse, die keine Menge ist, ist nicht Element irgend einer anderen Klasse. \section{Klassen und Mengen} \label{section0} Obgleich wir im Wesentlichen {\"u}ber \emph{Mengen} sprechen wollen, haben wir am Anfang nur \emph{Klassen}. Dieser Begriff wird nicht formal definiert. Anschaulich gesprochen, ist eine Klasse eine Zusammenfassung von Objekten. Die beteiligten Objekte heissen auch Elemente der Klasse. Mengen werden dann als eine besondere Art von Klassen charakterisiert. Die folgenden Definitionen und Axiome folgen dem Aufbau einer vereinfachten Version der Mengenlehre nach \emph{von~Neumann-Bernays-G{\"o}del} (\emph{NBG}\index{NBG}).. Diese Version wird auch \emph{MK}\index{MK} nach \emph{Morse-Kelley} genannt. Die hier vorgestellte Mengenlehre hat als Ausgangsobjekte \emph{Klassen}. Weiterhin wird nur ein einziges Symbol f{\"u}r eine bin{\"a}re Relation vorausgesetzt: der \emph{Enthaltenseinoperator}. \par \begin{idefn}[Elementbeziehung] \label{in} $$x \in y$$ \end{idefn} Wir sagen auch $x$ \emph{ist Element von} $y$, $x$ \emph{geh{\"o}rt zu} $y$, $x$ \emph{liegt in} $y$, $x$ \emph{ist in} $y$. Neben der Gleichheit ist dies das einzige Pr{\"a}dikat welches wir zu Beginn haben. Alle anderen werden definiert.\footnote{Das Gleichheitspr{\"a}dikat k{\"o}nnte auch innerhalb der Mengenlehre definiert werden, aber dann wird auch ein weiters Axiom ben{\"o}tigt und es ergeben sich technischen Schwierigkeiten bei der Herleitung der Gleichheitsaxiome.} Zu Anfang haben wir auch noch keine Funktionskonstanten. Obgleich wir die Elementbeziehung einfach negieren k{\"o}nnen, m{\"o}chten wir daf{\"u}r eine Abk{\"u}rzung definieren. \par \begin{defn}[Negation der Elementbeziehung] \label{notIn} $$x \notin y\ := \ \neg x \in y$$ \end{defn} Unser erstes Axiom besagt, dass beliebige Klassen $x$ und $y$ genau dann gleich sind, wenn sie dieselben Elemente enthalten.\footnote{Falls wir das Gleichheitspr{\"a}dikat nicht als logisches Symbol voraussetzen w{\"u}rden, dann w{\"u}rden wir es hiermit definieren.} \par \begin{ax}[Extensionalit{\"a}t\index{Extensionalit{\"a}tsaxiom}] \label{axiom:extensionality} \mbox{} \begin{longtable}{{@{\extracolsep{\fill}}p{\linewidth}}} $\forall z\ (z \in x\ \leftrightarrow \ z \in y)\ \rightarrow \ x \ = \ y$ \end{longtable} \end{ax} Die Klassen $x$ and $y$ k{\"o}nnen verschieden definiert sein, beispielsweise: \par \begin{tabularx}{\linewidth}{rcX} $x$ & = & Klasse aller nichtnegativen ganzen Zahlen, \\ $y$ & = & Klasse aller ganzen Zahlen, die als Summe von vier Quadraten geschreiben werden k{\"o}nnen, \end{tabularx} \par aber wenn sie dieselben Elemente besitzen, sind sie gleich. Jetzt legen wir fest, was eine \emph{Menge} ist. \par \begin{defn}[Menge\index{Menge!Definition}] \label{isSet} $$\mathfrak{M}(x)\ := \ \exists y\ x \in y$$ \end{defn} Mengen sind also nichts anderes, als Klassen mit einer besonderen Eigenschaft. Eine Klasse ist genau dann eine Menge, wenn sie Element irgendeiner Klasse ist. Als erste Folgerung aus dem Extensionalit{\"a}tsaxiom erhalten wir das Folgende.\footnote{Es wird ein eingeschr{\"a}nkter Allquantor benutzt, $z$ l{\"a}uft nur {\"u}ber Mengen.} \par \begin{prop} \label{theorem:extensionalitySetRestricted} \mbox{} \begin{longtable}{{@{\extracolsep{\fill}}p{\linewidth}}} $\forall \ \mathfrak{M}(z)\ (z \in x\ \leftrightarrow \ z \in y)\ \rightarrow \ x \ = \ y$ \end{longtable} \end{prop} \begin{proof} Angenommen es gelte $\forall \ \mathfrak{M}(z) \ ( z \in x \ \leftrightarrow \ z \in y)$. Sei $z$ eine beliebige Klasse. Falls $z \in x$ dann gilt $z$ ist eine Menge nach Definition~\ref{isSet}, und daraus folgt mit der Annahme $z \in y$. Analog folgt $z \in y \ \rightarrow \ z \in x$. Da $z$ beliebig, haben wir $\forall z \ (z \in x \ \leftrightarrow \ z \in y)$. Und mit dem Extensionalit{\"a}tsaxiom~\ref{axiom:extensionality} erhalten wir daraus $x = y$. \end{proof} Weiterhin k{\"o}nnen wir in dem Extensionalit{\"a}tsaxiom die Implikation umkehren. \par \begin{prop} \label{theorem:extensonalityEquivalence} \mbox{} \begin{longtable}{{@{\extracolsep{\fill}}p{\linewidth}}} $x \ = \ y\ \leftrightarrow \ \forall z\ (z \in x\ \leftrightarrow \ z \in y)$ \end{longtable} \end{prop} \begin{proof} Dies ist eine einfache Anwendung des zweiten identit{\"a}tslogischen Axioms. \end{proof} Unser zweites Axiom erm{\"o}glicht eine einfache M{\"o}glichkeit Klassen zu bilden. Eine Klasse wird ganz einfach durch die Angabe einer pr{\"a}dikatenlogischen Formel charakterisiert. \par \begin{ax}[Komprehension] \label{axiom:comprehension} \mbox{} \begin{longtable}{{@{\extracolsep{\fill}}p{\linewidth}}} $\exists x\ \forall y\ (x \in y\ \leftrightarrow \ (\mathfrak{M}(y)\ \land \ \phi(y)))$ \end{longtable} \end{ax} \index{NBG}Durch eine {\"A}nderung dieses Axioms w{\"u}rden wir im Folgenden ein \emph{NBG}-Axiomensystem der Mengenlehre erhalten, welches auf \emph{John von Neumann}, \emph{Isaak Bernays} und \emph{Kurt G{\"o}del} zur{\"u}ckgeht. \par\index{pr{\"a}dikativ}\index{Formel, pr{\"a}dikative} Dazu definieren wir: eine Formel, in der alle gebundenen Subjektvariablen auf Mengen restringiert sind wird \emph{pr{\"a}dikative Formel} genannt. Pr{\"a}dikative Formeln formalisieren also diejenigen Eigenschaften, die man als {\glqq Eigenschaften von Mengen\grqq} bezeichnen kann.\footnote{Noch etwas formaler: in einer pr{\"a}dikativen Formel laufen alle Quantorenvariablen nur {\"u}ber Mengen: $\forall \ \mathfrak{M}(x) \ \exists \ \mathfrak{M}(y) \ldots$} Fordern wir nun also zus{\"a}tzlich, dass $\phi$ pr{\"a}dikativ sein muss, dann erhalten wir im Folgenden ein NBG-System. Durch das Komprehensionsaxiom und die Extensionalit{\"a}t wird nun der Zusammenhang zwischen einer Aussage $\phi(y)$ und der durch sie definierten Klasse festgelegt. Dabei behaupted das Komprehensionsaxiom die Existenz mindestens einer Klasse, deren Elemente die Aussage $\mathfrak{M}(y) \land \phi(y)$ erf{\"u}llen. Das Extensionalit{\"a}tsaxiom und die Gleichheitsaxiome sichern ab, dass es h{\"o}chstens eine solche Klasse gibt: irgend zwei Klassen, welche dieselben Elemente besitzen, sind gleich im Sinne der Ersetzbarkeit in allen einschl{\"a}gigen Aussagen. Mit anderen Worten: es gibt nur genau eine solche Klasse. \par \begin{prop} \label{theorem:comprehension} \mbox{} \begin{longtable}{{@{\extracolsep{\fill}}p{\linewidth}}} $\exists! x\ \forall y\ (x \in y\ \leftrightarrow \ (\mathfrak{M}(y)\ \land \ \phi(y)))$ \end{longtable} \end{prop} \begin{proof} Zu zeigen ist: $$ \begin{array}{rl} \exists x & \forall y \ (y \in x \leftrightarrow \ \mathfrak{M}(y) \land \phi(y)) \\ \land \ \forall u \ \forall v & (\forall y \ (y \in u \leftrightarrow \mathfrak{M}(y) \land \phi(y)) \ \land \ \forall y \ ( y \in v \leftrightarrow \ \mathfrak{M}(y) \land \phi(y))) \\ & \qquad \rightarrow u = v) \end{array} $$ Seien $u$ und $v$ beliebig. Es gelte weiterhin: \par $\forall y \ (y \in u \leftrightarrow \ \mathfrak{M}(y) \land \phi(y)) \land \ \forall y \ ( y \in v \leftrightarrow \mathfrak{M}(y) \land \phi(y)))$ \par Dann folgt mit \ref{allandpp}: $\forall y \ ((y \in u \leftrightarrow \mathfrak{M}(y) \land \phi(y)) \land (y \in v \leftrightarrow \mathfrak{M}(y) \land \phi(y)))$ \par Daraus erhalten wir mit \ref{andequi}: $\forall y \ ((y \in u \leftrightarrow y \in v ))$. Und mit Proposition~\ref{theorem:extensonalityEquivalence} folgt nun $u = v$. Also haben wir gezeigt: \par $\forall u \ \forall v \ (\forall y \ (y \in u \leftrightarrow \mathfrak{M}(y) \land \phi(y)) \land \ \forall y \ (y \in v \leftrightarrow \mathfrak{M}(y) \land \phi(y))) \rightarrow u = v)$ \par Zusammen mit Axiom~\ref{axiom:comprehension} folgt nun die Behauptung. \end{proof} Ausgehend von \ref{theorem:comprehension} k{\"o}nnen wir die Sprachsyntax erweitern und eine neue abk{\"u}rzende Schreibweise einf{\"u}hren. \par \begin{rul}[Klassenschreibweise] \label{rule:classDefinition} F{\"u}r jede Formel $\alpha(x)$ definieren wir den Termausdruck $\{ x \ | \ \alpha(x)\}$ durch $$ \exists y \ (y = \{x \ | \ \alpha(x) \} \ \land \ \forall x \ x \in y \ \leftrightarrow \mathfrak{M}(x) \ \land \alpha(x)) $$ \par Die freien Variablen von $\{ x \ | \ \alpha(x)\}$ sind die freien Variablen von $\alpha(x)$ vermindert um $\{ x \}$. Die gebunden Variablen entsprechen den gebunden Variablen von $\alpha(x)$. Alle Ableitungsregln werden entsprechend erweitert. %old % Der Ausdruck $\{ x | \alpha(x)\}$ bezeichnet ebenfalls einen Term. Sei $\beta(y)$ eine Formel und $beta(\{x | \alpha(x)\}$ die Formel, die bei Ersetzung von y durch den angegebenen Term entstehende Formel. Diese Formel kann ersetzt werden durch $\beta(y) \ \land \ \forall x \ x \in y \leftrightarrow \mathfrak{M}(x) \ \land \ \alpha(y)$. % \par % In dem Term $\{ x | \alpha(x)\}$ gilt $x$ als gebunden und der Term besitzt zus{\"a}tzlich die gebunden Variablen von $\alpha$ als gebundene Variablen. Die freien Variablen von $\alpha$ sind auch die freien Variablen des neuen Termausdrucks. \end{rul} Insbesondere muss die Substitutionsregel angepasst werden. Es handelt sich hierbei um eine \emph{konservative} Erweiterung. %old % { x | alpha (x)} = { x | alpha (x)} % y = y n All x x in y <-> M(x) n alpha(x) Im Folgenden wird auf diese Schreibweise zur{\"u}ckgegriffen. Die neue Schreibweise kann auch in einfacher Weise in die alte Syntax transformiert werden. Die G{\"u}ltigkeit der Ausgangspr{\"a}dikate dr{\"u}ckt sich f{\"u}r diese neue Termart wie folgt aus. \par \begin{prop} \label{theorem:setNotation} \mbox{} \begin{longtable}{{@{\extracolsep{\fill}}p{\linewidth}}} $(y \in \{ x \ | \ \phi(x) \} \ \leftrightarrow \ (\mathfrak{M}(y)\ \land \ \phi(y)))\ \land \ (y \ = \ \{ x \ | \ \phi(x) \} \ \leftrightarrow \ \forall z\ (z \in y\ \leftrightarrow \ z \in \{ x \ | \ \phi(x) \} ))\ \land \ (\{ x \ | \ \phi(x) \} \ = \ \{ x \ | \ \psi(x) \} \ \leftrightarrow \ \forall z\ (z \in \{ x \ | \ \phi(x) \} \ \leftrightarrow \ z \in \{ x \ | \ \psi(x) \} ))\ \land \ (\{ x \ | \ \phi(x) \} \in \{ x \ | \ \psi(x) \} \ \leftrightarrow \ \forall u\ \forall v\ ((u \ = \ \{ x \ | \ \phi(x) \} \ \land \ v \ = \ \{ x \ | \ \psi(x) \} )\ \rightarrow \ u \in v))\ \land \ (\{ x \ | \ \phi(x) \} \in y\ \leftrightarrow \ \forall u\ (u \ = \ \{ x \ | \ \phi(x) \} \ \rightarrow \ u \in v))$ \end{longtable} +++ wenn diese Formel richtig gesetzt w{\"u}rde, sollte sie so aussehen: \begin{align} y \in \{ x~|~\phi(x) \} & \leftrightarrow \mathfrak{M}(y) \land \phi(y) \tag{a} \\ y = \{ x~|~ \phi(x) \} & \leftrightarrow \forall z \ (z \in y \leftrightarrow z \in \{ x~|~\phi(x) \}) \tag{b} \\ \{ x~|~\phi(x) \} = \{ x~|~\psi(x) \} & \leftrightarrow \forall z \ (z \in \{ x~|~\phi(x) \} \tag{c} \\ \begin{split} & \qquad \leftrightarrow z \in \{x~|~\psi(x) \}) \nonumber \\ \{ x~|~\phi(x) \} \in \{ x~|~\psi(x) \} & \leftrightarrow \forall u \ \forall v \ ((u = \{ x~|~\phi(x) \} \\ & \qquad \land \ v = \{ x~|~\psi(x) \}) \rightarrow u \in v) \end{split} \tag{d} \\ \{ x~|~\phi(x) \} \in y & \leftrightarrow \forall u \ (u = \{ x~|~\phi(x) \} \rightarrow u \in y) \tag{e} \end{align} \end{prop} \begin{proof} +++ fehlt noch. \end{proof} Durch sukzessives Anwenden des obigen Satzes kann also die neue Syntax in die alte {\"u}berf{\"u}hrt werden. %% end of chapter Anfangsgr{\"u}nde \backmatter \addcontentsline{toc}{chapter}{\indexname} \printindex \end{document}