TITLE: Inductive/Recursive definitions and Induction
QUESTION [3 upvotes]: I have known the principle of mathematical induction for a long time on set of natural numbers.
Recently, i began reading mathematical logic books and learned about inductive and recursive definition of sets.Now i'm trying to relate the two.   
1 - Can we generalize the principle of mathematical induction to prove the property of the element of some general set ( instead of the set of natural numbers ) ?     
1 . 1 -    If yes, should the general set be able to be inductive ( recursively ) defined so that the principle of mathematical induction will work in prove some property of its elements ?    
1 . 1 . 1 - I  f this is a necessary condition, there is a way to know if some set can be inductively defined or is it more of a guess ?    
My question is really defined in three-layers , the second layer only makes sense if the first layer is true, and the third layer only makes sense if the previous layers are true.   
Regardless, of what layers make sense, i'm curious about justification and some extra information ( i know nothing about structural, transfinite and noetherian induction, should i learn those to understand my question ? ) .   
P.S.: By inductive definition of a set $E$ i'm meaning this: 
We are interested in defining the smallest subset of a fixed set $E$ that includes chosen elements and that is closed under certain operations defined on $E$.That is the lowest base case or lowest subset.
The recursive or inductive cases show how we can construct the next level subset, from a current level.
In the end, the total set to be defined consists of a sequence of various subsets ( each one representing a level and being indexed by a natural number in the sequence ).

REPLY [1 votes]: The most general notions are well-founded induction and well-founded recursion (inductive definition).
Let $R$ be a relation on a class $C$. If $R$ supports induction on $C$, then we can use it to prove things, by induction, about the elements of $C$.
In a proof by induction, you will prove that for each $x\in C$, whenever $(\forall y\in C)(R(y,x)\implies\phi(y))$ holds then so does $\phi(x)$. You will conclude from this, by induction, that $\phi(x)$ holds for all $x\in C$.
What relations support induction in this fashion depends on whether you accept the axiom of regularity. If you do, then it is sufficient for each non-empty sub*set* of $C$ to have an $R$-minimal element. When avoiding regularity, the usual approach is to add the requirement that $R$ be "set-like", so that $R^{-1}\{x\}$ is a set for each $x$.
In a recursive definition, you will define a function that takes an element $x$ of $C$ and a function $g$ on $R^{-1}\{x\}$ and conclude that there is a function $F$ on $C$ such that for each $x\in C$, $F(x) = g(x,F\restriction R^{-1}\{x\})$.
It seems pretty clear that for recursive definition, there is no way to avoid requiring the relation to be set-like, but I could be mistaken.
Since there was a list floating through the comments, I'll consolidate it here:

Well-founded induction

Structural induction
$\in$-induction

Transfinite induction

Induction on $\omega$, the set of finite ordinals.




These are the sorts of induction I know about from set theory. In the context of axiomatic theories of arithmetic (e.g., Peano arithmetic of various sorts) the varieties of induction/recursion are different, but I don't know anything about that.
{"set_name": "stack_exchange", "score": 3, "question_id": 441438}