6
$\begingroup$

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?

  • 2
    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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7988).2012-04-22

0 Answers 0