Can you use the principle of mathematical induction (PMI) on any countably infinite set? I was pondering the PMI and there's something bothering me about proofs that I've seen that the well-ordering principle (WOP) and the PMI imply each other. It seems to me that you could use the PMI on a set $S \subseteq \Bbb{Z}$ that has a maximum element $a$. Let $p:S\to\{T,F\}$ be a propositional function on S. The base case can be to prove $p(a)$, and the inductive step can be to prove $p(k) \to p(k-1)$. My intuition is that by the PMI, $p(k)=T \; \forall k\in S$. 
My pondering didn't stop there. I started wondering, well why does there even have to be a maximum element? Why does the set need to even contain numbers? What if there were some way to bijectively map every element in $S$ to $\Bbb N$ (in other words, what if $S$ were countably infinite) and we did the following proof:
Let $S$ be a countably infinite set. Let $p:S \to \{T,F\}$ be a propositional function on S. Let $f:\Bbb N \to S$ be a bijection. The goal is to prove $p(a) = T \; \forall a \in S$. 
Base case:
prove $p(f(1)) = T$.
Inductive step:
prove $p(f(n)) \to p(f(n+1))$.
Therefore $p(a) = T \; \forall a \in S$ as desired.
This seems to me that you could use induction to prove things over $\Bbb Q$, $\Bbb Z$, or generally any countable set. If this is true, why is the PMI so commonly taught in number theory courses as limited to be useful only in the case where the WOP is true?
 A: Yes, what you do is perfectly ok, and you made a good insight about induction, well done!
Please note though that the WOP may not hold relative to the $<$ relation as normally defined for $\mathbb{Z}$ and $\mathbb{Q}$, but if you have a countable set $S$ then that means that the WOP does hold ... relative to the relation $xRy$ iff $f^{-1}(x) < f^{-1}(y)$ where $f$ is a bijection $f:\mathbb{N} \rightarrow S$. But the reason we typically don't use this, is because it is typically unusable, impractical, or unnecessary.
For example, we can take a listing (ordering) of $\mathbb{Z}$:
0,-1,1,-2,2,-3,3,...
But will the property $P$ in question be such that it can be (easily) shown that every entry in this list has property $P$ on the basis of its earlier entries having $P$, without there being a just-as-easy proof that shows that all entries have property $P$ without using induction? There can certainly be cases like that, but they are far less likely to 'naturally' occur than they do for a structure like $\mathbb{N}$.
A: What if you had an uncountable set that was not well ordered, and you could place the elements in concentric rings. Could you do an induction proof on the indexes of the rings and show that if something were true for elements in ring with index $n$, and was also true for elements in a ring of index $n+m$ for any $m>1$, then that condition would be true for elements in every ring indexed at $n+m+k$?  Just a thought.
