Overleg:Inductie (wiskunde)

Mocht Berteun dit lezen, ik zou graag iets doen aan het samenvoegen van onze artikelen over dit onderwerp. En deze domme tekst is omdat ik de overlegpagina aan moest maken.

domein

Vanaf Bewijs door structuurinductie heeft het niets meer met wiskunde te maken. In één van de eerste regels staat, dat inductie gedefinieerd is over een vastgelegde verzameling. Zo moet het ook. Maar in de paragraaf Bewijs door structuurinductie gaat het over andere algemene structuren en hebben we de duidelijk vaste verzamelingen achter ons gelaten. Zo kan je alles beweren. ChristiaanPR (overleg) 14 jan 2011 23:45 (CET)

Ook structurele inductie is gedefinieerd over een vastgelegde verzameling, en wordt in het bijzonder gebruikt als die verzameling inductief gedefinieerd is (bijv. termen, logische formules, etc). Het LEGO-voorbeeld is misschien inderdaad wel wat ongelukkig, dat ben ik met je eens, maar structurele inductie wordt in de wiskunde zéér veel gebruikt. Hoopje (overleg) 15 jan 2011 10:02 (CET)

Hoopje, ik citeer: "vakgebieden binnen de wiskunde en informatica die naar formele constructies kijken, of anderszins de geordende verzamelingen achter zich laten". Zijn de welgedefinieerde verzamelingen, waar jij over praat wel of niet geordend? Zonder goed voorbeeld is het niet duidelijk. Niet dat ik dat begrijp, maar zo ziet het eruit alsof je in één keer naar de hogere theorie van elliptische functies springt. Ik geloof dat ik het met jouw antwoord niet eens ben. ChristiaanPR (overleg) 15 jan 2011 20:53 (CET)

Natuurlijk zijn die verzamelingen (welgefundeerd) geordend, anders zou je helemaal geen inductie kunnen toepassen. Ze zijn echter vaak impliciet geordend (door de inductieve definitie) en vaak ook niet totaal geordend. Nogmaals, voorbeelden zijn: logische formules (geordend door "subformule"), termen (geordend door "subterm"), etc. Dat soort inductie wordt vaak structurele inductie (of structuurinductie) genoemd omdat je als het ware de structuur van de formules in je bewijs opbouwt, en dat soort inductie wordt zéér vaak toegepast. (Het tweede deel van de zin die je citeerde is overigens inderdaad misleidend, ik zal hem verwijderen.) Hoopje (overleg) 16 jan 2011 00:54 (CET)

Ik begrijp er niets van. Hetgeen er in Bewijs door structuurinductie en in Paradox staat is retoriek. Het gaat op geen enkele manier meer over getallen en dat is een vereiste voor wiskunde. ChristiaanPR (overleg) 27 feb 2011 23:13 (CET)

Dan hanteer je een zeer smalle definitie van wiskunde. Verzamelingenleer, Categorietheorie, Logica, Topologie, Typentheorie etc, etc, etc, zijn allemaal deelgebieden van de wiskunde waar niet noodzakelijk getallen in voorkomen. Bovendien wordt inductie niet alleen in de wiskunde gebruikt, maar ook in vakgebieden die (tegenwoordig) soms niet meer als wiskunde worden gezien, zoals theoretische informatica. Ik wil het stukje over structuurinductie wel iets formeler maken, maar vandaag heb ik daar zeer waarschijnlijk geen tijd voor. Hoopje (overleg) 28 feb 2011 08:30 (CET)

Kom je dan niet bij Gödel terecht? ChristiaanPR (overleg) 28 feb 2011 18:06 (CET)

Wat bedoel je precies? Gödel heeft naar mijn weten in de meeste deelgebieden die ik noemde niet gewerkt. Ik kan me voorstellen dat je naar Gödel-nummers verwijst, maar hoe zijn die relevant voor de discussie? Hoopje (overleg) 28 feb 2011 21:44 (CET)

In mijn intuïtie zijn alleen berekeningen met getallen, met geometrische figuren en variabelen die deze twee representeren mogelijk. Hetgeen ik over logica heb begrepen is dat het sluitstuk daarvan de onvolledigheidsstelling van Gödel is. Met mijn definitie van wiskunde kan ik zeer goed uit de voeten. ChristiaanPR (overleg) 28 feb 2011 22:30 (CET)

De onvolledigheidsstelling is inderdaad een belangrijke stelling binnen de logica, maar sindsdien is er nog een hoop uitgevonden. Sluitstuk zou ik het niet willen noemen. Bovendien snap ik noch steeds niet zo wat dat met de discussie te maken heeft.

