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?

  • $\begingroup$ Yes, you can do this. And it's often useful. I think it's just more convenient to leave the PMI to only be about integers, since it is most natural there. If you're using induction on a different countable set $S$, you'll need some indexing $f$ like you are using anyway, so you might as well just use induction on $\mathbb{N}$. This to me is rather more natural than having to cite a particular corollary of PMI. $\endgroup$ – Jair Taylor May 15 '17 at 23:24
  • 1
    $\begingroup$ For an arbitrary bijection $f: \mathbb N \to S$ there won't be any nice relation between the statements $p(f(n))$ and $p(f(n+1))$, so the assumption of $p(f(n))$ will be unlikely to help you prove $p(f(n+1))$. Induction won't be useful unless you're using an order relation that has some connection to the structure of the problem at hand. $\endgroup$ – Robert Israel May 15 '17 at 23:32
  • $\begingroup$ Has to be a well-ordered set. (Similarly, transfinite induction doesn't require a set to be countable, but does require that the set be well-ordered.) $\endgroup$ – avs May 15 '17 at 23:34
  • $\begingroup$ Robert, I understand that generally having $p(f(n))$ as an assumption wont help to prove $p(f(n+1))$. However, if you could find a way to prove the implication, would my scheme work? In the way Jair Taylor said above $\endgroup$ – Tyler Alkatraz Randall May 15 '17 at 23:36
  • $\begingroup$ I finally found a relevant post on here. Very interesting, for anyone who wants to check out the answers math.stackexchange.com/questions/1261692/… $\endgroup$ – Tyler Alkatraz Randall May 15 '17 at 23:42

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}$:


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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.