43. ! Definicja indukcyjna (rekurencyjna)

Indukcyjna (stosuje zasadę dowodu indukcyjnego, wskazuje pierwszy element i precyzuje zasadę postępowania np. ciąg liczb dodatnich – 1, 1+1, ...)

Jest to definicja odwołująca się do samej siebie, do elementu o mniejszej komplikacji.

Zwykle wynikiem rekurencji jest ciąg <a0, a1, a2, a3, ... > dla którego definicja elementua

n wykorzystuje elementy poprzedzające.

Element początkowy (lub kilka początkowych) muszą być dane bezpośrednio.

log. definicja zbioru, w którym dają się wyróżnić elementy wyjściowe oraz elementy otrzymane z wyjściowych;

definicja indukcyjna. składa się z 2 części: warunku wyjściowego (określającego obiekty, które na pewno należą do definiowanego zbioru) i warunku indukcyjnego (określającego stosunek, w jakim muszą pozostawać nowe obiekty do tych już należących do zbioru, aby też mogły być do tego zbioru zaliczone).

Definicje indukcyjne służą do definiowania zbiorów obiektów, posiadających pewną własność (np. zbioru liczb naturalnych). W definicji takiej najpierw wskazuje się najprostszy (najmniejszy, itp.) obiekt, który definiowaną własność posiada (np. 0 jest liczbą naturalną), a

następnie pokazuje się, w jaki sposób owa własność przenosi się na obiekty bardziej złożone, czyli jak konstruować – albo obliczać – pozostałe elementy zbioru (np., jeśli S jest symbolem funkcji następnika: jeśli n jest liczbą naturalną, to S(n) również jest liczbą naturalną).