Overleg:Volledige inductie

"Volledige inductie" is eigenlijk wat later in het artikel "sterke inductie" wordt genoemd. Het artikel beschrijft dus eigenlijk "wiskundige inductie". In die zin is het huidige artikel misleidend. [commentaar van een hoogleraar wiskunde]

== Eerlijk gezegd vind ik al die nieuwe voorbeelden nogal overdreven. Ze brengen niets nieuws. Wat mij betreft blijft alleen het eerste voorbeeld staan. Madyno (overleg) 15 okt 2011 23:13 (CEST)

Ieder geheel getal is door een priemgetal te delen

Kan zijn, maar mijns inziens is het volgende voorbeeld niet overdreven.

Inductiebegin

2 is door een priemgetal te delen, door 2 zelf.

Inductieveronderstelling

Tot en met n zijn alle getallen door een preimgetal te delen.

Inductiestap

• Voor het geval n+1 zelf een priemgetal is, is de inductiestap gedaan.
• Anders zijn er twee getallen a en b, zodat $n+1=a\cdot b$. Voor a en b geldt dat $2\leq a,b\leq n$. a en b zijn beide volgens de inductieveronderstelling door een priemgetal te delen. Kies een priemgetal p waarvoor geldt dat a door p is te delen. Nu moet n+1 ook door p zijn te delen. Daarmee is ook voor dit geval de inductiestap gedaan.

ChristiaanPR (overleg) 18 mrt 2013 20:36 (CET)

Waarom zou je hier inductie gebruiken? Als het getal priem is zijn we klaar; als het niet priem is, is het deelbaar door een priemgetal. Klaar.Madyno (overleg) 18 mrt 2013 20:30 (CET)

• Wannner een getal geen priemgetal is, is het het product van tenminste twee andere getallen. Dat betekent nog niet dat het door een priemgetal is te delen. ChristiaanPR (overleg) 18 mrt 2013 20:37 (CET)

