On what sets other than $\mathbb{N}$ might we use proof by induction?

Question

Suppose we have a set $S$ with $s_1\in S$ and $f: S\to S$ and $n\subset S$ such that $n=\{s_1, f(s_1), f(f(s_1)), \cdots \}$ ($n$ not necessarily infinite).

To establish properties of $n$, can we use proof by induction on $n$ itself using $f$ as the successor function?

---

EDIT: Suppose $f:S\to S$. For what it is worth, here is my own formal proof that for every $s_1\in S$ there exists a set $n\subset S$ on which induction holds, with $f$ being the successor function and $s_1$ being the "first element" in $n$. The key to the proof is the construction of the subset $n$:

$\forall a:[a\in n \iff a\in S\land \forall b\subset S:[s_1\in b\land \forall c\in b : [f(c)\in b]]\implies a\in b]$

We can show that:

(1) $s_1\in n$

(2) $\forall a\in n: f(a)\in n$

(3) $\forall P\subset n:[s_1\in P \land \forall a\in P: [f(a)\in P] \implies \forall a\in n : [a\in P]]$

These are the equivalent of 3 of the 5 Peano axioms for the natural numbers (the modern set-theoretic version). Missing are only that $f$ would be injective, and that $s_1$ would have no pre-image in $n$ under $f$.

Answer 1

To elaborate on my comment, the crux of this question is not proving that induction works but even defining the set $n$ at all (once you've defined it, induction will be trivial from the definition). Your definition $n=\{s_1, f(s_1), f(f(s_1)), \cdots \}$ is of course not rigorous unless you explain what the "$\cdots$" is supposed to mean.

There are various ways to make this definition precise, but the following is one of the easiest. Define $n$ to be the smallest subset of $S$ which contains $s_1$ and is closed under $f$. More precisely, $n$ is the intersection of all the subsets $A\subseteq S$ such that $s_1\in A$ and for all $a\in A$, $f(a)\in A$.

From this definition, induction is essentially a tautology. Induction says that given a property $P$ of elements of $n$, if $P(s_1)$ is true and $P(a)$ implies $P(f(a))$ for all $a\in n$, then $P(a)$ is true for all $a\in n$. But given such a $P$, just define $A=\{a\in n:P(a)\}$. Then $A$ contains $s_1$ and is closed under $f$, so by definition of $n$, $n\subseteq A$. Thus $P(a)$ is true for all $a\in n$.

Answer 2

I'll predict that what you'd get doing something like that would look a lot like $\mathbb{N}$. That is, you could probably find a way to associate $S$ and $\mathbb{N}$ with each other. That is, you could write $s_{1} = s \in S, s_{n + 1} = f(s_{n})$, but by doing so, there's really not much difference between "inducting" on $S$ and inducting on $\mathbb{N}$, in that $s_{1}$ is "basically" $1$, $s_{2}$ is "basically" $2$, and so on. So though you could make $S$ different from $\mathbb{N}$, there won't be much difference as far as induction goes (though $S$ may have other "features" very different from $\mathbb{N}$.

Other responses are right that you would have to provide a more formal and rigorous definition. But I think for such "casual" uses as this forum, I think the meaning is clear; but as I've said, I think what you'd end up with wouldn't amount to much much more than a basic enumeration of $S$, and not really buy you anything useful. By enumerating a set, you are able to do induction on it, but all you're really doing is inducting on $\mathbb{N}$, and passing it to your enumerated set.

EDIT: In response to a comment, the set may be finite, e.g. if $f$ is the identity. In this case, it's not the same as $\mathbb{N}$, but the "induction" will just repeat indefinitely; that is, there will be some $k$ such that $f^{k}(s) = s$ for all $s$. The induction is there, and it's different from $\mathbb{N}$ but you can still enumerate $S$, albeit redundantly (i.e. $s_{i} = s_{i + k}$).