A simple proof and some difficult examples for Hindman's theorem (Q424579): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
The author gives a new, simplified proof of Hindman's theorem that formalizes in the system \(\mathsf{ACA}^+\). This is slightly weaker than the best known upper bound \(\mathsf{ACA}^+_0\) (note the subscript 0 which indicates that induction is restricted to \(\Sigma^0_1\) formulas) on the strength of Hindman's theorem, see [\textit{A. R. Blass}, \textit{J. L. Hirst} and \textit{S. G. Simpson}, ``Logical analysis of some theorems of combinatorics and topological dynamics'', Contemp. Math. 65, 125--156 (1987; Zbl 0652.03040)]. Moreover, the author introduces a technique to construct instances of Hindman's theorem which have computationally difficult solutions. He uses this technique to show that parts of his new proof are optimal. Also, he constructs an instance which has no \(\Sigma_2\) solutions. This improves the best known lower bound which was \(\Delta_2\). This research is connected to the long-standing open problem to determine the precise strength, in the sense of reverse mathematics, of Hindman's theorem. | |||
Property / review text: The author gives a new, simplified proof of Hindman's theorem that formalizes in the system \(\mathsf{ACA}^+\). This is slightly weaker than the best known upper bound \(\mathsf{ACA}^+_0\) (note the subscript 0 which indicates that induction is restricted to \(\Sigma^0_1\) formulas) on the strength of Hindman's theorem, see [\textit{A. R. Blass}, \textit{J. L. Hirst} and \textit{S. G. Simpson}, ``Logical analysis of some theorems of combinatorics and topological dynamics'', Contemp. Math. 65, 125--156 (1987; Zbl 0652.03040)]. Moreover, the author introduces a technique to construct instances of Hindman's theorem which have computationally difficult solutions. He uses this technique to show that parts of his new proof are optimal. Also, he constructs an instance which has no \(\Sigma_2\) solutions. This improves the best known lower bound which was \(\Delta_2\). This research is connected to the long-standing open problem to determine the precise strength, in the sense of reverse mathematics, of Hindman's theorem. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Alexander P. Kreuzer / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03B30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03F35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05D10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6040394 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Hindman's theorem | |||
Property / zbMATH Keywords: Hindman's theorem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
reverse mathematics | |||
Property / zbMATH Keywords: reverse mathematics / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Ramsey theory | |||
Property / zbMATH Keywords: Ramsey theory / rank | |||
Normal rank |
Revision as of 22:28, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A simple proof and some difficult examples for Hindman's theorem |
scientific article |
Statements
A simple proof and some difficult examples for Hindman's theorem (English)
0 references
1 June 2012
0 references
The author gives a new, simplified proof of Hindman's theorem that formalizes in the system \(\mathsf{ACA}^+\). This is slightly weaker than the best known upper bound \(\mathsf{ACA}^+_0\) (note the subscript 0 which indicates that induction is restricted to \(\Sigma^0_1\) formulas) on the strength of Hindman's theorem, see [\textit{A. R. Blass}, \textit{J. L. Hirst} and \textit{S. G. Simpson}, ``Logical analysis of some theorems of combinatorics and topological dynamics'', Contemp. Math. 65, 125--156 (1987; Zbl 0652.03040)]. Moreover, the author introduces a technique to construct instances of Hindman's theorem which have computationally difficult solutions. He uses this technique to show that parts of his new proof are optimal. Also, he constructs an instance which has no \(\Sigma_2\) solutions. This improves the best known lower bound which was \(\Delta_2\). This research is connected to the long-standing open problem to determine the precise strength, in the sense of reverse mathematics, of Hindman's theorem.
0 references
Hindman's theorem
0 references
reverse mathematics
0 references
Ramsey theory
0 references