Can One Discuss Induction without Sets? The standard presentation of mathematical induction involves subsets having a certain property. Here is a typical formulation from Gallian's Contemporary Abstract Algebra, Ninth edition:

It seems to me, then, that set theory is more fundamental than induction in this formulation. One works with sets as axiomatized by ZFC or NBG or something else, and in particular with the set of integers and its subsets.
On the other hand, construction of the natural numbers seems not to require sets at all. For example, many sources including Wikipedia specify the Peano axioms without referencing sets.
It therefore seems feasible to specify the procedure of mathematical induction in a way which does not reference sets at all.
Can you provide a source which does this precisely?
 A: Not really an answer but a bit too long for a comment: Wikipedia is stating the first-order Peano axioms, which crucially contain the first-order axiom schema of induction. This talks indirectly about subsets of $\mathbb{N}$ by talking about predicates $P(n)$, which is a way to refer to the subset $\{ n \in \mathbb{N} : P(n) \text{ true} \}$. Crucially, since first-order induction can only talk about countably many subsets this way, this is actually a strictly weaker notion of induction than full induction using arbitrary subsets, which must be stated in second-order arithmetic.
So there's an argument to be made that first-order induction does not capture the full strength of induction. As evidence for this, the first-order Peano axioms have nonstandard models which contain e.g. positive integers $n$ satisfying $n > 1, n > 2, n > 3, \dots$, while the second-order Peano axioms have the standard natural numbers $\mathbb{N}$ as their only model. Nonstandard models have inductive subsets which are not the entire model, but none of them can be described using a predicate.
On the other hand, first-order induction is perfectly sufficient to carry out ordinary inductive proofs of any statement $\forall n P(n)$ that Peano arithmetic can express, and also to carry out recursive constructions of functions.
