Say I need to prove some proposition $P$ about sets of integers, and I have the necessary proofs for applying induction on the number of elements of set $S$:
- $P(S)$ is true for all sets $S$ having one element.
- Given that $P(S)$ is true for all sets of integers $S$ having $n$ elements I can prove $P(S')$ is true for all sets of integers $S'$ having $n+1$ elements.
A simple example would be to prove a theorem about the greatest common denominators $(s_1, s_2, \cdots s_n$): For positive integer $m$, $$ (m s_1, m s_2, \cdots m s_n) = m (s_1, s_2, \cdots s_n) $$ with the induction step using the theorem $(ma,mb)=m(a,b)$.
Having used induction to prove proposition $P$ in this way, it strikes me that I have proven $P$ for all sets containing any (arbitrarily large) finite number of elements, but I don't know if that proves $P(S)$ for all sets of integers.
Does induction, established on the number of elements in a set, extend the proof to infinite sets?
In the simple example, could I use the outlined proof to say that for all sets of integers $S$ and positive integer $m$ $$ \left( mS \right) = m \left( S \right) $$ where parentheses around a set mean the gcd of all members of that set, and the set $ms$ is defined as the set of all integers of the form $ms_i$ where $s_i\in S$? I'm pretty sure in this simple case the "infinite set" version of the theorem is true, but did the proof by induction establish this?
This question Munkres's Strong induction principle vs. "traditional" mathematical induction is not quite on point for the issue I pose: It lets you prove that all the elements of a particular infinite set (namely $\mathbb Z^+$) satisfy some property of each individual element, but it doesn't say anything about infinite sets satisfying some property involving combinations of elements.
This issue goes to the logical foundation of induction, so for all I know the answer might depend on the proof-logic axioms you are using, but I suspect there is some solid answer based on usual logic and set theory axioms.
Consider the proposition $P(S)$ which asserts "$S$ is a finite set."