Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by divisibility rather than as usual. I was happy to see that that method was an actual induction. Unfortunately, I was unable to complete the proof.

I would like to know if there are some nice examples of proofs by induction in sets with well-founded relations which are not strict total orders which could help me understand better the method and what minimal elements actually are in general binary relations. I would like to stick to the definition in the Wikipedia article, which in particular requires that standard induction in natural numbers be done with respect to the strict order $<$. With this in mind, by the terms "partial order" and "preorder", I will mean "partial order minus the identity relation" and "preorder minus the identity relation".

I would like to split my question into three parts, each about a different class of relations. Could you give me examples of (possibly accessible and instructive) inductive proofs with respect to well-founded relations which are

(a) partial orders which are not total orders,

(b) preorders which are not partial orders,

(c) binary relations which are not preorders?

share|cite|improve this question
The Fundamental Theorem of Arithmetic, though usually stated as a strong induction proof over the usual order of $\mathbb{N}$, is actually an induction over the divisibility partial order of $\mathbb{N}$. – Arturo Magidin Apr 19 '12 at 18:52
A lot of elementary proofs in logic are structural inductions on the recursively-defined set of formulae. – Chris Eagle Apr 19 '12 at 19:14
Besides the structural induction, a lot of such proofs happens when showing that some algorithm stops, this also applies to any rewriting systems. For example see 33 Examples of Termination. – dtldarek Apr 22 '12 at 20:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.