_03-Mengen.tex

\setchapterpreamble[c][.7\textwidth]{\itshape\color{gray}\small
    In diesem Vortrag werden grundlegende Eigenschaften und Operationen von Mengen vorgestellt. Ebenso werden Familien, Tupel und Mengenprodukte eingeführt, da sie grundlegend für die Konzepte „Relation“, „Folge“ und „Verknüpfung“ in den späteren Vorträgen sind.
\vspace{24pt}}

    
\chapter{Mengen und Familien} \label{chap:mengen}


\section{Mengen und Elemente}


Eine historische Definition des Mengenbegriffs wurde bereits in \cref{mengenimlogikkapitel} gegeben.


\begin{defin}[Menge] \label{def:menge} \index{Menge}
    Eine \textbf{Menge} ist ein mathematisches Objekt, dem andere Objekte als ihre \textbf{Elemente} angehören können.
\end{defin}


\begin{nota}[Elementzeichen]
    Seien $x$ irgendein Objekt und $M$ eine Menge. Man schreibt
    \begin{align*}
        x  \in M \qquad&:\Leftrightarrow\qquad \text{$x$ ist ein Element von $M$} && (\text{lies: „$x$ in $M$“})\\
        x\notin M \qquad &:\Leftrightarrow\qquad \text{$x$ ist kein Element von $M$} && (\text{lies: „$x$ nicht in $M$“})
    \end{align*}
    Die Elementrelation $\in$ ist ein zweistelliges Prädikat im Sinne von \cref{def:praedikat}.

    Für ein Objekt $x$ und eine Menge $M$ ergibt es nur Sinn, zu fragen, \emph{ob} $x$ ein Element von $M$ ist -- dagegen ergäbe es keinen Sinn, danach zu fragen, „an welcher Stelle“ oder „wie oft“ $x$ ein Element von $M$ wäre.
\end{nota}


Der Mengenbegriff soll sich rein \emph{extensiv} verhalten, d.h. eine Menge soll allein dadurch bestimmt sein, welche Elemente ihr angehören. Diese Forderung wird durch das sogenannte \textbf{Extensionalitätsaxiom} realisiert:


\begin{axiom}[Gleichheit von Mengen] \label{mengengleich} \index{Extensionalitätsaxiom}
    Zwei Mengen $M,N$ stimmen genau dann überein, wenn sie dieselben Elemente enthalten. Als Formel:
        \[ (\forall x:\quad x\in M\ \leftrightarrow\ x\in N)\qquad\leftrightarrow\qquad M=N\]
    Dementsprechend sind zwei Mengen \emph{verschieden}, wenn mindestens eine der beiden ein Element enthält, das die andere nicht enthält.
\end{axiom}


\begin{defin}[Extension einer Eigenschaft] \label{def:extension} \index{Extension (einer Eigenschaft)}
    Sei $E(x)$ eine Eigenschaft. Die Menge aller Objekte (vom Typ der Variablen $x$) mit der Eigenschaft $E$ ist aufgrund des Extensionalitätsaxioms \cref{mengengleich} eindeutig bestimmt. Sie heißt die \textbf{Extension}\footnote{vgl. \cref{extensionimlogikkapitel}} von $E$ und wird notiert mit
    \begin{align*}
        \{ x\mid E(x) \} && (\textnormal{lies: „Menge aller $x$, für die gilt: $E(x)$“})
    \end{align*}
    In diesem Ausdruck fungiert das Zeichen „$x$“ als gebundene Variable im Sinne von \cref{gebundenevariable}. Per Definition gilt:
        \[ \forall a:\qquad a\in \{x\mid E(x)\} \ \leftrightarrow\ E(a) \]
    Für eine Menge $M$ (von Objekten vom Typ der Variablen $x$) wird mit
        \[ \{ x\in M\mid E(x) \} := \{ x\mid x\in M\ \text{und}\ E(x)\} \]
    die Menge aller Elemente von $M$, die die Eigenschaft $E$ besitzen, notiert.
\end{defin}


\begin{bsp} \label{bsp:extension}
    Das Konzept „Extension einer Eigenschaft“ erlaubt es, Mengen über Eigenschaften zu definieren. Zum Beispiel:
    \begin{enumerate}
        \item Es ist $\bbP := \{p\mid p\ \text{ist eine Primzahl}\}$ die Menge aller Primzahlen. Beispielsweise sind $23\in \bbP$ und $97\in\bbP$, denn $23$ und $97$ sind Primzahlen. Dagegen ist $91\notin \bbP$, denn $91$ ist keine Primzahl wegen $91=7\cdot 13$.
        \item Es ist $\{ x\mid x\ \text{liest dieses Vorkursskript} \}$ die Menge aller Leser dieses Skripts. Zum Beispiel bist DU ein Element dieser Menge.
        \item Es ist $[0,1] := \{ x\in \R \mid 0\le x\le 1\}$ die Menge aller reellen Zahlen zwischen Null und Eins, das sogenannte (abgeschlossene) \emph{Einheitsintervall}. (Für allgemeine Intervalle siehe \cref{def:intervall})
        \item Es ist $Q:=\{ n\in \N \mid \exists m\in \N:\ n=m^2 \}$ die Menge aller Quadratzahlen. Beispielsweise sind $100\in Q$ und $529\in Q$, aber $12\notin Q$ und $1000\notin Q$.
    \end{enumerate}
\end{bsp}


\begin{nota}[Definition einer Menge durch Auflistung ihrer Elemente] \label{auflistung}
    Seien $n\in \N$ und $a_1,\dots , a_n$ eine Handvoll Objekte. Dann bezeichnet
        \[ \{a_1,\dots , a_n\} := \{ x\mid x=a_1\ \text{oder}\ \ldots\ \text{oder}\ x=a_n \} \]
    diejenige Menge, die genau aus $a_1,\dots , a_n$ besteht. Auf diese Weise kannst du Mengen mit „wenigen“ Elementen über eine Auflistung aller ihrer Elemente definieren.
\end{nota}


\begin{bsp}
    Zum Beispiel ist
        \[ M:=\{2,3,5,7\} \]
    diejenige Menge, die genau aus den Zahlen $2$, $3$, $5$ und $7$ besteht.
\end{bsp}


\begin{bem}
    Gelegentlich werden auch Mengen mit unendlich vielen Elementen über eine Art „Auflistung“ definiert, zum Beispiel
        \[ M := \{1, 3, 5, 7, 9,\ldots \} \]
    Diese Art von „Definition“ setzt beim Leser das Erkennen eines intendierten Musters voraus und kann zu Missverständnissen führen. Im Zweifelsfall solltest du eine Definition über eine Eigenschaft bevorzugen. In diesem Fall wäre das
        \[ M := \{n \in \N \mid n\ \text{ist ungerade} \} \]
\end{bem}


\begin{nota} \label{beschraenktquant}
    Seien $E(x)$ eine Eigenschaft und $M$ eine Menge (von Objekten vom Typ der Variablen $x$). Für Aussagen über die Elemente von $M$ gibt es folgende Schreibweisen\footnote{vgl. \cref{def:allquant}, \cref{def:existquant} und \cref{def:eindquant}}
    \begin{align*}
        \forall x\in M:\ E(x) \qquad :& \Leftrightarrow\qquad \forall x:\ (x\in M\ \to\ E(x))  \\
        (\text{lies: „Für jedes $x$ aus $M$ gilt $E(x)$“}) & \\[0.5em]
        \exists x\in M:\ E(x) \qquad :& \Leftrightarrow\qquad \exists x:\ (x\in M\ \land\ E(x))  \\
        (\text{lies: „Es gibt ein $x$ in $M$, für das $E(x)$ gilt“}) & \\[0.5em]
        \nexists x\in M:\ E(x) \qquad :& \Leftrightarrow\qquad \nexists x:\ (x\in M\ \land\ E(x))  \\
        (\text{lies: „Es gibt kein $x$ in $M$, für das $E(x)$ gilt“}) & \\[0.5em]
        \exists ! x\in M :\ E(x) \qquad :& \Leftrightarrow\qquad \exists ! x:\ (x\in M\ \land\ E(x)) \\ (\text{lies: „Es gibt genau ein $x$ in $M$, für das $E(x)$ gilt“})
    \end{align*}
    um auszudrücken, dass jedes/mindestens eines/keines/genau eines der Elemente von $M$ die Eigenschaft $E$ besitzt.
\end{nota}


\begin{bsp}
    Es gilt:
    \begin{align*}
        \forall n\in \N &:\ n\cdot (n+1)\ \text{ist eine gerade Zahl} && (\text{vgl. \cref{bsp:fallunterscheidung}})\\
        \exists x\in \R &:\ x^5 = x+1 && (\text{vgl. \cref{bsp:exverwendung}})\\
        \nexists n\in \N &:\ 17\cdot n = 198 && (\text{vgl. \cref{bsp:reductio}})\\ 
        \exists ! a\in \R \ \forall x\in \R & :\ ax=a &&(\text{vgl. \cref{bsp:eindbeweis}})
    \end{align*}
\end{bsp}





\section{Teilmengen}


\begin{defin}[Teilmenge] \label{def:teilmenge} \index{Teilmenge}
    Seien $M$ und $N$ zwei Mengen. $M$ heißt eine \textbf{Teilmenge} (manchmal auch: \textbf{Untermenge}) von $N$ (und $N$ eine \textbf{Obermenge} von $M$), falls jedes Element von $M$ auch ein Element von $N$ ist. Notation:
    \begin{align*}
        M \subseteq N \qquad &:\Leftrightarrow\qquad M\ \text{ist eine Teilmenge von $N$} \\
        M \nsubseteq N \qquad &:\Leftrightarrow\qquad M\ \text{ist keine Teilmenge von $N$}
    \end{align*}