Ook noemt je al geometrische figuren. Dat zijn ook geen getallen, hoewel je ze door getallen kunt representeren (maar je kunt Word-documenten ook door getallen representeren). Categorieën zijn geen getallen. Typen zijn geen getallen. Waarheidswaarden zijn geen getallen. Toch worden die door deelgebieden van wiskunde bestudeerd. Je kan misschien zelf goed uit te voeten met jouw kijk op wiskunde, maar voor mij is die in ieder geval veel te nauw. Hoopje (overleg) 28 feb 2011 23:53 (CET)

Op mijn eigen niveau, maar ik geloof dat ik maar gewoon weer sommen ga maken. ChristiaanPR (overleg) 1 mrt 2011 01:08 (CET)

Overigens ziet Voorbeeld 5 er al wel weer veel mooier uit. ChristiaanPR (overleg) 1 mrt 2011 01:10 (CET)

Eenvoudige lezer

Ik denk niet dat de eenvoudige lezer, die wil weten wat volledige inductie naar n inhoudt, erg geholpen is met de opbouw van dit artikel. (Ik was het) Madyno (overleg) 17 jul 2011 10:44 (CEST)

Mee eens, het artikel is duidelijk voor verbetering vatbaar. Mvg JRB (overleg) 17 jul 2011 01:00 (CEST)

Ik denk erover een apart artikel over (gewone) "Volledige inductie" te schrijven, Madyno (overleg) 17 jul 2011 10:44 (CEST)

Prima, dan kan dat stuk voor het grootste deel afgesplitst worden. Ik zag verder in de Engels-, Duits- en Franstalige wikipedia een paar alinea's die wel bruikbaar zijn om met name in het begin van dit artikel een en ander wat eenvoudiger uit te leggen. Mvg JRB (overleg) 17 jul 2011 11:43 (CEST)

Dit lemma gaat eigenlijk over volledige inductie, wat Madyno daar heeft geschreven klopt. Voor zover het in dit lemma over volledige inductie gaat staat er voor de helft veel te veel en is het voor de andere helft niet te begrijpen. Inductie in de wiskunde betekent, dat zonder dat je een stelling al kan bewijzen, ziet dat de stelling waar is. Dat komt ook overeen met wat er in het lemma Deductie versus inductie staat, hoewel wat daar staat ook nog kan worden verbeterd. ChristiaanPR (overleg) 23 okt 2011 16:59 (CEST)

Volledige inductie

Er is een apart lemma over volledige inductie. Daarom vind ik dat dit onderwerp in dit lemma te uitgebreid behandeld wordt. Madyno (overleg) 27 mei 2014 12:09 (CEST)

Ik ben het met je eens dat de situatie op dit moment niet optimaal is. Ik stel voor volledige inductie in dit artikel alleen samenvattend te behandelen en d.m.v. een "hoofdartikel"-constructie naar volledige inductie te verwijzen. Daarnaast kan ook het artikel transfiniete inductie worden uitgebreid en in dit artikel worden genoemd. Als dan alle vormen inductie eigen artikelen krijgen, ben ik er ook voor structurele inductie een eigen artikel te geven en daar met een "hoofdartikel"-constructie naar te verwijzen. In dit artikel blijven dan de algemene principes en verwijzingen naar de speciale vormen staan. Hoopje (overleg) 27 mei 2014 15:40 (CEST)

Het compleet laten verdwijnen van voorbeelden zonder ze te laten terugkeren in het andere artikel vind ik tamelijk kort door de bocht. Een motivatie voor het niet laten terugkeren van de diverse voorbeelden heb ik niet gezien. Bob.v.R (overleg) 3 jun 2014 21:28 (CEST)

Er is een apart lemma gewijd aan volledige inductie. Ik vind het absoluut onnodig en ook ongewenst om zaken dubbel te vermelden. Madyno (overleg) 4 jun 2014 00:28 (CEST)

Na diverse acties van twee gebruikers zitten we nu na twee dagen met artikel waarin geen enkel voorbeeld meer staat. Redelijk absurd, als je kijkt wat de uitgangssituatie was. Is het de beide gebruikers misschien mogelijk om te bedenken dat er misschien ook nog lezers van dit artikel zijn? Bob.v.R (overleg) 4 jun 2014 13:35 (CEST)

De acties zijn nog niet afgerond. Wat het lemma over inductie betreft, de basisgedachte dat het een overzicht geeft van wat inductie inhoudt, is redelijk verwezenlijkt. Het lemma over volledige inductie ga ik nog bekijken. Madyno (overleg) 4 jun 2014 14:05 (CEST)

