An intuitionistic proof of Kruskal's theorem
type: Item
instance of: scholarly article
title: An intuitionistic proof of Kruskal's theorem
zbMATH Open document ID: 1063.03046
author: Wim Veldman
published in: Archive for Mathematical Logic
publication date: 2004-09-22T00:00:00Z
full work available at URL: http://hdl.handle.net/2066/18887
review text: Vazsonyi's conjecture says that the collection of all finite trees is well-quasi-ordered by the relation of embeddability, that is, for every infinite sequence \(\alpha(0),\alpha(1),\alpha(2),\dots\) of finite trees there exist \(i, j\) such that \(i < j\) and \(\alpha(i)\) embeds into \(\alpha(j)\). In 1960, Kruskal established an even stronger result that he called the Tree Theorem. The paper under review presents a detailed proof of an intuitionistic version of Kruskal's Theorem; moreover, it discusses a number of intuitionistic variants of many other classical Ramseyan theorems. With few exceptions, the proofs of the results do not exceed the bounds of the system of intuitionistic analysis \textbf{FIM} of Kleene and Vesley. Contents: Dickson's lemma; Almost full relations; Some induction principles and Brouwer's Thesis; Ramsey's Theorem; The Finite Sequence Theorem; Vazsonyi's conjecture for binary trees; Higman's Theorem; Vazsonyi's conjecture and the Tree Theorem; Minimal-bad-sequence arguments; The principle of open induction; Concluding remarks.
Mathematics Subject Classification ID: 03F55
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 2102098
zbMATH Keywords: intuitionistic mathematics
zbMATH Keywords: Vazsonyi's conjecture
zbMATH Keywords: Kruskal's Theorem
zbMATH Keywords: Tree Theorem
zbMATH Keywords: Ramsey's Theorem
reviewed by: Victor N. Krivtsov
MaRDI profile type: Publication
OpenAlex ID: W2039705582
DOI: 10.1007/S00153-003-0207-X
Recommended article: Proof-theoretic investigations on Kruskal's theorem
Recommended article: An intuitionistic proof of Tychonoff's theorem
Recommended article: A constructive proof of Kirszbraun's theorem
Recommended article: A Constructive Proof of the Topological Kruskal Theorem
Recommended article: Q5203029
Recommended article: An Elementary Proof of Krull's Intersection Theorem
Recommended article: A generalization of a theorem of Kruskal
Recommended article: Q3824427
Recommended article: An Intuitionistic Version of Cantor's Theorem
Recommended article: A short proof of Krull's intersection theorem
description: scientific article; zbMATH DE number 2102098