Kurs:Mathematik (Osnabrück 2009-2011)/Teil I/Arbeitsblatt 3

Aufwärmaufgaben

Aufgabe

Man gebe Beispiele ${}(M,0,')$ für Mengen mit einem ausgezeichneten Element ${}0\in M$ und einer Abbildung ${}'\colon M\rightarrow M$ an, die je zwei der Dedekind-Peano-Axiome erfüllen, aber nicht das dritte.

Aufgabe

Es sei ${}\mathbb {N}$ die Menge der natürlichen Zahlen und ${}n\in \mathbb {N}$. Zeige, dass die Menge

${}\mathbb {N} _{\geq n}={\left\{x\in \mathbb {N} \mid x\geq n\right\}}\,$

ebenfalls die Dedekind-Peano-Axiome (mit welchem ausgezeichneten Element und mit welcher Nachfolgerabbildung?) erfüllt.

Die folgende Aufgabe sollte man nicht bearbeiten, sondern zum Anlass nehmen, sich über unser Ziffernsystem zu freuen.

Aufgabe

Man definiere, welche endlichen Zeichenketten aus ${}I,V,X,L,C,D,M$ im römischen Zahlsystem (mit oder ohne Subtraktionsregel) erlaubt sind und welche nicht. Man erstelle einen Algorithmus, der zu jeder erlaubten römischen Zahl den Nachfolger berechnet.

Aufgabe

Es sei ${}M$ eine Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge davon. Zeige, dass durch die Gleichmächtigkeit von Mengen eine Äquivalenzrelation auf ${}{\mathfrak {P}}\,(M)$ definiert wird.

Aufgabe

Es seien ${}L$ und ${}M$ zwei Mengen und ${}\varphi \colon L\rightarrow M$ eine bijektive Abbildung zwischen diesen Mengen. Zeige, dass für jede Teilmenge ${}S\subseteq L$ eine Bijektion ${}S\rightarrow \varphi (S)$ vorliegt, und dass ebenso für jede Teilmenge ${}T\subseteq M$ eine Bijektion ${}\varphi ^{-1}(T)\rightarrow T$ vorliegt.

Aufgabe

Skizziere ein Inklusionsdiagramm für sämtliche Teilmengen einer dreielementigen Menge.

Aufgabe

Skizziere ein Teilerdiagramm für die Zahlen ${}25,30,36$ sowie all ihrer positiven Teiler.

Aufgabe

Es sei ${}M$ eine Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge davon. Zeige, dass durch

$S\preccurlyeq T,{\text{wenn es eine injektive Abbildung }}S\rightarrow T{\text{ gibt}},$

eine reflexive und transitive Relation auf ${}{\mathfrak {P}}\,(M)$ definiert wird, die in aller Regel weder symmetrisch noch antisymmetrisch ist.

Die folgenden Aufgaben über endliche Mengen sind intuitiv zumeist klar. Es geht aber darum, sie unter Bezug auf die Definitionen mit Hilfe von bijektiven Abbildungen zu beweisen.

Aufgabe

Es sei ${}n\in \mathbb {N}$, ${}n\geq 1$ und ${}x\in \{1,\ldots ,n\}$. Zeige, dass die Menge

$\{1,\ldots ,n\}\setminus \{z\}$

die Anzahl ${}n-1$ besitzt.

Aufgabe

Es seien ${}m$ und ${}n$ natürliche Zahlen. Zeige durch Induktion über ${}m$, dass aus einer Bijektion

$\varphi \colon \{1,\ldots ,m\}\longrightarrow \{1,\ldots ,n\}$

folgt, dass ${}m=n$ ist.

Aufgabe

Es sei ${}M$ eine endliche Menge. Zeige, dass die Anzahl von ${}M$ wohldefiniert ist.

Aufgabe

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und es sei ${}T\subseteq M$ eine Teilmenge. Zeige, dass ${}T$ ebenfalls eine endliche Menge ist, und dass für ihre Anzahl ${}k$ die Abschätzung

${}k\leq m\,$

gilt. Zeige ferner, dass ${}T$ genau dann eine echte Teilmenge ist, wenn

${}k<m\,$

ist.

Aufgabe

Es seien ${}S$ und ${}T$ endliche Teilmengen einer Menge ${}M$. Zeige, dass dann auch die Vereinigung ${}S\cup T$ endlich ist.

Die beiden folgenden Aufgaben verwenden das Maximum einer geordneten Menge.

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt maximal (in ${}I$) oder ein maximales Element (von ${}I$), wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}x\preccurlyeq y$ gibt.

Aufgabe

