Verschoben! Strukturelle Induktion

Neue Frage »

Wambologie Auf diesen Beitrag antworten »
Strukturelle Induktion
Meine Frage:
halli hallo,

Ich hatte diese Frage bereits unter "Algebra" gestellt, doch schien es die falsche Rubrik gewesen zu sein. Daher poste ich es erneut hier nur mit dem Unterschied, dass ich meine Idee bzw. mein Ansatz umgeändert habe:


ich habe immernoch so meine Probleme mit der strukturellen Induktion und benötige daher eure Hilfe.
Meine Aufgabe lautetet wie folgt:

ist eine nicht leere Menge. und die Menge aller Bäume über X.

Gegeben ist die Definition der Anzahl der Blätter


für alle


Zu zeigen ist
für alle

Meine Ideen:
Sei so gewählt, dass für alle mit gilt.

I.A.
Sei t die leere Menge. Dann gilt wegen also auch


Für L(0):








Für L(1):








_____________________________________________________


So würde ich mein I.A. setzten, doch habe ich überhaupt keinen Plan ob man es so machen darft.


Falls meine Überlegungen richtig sind, frage ich mich, wie meine I.V und mein I.S aussieht.
Beim I.S. kann ich mir schon vorstellen, dass ich da eine Fallunterscheidung machen muss, wegem dem logischen ODER Operanten. Aber mehr fällt mir nicht mehr ein, wie ich an die Aufgabe herangehen soll....


Wäre euch sehr dankbar, wenn ihr mir weiterhelfen würdet smile
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

das hier ist Graphentheorie und definitiv weder Algebra noch Analysis. Das wäre hier am besten unter Sonstiges aufgehoben. (Vielleicht ist ein Mod ja so nett.)

Deine Notation ist inkonsistent. Was ist denn ? Und was ist h? Die Höhe des (Binär)baums ?

Zitat:

Das kann nicht sein. Damit die rechte Elementbeziehung gültig ist müsste eine natürliche Zahl sein. In welchem Sinne soll t Element einer natürlichen Zahl sein.
Ferner sind 0 und 1 keine Bäume (oder habt ihr dafür irgendwelche Konventionen?), damit ist L(0) und L(1) undefiniert. Wieso schreibst du die hin, wenn du darunter eh was anderes ausrechnest?

Zitat:

Hier stimmt kein einziges =. Auf beiden Seiten stehen jeweils verschiedenartige Objekte, die nicht einmal vergleichbar sind - geschweige denn gleich - wie z.b. in Tupel und eine natürliche zahl.
Wambologie Auf diesen Beitrag antworten »

Die Gesamte Aufgabenstellung befindet sich im Anhang.




Das mein I.A. falsch ist, hab ich mir schon denken können. Doch habe ausser dieser keine weiteren Ideen mehr, wie die Aufgabe lösen könnte bzw. zumindest den I.A. ermitteln kann unglücklich
Captain Kirk Auf diesen Beitrag antworten »

Dann habt ihr wohl im Skript definiert was ist. Der allererste Arbeitsschritt ist das nachschlagen unbekannter Begriffe.

induktionsanfang sind die zwei Basisfälle der Definition, sauber hingeschrieben.
Im I.S. wird der dritte Fall verbraten.

Edit: Anscheinend untertützt das Boardlatex kein großes \Tau, ich habe es mal in ein kleines geändert. LG Iorek
Wambologie Auf diesen Beitrag antworten »

Die Definitionen sind im Anhang.
h ist die höhe des Binärbaums.


Also ist mein I.A. doch richtig oder wie darf ich deine Aussage
"induktionsanfang sind die zwei Basisfälle der Definition, sauber hingeschrieben. "
verstehen?

Denn im vorherigen Kommentar sagtest du ja, dass dies nicht so gehen.
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Also ist mein I.A. doch richtig oder wie darf ich deine Aussage "induktionsanfang sind die zwei Basisfälle der Definition, sauber hingeschrieben. " verstehen?

Wie kommst du darauf dein induktionsanfang wäre richtig? Was du dort hingeschrieben ist ergibt mathematisch keinerlei Sinn. Es mag sein, dass es richtiger Gedanke dabei ist, es ist aber dermaßen unsauber hingeschrieben, dass das nicht mehr zu erkennen ist.
Beginne mit dem ersten Fall


Danke Iorek, ich hatte nicht nachkontrolliert, weil ich davon ausging das wäre dabei.
 
 
Wambologie Auf diesen Beitrag antworten »

Sei dann gilt (dass heißt l = 0 = h). Daraus folgt:



Sei mit , dann gilt (dass heißt l = 1 = h). Daraus folgt:




So wäre mein "sauberer" Aufschrieb. Doch ändern tut sich ja garnichts unglücklich
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Doch ändern tut sich ja garnichts unglücklich

Wenn man jetzt noch statt tau L schreibt, ja dann ist das ein sauberer Aufschrieb.
Und es ändert sich viel: Es ist der Unterschied zwischen Nonsense und Mathematik.
Wambologie Auf diesen Beitrag antworten »

gut smile

Und wie würde dein meine I.V aussehen?
Im Prinzip müsste es ja dann die Behauptung sein.

Sprich sowas wie:
Sei so gewählt, dass die Aussage:



für alle gilt


I.S.
Wäre dann der Beweis für , sprich .
Hier müsste man dann aber wohl eine Fallunterscheidung machen, wegen dem logischen ODER Operator.
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Sprich sowas wie: Sei so gewählt, dass die Aussage: für alle gilt

Wieso wählst du l wenn es danach nie wieder vorkommt?

Zitat:
Hier müsste man dann aber wohl eine Fallunterscheidung machen, wegen dem logischen ODER Operator.

ich wüßte nicht warum man einen sollte. Bzw. vielleicht versteht ich auch nicht was du mit logischen ODER Operator meinst. Ist ODER eine Abkürzung für Irgendwas? (Du schreibst es ja groß)
Wambologie Auf diesen Beitrag antworten »

Was ich vergessen habe hier zu schreiben:
Sei so gewählt, dass für alle mit .

Das habe ich noch vor meinem I.A. geschrieben. Daher kam ich auf die h = l +1.
Oder ist es überflüssig?



Auf die Idee mit der Fallunterscheidung kam ich, weil es ja heißt, dass t1 oder t2 ungleich Null ist. Sprich dass man es einmal für t1 ungleich Null zeigt und einmal t2 ungleich Null.
Wabologie Auf diesen Beitrag antworten »

Mein Beweis sieht jetzt folgendermaßen aus:

I.V.
Sei so gegeben, dass und gilt.


I.S.

Sei mit und

1. Fall Setzte
Dann gilt:





2. Fall Setzte
Dann gilt:
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »