Diskussion:Strukturelle Induktion

Kann man hier vllt. ein Beispiel bringen? Strukturelle Induktion ist also allgemeiner als vollständige Induktion aber ein Spezialfall für partielle Ordnungen !? --92.78.177.208 18:36, 22. Dez. 2008 (CET)

Habe sogar grad bei Transfinite Induktion gelesen, dass DIESE widerum die Verallgemeinerung für beliebige geordnete Mengen sein soll. Da scheint mir irgendwas doppelt zu sein oderso...

Ich würde den Artikel mal für die Qualitätssicherung vorschlagen, er ist irgendwie nicht so richtig lehrreich. Das mit der tranfiniten Induktion bringt mich auch grade recht durcheinander. -- Euronymous 00:14, 2. Mai 2010 (CEST)

Beispiele sind eine gute Idee, aber die, die mir einfallen, versteht man nur, wenn man die Gebiete versteht, aus denen sie kommen... Ich denke drüber nach. -- UKoch 15:33, 4. Mär. 2011 (CET)

Ich habe ein Bsp. hinzugefügt. Wer sich mit wiki-gerechtem Formelumbruch in TeX auskennt, möge dafür sorgen, dass die Gleichungen nicht über den Bildschirmrand hinausragen. Ansonsten gut so? -- UKoch 17:40, 21. Mär. 2011 (CET)

Hab' mal Zeilenumbrüche eingebaut.

Zum "gut so?": Ich denke, man sollte den Beweis so auffassen, dass er eine Funktion definiert, die als $T'$ notiert wird, wobei der formale Parameter $T$ ist. Damit könnte man in der nun umgebrochenen Formel das ' explizit verwenden, und müsste sich nicht auf seltsame Formulierungen einlassen (Substitutionen, die gar nichts bewirken, aber angeblich trotzdem angewendet worden sind :) ). --Daniel5Ko 00:48, 22. Mär. 2011 (CET)

Hallo Daniel, danke für die Zeilenumbrüche. -- Mit dem Strich als Funktion hast Du m.E. Recht, aber man müsste dann immer noch sowas wie $F'''\equiv F$ schreiben, denke ich. Die leeren Anwendungen der IS handelt man sich eben mit der strukt. Induktion ein. -- UKoch 17:25, 22. Mär. 2011 (CET)

Ja. Ich meinte ja nicht, dass da Gleichungen verschwinden, sondern dass tatsächlich eine sichtbare Änderung stattfindet. Eben $F'''{\stackrel {3\times {\mbox{IA}}}{\equiv }}F$ statt $F{\stackrel {3\times {\mbox{IA}}}{\equiv }}F$.

Ach so. Dann mach's doch so, ich meckere dann schon. :-) Zwischenzeitlich fiel mir ein, dass man das Bsp. verkürzen könnte, wenn man aussagenlog. Formeln nur mit und/oder/nicht definiert und den Satz beweist, dass jede solche Formel in eine Formel nur mit NAND umgewandelt werden kann. -- UKoch 21:47, 23. Mär. 2011 (CET)

Hmmm, hab' mal die Striche eingesetzt. Dabei ist mir aufgefallen, dass wenn man sie als Funktionen interpretiert, die rekursiv auf Teiltermen arbeiten, dann $=$ im hinteren Teil abgebrachter ist als $\equiv$. Das passt dann allerdings nicht mehr so gut zum Text... --Daniel5Ko 22:32, 23. Mär. 2011 (CET)

Erstmal danke! = statt $\equiv$ finde ich schon OK. Aber alle binären Operatoren brauchen (), weil's so def. ist; ich setze sie zu Anfang ein. Dagegen dürfen um Negationen herum keine () stehen. Das Problem ist natürlich, dass man ohne () nicht mehr erkennt, was das Argument von ' ist. Mein Vorschlag: Das Argument von ' mit [] kennzeichnen; dann () wirklich nur da verwenden, wo von der Def. erlaubt/gefordert. -- UKoch 21:22, 24. Mär. 2011 (CET)

(entrückt.) Ja, eine abweichende Klammerung wäre u.U. gut. Notationstest mit verschiedenen Klammerungen und auch mit wieder-Weglassung des Strichs (der wird ja dann an der Stelle eigentlich nicht mehr gebraucht!):

1. $\lnot \lnot A\equiv [\![\lnot \lnot A]\!]=\lnot [\![\lnot A]\!]=\lnot \lnot [\![A]\!]$
2. $\lnot \lnot A\equiv [\lnot \lnot A]'=\lnot [\lnot A]'=\lnot \lnot [A]'$
3. $(A\lor B)\equiv [(A\lor B)]=\lnot (\lnot [A]\land \lnot [B])$

