Wohlfundierte Induktion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:13 Mo 24.03.2014 | | Autor: | mgtb1994 |
| Aufgabe | Es sind 2 Aufgaben die miteinander verbunden sind:
Ist [mm] \le [/mm] lex auf [mm] \IN^\* [/mm] wohlfundiert?
Beweisen Sie Beispiel 3.4 mittels wohlfundierter Induktion. Wählen sie die wohlfundierte Ordnung [mm] \le [/mm] derart, dass es nur einen Basisfall gibt. |
Ich würde sagen das sie wohlfundiert ist, da das leere Wort ja minimal ist. Das wäre meiner Meinung auch der Basisfall.
Mit dem Schritt komme ich jetzt aber nicht weiter. Oder kann man sagen * = *+1?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:18 Di 25.03.2014 | | Autor: | tobit09 |
Hallo mgtb1994!
> Es sind 2 Aufgaben die miteinander verbunden sind:
>
> Ist [mm]\le[/mm] lex auf [mm]\IN^\*[/mm] wohlfundiert?
>
> Beweisen Sie Beispiel 3.4 mittels wohlfundierter Induktion.
> Wählen sie die wohlfundierte Ordnung [mm]\le[/mm] derart, dass es
> nur einen Basisfall gibt.
Verrätst du uns auch, was Beispiel 3.4 besagt? 
> Ich würde sagen das sie wohlfundiert ist, da das leere
> Wort ja minimal ist.
(Also enthält [mm] $\IN^\*$ [/mm] bei euch doch auch das leere Wort?)
Nicht jede Relation mit einem minimalen Element ist wohlfundiert!
Wie habt ihr wohlfundiert genau definiert? Da gibt es nämlich mindestens zwei äquivalente Formulierungen.
> Mit dem Schritt komme ich jetzt aber nicht weiter. Oder
> kann man sagen * = *+1?
Was meinst du mit *? Was meinst du mit *+1?
Welche Aussage soll überhaupt per wohlfundierter Induktion (mit welcher wohlfundierten Relation?) gezeigt werden?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:18 Di 25.03.2014 | | Autor: | mgtb1994 |
Ups xD Total vergessen das Beispiel mit anzugeben.
Sei P die formale Sprache der Palindrome über dem Alphabet {a,b}.
Die Aussage
"Wenn x [mm] \in [/mm] P und l(x) gerade, dann hat x eine gerade Anzahl von as."
kann mit wohlfundierter Induktion bewiesen werden.
Das mit * war falsch von mir. War beim falschen Beispiel. Sorry xD
Wohlfunfiert heißt bei uns,dass es keine unendlich absteigende Kette gibt. Bedeutet das jetzt das [mm] \le [/mm] lex auf [mm] \IN [/mm] hoch* nicht wohlfundiert ist, da es ja unendlich viele Vorgänger für jede Möglichkeit, außer dem leeren Wort gibt?
Hoffe es ist jetzt verständlicher.
Maximilian
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:49 Di 25.03.2014 | | Autor: | tobit09 |
> Ups xD Total vergessen das Beispiel mit anzugeben.
> Sei P die formale Sprache der Palindrome über dem Alphabet
> {a,b}.
> Die Aussage
> "Wenn x [mm]\in[/mm] P und l(x) gerade, dann hat x eine gerade
> Anzahl von as."
> kann mit wohlfundierter Induktion bewiesen werden.
Eine Möglichkeit: Wir zeigen per "gewöhnlicher" vollständiger Induktion nach k (man könnte auch sagen: "per wohlfundierter Induktion auf der Menge [mm] $\IN_0$ [/mm] mit der gewöhnlichen Ordnungsrelation darauf mit Fallunterscheidung nach $k=0$ und $k>0$"):
(*) Für alle [mm] $k\in\IN_0$ [/mm] gilt: Ist [mm] $x\in [/mm] P$ mit $l(x)=2*k$, so hat $x$ eine gerade Anzahl von a's.
Daraus folgt dann die Behauptung.
Um nun (*) per vollständiger Induktion zu zeigen, ist zu zeigen:
1. Induktionsanfang (oder Basisfall $k=0$): Ist [mm] $x\in [/mm] P$ mit $l(x)=2*0$, so hat $x$ eine gerade Anzahl von a's.
2. Induktionsschritt (oder Fall $k>0$): Für beliebig vorgegebenes $k>0$ habe jedes [mm] $x'\in [/mm] P$ mit $l(x')=2*k'$ für ein [mm] $k'\in\IN_0$ [/mm] mit $k'<k$ eine gerade Anzahl von a's. Zu zeigen ist, dass auch jedes [mm] $x\in [/mm] P$ mit $l(x)=2*k$ eine gerade Anzahl von a's hat.
Zu 1.: Wie kann ein [mm] $x\in [/mm] P$ mit $l(x)=2*0=0$ nur aussehen?
Zu 2.: Sei also [mm] $x\in [/mm] P$ mit $l(x)=2*k$. Betrachte mal das Wort x', dass aus x durch Weglassen des ersten und letzten Buchstabens entsteht.
> Wohlfunfiert heißt bei uns,dass es keine unendlich
> absteigende Kette gibt.
O.K.
> Bedeutet das jetzt das [mm]\le[/mm] lex auf
> [mm]\IN[/mm] hoch* nicht wohlfundiert ist, da es ja unendlich viele
> Vorgänger für jede Möglichkeit, außer dem leeren Wort
> gibt?
Die Wörter der Form [mm] $1111\ldots1$ [/mm] haben auch nur endlich viele Vorgänger.
Benutze die Definition der Wohlfundiertheit! Um die Wohlfundiertheit von [mm] $\le_{lex}$ [/mm] auf [mm] $\IN^\*$ [/mm] zu widerlegen, gib eine konkrete unendlich absteigende Kette an.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:42 Di 25.03.2014 | | Autor: | mgtb1994 |
Zu 1: Ein Wort der Länge 0 ist die leere Menge, also 0 as. Das bestätigt die Basis, denn 0 ist eine gerade Zahl.
Es gibt zum Beispiel für 1 unendlich viele Vorgänger.
(1) > (0,1) > (0,0,1) >......
Man kann immer eine 0 mehr vor der 1 setzen. Oder irre ich mich hier?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:52 Di 25.03.2014 | | Autor: | tobit09 |
> Zu 1: Ein Wort der Länge 0 ist die leere Menge,
(Das leere Wort, nicht die leere Menge meinst du.)
Vor allem ist es das einzige Wort der Länge 0.
> also 0 as.
> Das bestätigt die Basis, denn 0 ist eine gerade Zahl.
![[ok]](/images/smileys/ok.gif "[ok]")
> Es gibt zum Beispiel für 1 unendlich viele Vorgänger.
>
> (1) > (0,1) > (0,0,1) >......
>
> Man kann immer eine 0 mehr vor der 1 setzen. Oder irre ich
> mich hier?
Sehr schön!
Also kann die lexikographische Ordnung auf [mm] $\IN^\*$ [/mm] nicht wohlfundiert sein.
(Vorausgesetzt die 0 ist bei euch eine natürliche Zahl. In diesem Fall muss ich in meiner vorherigen Antwort das Wort [mm] $(1,1,1,\ldots,1)$ [/mm] durch [mm] $(0,0,0,\ldots,0)$ [/mm] ersetzen.)
|
|
|
|
