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?

  • 5
    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}$.2012-04-19
  • 4
    A lot of elementary proofs in logic are [structural inductions](http://en.wikipedia.org/wiki/Structural_induction) on the recursively-defined set of formulae.2012-04-19
  • 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