Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Reflexivität einer Relation ${\displaystyle {}R}$ auf einer Menge ${\displaystyle {}M}$.
2. Teilbarkeitstheorie (N)/Kleinstes gemeinsames Vielfache/Definition/Begriff
3. Die kanonische Projektion zu einer Äquivalenzrelation ${\displaystyle {}\sim }$ auf einer Menge ${\displaystyle {}M}$.
4. Ungerichteter Graph/Kantenteilmenge/Restgraph/Definition/Begriff
5. Ungerichteter Graph/Zusammenhangskomponente/Definition/Begriff
6. Graph/Knotenüberdeckung/Definition/Begriff

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

Zeige, dass für natürliche Zahlen die folgenden Teilbarkeitsbeziehungen gelten.

1. Für jede natürliche Zahl ${\displaystyle {}a}$ gilt ${\displaystyle {}1\,{|}\,a}$ und ${\displaystyle {}a\,{|}\,a}$.
2. Für jede natürliche Zahl ${\displaystyle {}a}$ gilt ${\displaystyle {}a\,{|}\,0}$.
3. Gilt ${\displaystyle {}a\,{|}\,b}$ und ${\displaystyle {}b\,{|}\,c}$, so gilt auch ${\displaystyle {}a\,{|}\,c}$.
4. Gilt ${\displaystyle {}a\,{|}\,b}$ und ${\displaystyle {}c\,{|}\,d}$, so gilt auch ${\displaystyle {}ac\,{|}\,bd}$.
5. Gilt ${\displaystyle {}a\,{|}\,b}$, so gilt auch ${\displaystyle {}ac\,{|}\,bc}$ für jede natürliche Zahl ${\displaystyle {}c}$.
6. Gilt ${\displaystyle {}a\,{|}\,b}$ und ${\displaystyle {}a\,{|}\,c}$, so gilt auch ${\displaystyle {}a\,{|}\,{\left(rb+sc\right)}}$ für beliebige natürliche Zahlen ${\displaystyle {}r,s}$.

1. Ist klar wegen

   ${\displaystyle {}a=a\cdot 1\,.}$

2. Ist klar wegen

   ${\displaystyle {}0=a\cdot 0\,.}$

3. Die beiden Voraussetzungen bedeuten die Existenz von ${\displaystyle {}s,t\in \mathbb {N} }$ mit ${\displaystyle {}b=as}$ und ${\displaystyle {}c=bt}$. Somit ist

   ${\displaystyle {}c=bt=(as)t=a(st)\,}$

   und ${\displaystyle {}a}$ ist auch ein Teiler von ${\displaystyle {}c}$.

4. Aus den Voraussetzungen ${\displaystyle {}b=as}$ und ${\displaystyle {}d=tc}$ ergibt sich direkt

   ${\displaystyle {}bd=astc=acts\,,}$

   also ist ${\displaystyle {}ac}$ ein Teiler von ${\displaystyle {}bd}$.

5. Aus der Voraussetzung ${\displaystyle {}b=as}$ ergibt sich direkt

   ${\displaystyle {}bc=acs\,,}$

   also ist ${\displaystyle {}ac}$ ein Teiler von ${\displaystyle {}bc}$.

6. Aus den Voraussetzungen ${\displaystyle {}b=at}$ und ${\displaystyle {}c=au}$ ergibt sich direkt mit dem Distributivgesetz

   ${\displaystyle {}rb+sc=rat+sau=a(rt+su)\,,}$

   also ist ${\displaystyle {}a}$ ein Teiler von ${\displaystyle {}rb+sc}$.

Bestimme in ${\displaystyle {}\mathbb {Z} }$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${\displaystyle {}1085}$ und ${\displaystyle {}806}$ und schreibe die beiden Zahlen als Vielfache des größten gemeinsamen Teilers.

Es ist

${\displaystyle {}1085=1\cdot 806+279\,,}$

${\displaystyle {}806=2\cdot 279+248\,,}$

${\displaystyle {}279=1\cdot 248+31\,,}$

${\displaystyle {}248=8\cdot 31\,.}$

Der größte gemeinsame Teiler ist also ${\displaystyle {}31}$. Aus den Rechnungen erhält man

${\displaystyle {}806=2\cdot 279+248=2(248+31)+248=3\cdot 248+2\cdot 31=3\cdot 8\cdot 31+2\cdot 31=26\cdot 31\,}$

und

