Paper Description: MIP-9606

BibTeX entry:

@incollection{MIP-9606,
author="A. Geser",
title="A proof of Higman's Lemma by open induction",
institution="Fakult{\"a}t f{\"u}r Mathematik und Informatik, Universit{\"a}t Passau",
year=1996,
number={MIP-9606}
}

Abstract:

We use Raoult's principle of open induction to give a constructive proof of Higman's Lemma. In contrast to previous proofs, our proof directly uses the property that every infinite sequence has an infinite ordered subsequence. This straightens the inductive argument at the cost of a more complex order.
List of Keywords: Wellfounded order. Open induction. Complete partial order, Higman's Lemma, Kruskal's Tree Theorem.

Paper itself:

Cross links:

Ulrike Peiker, Martin Griebl