| |
| Autor |
 Induktion über f |
|
ucurum36
Neu 
Dabei seit: 07.06.2022
Mitteilungen: 1
 |  Themenstart: 2022-06-07
|
Allgemeiner kann auch für eine beliebige Menge M eine Aussage A(m) für alle m∈M
bewiesen werden, indem man eine Funktion f:M → \ \IN
angibt und zeigt, dass für jedes m ∈ M aus der Annahme „A(m) ist falsch“ folgt, dass es ein m′ ∈ M mit
f(m′)
|
 Profil
| | Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen. |
StrgAltEntf
Senior 
Dabei seit: 19.01.2013
Mitteilungen: 8293
Wohnort: Milchstraße
 | Beitrag No.1, eingetragen 2022-06-07
|
Hallo ucurum36,
woher stammt denn diese Aussage/Sprechweise? Aus einer Vorlesung, oder aus einem Lehrbuch?
Es ist etwas befremdlich, wenn das dort ohne ein Beispiel eingeführt wurde.
Zunächst:
"Aus der Annahme 'A(m) ist falsch' folgt, dass es ein m′ ∈ M mit
f(m′) < f(m) gibt, sodass auch A(m′) falsch ist
ist äquivalent zu
"Aus 'A(m') ist richtig' für alle m' mit f(m') < f(m) folgt, dass A(m)"
Beispiel:
M sei die Menge der Bäume. Behauptung: Die Ecken jedes Baums m sind mit zwei Farben färbbar.
Beweis: Über die Anzahl der Ecken des Baums. Für einen Baum m sei also f(m) die Anzahl der Ecken von m.
Sei nun m ein Baum. Entferne eine Endecke x von m. Das ergibt einen Baum m' mit f(m') = f(m) - 1 < f(m). Nach Voraussetzung ist m' mit zwei Farben färbbar - es sei g: V(m') -> {0,1} eine Zweifärbung. Es sei y der Nachbar von x in m. Setze g auf V(m) durch g(x) = 1 - g(y) fort. Diese Fortsetzung ist eine Zweifärbung auf m. q. e. d.
|
Profil
|
tactac
Senior 
Dabei seit: 15.10.2014
Mitteilungen: 2796
 | Beitrag No.2, eingetragen 2022-06-07
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}\)
Randbemerkung:
Es handelt sich übrigens um ein ganz allgemeines Prinzip:
Wenn ${\prec} \subseteq X \times X$ eine wohlfundierte Relation ist, dann auch die Relation ${\prec}' \subseteq M \times M$, definiert durch $m \prec' n :\Leftrightarrow f(n) \prec f(m)$, für beliebige $f \colon M \to X$.
Im Beispiel hier ist $X = \IN$ und ${\prec} = {<}$.
Nimmt man statt < die Nachfolgerrelation auf $\IN$ (das zugehörige Induktionsprinzip ist dann nicht "starke Induktion", sondern die übliche vollständige Induktion), ergibt sich für ein $f \colon M \to \IN$ das Induktionsprinzip: Um $A(m)$ für alle $m \in M$ zu zeigen, ist hinreichend, zu zeigen:
* $A(m)$ für alle $m$ mit $f(m)=0$,
* für alle $k\in\IN$: Falls $A(m)$ für alle $m$ mit $f(m)=k$, so $A(m)$ für alle $m$ mit $f(m)=k+1$.\(\endgroup\)
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