${\displaystyle {}1085=806+279=26\cdot 31+9\cdot 31=35\cdot 31\,.}$

Wir betrachten auf der Menge ${\displaystyle {}C}$ aller stetigen Funktionen von ${\displaystyle {}\mathbb {R} }$ nach ${\displaystyle {}\mathbb {R} }$ die folgende Relation: Es ist ${\displaystyle {}f\sim g}$, falls es eine nullstellenfreie stetige Funktion ${\displaystyle {}\alpha \colon \mathbb {R} \rightarrow \mathbb {R} }$ mit

${\displaystyle {}f=g\cdot \alpha \,}$

gibt.

1. Zeige, dass ${\displaystyle {}\sim }$ eine Äquivalenzrelation ist.
2. Zeige, dass aus ${\displaystyle {}f\sim g}$ folgt, dass die Nullstellenmenge von ${\displaystyle {}f}$ und von ${\displaystyle {}g}$ übereinstimmen.
3. Zeige, dass die beiden Funktionen

   ${\displaystyle {}f(x)=x\,}$

   und

   ${\displaystyle {}g(x)=x^{2}\,}$

   nicht zueinander äquivalent sind.

1. Es ist ${\displaystyle {}f\sim f}$, da

   ${\displaystyle {}f=1\cdot f\,}$

   ist, man also für ${\displaystyle {}\alpha }$ die konstante Funktion mit dem Wert ${\displaystyle {}1}$ nehmen kann, die stetig ist und keine Nullstelle besitzt. Zum Nachweis der Symmetrie sei

   ${\displaystyle {}f=g\cdot \alpha \,}$

   mit einer stetigen nullstellenfreien Funktion ${\displaystyle {}\alpha }$. Dann ist auch die Funktion

   ${\displaystyle {\frac {1}{\alpha }}\colon \mathbb {R} \longrightarrow \mathbb {R} ,\,x\longmapsto {\frac {1}{\alpha (x)}},}$

   wohldefiniert, nullstellenfrei und nach Fakt ***** auch stetig. Damit gilt

   ${\displaystyle {}f\cdot {\frac {1}{\alpha }}=g\,.}$

   Zum Nachweis der Transitivität gelte

   ${\displaystyle {}f=g\cdot \alpha \,}$

   und

   ${\displaystyle {}g=h\cdot \beta \,}$

   mit stetigen nullstellenfreien Funktionen ${\displaystyle {}\alpha ,\beta }$. Dann ist

   ${\displaystyle {}f=g\cdot \alpha =h\cdot \beta \cdot \alpha \,}$

   und ${\displaystyle {}\beta \cdot \alpha }$ ist ebenfalls nach Fakt ***** eine stetige nullstellenfreie Funktion.

2. Es sei

   ${\displaystyle {}f=g\cdot \alpha \,}$

   mit ${\displaystyle {}\alpha }$ stetig und nullstellenfrei. Dann ist für jedes ${\displaystyle {}x\in \mathbb {R} }$

   ${\displaystyle {}f(x)=g(x)\cdot \alpha (x)\,.}$

   Wegen

   ${\displaystyle {}\alpha (x)\neq 0\,}$

   gilt

   ${\displaystyle {}f(x)=0\,}$

   genau dann, wenn

   ${\displaystyle {}g(x)=0\,}$

   ist. Dies bedeutet, dass ${\displaystyle {}f}$ und ${\displaystyle {}g}$ die gleichen Nullstellen besitzen.

3. Nehmen wir an, dass ${\displaystyle {}x}$ und ${\displaystyle {}x^{2}}$ im beschriebenen Sinne äquivalent sind. Dann gibt es eine stetige nullstellenfreie Funktion ${\displaystyle {}\alpha }$ mit

   ${\displaystyle {}x^{2}=\alpha (x)\cdot x\,}$

   für alle ${\displaystyle {}x\in \mathbb {R} }$. Für ${\displaystyle {}x\neq 0}$ bedeutet dies

   ${\displaystyle {}\alpha (x)={\frac {x^{2}}{x}}=x\,.}$

   Wegen der vorausgesetzten Stetigkeit von ${\displaystyle {}\alpha }$ bedeutet dies nach Fakt *****  (2), dass auch

   ${\displaystyle {}\alpha (0)=0\,}$

   sein muss. Dies widerspricht aber der vorausgesetzten Nullstellenfreiheit von ${\displaystyle {}\alpha }$.