Ik wijs er nogmaals op dat het artikel in de huidige vorm geen enkel voorbeeld bevat (twee dagen terug nog vijf voorbeelden). Bob.v.R (overleg) 4 jun 2014 18:43 (CEST)

Allemaal voorbeelden van volledige inductie! Kijk maar bij dat lemma. Madyno (overleg) 4 jun 2014 20:14 (CEST)

Welgefundeerde verzameling

In het lemma wort gesproken over een welgefundeerde verzameling. De Engelse Wikipedia versrtaat daaronder echter heel wat anders. Madyno (overleg) 29 mei 2014 21:56 (CEST)

Zo te zien komt 'Welgefundeerde relatie' overeen met 'Well-founded relation'. Wat klopt er niet volgens jou? Bob.v.R (overleg)

Als je goed kijkt staat hierboven: "welgefundeerde verzameling". Madyno (overleg) 30 mei 2014 11:19 (CEST)

Volgens mij gaat het om een verzameling met een welgefundeerde partiele ordening.Madyno (overleg) 30 mei 2014 11:25 (CEST)

Akkoord. Maar op de Engelse wikipedia is 'Well-founded set' een redirect naar 'Well-founded relation'. Wat bedoel je met 'heel wat anders'? Bob.v.R (overleg) 30 mei 2014 14:04 (CEST)

De Engelse W. verwijst "Well founded set" inderdaad door naar "well founded relation", maar vermeldt daar: In set theory, a set x is called a well-founded set if the set membership relation is well-founded on the transitive closure of x. The axiom of regularity, which is one of the axioms of Zermelo–Fraenkel set theory, asserts that all sets are well-founded. Madyno (overleg) 30 mei 2014 23:56 (CEST)

Dank je voor de toelichting. Inderdaad, ik zie het nu ook. We zouden in het artikel dus niet de term 'welgefundeerde verzameling' moeten gebruiken. Bob.v.R (overleg) 31 mei 2014 07:17 (CEST)

Nee, dat denk ik ook. Het is toch voldoende over een verzameling met een welgefundeerde ordening (relatie?) te spreken.Madyno (overleg) 31 mei 2014 20:36 (CEST)

Overigens noemt de Duitse W. wel een "(wohl)fundierte Menge" in de zin zoals het lemma dit gebruikt.Madyno (overleg) 31 mei 2014 21:01 (CEST)

Uit diverse literatuur op internet maak ik op dat een verzameling met een welgefundeerde relatie daarop veelal een welgefundeerde verzameling wordt genoemd. De definitie in de Eng. W. lijkt een speciaal geval voor de relatie "element van".Madyno (overleg) 1 jun 2014 00:40 (CEST)

Directe voorganger

In het lemma staat: Naast welgefundeerdheid is het echter ook nog noodzakelijk dat ieder element van de verzameling een directe voorganger heeft in de partiële ordening. Daar begrijp ik niets van.Madyno (overleg) 29 mei 2014 21:59 (CEST)

Bedoel je dit serieus, of is dit een 'standpunt' om een discussie te starten? Ik heb zojuist de opmaak van de door jou bedoelde sectie gewijzigd, ik denk dat het nu helderder ingedeeld is. Groeten, Bob.v.R (overleg) 29 mei 2014 22:26 (CEST)

Zeker bedoel ik dit serieus. Als de ordening welgefundeerd is, heeft iedere keten een minimaal element. Maar een minimaal element heeft geen directe voorganger.Madyno (overleg) 30 mei 2014 11:28 (CEST)

Okay, er moeten dus inderdaad twee zaken worden opgehelderd. Een definitie van 'directe voorganger' ontbreekt en er moet een uitzondering worden gemaakt voor minimale elementen. Bob.v.R (overleg) 30 mei 2014 14:11 (CEST)

Hoewel dat in ons artikel wel gesteld wordt, is het volgens mij ook helemaal niet waar dat het noodzakelijk is dat ieder element ofwel minimaal is ofwel een directe voorganger heeft. Het schema

$\forall x\in X\,[(\forall y\in X\,(y<x\to P(y)))\to P(x)]\to \forall x\in X\,P(x)$

is geldig voor alle welgefundeerde verzamelingen. Zie de Engelse WP. Hoopje (overleg) 30 mei 2014 14:31 (CEST)

Verbetering

Ik heb alvast een poging tot verbetering gedaan. Madyno (overleg) 31 mei 2014 22:26 (CEST)

Is er een bron voor de term 'welgefundeerde inductie'? Bob.v.R (overleg) 31 mei 2014 22:37 (CEST)

Zowel de D. als de E. W. noemen deze term. Wel is de E. algemener. Madyno (overleg) 31 mei 2014 23:16 (CEST)