\end{defin}


\begin{figure}[ht]
    \begin{tikzpicture}
        \filldraw[fill=blue!10!white, draw=black] (0,0) ellipse (2cm and 1.3cm);
        \filldraw[fill=blue!25!white, draw=black] (.5,0) ellipse (1cm and .7cm);
        \path (-1.2,0) node {$N$} (.5,0) node {$M$};
    \end{tikzpicture}
    \centering \caption{Die Menge $M$ ist eine Teilmenge der Menge $N$.}
\end{figure}


\begin{bem}[Teilmengeninklusionen beweisen/widerlegen] \label{teilmengebeweisen}
    Seien $M,N$ zwei Mengen. Da es sich bei der Aussage „$M\subseteq N$“ um eine Allaussage handelt (\emph{jedes} Element von $M$ ist ein Element von $N$), kannst du sie mit der Technik aus \cref{allbeweis} beweisen: fixiere ein beliebiges Element von $M$ und zeige irgendwie, dass es auch ein Element von $N$ ist.

    Wenn du meinst, dass „$M\subseteq N$” eine falsche Aussage ist, kannst du sie mit der Technik aus \cref{gegenbeispiel} widerlegen: finde ein Element von $M$, das kein Element von $N$ ist.
\end{bem}


\begin{bsp} \quad
    \begin{enumerate}
        \item Es ist $\{s\mid s\ \text{ist ein Spartaner}\}\subseteq \{g\mid g\ \text{ist ein Grieche}\}$, da alle Spartaner Griechen sind.
        \item Es ist $\N\subseteq \Z$.
        \item Es ist $\{\text{Regelmäßige Mensa-Essen}\} \nsubseteq \{ \text{Mahlzeiten, die nicht satt machen}\}$. Beispielsweise fand ich die Schupfnudelpfanne immer ordentlich sättigend.
    \end{enumerate}
\end{bsp}


\begin{satz}[Eigenschaften von $\subseteq$] \label{teilmengeneig}
    Seien $L,M,N$ drei Mengen. Dann gilt:
    \begin{enumerate}
        \item (Reflexivität) $M\subseteq M$.
        \item (Transitivität) Aus $L\subseteq M$ und $M\subseteq N$ folgt $L\subseteq N$.
        \item (Antisymmetrie) Aus $M \subseteq N$ und $N\subseteq M$ folgt $M=N$.
    \end{enumerate}
    \begin{figure}[ht]
        \begin{tikzpicture}
            \filldraw[fill=blue!10!white, draw=black] (0,0) ellipse (2cm and 1.3cm);
            \filldraw[fill=blue!20!white, draw=black] (.5,0) ellipse (1.3cm and .9cm);
            \filldraw[fill=blue!30!white, draw=black] (.8,0) ellipse (.7cm and .5cm);
            \path (-1.4,0) node {$N$} (-.3,0) node {$M$} (.8,0) node {$L$};
        \end{tikzpicture}
        \centering \caption{Illustration der Transitivität von $\subseteq$}
    \end{figure}
\end{satz}
\begin{proof}
    \begin{enumerate}
        \item Für alle Elemente $m\in M$ gilt per se schon $m\in M$. Also ist $M$ in $M$ enthalten.\footnote{vgl. \cref{implikationref}: Jede Aussage impliziert sich selbst.}
        \item Sei $x\in L$ beliebig. Wegen $L\subseteq M$ gilt dann $x\in M$. Aus $x\in M$ folgt wegen $M\subseteq N$, dass auch $x\in N$. Da das Element $x\in L$ beliebig gewählt war, ist damit $L\subseteq N$ bewiesen.\footnote{Das war ein direkter Beweis mit Zwischenschritten, vgl. \cref{implikationtrans}: $x\in L\xrightarrow{L\subseteq N} x\in N \xrightarrow{N\subseteq M} x\in M$}
        \item Seien $M\subseteq N$ und $N\subseteq M$, sowie $x$ beliebig. Dann gilt $x\in M\ \leftrightarrow\ x\in N$, denn:
        \begin{labeling}
            \item[„$\Rightarrow$“] folgt aus $M\subseteq N$.
            \item[„$\Leftarrow$“] folgt aus $N\subseteq M$.
        \end{labeling}
        Weil $x$ beliebig gewählt war, folgt nun aus \cref{mengengleich} die Gleichheit $M=N$.\footnote{Das war ein Äquivalenzbeweis per Hin- und Rückrichtung, vgl. \cref{hinruck}.} \qedhere
    \end{enumerate}
\end{proof}


\begin{nota}[Echte Teilmenge]
    Nach \cref{teilmengeneig} ist jede Menge eine Teilmenge von sich selbst. Manchmal möchte man im Umgang mit Teilmengen diese eine „triviale“ Teilmenge ausschließen. Für Mengen $M,N$ definiert man daher: $M$ heißt eine \textbf{echte Teilmenge} von $N$, falls $M$ eine Teilmenge von $N$ ist, aber die Obermenge $N$ strikt größer ist. Notation:
    \begin{align*}
        M\subsetneq N \qquad:\Leftrightarrow\qquad M\subseteq N\quad \land\quad \exists x\in N:\ x\notin M
    \end{align*}
    $\subseteq$ und $\subsetneq$ unterscheiden sich in derselben Hinsicht wie $\le$ und $<$. Siehe dazu \cref{striktkleiner}.

    Bisweilen werden in der Literatur auch abweichende Schreibweisen benutzt: etwa $M\subseteq N$ für beliebige und $M\subset N$ für echte Teilmengen; oder aber $N\subset M$ für beliebige und $M\subsetneqq N$ für echte Teilmengen.
    \[\begin{tabular}{rccc}
        & Teilmenge & echte Teilmenge \\ \midrule
        Dieser Text & $\subseteq$ & $\subsetneq$ \\
        Alternative 1 & $\subseteq$ & $\subset$ \\
        Alternative 2 & $\subset$ & $\subsetneq$ oder $\subsetneqq$
    \end{tabular}\]
    Aufgrund seiner Mehrdeutigkeit werde ich das Zeichen $\subset$ nicht verwenden.
\end{nota}


