An analysis of Ramsey's theorem
type: Item
instance of: scholarly article
title: An analysis of Ramsey's theorem
zbMATH Open document ID: 0824.03034
author: Thierry Coquand
published in: Information and Computation
publication date: 1995-11-09T00:00:00Z
review text: The main result of this paper may be paraphrased as follows. A collection \(B\) of finite sets of natural numbers is called unavoidable iff every infinite set of natural numbers has a subset in \(B\). Let \(s\) be a fixed natural number, the number of colours. Given a collection \(B\) of finite sets of natural numbers we denote by \(B_ n\) the collection of those sets of natural numbers that, whenever their \(n\)-element-subsets are coloured by \(s\) colours, will always have a homogeneous subset in \(B\), where a homogeneous set is one such that every one of its \(n\)-element- subsets gets one and the same colour. The main theorem of the paper says that, if \(B\) is unavoidable, each \(B_ n\) is unavoidable. Given any number \(k\), we may choose \(B\) to be the collection of those finite sets of natural numbers that have their first element greater than \(k\), and whose number of elements exceeds its first element. We then obtain the famous generalization by \textit{J. Paris} and \textit{L. Harrington} of Ramsey's Theorem [see: ``A mathematical incompleteness in Peano arithmetic'', in: Handbook of mathematical logic (J. Barwise, ed.), 1133- 1142 (1977; Zbl 0443.03001)]. The author gives a beautiful constructive proof of his main theorem (the classical argument by compactness is of course unconstructive), thus answering a question raised by G. Stolzenberg. A main step in the author's argument is his replacement of the notion of ``unavoidable'' by the notion of ``ample''. The latter notion is defined inductively and coincides with the former one in classical mathematics, and also, by Brouwer's bar theorem, in intuitionistic mathematics, but not in the more general context of constructive mathematics. The author's Lemma 7 is a very nice constructive substitute for König's Infinity Lemma, very different from the intuitionistic fan theorem. The author later saw that his result is related to an intuitionistic version of the infinite Ramsey Theorem given by the reviewer a…
Mathematics Subject Classification ID: 03F65
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03F55
zbMATH DE Number: 590743
zbMATH Keywords: homogeneous set
zbMATH Keywords: Ramsey's Theorem
zbMATH Keywords: constructive proof
reviewed by: Wim Veldman
MaRDI profile type: Publication
full work available at URL: inco.1994.1034
OpenAlex ID: W1976279751
DOI: 10.1006/INCO.1994.1034
Recommended article: Ramsey's Theorem and the Pigeonhole Principle in Intuitionistic Mathematics
Recommended article: Another proof of the intuitionistic Ramsey theorem
Recommended article: Finiteness classes arising from Ramsey-theoretic statements in set theory without choice
Recommended article: Nonstandard combinatorics
Recommended article: An Introduction to Ramsey Theory
Recommended article: On a problem of formal logic.
Recommended article: Q3717797
Recommended article: A dual form of Ramsey's theorem
Recommended article: Q3204500
description: scientific article; zbMATH DE number 590743