De recent toegevoegde opmerking over het formeel mogen weglaten van de afzonderlijke eis aan minimale elementen lijkt volgens de logica correct, maar ik ben het ermee eens dat de eis er toch staat, anders dan wordt het wel erg cryptisch. En in de praktijk zal die stap (bewijzen voor minimale elementen) toch moeten worden gezet. Bob.v.R (overleg) 2 jun 2014 01:43 (CEST)

Daarom staat het ook als opmerking. Madyno (overleg) 2 jun 2014 10:33 (CEST)

Minimaal element en keten

Zojuist was er wat heen en weer ge-edit tussen Hoopje en mij. Dit brengt aan het licht dat twee zaken nog kunnen worden verbeterd. Ten eerste is het begrip 'keten' niet gedefinieerd. Dit blijkt nu voor misverstanden te zorgen. We hebben kennelijk een strenge definitie nodig van het begrip 'keten'. Ten tweede wordt er gesproken over een 'keten die een minimaal element bevat'. Deze formulering blijkt ambigu te zijn, er zijn minstens twee interpretaties bij te bedenken (misschien nog meer). Interpretatie 1: de keten moet een element bevatten waarvoor er binnen de keten geen voorganger te vinden is. Interpretatie 2: de keten moet minstens een van de minimale elementen uit de overkoepelende verzameling bevatten. Groeten, Bob.v.R (overleg) 4 jul 2015 13:35 (CEST)

Sowieso wordt een totaal geordende verzameling een keten genoemd. Maar hier gaat het om aftelbare ketens. Verder wordt m.i in een 'keten die een minimaal element bevat', een minimaal element t.o.v de keten bedoeld. Madyno (overleg) 4 jul 2015 14:56 (CEST)

Het gaat over alle niet-lege ketens, niet alleen de aftelbare. Een welgefundeerde verzameling is per definitie een verzameling V met een ordening < zodat elke niet-lege verzameling een minimaal element heeft m.b.t. <. Natuurlijk gaat het inderdaad over een minimaal element t.o.v. die deelverzameling, anders zou geen enkele verzameling (met minstens één niet-minimaal element) welgefundeerd zijn. Hoopje (overleg) 4 jul 2015 18:22 (CEST)

Dat weet ik, maar het gaat me om welgefundeerde inductie. Het lemma suggereert dat elke aftelbare keten een minimaal element heeft, en dat zag ik ook ergens op de Engelse Wiki. Helaas kan ik het o[p dit moment niet terugvinden. Ik zoek verder. Madyno (overleg) 4 jul 2015 20:32 (CEST)

Weer gevonde: Equivalently, assuming some choice, a relation is well-founded if and only if it contains no countable infinite descending chains: that is, there is no infinite sequence x0, x1, x2, ... of elements of X such that xn+1 R xn for every natural number n. Madyno (overleg) 4 jul 2015 20:50 (CEST)

Dat gaat om aflopende rijtjes, niet om oplopende ketens. In dit artikel wordt expliciet $x_{0}<x_{1}<x_{2}<\cdots$ genoemd. Dat elke keten (niet alleen een aftelbare) een minimaal element heeft volgt direct uit de definitie van welgefundeerde verzameling. Om te laten zien dat daaruit volgt dat er geen oneindig dalende ketens bestaan heb je het keuzeaxioma nodig.

Ik stel voor de paragraaf om te schrijven, en in plaats van "elke keten heeft een kleinste element" te schrijven dat er geen "oneindige aflopende rijtjes" bestaan. Dat geeft ook meer intuitie waarom inductie een geldige bewijsmethode is.

Hoopje (overleg) 4 jul 2015 21:35 (CEST)

Gelet op mijn eerstgenoemde punt heb ik een begin gemaakt met Oneindig dalende keten, gestart als een vertaling van de Engelstalige versie. Bob.v.R (overleg) 4 jul 2015 23:29 (CEST)

Ik zou liever een lemma 'Keten' invoeren en daarin de diverse mogelijkheden bespreken. Madyno (overleg) 4 jul 2015 23:43 (CEST) Verder ontbreken expliciet:

welgefundeerde verzameling

welgefundeerde ordening

Madyno (overleg) 4 jul 2015 23:49 (CEST)

Sterke inductie: voorwaarde 1. overtollig (wordt geïmpliceerd door 2.)

– De voorgaande bijdrage werd geplaatst door 62.207.26.70 (overleg · bijdragen)

Dat staat er al. - Patrick (overleg) 6 jan 2016 11:49 (CET)

Zie ook het kopje "Verbetering". - Patrick (overleg) 6 jan 2016 11:56 (CET)