A simple proof and some difficult examples for Hindman's theorem (Q424579): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2962863029 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0906.3885 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A short proof of Hindman's theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3797180 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ultrafilters: Some old and some new results / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite sums from sequences within cells of a partition of N / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3370068 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algebra in the Stone-Čech compactification: theory and applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3395521 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hindman's theorem: an ultrafilter argument in second order arithmetic / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 07:42, 5 July 2024
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