Es sei ${}(I,\preccurlyeq )$ eine total geordnete Menge. Zeige durch Induktion, dass jede nichtleere endliche Teilmenge ${}T\subseteq I$ ein eindeutiges Maximum besitzt.

Aufgabe

Es sei ${}T\subseteq \mathbb {N}$ eine nichtleere Teilmenge der natürlichen Zahlen. Zeige, dass ${}T$ genau dann endlich ist, wenn ${}T$ ein Maximum besitzt.

Es seien ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$ zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

$F\colon M_{1}\longrightarrow M_{2},\,x\longmapsto F(x),$

heißt ordnungstreu (oder monoton), wenn für alle ${}x,x'\in M_{1}$ mit ${}x\leq _{1}x'$ stets auch ${}F(x)\leq _{2}F(x')$ gilt.

Aufgabe

Es sei ${}(M,\leq )$ eine endliche total geordnete Menge. Definiere für ein geeignetes ${}n\in \mathbb {N}$ eine ordnungstreue bijektive Abbildung

${\{1,\ldots ,n\}}\longrightarrow M,$

wobei ${}{\{1,\ldots ,n\}}$ mit der natürlichen Ordnung versehen sei.

Aufgaben zum Abgeben

Aufgabe (4 Punkte)

Wir betrachten eine digitale Uhr, die ${}24$ Stunden, ${}60$ Minuten und ${}60$ Sekunden anzeigt. Beschreibe die möglichen Zustände (also die möglichen Zeitangaben) mit Hilfe einer geeigneten Produktmenge. Definiere (mit Hilfe von geeigneten Hilfsabbildungen) die Nachfolgerabbildung, die zu jeder Zeitangabe die Zeitangabe der nächsten Sekunde berechnet.

Aufgabe (2 Punkte)

Es sei ${}(M,\leq )$ eine geordnete Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge von ${}M$. Zeige, dass die Abbildung

$M\longrightarrow {\mathfrak {P}}\,(M),\,x\longmapsto {\left\{y\in M\mid y\leq x\right\}},$

ordnungstreu und injektiv ist, wobei die Potenzmenge mit der Inklusion versehen ist.

Die folgende Aussage verwendet, dass sich jede natürliche Zahl ${}n\geq 1$ eindeutig als Produkt ${}n=2^{k}u$ mit ${}k\in \mathbb {N}$ und ${}u\in \mathbb {N}$ ungerade schreiben lässt.

Aufgabe (4 Punkte)

Wir definieren auf ${}\mathbb {N} _{+}$ eine neue Relation ${}R$ durch folgende Vorschrift: Für zwei Zahlen ${}n,m\in \mathbb {N} _{+}$ mit ${}n=2^{k}t$ und ${}m=2^{\ell }u$ mit ${}t,u$ ungerade sei

$nRm{\text{ falls }}t<u{\text{ gilt oder falls zugleich }}t=u{\text{ und }}k\leq \ell {\text{ gilt}}$

(rechts wird auf die natürliche Ordnung in ${}\mathbb {N}$ Bezug genommen).

1. Zeige, dass ${}R$ eine totale Ordnung auf ${}\mathbb {N} _{+}$ ergibt und beschreibe exemplarisch diese Ordnung.
2. Zeige, dass es zu jedem ${}n\in \mathbb {N} _{+}$ ein wohldefiniertes Element ${}n^{\star }\in \mathbb {N} _{+}$, ${}n^{\star }\neq n$, derart gibt, dass ${}nRn^{\star }$ gilt und dass es zwischen ${}n$ und ${}n^{\star }$ keine weiteren Elemente gibt (diese Formulierung ist zu präzisieren).
3. Erfüllt die Menge ${}(\mathbb {N} _{+},1,\star )$ die Dedekind-Peano-Axiome?

Aufgabe (3 Punkte)

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und es sei

$M\longrightarrow N$

eine surjektive Abbildung in eine weitere Menge ${}N$. Zeige, dass dann auch ${}N$ endlich ist, und dass für ihre Anzahl ${}n$ die Abschätzung

${}n\leq m\,$

gilt.

Die folgende Aufgabe ist zum jetzigen Zeitpunkt vermutlich schwierig.

Aufgabe (5 Punkte)

Wir betrachten eine digitale Uhr, die ${}24$ Stunden, ${}60$ Minuten und ${}60$ Sekunden anzeigt. Zur Karnevalszeit läuft sie aber nicht in Sekundenschritten, sondern addiert, ausgehend von der Nullstellung, in jedem Zählschritt immer ${}11$ Stunden, ${}11$ Minuten und ${}11$ Sekunden dazu. Wird bei dieser Zählweise jede mögliche digitale Anzeige erreicht? Nach wie vielen Schritten kehrt zum ersten Mal die Nullstellung zurück?