\begin{bsp} \quad
    \begin{itemize}
        \item Es gilt $\N\subsetneq\Z\subsetneq\Q\subsetneq\R\subsetneq\C$.
        \item Es ist $\{\text{Spartaner}\}\subsetneq \{\text{Griechen}\}$. Zum Beispiel ist Thales von Milet\footnote{\href{https://de.wikipedia.org/wiki/Thales}{Thales von Milet (ca. 6. Jhd. v. Chr.)}} ein Grieche, der nicht aus Sparta stammt.
    \end{itemize}
\end{bsp}


\begin{bem}[Gleichheit von Mengen beweisen] \label{mengengleichbeweis}
    Aus \cref{teilmengebeweisen} und \cref{teilmengeneig} ergibt sich eine Methode, die Gleichheit zweier Mengen $M,N$ zu zeigen:
    \begin{labeling}
        \item[„$\subseteq$“] In einem ersten Schritt beweise, dass jedes Element von $M$ auch in $N$ liegt.
        \item[„$\supseteq$“] Im zweiten Schritt beweise, dass auch jedes Element von $N$ in $M$ liegt.
    \end{labeling}
    In Beweisen solltest du die Abschnitte, die den einzelnen Inklusionen $M\subseteq N$ und $N\subseteq M$ gewidmet sind, mit Markierungen deutlich machen.
\end{bem}


\begin{bsp} \label{bsp:mengengleichbeweis}
    Es ist $\{1,2,3\}=\{1,1,3,2\}$.
\end{bsp}
\begin{proof}
    \begin{labeling}
        \item[„$\subseteq$“] Sei $x\in\{1,2,3\}$, also $x=1$, $x=2$ oder $x=3$. In jedem dieser Fälle\footnote{vgl. \cref{auflistung} und \cref{fallunterscheidung}} gilt auch $x\in\{1,1,3,2\}$.
        \item[„$\supseteq$“] Sei umgekehrt $x\in\{1,1,3,2\}$,  also $x=1$, $x=1$, $x=3$ oder $x=2$. In jedem dieser Fälle gilt auch $x\in\{1,2,3\}$. \qedhere
    \end{labeling}
\end{proof}


\begin{bem} \label{mengenstrukturlos}
    An diesem Beispiel wird deutlich, dass die Elemente einer Menge keiner Reihenfolge oder „Platzierung“ unterliegen. Eine Menge $M$ trägt von sich aus bis auf ihre Elemente keine weitere Struktur. Fragen wie „Wie genau / Wie oft / An welcher Stelle ist $x$ in $M$ enthalten?“ kann sie nicht beantworten, sondern nur: „Ist $x$ in $M$ enthalten (oder nicht)?“ Zwar lässt sich durchaus fragen, wie viele Objekte einer gewissen Sorte in $M$ enthalten sind -- beispielsweise wieviele gelbe M\&Ms in einem Päckchen enthalten sind -- aber eben nicht, wie oft ein- und dasselbe Objekt in $M$ liegt. Hinsichtlich der Dualität zwischen Syntax und Semantik (\cref{syntaxvssemantik}) entsprechen Mengen Eigenschaften. Und es lässt sich ja auch nicht fragen, „wie oft“ ein Objekt eine gewisse Eigenschaft besitzt, sondern nur, \emph{ob} es sie besitzt (oder nicht).
    
    Um den Elementen dennoch verschiedene „Plätze“ zuzuweisen, können \emph{Familien}, die später in \cref{def:familie} eingeführt werden, verwendet werden. Ein weiteres Konzept, das die Elemente einer Menge in eine Art „Reihenfolge“ bringt, sind \emph{Ordnungsrelationen}, die in \cref{sec:ordnungsrelationen} eingeführt werden.
\end{bem}





\section{Die leere Menge}


\begin{defin} \index{Leere Menge} \index{Einermenge}
    Eine Menge heißt
    \begin{itemize}
        \item \textbf{leer}, wenn sie gar keine Elemente enthält.
        \item \textbf{nichtleer}, wenn sie nicht leer ist.\footnote{Im Englischen heißt eine Menge ``\href{https://en.wikipedia.org/wiki/Inhabited_set}{inhabited}'', wenn sie mindestens ein Element enthält.}
        \item eine \textbf{Einermenge} (englisch: ``singleton''), wenn sie genau ein Element enthält, also von der Form $\{x\}$ für irgendein Objekt $x$ ist.
    \end{itemize}
\end{defin}


\begin{satz} \label{leeremengeeind}
    Es gibt genau eine leere Menge.
\end{satz}


Ich werde den Beweis noch eine Weile aufschieben und in \cref{bew:leeremengeeind} nachreichen.


\begin{nota}[\textbf{Die} leere Menge]
    Im Sinne von \cref{kennzeichnung} können wir daher von \emph{der} leeren Menge sprechen. Die leere Menge wird meist notiert mit
        \[ \emptyset \]
    Angelehnt an \cref{auflistung} notieren manche Autoren die leere Menge auch mit „ $\{\}$ “.
\end{nota}


\begin{bsp}
    Es gilt:
    \begin{enumerate}
        \item Die Menge $M:=\{p\mid p\ \text{ist eine gerade Primzahl}\}$ ist nichtleer, weil die $2$ eine gerade Primzahl ist. Weil $2$ auch die einzige gerade Primzahl ist, ist sogar $M=\{2\}$, d.h. $M$ ist eine Einermenge.
        \item Die Menge $M:= \{ q\in \Q\mid q^2=6\}$ ist leer, d.h. $M=\emptyset$, da die $6$ keine rationale Quadratwurzel besitzt.
    \end{enumerate}
\end{bsp}


\begin{bem}[vacuous truths] \label{vacuoustruth} \index{vacuous truth}
    Betrachte einmal die beiden Allaussagen:
    \begin{itemize}
        \item „Alle rosa Elefanten können fliegen.“
        \item „Jedes fünfeckige Rechteck ist ein Quadrat.“
    \end{itemize}	
    Sowohl die Menge der rosa Elefanten als auch die Menge der fünfeckigen Rechtecke ist leer. Beide Allaussagen quantifizieren lediglich über eine leere Menge, sind also von der Gestalt
        \[ \forall x\in \emptyset:\ E(x) \]
    für eine gewisse Eigenschaft $E$. Es mag vielleicht überraschend klingen: Aussagen dieser Form sind grundsätzlich wahr!
    \begin{proof}
        Gemäß \cref{beschraenktquant} ist obige Formel gleichbedeutend zu
            \[ \forall x:\qquad x\in \emptyset\ \to\ E(x) \]
        Sei nun $x$ ein beliebiges Objekt (hier kommt die Beweistechnik aus \cref{allbeweis} zum Einsatz). Die Aussage $x\in\emptyset$ ist falsch, da die leere Menge keine Elemente enthält. Nach dem Prinzip \emph{ex falso quodlibet} aus \cref{exfalso} ist dann die Implikation $x\in \emptyset\ \to\ E(x)$ eine wahre Aussage. Weil das Objekt $x$ beliebig gewählt war, ist somit die Allaussage $\forall x: \left(x\in \emptyset\ \to\ E(x)\right)$ bewiesen.
	\end{proof}
    Aussagen, die den Elementen einer leeren Menge eine gewisse Eigenschaft zuordnen, etwa dass alle rosa Elefanen fliegen können oder dass jedes fünfeckige Rechteck ein Quadrat ist, sind also stets wahr, egal um welche Eigenschaft es sich handelt. Solche „leeren Wahrheiten“ werden im Englischen ``vacuous truths'' genannt.
\end{bem}


\begin{satz} \label{leeremengeimmerdrin}
    Sei $M$ eine Menge. Dann gilt $\emptyset\subseteq M$.

    Mit anderen Worten: Die leere Menge $\emptyset$ ist Teilmenge einer jeden beliebigen Menge.
\end{satz}
\begin{proof}
    Zu zeigen ist, dass jedes Element von $\emptyset$ auch ein Element von $M$ ist. Dies ist eine ``vacuous truth'' und somit eine wahre Aussage.
\end{proof}


\begin{proof}[von \cref{leeremengeeind}] \label{bew:leeremengeeind}
    Es gibt genau eine leere Menge, denn:

    (Existenz): Sei $\bot$ irgendeine Eigenschaft, die kein einziges Objekt besitzt (z.B. „$x\neq x$“). Dann ist $\{ x\mid \bot \}$ eine leere Menge.

    (Eindeutigkeit): Seien $M,N$ zwei leere Mengen. Nach \cref{leeremengeimmerdrin} sind es zwei ``vacuous truths'', dass jedes Element von $M$ auch eines von $N$ ist (also $M\subseteq N$) und ebenso jedes Element von $N$ auch eines von $M$ (also $N\subseteq M$). Aus \cref{teilmengeneig}c) folgt dann $M=N$.
\end{proof}





\section{Die Potenzmenge}


\begin{defin}[Potenzmenge] \label{def:potenzmenge} \index{Potenzmenge}
    Sei $M$ eine Menge. Die Menge aller Teilmengen von $M$ heißt die \textbf{Potenzmenge} von $M$ und wird mit „$\calP(M)$“ notiert:
    \begin{align*}
        \calP(M) := \{N \mid N \ \text{ist eine Teilmenge von $M$} \}
    \end{align*}
\end{defin}


\begin{bsp} \label{bsp:potenzmenge} \quad
    \begin{enumerate}
        \item(Triviale Teilmengen) Sei $M$ eine Menge. Nach \cref{leeremengeimmerdrin} und \cref{teilmengeneig}a) gilt auf jeden Fall $\emptyset\in \calP(M)$ und $M\in \calP(M)$.
        \item Für $M=\{1,2,3\}$ ist
            \[ \calP(M)=\left\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\right\} \]
    \end{enumerate}
    In manchen Büchern wird die Potenzmenge einer Menge $M$ mit „$2^M$“ notiert, woher der Name „Potenzmenge“ stammt. Es lässt sich zeigen: ist $n\in \N$ und enthält die Menge $M$ genau $n$-viele Elemente, so enthält $\calP(M)$ genau $2^n$-viele Elemente.
\end{bsp}


\begin{bem}
    Die Konzepte „Einermenge“ und „Potenzmenge“ erlauben es, Elementaussagen und Teilmengenaussagen ineinander zu überführen. Denn für Mengen $M,N$ und Objekte $x$ gilt:
        \[ x\in M\ \leftrightarrow\ \{x\}\subseteq M \quad\qquad\text{sowie}\quad\qquad M\subseteq N\  \leftrightarrow\ M\in \calP(N) \]
\end{bem}


\begin{vorschau}[* Mengen von Mengen von Mengen von \dots] \label{mengeniterativ}
    Das Konzept der Menge ist iterativ. Eine Menge kann auch wieder Element einer Menge sein, die wiederum in einer Menge enthalten sein kann usw.
    \begin{enumerate}[(1)]
        \item Zum Beispiel ist die Menge $\N$ ein Element der Einermenge $\{\N\}$, die wiederum ein Element der dreielementigen Menge $\{ \{\N \}, 4, \Z\}$ ist.
        \item(Zermelo'sche Zahlreihe) Es ist $\emptyset$ eine Menge, die überhaupt keine Elemente enthält, wohingegen $\{\emptyset\}$ eine Einermenge ist, deren einziges Element das Objekt $\emptyset$ ist. Insbesondere ist $\{\emptyset\}$ eine nichtleere Menge, also $\{\emptyset\}\neq \emptyset$. Somit haben auch die beiden Einermengen $\{\{\emptyset\}\}$ und $\{\emptyset\}$ zwei verschiedene Elemente, sind also ebenfalls voneinander verschieden. Iterativ erhält man eine unendliche Folge paarweise verschiedener Mengen:
        \[ \emptyset \ ,\quad \{\emptyset\} \ ,\quad \{\{\emptyset\}\} \ ,\quad \{\{\{\emptyset\}\}\} \ , \quad \{\{\{\{\emptyset\}\}\}\} \ ,\quad \dots \]
        welche auch \emph{Zermelo'sche Zahlreihe} genannt wird.
        \item Damit verwandt ist das \href{https://de.wikipedia.org/wiki/Nat\%C3\%BCrliche_Zahl#Von_Neumanns_Modell_der_nat\%C3\%BCrlichen_Zahlen}{von Neumannsche Modell der natürlichen Zahlen}. Beide Konstruktionen ermöglichen die Simulation natürlicher Zahlen durch gewisse Mengen und demonstrieren dadurch, dass sich der Begriff der natürlichen Zahl, wenn man es denn will, zurückführen lässt auf den Begriff der Menge.
        \item(Von-Neumann-Universum) Sei $X$ eine Menge und für $n \in \N$ sei\footnote{Zur Definition von $\cup$ siehe \cref{sec:mengenop}.}
        \[ \calP^n(X):=\underbrace{\calP(\dots\calP(}_{n\text{-mal}}X)) \qquad\text{und}\qquad V_n(X):=X\cup\calP^1(X)\cup\ldots\cup \calP^n(X) \]
        Man erhält eine aufsteigende Folge von Mengen
        \[ X=V_0(X) \subseteq V_1(X) \subseteq V_2(X) \subseteq V_3(X) \subseteq \ldots \]
        Aber diese \emph{kumulative Hierarchie} erschöpft sich selbst im Unendlichen nicht: Setzt man $V_\infty(X):=\bigcup_{n\in \N} V_n(X)$, so lässt sich im Anschluss ja fortfahren, indem man für $n\in \N$ definiert:
        \[ V_{\infty+n}(X):=V_\infty(X)\cup\calP^1(V_\infty(X))\cup\ldots\cup \calP^n(V_\infty(X)) \]
        So geht es immer weiter. Die Gesamtheit aller Mengen, die sich auf diesem Wege erzeugen lassen, also alle Mengen, deren Elemente sich in (möglicherweise unendlicher) verschachtelter Gestalt als „Mengen von Mengen von \dots von Elementen von $X$“ schreiben lassen, heißt das von $X$ erzeugte \emph{Von-Neumann-Universum}.\footnote{vgl. \cref{higherorder}}

        In der gewöhnlichen Mathematik werden davon nur die ersten paar Stufen benötigt. Beispielsweise verwendet man $\R$ zum Rechnen, $V_1(\R)$ zum Untersuchen von Stetigkeit und $V_2(\R)$ zum Vergleich verschiedener Topologien auf $\R$.
    \end{enumerate}
\end{vorschau}


\begin{defin}[Mengensystem] \index{System von Mengen} \index{Mengensystem}
    Eine Menge $\calM$ heißt ein \textbf{Mengensystem}, wenn jedes ihrer Elemente ebenfalls eine Menge ist.

    Ist $M$ irgendeine Menge, so ist beispielsweise jede Teilmenge $\calT\subseteq \calP(M)$ ein Mengensystem. Man nennt dann $\calT$ auch ein \textbf{System von Teilmengen von $M$}.
\end{defin}





\section{Familien}


Mit dem Begriff der Familie können wir einer Sammlung von Objekten eine zusätzliche Struktur verleihen: Statt uns nur zu merken, welche Objekte in unserer Sammlung enthalten sind (wie dies bei Mengen der Fall ist), unterscheiden wir nun verschiedene „Stellen“, an denen sich Objekte in der Sammlung befinden können. Realisiert wird das, indem wir die Objekte unserer Sammlung mit Indizes versehen und dann von dem „Objekt mit Index $i$ / an der Stelle $i$“ sprechen:


\begin{defin}[Familien] \label{def:familie} \index{Familie} \index{Indexmenge} \index{Einträge einer Familie}
    Eine \textbf{Familie} $a$ besteht aus
    \begin{itemize}
        \item Einer beliebigen Menge $I$, welche die \textbf{Indexmenge} der Familie genannt wird und deren Elemente die \textbf{Indizes} der Familie heißen.
        \item Für jeden Index $i\in I$ ein Objekt „$a_i$“, welches der \textbf{Eintrag an der $i$-ten Stelle} oder die \textbf{$i$-te Komponente} der Familie $a$ genannt wird.
    \end{itemize}
    Die Familie $a$ wird dann notiert als
    \begin{align*}
        (a_i)_{i\in I} && (\text{lies: „$a_i$, $i$ aus $I$“})
    \end{align*}
    Man spricht auch von einer \emph{Familie mit Indexmenge $I$} oder einer \textbf{durch $I$ indizierten Familie}.
\end{defin}


\begin{axiom}[Gleichheit von Familien] \label{familiengleich}
    Sind $I$ irgendeine Menge und $(a_i)_{i\in I}$ und $(b_i)_{i\in I}$ zwei durch $I$ indizierte Familien, so sind diese beiden Familien genau dann gleich, wenn sie an jedem Index denselben Eintrag besitzen. Als Formel:
    \begin{align*}
        (a_i)_{i\in I}=(b_i)_{i\in I} \qquad\leftrightarrow\qquad \forall i\in I:\ a_i=b_i
    \end{align*}
    Dementsprechend sind zwei solche Familien \emph{verschieden}, wenn sie sich an mindestens einem Index unterscheiden.
    
    Zwei Familien mit verschiedenen Indexmengen sind von vornherein voneinander verschieden.
\end{axiom}


\begin{nota} \label{mengeeinerfamilie} \quad
    \begin{itemize}
        \item Wenn ich, ohne vorher die Menge $I$ definiert zu haben, so etwas wie „Sei $(a_i)_{i\in I}$ eine Familie“ schreibe, so meine ich damit „Sei $I$ eine beliebige Menge und $(a_i)_{i\in I}$ eine Familie mit Indexmenge $I$“.
        \item Sei $a=(a_i)_{i\in I}$ eine Familie. Dann bezeichnet
            \[ \{a_i \mid i\in I\} := \{x\mid \exists i\in I:\ x=a_i \} \]
        die Menge der Einträge der Familie $a$. Beim Übergang von $(a_i)_{i\in I}$ zu $\{a_i\mid i\in I\}$ wird die Indizierung „vergessen“.
    \end{itemize}
\end{nota}


\begin{bsp} \quad
    \begin{enumerate}
	\item Nehmen wir als Indexmenge $I$ die Menge der belegten Stühle im Raum und als das Objekt $a_i$ die Person, die auf Stuhl $i$ sitzt, so erhalten wir eine Familie der hier im Raum sitzenden Leute $(a_i)_{i\in I}$. Sie unterscheidet sich von der \textit{Menge} der hier im Raum sitzenden Leute dadurch, dass sie auch die Information darüber, wer auf welchem Stuhl sitzt, enthält.
	
	Sind $i,j\in I$ zwei belegte Stühle und tauschen die Personen $a_i,a_j$ auf diesen beiden Stühlen ihre Plätze, so wird aus der Familie $(a_i)_{i\in I}$ der im Raum sitzende Leute eine neue Familie $(b_i)_{i\in I}$. Diese beiden Familien sind nicht gleich, denn es gilt $b_i=a_j\neq a_i$ und $b_j=a_i\neq a_j$.
	
	Dagegen hat sich die \emph{Menge} der im Raum sitzenden Leute durch den Sitzplatzwechsel nicht verändert, da sich noch immer dieselben Leute im Raum befinden (nur eben an anderen Stellen). Bei $\{a_i\mid i\in I\}$ und $\{b_i \mid i\in I\}$ handelt es sich also um dieselbe Menge, während $(a_i)_{i\in I}$ und $(b_i)_{i\in I}$ zwei verschiedene Familien sind.
	
    Hieran wird der Unterschied zwischen den Begriffen „Familie“ und „Menge“ deutlich. Zwei Mengen, welche genau dieselben Elemente enthalten, sind nach \cref{mengengleich} schon gleich; für eine Gleichheit von Familien müssen dagegen die Elemente sich auch noch an denselben „Stellen“ befinden. Im Gegensatz zu Mengen haben Familien also eine gewisse, durch die Indizierung gegebene, Zusatzstruktur.
	\item Bei Matrizen sowie den ``arrays'' aus der Informatik handelt es sich um spezielle Familien, siehe \cref{bsp:matrizen}.
    \end{enumerate}
\end{bsp}


\begin{defin}[Menge der Familien] \label{def:mengenpotenz}
    Seien $I,M$ zwei beliebige Mengen und $(a_i)_{i\in I}$ eine durch $I$ indizierte Familie. Ist jedes der $a_i$'s ein Element von $M$, so nennt man die Familie $(a_i)_{i\in I}$ eine \textbf{(durch $I$ indizierte) Familie mit Einträgen aus $M$} oder auch eine \textbf{$M$-wertige Familie}.
    
    Die Menge aller Familien mit Indexmenge $I$ und Einträgen aus $M$ wird mit $M^I$ notiert:
        \[ M^I := \{ (a_i)_{i\in I} \mid \forall i\in I:\ a_i \in M \} \]
    $M^I$ heißt auch die „$I$-te Potenz von $M$“, was aber nicht mit der Potenzmenge aus \cref{def:potenzmenge} verwechselt werden sollte.
\end{defin}


\begin{bsp}[* Folgen]
    Familien, deren Indexmenge die Menge $\N$ der natürlichen Zahlen ist, heißen \textbf{Folgen} und sind ein zentrales Thema in \cref{chap:analysis}. Für eine Menge $X$ ist $X^\N$ die Menge aller Folgen mit Einträgen aus $X$. Im Fall $X=\R$ spricht man von \emph{reellen Zahlenfolgen}. Elemente des „Folgenraums“ $\R^\N$ wären beispielsweise die Folge $(a_n)_{n\in\N}$ mit $a_n:=\frac{1}{n}$
    \[\begin{tabular}{c|cccccc}
            $n$ & $1$ & $2$ & $3$ & $4$ & $5$ & $\cdots$ \\
            \midrule
            $a_n$ & $1$ & $1/2$ & $1/3$ & $1/4$ & $1/5$ & $\cdots$
    \end{tabular}\]
    oder die Folge $(n^2)_{n\in \N}$ der Quadratzahlen. Analog sind $\Z^\N$, $\Q^\N$, $\C^\N$ die Mengen aller Folgen mit ganzzahligen/rationalen/komplexen Einträgen. Die Konstruktion ist iterierbar: Beispielsweise ist $(\Z^\N)^\N$ die Menge aller Folgen von Folgen von ganzen Zahlen.
\end{bsp}


\begin{defin}[Tupel] \label{def:tupel} \index{Tupel}
    Sei $n\in \N$ eine natürliche Zahl. Familien $(a_i)_{i\in I}$ mit der Indexmenge $I=\{1,\dots,n\}$ heißen \textbf{$n$-Tupel} und werden notiert in der Gestalt
        \[ (a_1,\dots,a_n)  \]
    2-Tupel, also Objekte der Form $(a,b)$, heißen \textbf{(geordnete) Paare}, 3-Tupel werden auch \textbf{Tripel} genannt.
    
    Ist $A$ eine Menge, so bezeichnet „$A^n$“ die Menge aller $n$-Tupel mit Einträgen aus $A$:
        \[ A^n := \{ (a_1,\dots , a_n) \mid a_1,\dots , a_n \in A \} \]
    Gemäß \cref{familiengleich} stimmen zwei $n$-Tupel genau dann überein, wenn sie komponentenweise übereinstimmen:
	\[ (a_1,\dots , a_n)=(b_1,\dots , b_n) \qquad\leftrightarrow\qquad a_1=b_1,\ \ldots\ ,\ a_n=b_n \]
\end{defin}


\begin{bsp} \label{bsp:vektoren}
    Es ist $\R^3$ die Menge aller Tripel reeller Zahlen:
        \[ \R^3 = \{(x,y,z) \mid x,y,z\in \R \} \]
    Diese Menge ist dir vielleicht schon aus der Schule bekannt. In der analytischen Geometrie repräsentieren die Elemente des $\R^3$ Punkte im Raum und die drei Einträge eines solchen Tripels repräsentieren seine Koordinaten bezüglich eines fixierten Koordinatensystems. In der Matrizenrechnung werden die Komponenten in einer senkrechten Anordnung notiert:
    \[\begin{pmatrix}
        x \\ y \\ z 
    \end{pmatrix} \]
    Man spricht von „Vektoren“. Hier wird auch die Signifikanz des Tupelbegriffs deutlich: Beispielsweise sind $\begin{psmallmatrix} 2 \\ 0 \\ 3 \end{psmallmatrix}$ und $\begin{psmallmatrix} 2 \\ 3 \\ 0 \end{psmallmatrix}$ zwei verschiedene Vektoren, denn sie unterscheiden sich in ihrer zweiten und dritten Komponente. Dagegen sind die \emph{Mengen} $\{2,0,3\}$ und $\{2,3,0\}$ identisch\footnote{vgl. \cref{bsp:mengengleichbeweis}}. Bei einer bloßen Menge gibt es keinen „zweiten Eintrag“ oder dergleichen.
\end{bsp}


\begin{defin}[* Leere Familie] \label{def:leerefam} \index{Leere Familie}
    Es gibt genau eine Familie, deren Indexmenge die leere Menge ist. Weil diese Familie keine Indizes hat, besitzt sie auch keine Einträge. Man spricht von der \textbf{leeren Familie} und notiert sie, ebenso wie die leere Menge, mit dem Zeichen $\emptyset$.
\end{defin}


\begin{bem}[* „Niedrige“ Potenzen]
    Sei $M$ eine beliebige Menge.
    \begin{itemize}
        \item(Nullte Potenz) Es ist eine ``vacuous truth'', dass alle Einträge der leeren Familie Elemente von $M$ sind. Daher ist $M^\emptyset=M^0 = \{\emptyset\}$ eine Einermenge, die als einziges Element die leere Familie enthält. Dies entspricht der Rechenregel $x^0=1$ für jede Zahl $x$.
        \item(Erste Potenz) Es ist $M^1 = \{(x)\mid x\in M\}$ die Menge aller „Eins-Tupel“ von Elementen aus $M$. Deren Elemente entsprechen letztendlich genau den Elementen von $M$. Oftmals wird zwischen $M$ und $M^1$ gar nicht unterschieden, was der Rechenregel $x^1=x$ entspricht.\footnote{In der Sprache von \cref{def:bijektiv} heißt das: Man hat eine „natürliche Bijektion“ zwischen $M$ und $M^1$. Für eine lange Liste weiterer Mengen, die auf eine solche Weise miteinander „identifiziert“ werden können, siehe \cref{anhang:natuerlichebijektionen}.}
    \end{itemize}
\end{bem}





\section{Operationen mit Mengen} \label{sec:mengenop}


\subsection*{Durchschnitt und Vereinigung}


\begin{defin} \index{Schnittmenge} \index{Durchschnitt von Mengen} \index{Vereinigungsmenge} \index{Differenzmenge} \index{Komplement} \label{def:capcup}
    Seien $M,N$ zwei Mengen.
    \begin{itemize}
        \item Der \textbf{Schnitt}\footnote{Die Bezeichnung kommt aus der Geometrie, wo der \emph{Schnitt}punkt zweier Geraden genau derjenige Punkt ist, der auf beiden Geraden zugleich liegt.} (oder auch \textbf{Durchschnitt} oder die \textbf{Schnittmenge}) von $M$ und $N$
        \begin{align*}
            M \cap N & := \{x \mid x \in M\ \text{und}\ x \in N\} && (\text{lies: „$M$ geschnitten $N$“})
        \end{align*}
        ist die Menge aller Objekte, die sowohl in $M$ als auch in $N$ enthalten sind.
        \item Die \textbf{Vereinigung} von $M$ und $N$
        \begin{align*}
            M \cup N & := \{x \mid x \in M\ \text{oder}\ x \in N\} && (\text{lies: „$M$ vereinigt $N$“})
        \end{align*}
        besteht aus denjenigen Objekten, die in mindestens einer der beiden Mengen $M,N$ enthalten sind.
        \item Die \textbf{Differenzmenge} von $M$ und $N$
        \begin{align*}
            M \setminus N & := \{ x \mid x \in M \ \text{und}\ x \notin N \}  && (\text{lies: „$M$ ohne $N$“})
        \end{align*}
        ist die Menge aller Elemente von $M$, die nicht in $N$ enthalten sind.

        Manche Autoren schreiben auch „$M-N$“ für die Differenzmenge. Ist $N$ eine Teilmenge von $M$, so schreibt man auch
        \begin{align*}
            N^c & := M\setminus N && (\text{sofern $N\subseteq M$})
        \end{align*}
        und spricht vom \textbf{(relativen) Komplement von $N$ (in $M$)}. Beachte, dass diese Schreibweise nur Sinn ergibt, wenn aus dem Kontext heraus klar ist, dass das Komplement in der Obermenge $M$ zu bilden ist. Manche Autoren schreiben auch „$\calC_M(N)$“ für das Komplement von $N$ in $M$. Ich werde diese Schreibweise aber nicht verwenden.
	\end{itemize}
    \begin{figure}[ht]
        \begin{minipage}{.48\textwidth}
            \centering
            \begin{tikzpicture}[scale=.75]
                \begin{scope}
                \clip (-1,0) circle (1.5cm);
                \fill[blue!30!white] (1,0) circle (1.5cm);
                \end{scope}
                \draw (-1,0) circle (1.5cm) (-1,-1) node {$M$} (1,0) circle (1.5cm) (1,-1) node {$N$};
            \end{tikzpicture}
            \caption{Schnitt $M\cap N$}
        \end{minipage}
        \quad
        \begin{minipage}{.48\textwidth}
            \centering
            \begin{tikzpicture}[scale=.75]
                \filldraw[fill=blue!30!white, draw=black] (-1,0) circle (1.5cm) (-1,-1) node {$M$} (1,0) circle (1.5cm) (1,-1) node {$N$};
            \end{tikzpicture}
            \caption{Vereinigung $M\cup N$}
        \end{minipage}
        \quad\\[1em]
        \begin{minipage}{.48\textwidth}
            \centering
            \begin{tikzpicture}[scale=.75]
                \fill[blue!30!white] (-1,0) circle (1.5cm);
                \begin{scope}
                \clip (-1,0) circle (1.5cm);
                \fill[white] (1,0) circle (1.5cm);
                \end{scope}
                \draw (-1,0) circle (1.5cm) (-1,-1) node {$M$} (1,0) circle (1.5cm) (1,-1) node {$N$};
            \end{tikzpicture}
            \caption{Differenz $M\setminus N$}
        \end{minipage}
        \quad
        \begin{minipage}{.48\textwidth}
            \centering
            \begin{tikzpicture}[scale=.75]
                \filldraw[fill=blue!25!white, draw=black] (0,0) ellipse (2cm and 1.3cm);
                \filldraw[fill=white!25!white, draw=black] (.5,0) ellipse (1cm and .7cm);
                \path (-1.2,0) node {$N^c$} (0,-1) node {$M$} (.5,0) node {$N$};
            \end{tikzpicture}
            \caption{Komplement von $N$ in $M$}
        \end{minipage}
    \end{figure}
\end{defin}


\begin{bsp} \quad
    \begin{enumerate}
        \item Seien $ M = \{1, 2, 4\}$ und $N = \{1, 4, 7\}$. Dann gilt: 
	\begin{align*}
            M \cap N &= \{1, 4\} & M \cup N &= \{1, 2, 4, 7\} & M \setminus N &= \{2\}
	\end{align*}
        \item Für $n\in \N$ bezeichne
            \[ n\Z := \{ m\in \Z \mid \exists k\in \Z:\ m=kn \} \]
        die Menge aller ganzzahligen Vielfachen von $n$, d.h. aller ganzen Zahlen, die durch $n$ teilbar sind. Dann wurde in \cref{bsp:hinruck} bewiesen, dass
            \[ 2\Z \cap 3\Z = 6\Z \]
        Für $m,n\in \N$ gilt allgemein $m\Z\cap n\Z = \kgV(m,n)\Z$, wobei „$\kgV(m,n)$“ das kleinste gemeinsame Vielfache von $m$ und $n$ bezeichnet.
    \end{enumerate}
\end{bsp}


\begin{defin}[Mengenfamilie] \index{Mengenfamilie}
    Eine \textbf{Mengenfamilie} (oder auch: \emph{Familie von Mengen}) ist eine Familie, deren Einträge allesamt Mengen sind.
\end{defin}


\begin{bsp}
    Beispielsweise ist $(\{1,\dots , n\})_{n\in \N}$ eine Familie von Teilmengen von $\N$, deren Einträge genau die „Anfangsabschnitte“ von $\N$ sind.
\end{bsp}


\begin{defin}[Schnitte und Vereinigungen beliebig vieler Mengen] \label{def:mehrfachcapcup}
    Sei $(M_i)_{i\in I}$ eine Familie von Mengen. Es heißen
    \begin{align*}
        \bigcap_{i\in I} M_i &:= \{x \mid \forall i\in I:\ x\in M_i\} & \bigcup_{i\in I}M_i &:= \{x \mid \exists i\in I:\ x\in M_i\}
    \end{align*}
    der \textbf{Durchschnitt} und die \textbf{Vereinigung} der $M_i$'s.
    
    Ist $\calM$ eine Menge, deren Elemente ebenfalls allesamt Mengen sind, so schreibt man
    \begin{align*}
        \bigcap \calM & := \{ m \mid \forall M\in \calM:\ m\in M \} & \bigcup \calM & := \{m\mid \exists M\in \calM:\ m\in M \}
    \end{align*}
    und spricht von \emph{Durchschnitt} und \emph{Vereinigung} von $\calM$.
\end{defin}


\begin{nota} \label{alternativmehrfachcapcup}
    Ist die Indexmenge von der Form $I=\{1,\dots,n\}$ für eine natürliche Zahl $n\in \N$, so schreibt man:\footnote{vgl. \cref{mehrfachprodukt}}
    \begin{align*}
        M_1\cap \ldots\cap M_n & := \bigcap_{i=1}^n M_i := \smashoperator[r]{\bigcap_{i\in \{1,\dots , n\}}} M_i \\
        M_1\cup \ldots\cup M_n & := \bigcup_{i=1}^n M_i := \smashoperator[r]{\bigcup_{i\in \{1,\dots , n\}}} M_i
    \end{align*}
\end{nota}


\begin{bsp}
    Sei $H$ die Menge aller Lustigen Taschenbücher und für $h\in H$ sei $L_h$ die Menge aller Menschen, die das Comicbuch $h$ gelesen haben. Dann ist $\bigcap_{h\in H} L_h$ die Menge aller Leute, die \emph{jedes} LTB gelesen haben. Dagegen ist $\bigcup_{h\in H} L_h$ die Menge aller Leute, die schonmal irgendein LTB gelesen haben.
\end{bsp}


\begin{bem}[Mengen-Operatoren vs. Aussagen-Operatoren]
    Die Operationen $\cap$ und $\cup$ sind in gewisser Weise mengentheoretische „Realisierungen“ der aussagenlogischen Junktoren $\land$ und $\lor$. Deshalb sehen sich auch die Zeichen so ähnlich. Trotzdem solltest du $\cap$ und $\cup$ sorgfältig von $\land$ und $\lor$ unterscheiden: Der Ausdruck „$M\cap N$“ ergibt nur Sinn, wenn $M$ und $N$ Mengen sind; der Ausdruck „$A\wedge B$“ dagegen nur, wenn $A$ und $B$ Aussagen sind.
    \begin{center}
    \begin{tabular}{rccccc}
        Mengenoperation: & $M\cap N$ & $M\cup N$ & $N^c$ & $\bigcap_{i\in I} M_i$ & $\bigcup_{i\in I} M_i$ \\ \midrule
        Logikoperation: & $A\land B$ & $A \lor B$ & $\neg B$ & $\forall x: E(x)$ & $\exists x: E(x)$
    \end{tabular}
    \end{center}
\end{bem}


\subsection*{Produkt}


\begin{defin}[Produkte von Mengen] \index{Produkt von Mengen} \index{Kartesisches Produkt}
    Sei $(M_i)_{i\in I}$ eine Familie von Mengen. Die Menge
        \[ \prod_{i\in I} M_i := \{ (x_i)_{i\in I} \mid \forall i\in I:\ x_i\in M_i \} \]
    aller durch $I$ indizierten Familien, an deren $i$-ter Stelle jeweils ein Element aus $M_i$ steht (für jedes $i\in I$), heißt das \textbf{(kartesische) Produkt} der $M_i$'s.

    Ist die Indexmenge von der Gestalt $I=\{1,\dots , n\}$ für ein $n\in \N$, so schreibt man\footnote{vgl. \cref{mehrfachprodukt}}
        \[ M_1\times\ldots\times M_n := \prod_{i=1}^n M_i := \smashoperator[r]{\prod_{i\in \{1,\dots , n\}}} M_i   \]
    Per Definition ist
        \[ M_1\times\ldots\times M_n = \{ (x_1,\dots , x_n) \mid x_1\in M_1,\ \ldots,\ x_n\in M_n \} \]
    die Menge aller $n$-Tupel, deren $i$-ter Eintrag jeweils ein Element von $M_i$ ist (für jedes $i\in \{1,\dots , n\}$).
    Insbesondere ist für zwei Mengen $M$ und $N$
    \begin{align*}
        M \times N & = \left\{ (x,y) \mid x\in M\ \text{und}\ y\in N \right\}  && (\text{lies: „$M$ kreuz $N$“})
    \end{align*}
    die Menge aller geordneten Paare, deren erster Eintrag aus $M$ und deren zweiter Eintrag aus $N$ stammt. Man spricht vom \emph{(kartesischen) Produkt} von $M$ und $N$.
\end{defin}


\begin{bsp} \quad
    \begin{enumerate}
        \item Es ist
            \[ \{2,3,4\}\times \{ \clubsuit,\heartsuit\} = \{ (2,\clubsuit), (3,\clubsuit), (4,\clubsuit), (2,\heartsuit), (3,\heartsuit), (4,\heartsuit) \}\]
        \item Es ist $\R\times \R=\R^2$ und die Elemente von $\R\times \R$ können als Koordinaten von Punkten in der Ebene interpretiert werden. Die Grundidee der analytischen Geometrie, Punkte und geometrische Figuren mithilfe von Koordinatensystemen als Lösungsmengen algebraischer Gleichungen zu beschreiben, wird traditionell Descartes\footnote{\href{https://de.wikipedia.org/wiki/Rene_Descartes}{René Descartes (1596-1650)}} (latinisiert: Cartesius) zugeschrieben. Daher die Rede vom „kartesischen“ Produkt.
        \begin{comment}
        \item Dagegen lässt sich $\N\times\N$ als zweidimensionales „Gitter“ veranschaulichen:
            \[ \begin{matrix}
                \vdots &&&& \\
                (0,3) & \vdots &&& \\
                (0,2) & (1,2) &&& \\
                (0,1) & (1,1) & (2,1) & \cdots & \\
                (0,0) & (1,0) & (2,0) & (3,0) & \cdots
            \end{matrix} \]
        \end{comment}
    \end{enumerate}
\end{bsp}


\begin{bsp}[* Matrizen und arrays] \label{bsp:matrizen} \index{Matrix} \quad
    \begin{enumerate}
        \item Seien $m,n\in \N$ und $M=\{1,\dots , m\}$, $N=\{1,\dots,n\}$. Dann ist
            \[ M\times N = \{ (i,j) \in \N\times \N \mid 1\le i\le m \ \text{und}\ 1\le j \le n \} \]
        die Menge aller Paare natürlicher Zahlen, deren erster Eintrag zwischen $1$ und $m$ und deren zweiter Eintrag zwischen $1$ und $n$ liegt.

        Familien mit Indexmenge $M\times N$ werden \textbf{($m\times n$)-Matrizen} genannt. Die Einträge einer Matrix werden in einem zweidimensionalen Schema (in „Matrixgestalt“) aufgelistet, wobei der erste Index die Zeile und der zweite Index die Spalte markiert:
        \begin{align*}
            \begin{pmatrix}
                a_{11} & \cdots & a_{1n} \\
                \vdots && \vdots \\
                a_{m1} & \cdots & a_{mn}
            \end{pmatrix}
        \end{align*}
        Ist $M$ irgendeine Menge, so wird mit
        \begin{align*}
            M^{m\times n} := M^{\{1,\dots , m\}\times \{1,\dots , n\}}
        \end{align*}
        die Menge aller $(m\times n)$-Matrizen mit Einträgen aus $M$ notiert. Beispielsweise ist $\R^{m\times n}$ die Menge aller $(m\times n)$-Matrizen, deren Einträge reelle Zahlen sind. Solche Matrizen sind ein zentrales Studienobjekt der Linearen Algebra.
        \item Seien $n\in \N$, $m_1,\dots , m_n\in \N$ und $M_i:=\{1,\dots , m_i\}$ für $i\in \{1,\dots , n\}$. Eine Familie mit Indexmenge $M_1\times\ldots\times M_n$ kannst du dir als „$n$-dimensionale Matrix“ vorstellen. In der Informatik werden solche Objekte „$n$-dimensionale arrays“ genannt. In Physik und multilinearer Algebra werden sie zur Koordinatendarstellung von \emph{Tensoren} verwendet.
    \end{enumerate}
\end{bsp}


\begin{bem}[Potenz als Produkt mit sich selbst]
    Seien $I,M$ zwei Mengen und $(M)_{i\in I}$ die „konstante Familie“, die an jedem Eintrag die Menge $M$ stehen hat. Dann ist $\prod_{i\in I} M$ schlicht die Menge $M^I$ aus \cref{def:mengenpotenz}. Ebenso gilt für jede natürliche Zahl $n$:
        \[ M^n = \underbrace{M\times\ldots\times M}_{\text{$n$-mal}} \]
    sodass beispielsweise $\R\times \R\times \R= \R^3$.

    Also ist $M^I$ eine Art „$I$-faches Produkt von $M$ mit sich selbst“, genauso wie für zwei natürliche Zahlen $m,n\in \N$ die Potenz $m^n$ das $n$-fache Produkt von $m$ mit sich selbst ist:
        \[ m^n := \underbrace{m\cdot\ldots\cdot m}_{\text{$n$-mal}}\]
    Aus diesem Grund wird $M^I$ die „$I$-te Potenz von $M$“ genannt.
\end{bem}


\begin{vorschau}[* Auswahlaxiom] \label{auswahlaxiom} \index{Auswahlaxiom} \index{intangible}
    Sind $M,N$ zwei nichtleere Mengen, etwa mit Elementen $x\in M$ und $y\in N$, so ist auch das kartesische Produkt $M\times N$ nichtleer, weil $(x,y)\in M\times N$. Ist dagegen $(M_i)_{i\in I}$ eine Familie unendlich vieler nichtleerer Mengen, so ist es, sofern keine weiteren Informationen über die Mengen $M_i$ bekannt sind, unmöglich, zu zeigen, dass auch das Produkt $\prod_{i\in I} M_i$ nichtleer ist.

    Sei zum Beispiel $I:= \calP(\R)\setminus \{\emptyset\}$ die Menge aller nichtleeren Teilmengen von $\R$. Du kannst ja mal versuchen, ein konkretes Element von $\prod_{M\in I} M$ hinzuschreiben, was darauf hinausläuft, irgendwie aus jeder nichtleeren Teilmenge von $\R$ ein Element „auszuwählen“.

    Einige (nichtkonstruktive) Sätze der modernen Mathematik sind nun allerdings darauf angewiesen, dass Produkte beliebig vieler nichtleerer Mengen stets nichtleer sind. Daher bildet genau diese Aussage ein eigenes Axiom, das sogenannte \href{https://en.wikipedia.org/wiki/Axiom_of_choice}{Auswahlaxiom}.

    Dabei handelt es sich um ein \emph{nichtkonstruktives} Axiom: es behauptet die Existenz eines Elements, ohne eine Anleitung für dessen Konstruktion an die Hand zu geben.\footnote{In der „konstruktiven Mathematik“ (vgl. \cref{nichtkonstruktiv}) wird das Auswahlaxiom daher nicht akzeptiert. Im mathematischen Mainstream, dem auch die Vorlesungen folgen, wird es dagegen bedenkenlos eingesetzt.} Mathematische Objekte, deren Existenz zwar abstrakt bewiesen werden kann, die sich aber nicht konkret beschreiben oder konstruieren lassen, werden im Englischen \emph{intangibles} genannt. Beispielsweise handelt es sich bei den Elementen von $\prod_{M\in \calP(\R)\setminus \{\emptyset\}} M$ um intangibles.
\end{vorschau}





\subsection*{* Disjunkte Vereinigung}


\begin{defin}[Disjunktheit] \label{def:disjunkt} \index{disjunkte Mengen}
    Zwei Mengen $M,N$ heißen \textbf{disjunkt}, wenn sie keine gemeinsamen Elemente haben, also wenn $M\cap N=\emptyset$.

    Eine Familie von Mengen $(M_i)_{i\in I}$ heißt \textbf{paarweise disjunkt}, wenn je zwei der $M_i$'s disjunkt sind, d.h. wenn gilt:
    \begin{align*}
        M_i\cap M_j \neq  \emptyset \quad& \to\quad i=j &&\text{für alle $i,j\in I$}
    \end{align*}
    Sind $M,N$ zwei disjunkte Mengen, so wird deren Vereinigung auch eine \textbf{disjunkte Vereinigung} genannt und mit
    \begin{align*}
        M\ \dot\cup\ N & := M\cup N && (\text{sofern $M,N$ disjunkt sind})
    \end{align*}
    notiert. Beachte, dass „$\dot\cup$“, anders als es der Vergleich mit \cref{entwederoder} vielleicht nahelegt, keine neue Mengenoperation darstellt, sondern schlicht die Vereinigung aus \cref{def:capcup}.\footnote{Die mengentheoretische „Realisierung“ des Entweder-Oder $\dot\lor$ ist die \emph{symmetrische Differenz}: \\
    $M\vartriangle N:= (M\setminus N)\ \dot\cup\ (N\setminus M)$} Der Punkt dient lediglich zur Mitteilung darüber, dass die beiden Mengen, von deren Vereinigung die Rede ist, disjunkt sind.

    Ebenso wird die Vereinigung einer Familie $(M_i)_{i\in I}$ paarweiser disjunkter Mengen deren \emph{disjunkte Vereinigung} genannt. Man schreibt:
    \begin{alignat*}{2}
        \dot{\smashoperator[r]{\bigcup_{i\in I}}}\ & M_i\ & := \smashoperator{\bigcup_{i\in I}} M_i \qquad &(\text{sofern die $M_i$'s paarweise disjunkt sind}) \\
        \intertext{Für ein System $\calM$ paarweise disjunkter Mengen schreibt man:}
        \dot{\bigcup}\ & \calM & := \bigcup \calM \qquad &(\text{sofern die Elemente von $\calM$ paarweise disjunkte Mengen sind})
    \end{alignat*}
\end{defin}


\begin{bsp} \label{bsp:disjunkt} \quad
    \begin{enumerate}
        \item Die Mengen $\{\text{Spieler der TSG Hoffenheim}\}$ und $\{\text{Spieler des FSV Mainz 05}\}$ sind disjunkt, weil kein Spieler zugleich bei beiden Vereinen verpflichtet ist.
        \item Die Mengen $\{\text{Informatikstudenten}\}$ und $\{\text{Mathestudenten}\}$ sind nicht disjunkt, weil manche Leute auch beide Fächer zugleich studieren.
        \item Es ist
        \begin{align*}
        \{1,2,3,4,5\} & = \{1,3,4\}\ \dot\cup\ \{2,5\} \\
        \Z & = \N_0\ \dot\cup\ \Z_{<0}
        \end{align*}
    \end{enumerate}
\end{bsp}


\begin{bem}
    Die Vereinigung einer paarweise disjunkten Mengenfamilie kannst du dir als eine Art „Addition“ vorstellen. Beispielsweise lässt sich zeigen: sind $m,n\in \N$ und $M$ eine Menge mit $m$-vielen Elementen, $N$ eine zu $M$ disjunkte Menge mit $n$-vielen Elementen, so enthält die disjunkte Vereinigung $M\ \dot\cup\ N$ genau $(m+n)$-viele Elemente.

    Für nicht-disjunkte Vereinigungen gilt das aber nicht. Beispielsweise ist
        \[\{1,3,4\} \cup \{2,3\}= \{1,2,3,4\} \]
    d.h. in diesem Beispiel enthält die Vereinigung einer dreielementigen Menge mit einer zweielementigen Menge nur vier Elemente.

    Aber auch nicht-disjunkte Mengen können aufeinander „addiert“ werden mithilfe des folgenden Tricks: Ist $(M_i)_{i\in I}$ eine beliebige (nicht notwendig paarweise disjunkte) Mengenfamilie, so können die $M_i$'s „künstlich disjunkt gemacht“ werden durch Übergang zu den Mengen
    \begin{align*}
        \{i\}\times M_i &= \{(i,x) \mid x\in M_i\} && i\in I
    \end{align*}
    Die Elemente von $\{i\}\times M_i$ kannst du dir vorstellen als „Klone“ der Elemente von $M_i$, welche mit einem „Marker“ versehen wurden, der ihre Zugehörigkeit zu $M_i$ kennzeichnet und sie von den Elementen von $\{j\}\times M_j$ für $j\in I\setminus \{i\}$ unterscheidet. Die Mengenfamilie $(\{i\}\times M_i)_{i\in I}$ ist nun paarweise disjunkt.
\end{bem}


\begin{defin}[Disjunkte Vereinigung] \label{def:disjunktcup} \index{Disjunkte Vereinigung}
    Sei $(M_i)_{i\in I}$ eine Familie von Mengen. Die Menge
        \[ \bigsqcup_{i\in I} M_i := \bigcup_{i\in I} (\{i\}\times M_i) = \{(i,x) \mid i\in I,\ x\in M_i \}\]
    heißt die (äußere) \textbf{disjunkte Vereinigung} der $M_i$'s.
    
    Ist die Indexmenge $I$ von der Gestalt $I=\{1,\dots , n\}$ für ein $n\in \N$, so schreibt man
        \[ M_1\sqcup\ldots\sqcup M_n := \bigsqcup_{i=1}^n M_i := \smashoperator[r]{\bigsqcup_{i\in \{1,\dots , n\}}} M_i \]
    Insbesondere ist für Mengen $M,N$:
        \[ M\sqcup N = \{ (i,x)\mid i=1\ \text{und}\ x\in M\quad\text{oder}\quad i=2\ \text{und}\ x\in N\} \]
    Man spricht von der \emph{disjunkten Vereinigung von $M$ und $N$}.
\end{defin}


\begin{bsp}
    Es ist
        \[\N \sqcup\N=\{(1,1),(1,2),(1,3),(1,4)\dots,(2,1),(2,2),(2,3),(2,4)\dots\} \]
    d.h. die Menge $\N\sqcup \N$ besteht aus zwei „Kopien“ von $\N$. Für jede natürliche Zahl $n$ enthält sie jeweils zwei „Klone“ von $n$, realisiert als $(1,n)$ und $(2,n)$.
    \begin{comment}
    \begin{figure}[ht]
    \begin{tikzpicture}
        \begin{scope}[xshift=-5cm,scale=1.5]
            \draw[step=.5cm,style=help lines] (-1,-.1) grid (1.3,.1);
            \draw[->,thick] (-1,0) -- (1.5,0) node[right] {$\N$};
            \foreach \x in {1,2,3,4,5}
            \draw[xshift=.5*\x cm] (-1.5,-.1) node[below] {\x};
        \end{scope}
        \begin{scope}[scale=1.5, xshift= 0.4cm]
            \draw[style=help lines,step=.5 cm] (-1.3,-.1) grid (1.3,1.3);
            \begin{scope}
                \draw[->, thick] (-1.3,0) -- (1.5,0) node[right] {$\N$};
                \draw[thick] (-1.2,-.1) -- (-1.2,1.4) node[above] {$\{1,2\}$} coordinate(y axis);
                \foreach \x in {1,2,3,4,5}
                \draw[xshift=.5*\x cm] (-1.5,-.1) node[below] {\x};
                \foreach \y in {1,2}
                \draw[yshift=.5*\y cm] (-1.3,0) node[left] {\y};
            \end{scope}
        \end{scope}
        \begin{scope}[scale=1.5,xshift=4cm]
            \draw[style=help lines,step=.5 cm] (-1.3,-.1) grid (1.3,2.3);
            \begin{scope}
                \draw[->, thick] (-1.3,0) -- (1.5,0) node[right] {$\N$};
                \draw[->, thick] (-1.2,-.1) -- (-1.2,2.5) node[above] {$\N$} coordinate(y axis);
                \foreach \x in {1,2,3,4,5}
                \draw[xshift=.5*\x cm] (-1.5,-.1) node[below] {\x};
                \foreach \y in {1,2,3,4}
                \draw[yshift=.5*\y cm] (-1.3,0) node[left] {\y};
            \end{scope}
        \end{scope}
    \end{tikzpicture}
    \centering \caption{Vergleich von $\N\cup\N\ (=\N)$, $\N\sqcup\N$ und $\N\times\N$.}
    \end{figure}
    \end{comment}
\end{bsp}
    
    
\begin{bem}[Produkt als Summe mit sich selbst]
    Seien $I,M$ zwei Mengen und $(M)_{i\in I}$ die „konstante Familie“, die an jedem Eintrag die Menge $M$ stehen hat. Dann ist $\bigsqcup_{i\in I} M_i$ genau das kartesische Produkt $I\times M$. Ebenso gilt für alle $n\in \N$:
        \[ \{1,\dots , n\} \times M = \underbrace{M\sqcup\ldots\sqcup M}_{\text{$n$-mal}} \]
    Also ist $I\times M$ die „$I$-fache Summe von $M$ mit sich selbst“, genauso wie für zwei natürliche Zahlen $m,n\in \N$ das Produkt $n\cdot m$ die $n$-fache Summe von $m$ mit sich selbst ist:
        \[ n\cdot m := \underbrace{m +\ldots + m}_{\text{$n$-mal}}\]
\end{bem}


\begin{vorschau}
    Der Ausdruck „disjunkte Vereinigung“ ist nun mehrdeutig:%mit mehreren Bedeutungen „überladen“.
    \begin{enumerate}[(1)]
        \item Zum einen bezeichnet er die disjunkte Vereinigung aus \cref{def:disjunktcup}, also die Konstruktion, mit der Mengen zuerst „künstlich disjunkt“ gemacht und daraufhin „addiert“ werden. Ich habe dafür folgende Notation verwendet:
            \[ M\sqcup N \qquad\text{bzw.}\qquad \bigsqcup_{i\in I} M_i \]
        \item Zum anderen bezeichnet er die gewöhnliche Vereinigung einer Familie paarweiser disjunkter Mengen aus \cref{def:disjunkt}, was ich notiert habe mit
            \[ M\ \dot\cup\ N \qquad\text{bzw.}\qquad   \dot{\bigcup_{i\in I}}\ M_i \]
    \end{enumerate}
    Hinzu kommt, dass in der Literatur beide Notationen durcheinander verwendet werden, d.h. sowohl die Objekte (1) als auch die Objekte (2) werden mal mit „$\dot\cup$“, mal mit „$\sqcup$“ bezeichnet.
    
    Tatsächlich ist es in den meisten Fällen gar nicht wichtig, wie genau die disjunkte Vereinigung „$M \sqcup N$“ definiert ist, d.h. wie ganau man die Mengen $M,N$ künstlich disjunkt gemacht hat. Die disjunkte Vereinigung bezieht ihre Signifikanz aus der kategorientheoretischen Eigenschaft, ein \emph{Koprodukt} zu sein. In dieser Hinsicht ist sie ein genaues Gegenstück zum kartesischen Produkt. Mehr darüber wirst du in Vorlesungen und Büchern über Kategorientheorie lernen.
\end{vorschau}





\clearpage
\section{Aufgabenvorschläge}


\begin{aufg}[Kennenlernen]
    Es sei $T$ die Menge aller Leute, die sich gerade in diesem Tutorium befinden.
    Welche der folgenden Mengen sind Teilmengen voneinander? Welche Mengen sind disjunkt oder gleich?
    \begin{align*}
        S&:= \{ x\in T \mid x\ \text{ist sportlich} \}  && \emptyset  \\
        N&:=  \{ x\in T \mid x\ \text{geht gern in die Natur} \} && T \\
        W & := \{ x\in T \mid x\ \text{kennt sich auf einem Spezialgebiet richtig gut aus} \} &&  N\setminus S  \\
        M &:= \{ x \in T \mid x\ \text{spielt ein Musikinstrument} \} && W \cup S
    \end{align*}
\end{aufg}


\begin{aufg}[Mengen vs. Familien (L)] \label{aufg:mengenvsfamilien}
    Es sei $I:=\{1,2,3,4,5\}$ und es sei $a=(a_i)_{i\in I}$ diejenige Familie mit $a_i=i+2$ für jedes $i\in I$. Welche der folgenden Objekte sind einander gleich und welche sind voneinander verschieden?
    \begin{center}
    {\renewcommand{\arraystretch}{1.6}
    \begin{tabular}{ccccccccc}
        $I$ && $(a_i)_{i\in I}$&& $\{a_i\mid i\in I\}$ && $(4,3,5,6,7)$ && $(2,1,3,4,5,5)$ \\
        $a$ && $\{1,2,3,4,5\}$ && $(3,4,5,6,7)$ && $\{4,3,5,6,7\}$ && $\{2,1,3,4,5,5\}$
	\end{tabular}}
    \end{center}
\end{aufg}


\begin{aufg}[Elemente und Teilmengen (L)] \label{aufg:elemente}
    Beurteilt für jede der folgenden Aussagen, ob sie wahr oder falsch ist:
    \begin{align*}
        \N&  \in \N & \N & \subseteq \N & \N & \in \calP(\N) &  \N & \subseteq \calP(\N) \\
        \N & \in \{ \N\} & \N & \subseteq \{ \N\} & \{ \N\} & \in \{ \N\} & \{\N\} & \subseteq \{ \N\} \\
        \{\N\} & \in \calP(\N) & \{ \N\} & \subseteq \calP(\N) & \calP(\N) & \in \calP(\N) & \calP(\N) & \subseteq \calP(\N) \\
        \emptyset & \in \emptyset & \emptyset &\subseteq \emptyset & \emptyset & \in \calP(\emptyset) & \{\emptyset\} & = \calP(\emptyset)
    \end{align*}
\end{aufg}


\begin{aufg}[Rechenregeln für Mengen]
    Sucht euch drei Formeln aus der Formelsammlung in \cref{anhang:capcupregeln}, \cref{anhang:bigcapcupregeln} und \cref{anhang:prodregeln} raus, illustriert sie jeweils an einem Beispiel und begründet ihre Allgemeingültigkeit.
\end{aufg}


\begin{aufg}[Tupel als strings]
    Wir betrachten die Mengen $T := \{ \text{Dr.} \}, A := \{ \text{Herr, Frau} \}$, $V:= \{ \text{Anne, John} \}$ und $N := \{ \text{Hathaway, Sinclair, Wayne} \}$. Listet die Elemente der folgenden Mengen auf:
    \begin{enumerate}
	\item $A \times N$
	\item $A\times T \times V\times N$
	\item $(T \cup V) \times N$
	\item $(T\times N)\cup (V\times N)$
    \end{enumerate}
\end{aufg}