|
==Algemene principes van bewijs door inductie==
Inductie is een bewijstechniek die kan worden toegepast op een [[partiële orde|partieel geordende]] verzameling, mits aan de voorwaarde wordt voldaan dat elke oneindige keten, dat is een verzameling van elkaar in de ordening opvolgende elementen, een minimaal (kleinste) element moeten hebben. Het inductieprincipe houdt in dat de geldigheid van een uitspraak bewezen wordt voor de minimale elementen en dat voor een willekeurig element de geldigheid van de uitspraak volgt uit de geldigheid voor z'n directe voorganger, als die er is, en anders uit de geldigheid voor alle voorgangers.
==Vormen van inductie==
Inductie wordt in de praktijk op verschillende manieren gebruikt om stellingen te bewijzen.
===Welgefundeerde inductie===
De algemeenste vorm van inductie is ''welgefundeerde inductie'' (ook wel ''Noetheriaanse inductie'' genoemd''). Zij ''V'' een verzameling met daarop een [[Welgefundeerde relatie|welgefundeerde]] partiële orde "<math>\prec</math>". Dat impliceert dat elke oneindige keten een minimaal element heeft. Een oneindige keten is dus altijd van de vorm:
:<math>x_0,x_1,x_2,\ldots</math> met voor alle <math>n\geq 0: x_n\prec x_{n+1}</math>
===Volledige inductie===
{{Zie hoofdartikel|Volledige inductie}}
EenDe bekendste vorm van welgefundeerdeinductie is ''volledige inductie''. Dit is heteen bekendevorm principevan welgefundeerde inductie voor de [[Natuurlijk getal|natuurlijke getallen]] van versterkte [[volledige inductie]], door sommige auteurs ook eenvoudigweg "volledige inductie genoemd". Het principe is gelijkwaardig aan (gewone) volledigeVolledige inductie, watkomt danin ooktwee wel eenvoudig als "inductie" wordt aangeduid.vormen voor:
* ''Zwakke inductie'': Zij <math>P</math> een eigenschap. Als
:# <math>P</math> geldt voor 0; en
==Structuurinductie==
:# uit het feit dat <math>P</math> geldt voor <math>n</math> volgt dat <math>P</math> geldt voor <math>n+1</math>;
In deelgebieden van de wiskunde waarin inductief gedefinieerde structuren, zoals termen of formules, een rol spelen, wordt ook vaak ''structuurinductie'' of ''structurele inductie'' toegepast. Een inductief gedefinieerde verzameling structuren bestaat uit een verzameling basisstructuren, die vervolgens wordt afgesloten onder een aantal operatoren. Het idee achter structuurinductie is nu dat als
#een: stellingdan geldt <math>P</math> voor alle mogelijke basisstructuren ennatuurlijke getallen.
* ''Sterke inductie'': Zij <math>P</math> een eigenschap. Als
#alle manieren om een nieuwe structuur te maken uit oude structuren waar de stelling al voor geldt, weer een structuur opleveren waar de stelling voor geldt ▼:# <math>P</math> geldt voor 0; en
dat de stelling dan geldt voor alle mogelijke termen die er zijn (dus voor de hele verzameling waar je naar kijkt).
:# uit het feit dat <math>P</math> geldt voor alle getallen <math>k < n</math> volgt dat <math>P</math> geldt voor <math>n</math>;
: dan geldt <math>P</math> voor alle natuurlijke getallen.
Structuurinductie onderscheidt zich van inductie op de natuurlijke getallen omdat de gebruikte ordening niet [[totale ordening|totaal]] is. Bovendien wordt de ordening meestal impliciet gedefinieerd in de inductieve definite. De kleinste objecten zijn de basisobjecten en wanneer objecten samengesteld worden ontstaat een groter object. Structuurinductie komt vaak voor binnen de [[Abstracte algebra|algebra]], [[logica]], [[theoretische informatica]] en andere gebieden waarin formules, termen, lijsten, programma's en andere inductief gedefinieerde structuren een rol spelen.
De twee vormen van volledige inductie zijn equivalent; dat wil zeggen dat met beide vormen dezelfde stellingen bewezen kunnen worden. Sterke inductie is direct een instantie van welgefundeerde inductie.
=== Voorbeeld 5===
''Definitie.'' De verzameling positieve [[Propositielogica|propositielogische]] formules is de kleinste verzameling zodat:
* een atomaire propositie <math>p_i</math> (voor <math>i\in\mathbb{N}</math>) een positieve formule is;
* als <math>\varphi</math> en <math>\psi</math> positieve formules zijn, dan ook <math>\varphi\wedge\psi</math>, <math>\varphi\vee\psi</math> en <math>\varphi\to\psi</math>;
''Stelling.'' Een positieve formule <math>\varphi</math> is [[Vervulbaarheid|vervulbaar]]. Sterker: <math>\varphi</math> wordt vervuld door de evaluatie die aan alle atomaire proposities die in <math>\varphi</math> voorkomen de waarheidswaarde ''waar'' toekent.
===Structurele inductie===
''Bewijs.''
{{Zie hoofdartikel|Structurele inductie}}
: ''Basisstap.'' Een atomaire formule <math>p_i</math> wordt vervuld door de valuatie die aan <math>p_i</math> de waarheidswaarde ''waar'' toekent.
''Structurele inductie'' (of ''structuurinductie'') is een vorm van inductie die werkt op inductief gedefinieerde verzamelingen. Een inductief (of recursief) gedefinieerde verzameling bestaat uit een aantal basisobjecten en wordt vervolgens [[Afsluiting (wiskunde)|afgesloten]] onder een aantal operaties. Het principe van structuurinductie is: als
#alle mogelijke basisobjecten een bepaalde eigenschap <math>P</math> hebben; en
▲#alle manieren om een nieuwenieuw structuurobject te maken uit oude structurenobjecten waarwaarvoor dedie stellingeigenschap al voor<math>P</math> geldt, weer een structuurobject opleveren waar de stellingwaarvoor voor<math>P</math> geldt
dan geldt hebben alle objecten in de verzameling de eigenschap <math>P</math>.
Ook structurele inductie is een vorm van welgefundeerde inductie (ook structurele inductie kan als equivalente sterke variant worden gedefinieerd).
: ''Inductiestap.''
: Stel dat <math>\varphi</math> van de vorm <math>\varphi_1\wedge\varphi_2</math> is. Volgens de inductiehypothese kunnen we aannemen, das <math>\varphi_1</math> en <math>\varphi_2</math> vervuld worden door de valuaties die aan alle atomaire proposities in <math>\varphi_1</math> resp. <math>\varphi_2</math> ''waar'' toekenennen. Dat betekent volgens de semantiek van <math>\wedge</math> dat <math>\varphi_1\wedge\varphi_2</math> vervuld wordt door de valuatie die aan alle atomair proposities ''waar'' toekent.
: Stel dat <math>\varphi</math> van de vorm <math>\varphi_1\vee\varphi_2</math> is. Volgens de inductiehypothese kunnen we aannemen, das <math>\varphi_1</math> en <math>\varphi_2</math> vervuld worden door de valuaties die aan alle atomaire proposities in <math>\varphi_1</math> resp. <math>\varphi_2</math> ''waar'' toekenennen. Dat betekent volgens de semantiek van <math>\vee</math> dat <math>\varphi_1\vee\varphi_2</math> vervuld wordt door de valuatie die aan alle atomair proposities ''waar'' toekent.
: Stel dat <math>\varphi</math> van de vorm <math>\varphi_1\to\varphi_2</math> is. Volgens de inductiehypothese kunnen we aannemen, das <math>\varphi_1</math> en <math>\varphi_2</math> vervuld worden door de valuaties die aan alle atomaire proposities in <math>\varphi_1</math> resp. <math>\varphi_2</math> ''waar'' toekenennen. Dat betekent volgens de semantiek van <math>\to</math> dat <math>\varphi_1\to\varphi_2</math> vervuld wordt door de valuatie die aan alle atomair proposities ''waar'' toekent.
: Daarmee is de stelling bewezen.
===Transfiniete inductie===
Een [[ordinaalgetal]] is een getal dat een in een (mogelijkerwijs oneindige) rij aangeeft. Ordinaalgetallen zijn een generalisatie van de natuurlijke getallen. Transfiniete inductie is een vorm van inductie die gebruikt wordt om te bewijzen dat een eigenschap geldt voor alle ordinaalgetallen, of algemener, voor alle elementen van een [[Welgeordendheid|welgeordende verzameling]].
Voor ordinaalgetallen bestaat een bewijs met transfiniete inductie meestal uit drie delen:
In de grondslagen van de wiskunde worden de natuurlijke getallen soms inductief als volgt gedefefinieerd:
# een bewijs dat de eigenschap geldt voor 0;
* 0 (nul) is een natuurlijk getal.
# een bewijs dat, voor een willekeurig, ordinaalgetal <math>\alpha</math> dat geen limiet-ordinaal is, geldt dat uit het feit dat <math>\alpha</math> de eigenschap heeft volgt dat <math>\alpha+1</math> de eigenschap heeft; en
* Als ''x'' een natuurlijk getal is, dan is ook ''Sx'' (lees: opvolger van ''x'', of ''x''+1) een natuurlijk getal.
# een bewijs dat, voor een willekeurig limiet-ordinaal <math>\lambda</math> geldt, dat uit het feit dat de eigenschap geldt voor alle ordinalen <math>\alpha < \lambda</math> volgt, dat de eigenschap geldt voor <math>\lambda</math>.
* Niets anders is een natuurlijk getal.
Als we de natuurlijke getallen zo definiëren, is de "gewone" inductie op natuurlijke getallen een speciaal geval van structuurinductie.
==Zie ook==
| 