From a282244 Sun Mar 12 15:14:31 2000 From: a282244 Newsgroups: schule.mathe Subject: Re: Induktion References: <38C93B66.969869BA@t-online.de> <38c9dda4.2121573@news.cis.dfn.de> <01bf8ba7$df3d5080$0b606d86@ml.csn.tu-chemnitz.de> <38cb5deb.181666694@news.btx.dtag.de> <8afr3r$cf5$1@news.BelWue.DE> From: Helmut.Richter@lrz-muenchen.de (Helmut Richter) Reply-To: Helmut.Richter@lrz-muenchen.de Organization: Leibniz-Rechenzentrum, Muenchen (Germany) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit "Gerhard Bitsch" writes: >Eine oft benötigte und zum Induktionsaxiom äquivalente >Eigenschaft der natürlichen Zahlen ist: >Jede nicht leere Menge von natürlichen Zahlen hat ein kleinstes Element >Dies führt zur Beweismethode mit dem "kleinsten Verbrecher" >[...] >Übungsaufgabe: Man zeige, dass das angegebene Prinzip >tatsächlich äquivalent zur vollständigen Induktion ist. Das ist für die natürlichen Zahlen äquivalent, aber nicht für alle Mengen. Im einen Fall (V.I.) hat man eine Nachfolgerfunktion auf der Menge, und der Induktionsschritt geht von einem Element auf den Nachfolger. Im anderen Fall (T.I.) hat man eine Wohlordnung (eine Ordnung, bei der jede nichtleere Menge ein kleinstes Element hat), und der Induktionsschritt geht von allen Elementen kleiner x auf x. Für die Äquivalenz wäre zu zeigen, dass man aus der Nachfolgerfunktion eine Wohlordnung machen kann und umgekehrt. Hat man eine Wohlordnung, dann ist der Nachfolger von x das kleinste Element größer x. Es kann aber sein, dass es Elemente gibt, die nie als Nachfolger auftreten. Als Beispiel die folgende Ordnung auf den natürlichen Zahlen: x<=0 für alle x x<=y wenn x, y nicht 0 sind und x im herkömmlichen Sinne kleiner als y ist Die Zahlen haben also die abgeänderte Ordnung 1, 2, 3, ..., 0, wobei die Pünktchen für die anderen Zahlen in ihrer gewöhnlichen Reihenfolge stehen. Das V.I.-Prinzip funktioniert nicht mehr, weil 0 nie erreicht wird. Das T.I.-Prinzip funktioniert weiterhin. Es ist wirklich allgemeiner. Außerdem braucht es keinen Induktionsanfang, aber das ist Haarspalterei. Das V.I.-Prinzip heißt "vollständige Induktion" und funktioniert nur für die natürlichen Zahlen (und für Wohlordnungen, die sich ordnungstreu auf sie abbilden lassen). Das T.I.-Prinzip heißt "transfinite Induktion" und funktioniert für alle Wohlordnungen. Übungsaufgabe: Man beweise folgenden Satz. Satz: Es sei F die Menge abbrechender Folgen natürlicher Zahlen (oder, was dasselbe ist, die Menge der Folgen natürlicher Zahlen, bei der alle bis auf endlich viele Glieder 0 sind). Es sei f eine Funktion von F nach F mit folgenden Eigenschaften: f(O)=O für die Folge O, die nur aus Nullen besteht. Ist (a_i) eine Folge nicht nur aus Nullen und die Folge (b_i) das Bild davon vermöge f, dann gibt es einen Index k, so dass b_kk [anschaulich: irgendwo in der Folge wirds kleiner und weiter hinten wenigstens nicht größer, davor mag passieren was will]. Dann gibt es zu jeder Folge s eine natürliche Zahl n, so dass f^n(s) die Folge nur aus Nullen ist. Mit transfiniter Induktion relativ leicht zu beweisen, mit vollständiger Induktion deutlich mühsamer. Helmut Richter ---------------------------------------------------------------------- From a282244 Thu Oct 5 09:58:12 DST 2000 From: a282244 Newsgroups: sci.math Subject: Re: induction & well ordering References: <8rg0ev$ff4$1@nnrp1.deja.com> <39DBE718.D055BC03@texas.net> From: Helmut.Richter@lrz-muenchen.de (Helmut Richter) Reply-To: Helmut.Richter@lrz-muenchen.de Organization: Leibniz-Rechenzentrum, Muenchen (Germany) James Buddenhagen writes: >barometer wrote: >> >> Is it true that well ordering in the naturals is equivalent to the >> induction principle (in the naturals again?). >> >Yes. I would have said no. More detail below. There are *two* induction principles: - one is often called "mathematical" induction, although it is not more "mathematical" than the other one. It draws a conclusion from one element to its successor. As the least element is not a successor, there must be a separate induction basis. - the other is called "transfinite" induction. It draws a conclusion from *all* elements less than x to x. As there is a well-defined set of elements less than the least, there is no need for a separate induction basis. If we define in an inductively defined set a well-ordering by the transitive closure of the successor relation, we get a connexion from M.I. to T.I. If we define in a well-ordered set the successor of x to be the least element greater than x (uniquely defined if there is any), we get a connexion from T.I. to M.I. The first transition works always. The seconds gives rise to an induction principle only if each element is a successor. To sum up: M.I. works only for sets where each element except the smallest is a successor, as is the case in Peano arithmetic. T.I. works in every well-ordered set. If the original poster meant M.I. (which I assume because it is more well-known), then his question has two possible answers: - Yes, because any two true sentences are equivalent. - No, because the mere fact that the natural numbers are well-ordered is not sufficient to establish M.I. I find the second answer more elucidating. Helmut Richter ---------------------------------------------------------------------- From a282244 Sun Oct 15 12:09:56 DST 2000 From: a282244 Newsgroups: de.sci.mathematik Subject: Re: Non-standard-Induktion References: <39e48b2f.101916@news.lrz-muenchen.de> From: Helmut.Richter@lrz-muenchen.de (Helmut Richter) Reply-To: Helmut.Richter@lrz-muenchen.de Organization: Leibniz-Rechenzentrum, Muenchen (Germany) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit lfm@gmx.de (Lukas-Fabian Moser) writes: >kennt ihr Beispiele für Beweise mittels Non-standard-Induktion >(beispielsweise n->n-1 und n->2n)? Ich habe nur im Buch "Proofs from >The Book" eines gefunden, wird das woanders öfter verwendet? Kein neues Beispiel, dafür der Versuch, sich von Begriffen wie "0", "n+1" zu lösen, die nur für die natürlichen Zahlen eine Bedeutung haben. Induktion kann man ganz kurz so charakterisieren: Auf jeden Fall hat man eine Wohlordnung (eine Ordnung, bei der jede nichtleere Menge ein kleinstes Element hat) auf der Menge, für deren Elemente man etwas beweisen will. Dann kann man nach zwei Weisen vorgehen; sei dabei F[x] die zu beweisende Eigenschaft des Elementes x: 1) Wenn (für alle y F[y]) -> F[x], dann für alle x : F[x] Die Gültigkeit an einer Stelle wird also aus der Gültigkeit an *allen* vorangehenden Stellen geschlossen (transfinite Induktion). 2) Sei N[x,y] die Eigenschaft von x, Nachfolger eines Elementes y zu sein und L[x] die Eigenschaft von x, kein Nachfolger zu sein. Das lässt sich, ohne Berufung auf Peano, allein in der Sprache der Wohlordnung ausdrücken: N[x,y] = x>y und für alle z>y : x<=z L[x] = es gibt kein y : N[x,y] Einen Nachfolger von x gibt es dabei, wenn x nicht das größte Element ist; dann gibt es genau einen. Damit die Induktion: Wenn für alle y : L[y] -> F[y] und für alle y : (F[y] -> für alle z : (N[z,y] -> F[z])) Dabei ist das letzte "für alle" ein Overkill, da es höchstens ein solches z, eben den Nachfolger von y, gibt - es könnte aber auch keines geben, und so bleibt die Aussage trotzdem eindeutig. Die Gültigkeit an einer Stelle wird also aus der Gültigkeit nur an der Vorgängerstelle geschlossen und muss als Induktionsanfang getrennt an allen Stellen gezeigt werden, die keine Vorgänger haben (vollständige Induktion). Im Falle der "standardmäßigen" vollständigen Induktion hat man also den Fall 2, wobei dort 0 die einzige Zahl mit der Eigenschaft L[] ist. Die "Non-Standard"-Fälle sind einfach andere Wohlordnungen auf N, z.B. xy (im üblichen Sinn) Das gibt dann die Induktion wie von Lukas-Fabian als Beispiel angegeben. Helmut Richter