Structurele inductie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Structurele inductie of structuurinductie is een bewijsmethode waarmee bewezen kan worden dat een bepaalde eigenschap geldt voor alle elementen van een inductief gedefinieerde verzameling. Het is een vorm van wiskundige inductie. Een inductief (of recursief) gedefinieerde verzameling bestaat uit een aantal basisobjecten en wordt vervolgens afgesloten onder een aantal operaties. Voorbeelden van inductief gedefinieerde verzamelingen zijn logische formules, wiskundige termen, en veel structuren uit de theoretische informatica, zoals bomen.

Het idee achter structuurinductie is dat als

  1. alle mogelijke basisobjecten een bepaalde eigenschap hebben; en
  2. alle manieren om een nieuw object te maken uit oude objecten waarvoor die eigenschap geldt, weer een object opleveren waarvoor geldt

de eigenschap dan geldt voor alle objecten in de verzameling.

Inductie in het algemeen is een bewijsmethode die gebruikt kan worden voor welgefundeerde verzamelingen (verzamelingen met een welgefundeerde ordening). Structuurinductie onderscheidt zich van inductie op de natuurlijke getallen (volledige inductie) omdat de gebruikte ordening niet 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 algebra, logica, theoretische informatica en andere gebieden waarin formules, termen, lijsten, programma's en andere inductief gedefinieerde verzamelingen een rol spelen.

In de grondslagen van de wiskunde worden de natuurlijke getallen soms inductief als volgt gedefinieerd:

  • (nul) is een natuurlijk getal.
  • Als een natuurlijk getal is, dan is ook (lees: opvolger van , of ) een natuurlijk getal.
  • Niets anders is een natuurlijk getal.

Als we de natuurlijke getallen zo definiëren, is de volledige inductie op natuurlijke getallen een speciaal geval van structuurinductie; dat wil zeggen, dat structuurinductie een generalisatie van volledige inductie is.

Voorbeeld[bewerken]

Definitie. De verzameling positieve propositielogische formules is de kleinste verzameling zodat:

  • een atomaire propositie (voor ) een positieve formule is;
  • als en positieve formules zijn, dan ook , en ;

Stelling. Een positieve formule is vervulbaar. Sterker: wordt vervuld door de evaluatie die aan alle atomaire proposities die in voorkomen de waarheidswaarde waar toekent.

Bewijs.

Basisstap. Een atomaire formule wordt vervuld door de valuatie die aan de waarheidswaarde waar toekent.
Inductiestap.
Stel dat van de vorm is. Volgens de inductiehypothese kunnen we aannemen, das en vervuld worden door de valuaties die aan alle atomaire proposities in resp. waar toekenennen. Dat betekent volgens de semantiek van dat vervuld wordt door de valuatie die aan alle atomair proposities waar toekent.
Stel dat van de vorm is. Volgens de inductiehypothese kunnen we aannemen, das en vervuld worden door de valuaties die aan alle atomaire proposities in resp. waar toekenennen. Dat betekent volgens de semantiek van dat vervuld wordt door de valuatie die aan alle atomair proposities waar toekent.
Stel dat van de vorm is. Volgens de inductiehypothese kunnen we aannemen, das en vervuld worden door de valuaties die aan alle atomaire proposities in resp. waar toekenennen. Dat betekent volgens de semantiek van dat vervuld wordt door de valuatie die aan alle atomair proposities waar toekent.
Daarmee is de stelling bewezen.