title: Structurele inductie
text: 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
  alle mogelijke basisobjecten een bepaalde eigenschap  hebben; en
  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 
  Definitie. De verzameling van positieve 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 dat  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 atomaire proposities waar toekent.
   Stel dat  van de vorm  is. Volgens de inductiehypothese kunnen we aannemen dat  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 atomaire proposities waar toekent.
   Stel dat  van de vorm  is. Volgens de inductiehypothese kunnen we aannemen dat  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 atomaire proposities waar toekent.
   Daarmee is de stelling bewezen.
  
  Logica
  Wiskundige terminologie