Indukcja strukturalna

Z Wikipedii, wolnej encyklopedii

Indukcja strukturalna – dość powszechnie stosowany wariant indukcji matematycznej, w którym rozważa się pewien zbiór termów uporządkowany następującą relacją: jeden term jest mniejszy od drugiego wtedy i tylko wtedy, gdy jest jego podtermem.

Zasada indukcji strukturalnej głosi, co następuje. Jeśli udowodnimy, że pewną własność mają wszystkie termy atomowe (czyli takie, które nie zawierają żadnych właściwych podtermów) oraz że dla każdego n-arnego symbolu funkcyjnego z tego, że własność tę mają termy wynika, że ma ją również term to mają ją wszystkie termy.