Oke, ik zie wat je bedoelt. Dan is inductie op[ z'n plaats. Neem het voorbeeld op, en maak ook duidelijk waarom inductie hier nuttig is. Madyno (overleg) 18 mrt 2013 21:21 (CET)

Beperking

Ik heb de paragraaf "Beperking" niet geschreven, maar vind het wel interessant. Waarom heb je hem weggedaan? Madyno (overleg)

• hallo Madyno, Het lemma zelf vind ik goed genoeg zoals het er nu staat, voorlopig vind ik dus dat het niet hoeft te worden aangevuld. De voorbeelden vind ik duidelijk. Bovenstaand bewijs lijkt mij voor de wiskunde belangrijk, dat is waarom ik het hier heb opgeschreven. Mijn idee is, dat deze stelling de enige uitzondering is op de "beperking", die ik heb weggehaald. Die had ik zelf ook geschreven. Om de beperking dan weer iets te gaan veranderen, is te veel wetenschap baseren op één voorbeeld. Voor mij is het zo klaar. ChristiaanPR (overleg) 23 mrt 2013 19:31 (CET)

• toch nog iets veranderd ChristiaanPR (overleg) 23 mrt 2013 23:36 (CET)

Ik heb je veranderingen van de vorm "bewezen is" -> "is bewezen" laten staan, maar dergelijke veranderingen betreffen alleen jouw persoonlijke smaak, en zijn dus niet relevant, en eigenlijk ook niet op z'n plaats. Madyno (overleg) 24 mrt 2013 14:42 (CET)

Vandermonde-matrix

De gelijkheid in voorbeeld 4. over de Vandermonde-matrix is met volledige inductie te bewijzen, maar van de Vandermonde-matrix staat op de pagina zelf geen enkele toepassing. Dat is het bezwaar van bewijzen van volledige inductie, dat het, afgezien van voorbeeld 2 over het ontbinden in priemgetallen, steeds alleen een oefening blijft. Daarom was voor mij het toevoegen van het voorbeeld van de Vandermonde-matrix niet nodig geweest. ChristiaanPR (overleg) 17 jun 2014 22:06 (CEST)

Literatuur

• "The theory of the foundations of mathematics - 1870 to 1940" - M. Scheffer - De enige website die ik er op het internet over vind: deze website is zo rommelig dat ik de titel uit de literatuurlijst heb weggehaald. ChristiaanPR (overleg) 19 nov 2021 09:19 (CET)

Ik ben het niet die een wijziging voorstelt. Jouw argumentatiwe lijkt me beslist onvoldoende. Kijk op blz. 34, daar wordt het principe besproken. Madyno (overleg) 19 nov 2021 18:25 (CET)

Geen boek als bron gebruiken dat nergens is te vinden terwijl er literatuur te over is waar de volledige inductie in staat uitgelegd. ChristiaanPR (overleg) 19 nov 2021 20:25 (CET)

Als buitenstaander/leek valt het me op dat uitgever en publicatiejaar ontbreken. Dat zou wel nuttig zijn om een indruk van de gezaghebbendheid te krijgen. Encycloon (overleg) 19 nov 2021 22:26 (CET)

Je bedoelt het artikel van Davis, dat als pdf op het web beschikbaar is. Het gaat erom dat de volledige inductie in een andere bron wordt uitgelegd en dat is het geval. Je kunt als datum gisteren aanhouden, de dag dat ik het op de wikipedia heb gezet. Ik zie vooralsnog het bezwaar niet dat Davis in zijn artikel niet de datum heeft geschreven dat hij het heeft gepubliceerd.

Het valt mij op dat het artikel uit de Bulletin of the American Mathematical Society uit 1909 is, terwijl op de Nederlandse wikipedia staat dat de eerste jaargang van dat tijdschrift in 1979 was. ChristiaanPR (overleg) 20 nov 2021 08:00 (CET)

De website van het Bulletin of the American Mathematical Society zelf zegt dat de eerste uitgave in 1894 was. Die webpagina van het NCBI waar dat jaartal 1979 kennelijk vandaan komt vermeldt ook een voorgangertijdschrift dat ook ook "Bulletin of the Mathematical Society" heet (en heel toevallig ook voor het eerst in 1894 gepubliceerd werd) maar een ander ISSN-nummer heeft. Ik ga er dus vanuit dat het gewoon om één tijdschrift gaat, dat om technische redenen twee NCBI-pagina's heeft.

Verder deel ik jouw mening dat je "[g]een boek als bron [moet] gebruiken dat nergens is te vinden" duidelijk niet. Literatuur moet niet alleen beschikbaar maar ook gezaghebbend zijn. Boeken zijn misschien niet via het internet te lezen, ze zijn vaak juist wel gezaghebbend. Die tekst van Davis is weliswaar via het internet beschikbaar, maar het is gewoon een notitie voor studenten ("lecture notes") van een college dat begin 21ste eeuw een paar jaar achter elkaar op een Amerikaanse universiteit gegeven werd: het is vast betrouwbaar maar niet gezaghebbend en daarom als bron minder geschikt. Dat artikel van M. Scheffer heb je naar mijn mening terecht verwijderd. Het lijkt te gaan om een soort scriptie van een student. Die scriptie heeft lang online gestaan en daarom is er blijkbaar ook naar gerefereerd, maar inmiddels lijkt hij van het internet verdwenen. Hoopje (overleg) 20 nov 2021 09:21 (CET)

Wat betekent "nergens te vinden". Ik heb een kopie uit 2002, waarin staat:
"Mark Scheffer, id. 415968, e-mail: zax@chello.nl. Last changes:

March 22, 2002. This report is part of a practical component of the Computing Science study at the Eindhoven University of Technology." Het zal me worst zijn of het wel of niet gebruikt wordt, maar rücksichtslos verwijderen omdat je het niet kunt vinden, gaat me te ver. Madyno (overleg) 20 nov 2021 09:44 (CET)

In de context was redelijk duidelijk wat ChristiaanPR met "nergens te vinden" bedoelde, namelijk dat het op internet nergens te vinden was. Verder ben ik het, zoals ik hierboven ook schreef, met je eens dat "rücksichtslos verwijderen omdat je het niet kunt vinden" in het algemeen niet goed is, maar in dit specifieke geval gaat het over een werkstuk van een student (studentennummer 415968), dus dat werk is, behalve "niet te vinden", ook nog eens niet gezaghebbend. Ik heb zelf geen kopie, dus over de kwaliteit van het werk kan ik niet oordelen, maar daar gaat het ook niet over. Hoopje (overleg) 20 nov 2021 10:09 (CET)

@ChristiaanPR: nee, op zich had ik het over Scheffer. Encycloon (overleg) 20 nov 2021 10:58 (CET)

Verduidelijking

Gebruiker:Hoopje heeft een vraag gesteld over mijn tekst "Als de uitspraak $E_{n+1}$ voor een bepaalde $n$ niet meer gedefinieerd is of de inductiestap anderszins voor de waarde $n$ niet meer geldt, dan kan inductie nog wel worden gebruikt om de uitspraak voor een beperkt aantal waarden te bewijzen, namelijk tot en met $n$." Ik begrijp niet wat er onduidelijk aan is, maar https://nl.wikipedia.org/w/index.php?title=Inductie_(wiskunde)&oldid=64233372#Eenvoudig_voorbeeld verheldert het misschien. We kunnen de tekst ook daarnaar verplaatsen, of ons beperken tot het voorbeeld. - Patrick (overleg) 1 mei 2023 23:42 (CEST)

Mijn vraag gaat er niet over of je zo dingen kunt bewijzen. Dat is ongetwijfeld zo (maar als je je sowieso al zulke sterke aannames over de verzameling kunt doen dat het een eindige verzameling wordt, dan vraag ik me wel af of je zo'n stapsgewijze aanpak in de praktijk wel nodig hebt). Waar mijn twijfel over gaat, is dat dat "volledige inductie" genoemd wordt. Geen van de andere Wikipedia-artikelen over volledige inductie waarvan ik de taal begrijp noemt zo'n bovengrens. Dan vind ik het niet gek om een bron te vragen als iemand die bewering in het artikel wil opnemen.

Overal waar "volledige inductie" gedefinieerd wordt (inclusief overigens het axioma in bijv. Peano-rekenkunde) noemt twee gevallen: de eigenschap geldt voor 0 (of een andere ondergrens); en als de eigenschap geldt voor n, dan ook voor n+1. Als je die twee gevallen bewezen hebt, dan geldt de eigenschap voor alle natuurlijke getallen. Niet voor alle natuurlijke getallen tot een bepaalde bovengrens, alle natuurlijke getallen. Je kunt dat tweede geval natuurlijk aanpassen (niet meer "voor alle n" maar "voor alle n kleiner dan k"). Maar dat heet dan naar mijn mening geen "volledige inductie" meer.

De oorspronkelijke bewering kwam trouwens van ChristiaanPR. Je hebt de tekst wat verbeterd, maar uiteindelijk niet die bewering eruit gehaald, waardoor een bronvraag nog steeds van toepassing is. ChristiaanPR verwees naar een voorbeeld op de Engelse Wikipedia. Daar stond: "Analogously, by induction, $c_{i}$ is a multiple of $p$ for all $i<r$ , which finishes the proof." (einde bewijs). Het is het enige voorkomen van het woord "induction" op die pagina. Het is dus ofwel niet "analogously" ofwel niet "by induction". En dat noemt ChristiaanPR dan een voorbeeld terwijl ik daar alleen maar een bewering in zie, dat iets met inductie bewezen zou kunnen worden.

Wat betreft het verplaatsen: daar is het in ieder geval beter op zijn plaats. Bij de welgefundeerde inductie wordt alleen een verzameling met een welgefundeerde ordening aangenomen. Dus kan het zijn dat die verzameling eindig is. Maar ook daar is dat een randgeval. Inductie is niet uitgevonden om dingen over eindige verzamelingen te bewijzen. Het is uitgevonden om dingen over oneindige verzamelingen te bewijzen. En als van die paar regels die we erover kwijt kunnen de helft over een praktisch irrelevant randgeval gaat, dan klopt er gewoon iets niet, ook niet als elke zin op zichzelf waar is. Hoopje (overleg) 2 mei 2023 07:55 (CEST)

Ik was en ben erg verbaasd over je vraag "Als E(n+1) voor een bepaalde n niet meer gedefinieerd is, of niet meer geldt, hoe bewijs je dan E(n) impliceert E(n+1) ??", omdat ik schreef "dan kan inductie nog wel worden gebruikt om de uitspraak voor een beperkt aantal waarden te bewijzen, namelijk tot en met $n$.", dus voor deze n is E(n+1) helemaal niet aan de orde. Je bronvraag suggereert ook dat je van iets heel eenvoudigs een bron verlangt. Ik heb expres 'inductie' geschreven in plaats van 'volledige inductie', het artikel Inductie (wiskunde) gebruikt die term ook in het geval van een eindige verzameling, zoals je zelf nu bevestigt. De toevoeging van een interessant voorbeeld is gewenst, maar niet noodzakelijk voor de indeling van vormen van inductie. - Patrick (overleg) 2 mei 2023 09:40 (CEST)

Het artikel waar je dat schreef, was Volledige inductie, niet Inductie. En als je $E(n)\rightarrow E(n+1)$ alleen kan bewijzen voor een bepaalde deelverzameling van $\mathbb {N}$, dan kan je $E(n)\rightarrow E(n+1)$ niet bewijzen. Niet een beetje, niet. Terwijl voor volledige inductie nu juist wel wordt geeist dat je $E(0)$ en $E(n)\rightarrow E(n+1)$ bewijst. Die bovengrens wordt in geen enkele uitleg van volledige inductie die ik ken gemeld. Ik snap dus niet waarom jullie die perse willen noemen.

Op het artikel Inductie is de situatie anders. Daar is het wat mij betreft een kwestie van balans. We hebben daar één niet al te lang paragraafje over welgefundeerde inductie. Ja, je kunt zeggen: een verzameling $V$ met een welgefundeerde ordening kan ook eindig zijn. Maar dat is natuurlijk niet de gebruikelijke use case van inductie. En als je dan vooral over dat geval gaat uitweiden dan wekt dat, naar mijn mening, alleen maar verwarring. Hoopje (overleg) 2 mei 2023 10:51 (CEST)

Een preciezere formulering is 'Als $E(k)$, en voor $m$ = $k$ t/m $n-1$ geldt $E(m)\rightarrow E(m+1)$, dan geldt $E(m)$ voor $m$ = $k$ t/m $n$.' Dat je niet kan zeggen 'voor $m$ = $k$ t/m $n-1$ geldt $E(m)\rightarrow E(m+1)$' is natuurlijk onzin. - Patrick (overleg) 2 mei 2023 12:13 (CEST)

Eenvoudige voorbeelden kunnen ook nuttig zijn voor een deel van de lezers. Meer geavanceerde voorbeelden kunnen worden toegevoegd. - Patrick (overleg) 2 mei 2023 12:25 (CEST)

Het is inderdaad een andere formulering. Daarom vroeg ik ook om een bron waarin (volledige) inductie met jouw alternatieve formulering beschreven wordt. Ik ken zo'n bron namelijk niet. En aan eigen onderzoek doen we hier, zoals je weet, niet.

Eenvoudige voorbeelden zijn inderdaad goed. Maar waarom denk je dat een voorbeeld waarin "Als $E(n)$ en $n<m$, dan geldt $E(n+1)$" bewezen wordt eenvoudiger is? Dat is inderdaad een eindige verzameling, maar dat bewijs heeft plotseling twee in plaats van één aannames, en die tweede aanname ($n<m$) is blijkbaar nog nodig ook, want anders kon je gewoon normale volledige inductie toepassen. Hoopje (overleg) 2 mei 2023 13:02 (CEST)

Ik zeg niet dat het eenvoudiger is, dat is een kwestie van smaak. - Patrick (overleg) 2 mei 2023 21:48 (CEST)

Het artikel Inductie (wiskunde) geeft duidelijk aan dat deze methode vooral voor oneindige verzamelingen wordt gebruikt. Er staat daar nergens dat de methode ook voor eindige verzamelingen kan worden gebruikt. Dat is volgens het Engelse artikel over het criterium van Eisenstein wel nodig. Die bron is geen eigen onderzoek. Waar vind ik iets over inductie over een eindige verzameling?

Ik had er een zin over geschreven, minder dan een regel. De hele paragraaf is nu twaalf regels. ChristiaanPR (overleg) 3 mei 2023 19:25 (CEST)