Präsenzblatt 3
Aufgabe PA 9
Es seien \( A \) und \( B \) zwei nichtleere Mengen und \( f\colon A\to B \) sowie \( g\colon B\to A \) zwei Abbildungen mit \[ g\circ f(a):=g(f(a))=a\quad\mbox{für alle}\ a\in A. \] Beweisen Sie, dass dann \( f \) injektiv und \( g \) surjektiv sind.
| \( \circ \) | Wir zeigen, dass \( f \) injektiv ist. Denn angenommen \( f(x)=f(y) \) mit \( x,y\in A, \) dann ist |
|
|
|
| Also ist \( f \) injektiv. | |
| \( \circ \) | Wir zeigen, dass \( g \) surjektiv ist. Wähle dazu \( x\in A \) beliebig, dann ist |
|
|
|
| Also ist \( g \) surjektiv. |
Damit sind alle Behauptungen gezeigt.\( \qquad\Box \)
Aufgabe PA 10
Wir betrachten die aus der Vorlesung bekannte Relation \( \sim_{\mathbb Z}. \)
| (i) | Beweisen Sie, dass \( \sim_{\mathbb Z} \) eine Äquivalenzrelation auf \( \mathbb N_0\times\mathbb N_0 \) darstellt. |
| (ii) | Beschreiben Sie mit eigenen Worten die Äquivalenzklassen. |
Wir zeigen nur (i). Dazu schreiben wir die Relation in der Form \[ (m_1,n_1)\sim_{\mathbb Z}(m_2,n_2)\quad\Longleftrightarrow\quad m_1+n_2=n_1+m_2\,. \] Es handelt sich um eine Äquivalenzrelation, denn wir verifizieren:
| \( \circ \) | Reflexivität: Es gilt \( (m,n)\sim_{\mathbb Z}(m,n), \) denn |
\[ m+n=m+n. \]
| Also ist die Relation reflexiv. | |
| \( \circ \) | Symmetrie: Es sei \( (m_1,n_1)\sim_{\mathbb Z}(m_2,n_2), \) dann ist |
\[ \begin{array}{l} m_1+n_2=n_1+m_2 \quad\Longrightarrow\quad n_2+m_1=m_2+n_1 \quad\Longrightarrow\quad m_2+n_1=n_2+m_1 \\ \phantom{m_1+n_2=n_1+m_2} \quad\Longrightarrow\quad (m_2,n_2)\sim_{\mathbb Z}(m_1,n_1). \end{array} \]
| Also ist die Relation symmetrisch. | |
| \( \circ \) | Transitivität: Es seien \( (m_1,n_1)\sim_{\mathbb Z}(m_2,n_2) \) und \( (m_2,n_2)\sim_{\mathbb Z}(m_3,n_3), \) dann ist |
\[ \begin{array}{l} m_1+n_2=n_1+m_2\quad\mbox{und}\quad m_2+n_3=n_2+m_3 \\ \quad\Longrightarrow\quad m_1+n_2+n_3=n_1+m_2+n_3\quad\mbox{und}\quad n_1+m_2+n_3=n_1+n_2+m_3 \\ \quad\Longrightarrow\quad m_1+n_2+n_3=n_1+n_2+m_3 \\ \quad\Longrightarrow\quad m_1+n_3=n_1+m_3 \\ \quad\Longrightarrow\quad (m_1,n_1)\sim_{\mathbb Z}(m_3,n_3). \end{array} \]
| Also ist die Relation transitiv. |
Das zeigt, dass \( \sim_{\mathbb Z} \) eine Äquivalenzrelation darstellt.\( \qquad\Box \)
Aufgabe PA 11
Im Fall \( m,n\not=0 \) setzen wir \[ [(m,n)]_{\mathbb Q}^{-1}:=[(n,m)]_{\mathbb Q} \] für das multiplikative Inverse einer rationalen Zahl \( [(m,n)]_{\mathbb Q}\in\mathbb Q. \)
| (i) | Zeigen Sie |
\[ [(m,n)]_{\mathbb Q}\cdot[(m,n)]_{\mathbb Q}^{-1}=1 \]
| unter Verwendung der Definition der Multiplikation in \( \mathbb Q. \) | |
| (ii) | Zeigen Sie, dass das neutrale Element \( 1\in\mathbb Q \) der Multiplikation eindeutig ist. Sie dürfen Kommutativität und Assoziativität der Multiplikation ohne Beweis voraussetzen. |
| (i) | Nach Definition ist |
\[ [(k,\ell)]_{\mathbb Q}\cdot[(m,n)]_{\mathbb Q}=[(km,\ell n)]_{\mathbb Q}\,. \]
| Hier ist jetzt also |
\[ \begin{array}{l} [(m,n)]_{\mathbb Q}\cdot[(m,n)]_{\mathbb Q}^{-1} \,=\,[(m,n)]_{\mathbb Q}\cdot[(n,m)]_{\mathbb Q} \\[0.6ex] \quad=\,[(mn,nm)]_{\mathbb Q} \,=\,[(mn,mn)]_{\mathbb Q} \,=\,[(1,1)]_{\mathbb Q}\,, \end{array} \]
| und nach der Einbettung von \( \mathbb Z \) in \( \mathbb Q \) handelt es sich bei der letzten Äquivalenzklasse um die rationale Zahl \( 1. \) | |
| (ii) | Angenommen, es gelten mit \( 1,1'\in\mathbb Q \) |
\[ p\cdot 1=p\quad\mbox{und}\quad p\cdot 1'=p\quad\mbox{für alle}\ p\in\mathbb Q \]
| bzw. zusammengefasst |
\[ p\cdot 1=p\cdot 1'=p\quad\mbox{für alle}\ p\in\mathbb Q. \]
| Dann hätten wir insbesondere auch |
\[ \begin{array}{ll} 1'\cdot 1=1' & \qquad\mbox{für}\ p=1' \\[0.6ex] 1\cdot 1'=1'\cdot 1=1 & \qquad\mbox{für}\ p=1, \end{array} \] und ein Vergleich beider Zeilen zeigt \( 1=1'. \)
Das war zu zeigen.\( \qquad\Box \)
Aufgabe PA 12
Beweisen Sie vermittels eines geeigneten Schemas: Die Vereinigung abzählbar unendlich vieler abzählbar unendlicher Mengen ist wieder abzählbar unendlich.
Es handelt sich zunächst um abzählbar unendlich viele Mengen, d.h. es existiert eine Abzählung der Mengen \[ M_1\,,\quad M_2\,,\quad M_3 \quad\mbox{usw.} \] Jede dieser Mengen selbst besitzt abzählbar unendlich viele Elementen, d.h. jede dieser Menge kann in der Form dargestellt werden \[ M_k=\{m_{k1},m_{k2},m_{k3},\ldots\}\,,\quad k=1,2,3,\ldots \] Die Elemente \( m_{k\ell} \) stellen wir nun in einem quadratischen Schema dar und wenden darauf das erste Cantorsche Diagonalverfahren an:
| \( m_{11} \) | \( \to \) | \( m_{12} \) | \( m_{13} \) | \( \to \) | \( m_{14} \) | \( m_{15} \) | \( \cdots \) | |||
| \( \swarrow \) | \( \nearrow \) | \( \swarrow \) | ||||||||
| \( m_{21} \) | \( m_{22} \) | \( m_{23} \) | \( m_{24} \) | \( m_{25} \) | \( \cdots \) | |||||
| \( \downarrow \) | \( \nearrow \) | |||||||||
| \( m_{31} \) | \( m_{32} \) | \( m_{33} \) | \( m_{34} \) | \( m_{35} \) | \( \cdots \) |
Die Pfeile geben eine mögliche Abzählung an.\( \qquad\Box \)