Schade. Nummer 1 sieht mMn am besten aus, und ist am besten lesbar, ist aber im vorliegenden Umfeld traditionell eher für Semantikfunktionen reserviert. Welche sollte man nehmen? --Daniel5Ko 22:07, 24. Mär. 2011 (CET)

Ich bin für 2. Dann müsste man noch den ' erklären. Aber sonst ist's hübsch! -- UKoch 14:36, 26. Mär. 2011 (CET)

Also mir ist's relativ egal. Aber Variante 3, die jetzt auch im Artikel steht, kommt mit dem kleinsten Erklärungsbedarf aus, glaube ich. Wir haben nun nicht 2 separate Konzepte, ' und [], sondern eben nur []. Einfach eine Funktion, deren Anwendung etwas seltsam hingeschrieben ist, und im Gegensatz zur Funktion ' zahlt die etwas seltsame Schreibweise sich echt aus. --Daniel5Ko 01:23, 2. Apr. 2011 (CEST)

Jo, finde ich gut. -- UKoch 15:27, 4. Apr. 2011 (CEST)

= Noethersche Induktion?

Ich habe beim Googeln in mehreren Links bemerkt, dass die strukturelle Induktion als Synonym zur noetherschen Induktion gilt. Dort ist diese Induktion etwas genauer erklärt. Der Sache nach decken sich auch beide Beschreibungen. Warum die strukturelle Induktion nur ein Spezialfall der Induktion in wohlfundierten Mengen sein soll, wie hier im Artikel am Schluss bemerkt ist, ist nicht ersichtlich.--Wilfried Neumaier 00:31, 23. Sep. 2010 (CEST)

Noethersche Induktion setzt irgendeine wohlfundierte geordnete Menge voraus. Bei der strukturellen Induktion ist die Ordnungsrelation eben die "Hat-als-Teil"-Relation. -- UKoch 15:33, 4. Mär. 2011 (CET)

Entschuldigung, es muss natürlich heißen: Bei der strukturellen Induktion ist die Ordnungsrelation die "Ist-Teil-von"-Relation. -- UKoch 21:09, 7. Mär. 2011 (CET)

= Rekusive Definition?

Hallo liebe Logiker! Wenn ich mir das erste Beispiel so ansehe, ist die strukturelle Induktion doch eine rekursive Definition. Wie wird das abgegrenzt und inwiefern ist das ein Beweisverfahren? Setzt eine Vollständige Induktion nicht sogar voraus, dass die Menge, über die induziert wird, rekursiv aufbaubar ist (damit die zu Beweisende allgemeine Eigenschaft auch vererbt werden kann)? Liebe Grüße --Leif Czerny 18:30, 6. Jul. 2011 (CEST)

Bin zwar kein richtiger Logiker, aber hallo nochmal! Strukturelle Induktion lässt sich als Rekursion (oder auch als Iteration) verstehen, das stimmt. Ich denke, man spricht dann von Rekursion, wenn es um die Programmierung so eines Verfahrens geht. -- Mit dem Beweisverfahren hast Du Recht: Ein Beweis per strukt. Ind. setzt voraus, dass die Menge selbst per strukt. Ind. definiert ist, darum auch so im Artikel. Wenn Du dazu weiter gehende Fragen hast, dann wäre meine Diskussionsseite vielleicht geeigneter? Grüße -- UKoch 23:44, 19. Okt. 2011 (CEST)

Hallo UKoch, der Zusammenhang taucht so in den Artikeln nicht explizit auf, daher meine Nachfrage. Vollständige Induktion hat z.B. keinen Link hierher, wohl aber auf Rekursion. In Rekursion steht es nicht einmal unter siehe auch, ebenso in Iteration oder Definition#Rekursive_Definition. Meine Frage war also nicht nur sachbezogen, sd. auch auf die Verlinkung des Artikels. LG --Leif Czerny 11:43, 20. Okt. 2011 (CEST)

Danke für den Tipp, habe auf Definition#Rekursive_Definition einen Link hierhin gesetzt. Jo, über die Benennung "rekursiv" bzw. "induktiv" haben wohl alle ihre eigenen Ansichten. Grüße -- UKoch 16:37, 20. Okt. 2011 (CEST)

Danke!--Leif Czerny 20:15, 20. Okt. 2011 (CEST)