הגדרה רקורסיבית – הבדלי גרסאות

 

ב[[מתמטיקה]] הגדרה רקורסיבית של מושג מתקבלת כהגדרה תקפה, אם אפשר להוכיח שהיא מספקת תשובה חד-משמעית בכל מקרה; ההוכחה היא בדרך כלל ב[[אינדוקציה מתמטית|אינדוקציה]] או ב[[אינדוקציה טרנספיניטית]]. הגדרה כזו נקראת ''הגדרה אינדוקטיבית''. דוגמאות:

# ב[[מערכת פאנו]] בונים את פעולת ה[[חיבור]] של [[מספר טבעי|מספרים טבעיים]] מתוך פעולת העוקב <math>\ S(x)</math> (העוקב של 5 הוא S(5)=6, וכדומה). את פעולת החיבור מגדירים באופן אינדוקטיבי: אם b=1 אז לפי ההגדרה <math>\ a+b=S(a)</math>; אחרת, b הוא העוקב של איבר מתאים c, ואז מגדירים a+b=S(a)+c. החלפנו כאן את המושג "b+?" במושג 'פשוט' יותר, "c+?".

# ב[[לוגיקה מתמטית]], [[פסוק (לוגיקה מתמטית)|פסוק]] תקני הוא אטום, או פסוק שנבנה באופן חוקי מפסוקים תקניים. זו הגדרה רקורסיבית, שבעזרת אינדוציה על אורך הפסוק אפשר לראות אותה כהגדרה אינדוקטיבית.