TY - THES UR - http://lib.ugent.be/catalog/pug01:1230584 ID - pug01:1230584 LA - eng TI - Unprovability and phase transitions in Ramsey theory PY - 2011 PB - Ghent AU - De Smet, Michiel WE01 802000260825 002003157306 AU - Weiermann, Andreas promotor WE01 802000038735 0000-0002-5561-5323 AU - Bovykin, Andrey copromotor AB - The first mathematically interesting, first-order arithmetical example of incompleteness was given in the late seventies and is know as the Paris-Harrington principle. It is a strengthened form of the finite Ramsey theorem which can not be proved, nor refuted in Peano Arithmetic. In this dissertation we investigate several other unprovable statements of Ramseyan nature and determine the threshold functions for the related phase transitions.Chapter 1 sketches out the historical development of unprovability and phase transitions, and offers a little information on Ramsey theory. In addition, it introduces the necessary mathematical background by giving definitions and some useful lemmas.Chapter 2 deals with the pigeonhole principle, presumably the most well-known, finite instance of the Ramsey theorem. Although straightforward in itself, the principle gives rise to unprovable statements. We investigate the related phase transitions and determine the threshold functions.Chapter 3 explores a phase transition related to the so-called infinite subsequence principle, which is another instance of Ramsey’s theorem.Chapter 4 considers the Ramsey theorem without restrictions on the dimensions and colours. First, generalisations of results on partitioning α-large sets are proved, as they are needed later. Second, we show that an iteration of a finite version of the Ramsey theorem leads to unprovability.Chapter 5 investigates the template “thin implies Ramsey”, of which one of the theorems of Nash-Williams is an example. After proving a more universal instance, we study the strength of the original Nash-Williams theorem. We conclude this chapter by presenting an unprovable statement related to Schreier families.Chapter 6 is intended as a vast introduction to the Atlas of prefixed polynomial equations. We begin with the necessary definitions, present some specific members of the Atlas, discuss several issues and give technical details. ER -Download RIS file
00000nam^a2200301^i^4500 | |||
001 | 1230584 | ||
005 | 20170116103804.0 | ||
008 | 110523s2011------------------------eng-- | ||
024 | a 1854/LU-1230584 2 handle | ||
040 | a UGent | ||
245 | a Unprovability and phase transitions in Ramsey theory | ||
260 | a Ghent, Belgium b Ghent University. Faculty of Sciences c 2011 | ||
518 | a Public defense: 2011-05-20 17:00 | ||
520 | a The first mathematically interesting, first-order arithmetical example of incompleteness was given in the late seventies and is know as the Paris-Harrington principle. It is a strengthened form of the finite Ramsey theorem which can not be proved, nor refuted in Peano Arithmetic. In this dissertation we investigate several other unprovable statements of Ramseyan nature and determine the threshold functions for the related phase transitions.Chapter 1 sketches out the historical development of unprovability and phase transitions, and offers a little information on Ramsey theory. In addition, it introduces the necessary mathematical background by giving definitions and some useful lemmas.Chapter 2 deals with the pigeonhole principle, presumably the most well-known, finite instance of the Ramsey theorem. Although straightforward in itself, the principle gives rise to unprovable statements. We investigate the related phase transitions and determine the threshold functions.Chapter 3 explores a phase transition related to the so-called infinite subsequence principle, which is another instance of Ramsey’s theorem.Chapter 4 considers the Ramsey theorem without restrictions on the dimensions and colours. First, generalisations of results on partitioning α-large sets are proved, as they are needed later. Second, we show that an iteration of a finite version of the Ramsey theorem leads to unprovability.Chapter 5 investigates the template “thin implies Ramsey”, of which one of the theorems of Nash-Williams is an example. After proving a more universal instance, we study the strength of the original Nash-Williams theorem. We conclude this chapter by presenting an unprovable statement related to Schreier families.Chapter 6 is intended as a vast introduction to the Atlas of prefixed polynomial equations. We begin with the necessary definitions, present some specific members of the Atlas, discuss several issues and give technical details. | ||
598 | a D1 | ||
100 | a De Smet, Michiel u WE01 0 802000260825 0 002003157306 0 056005425217 | ||
700 | a Weiermann, Andreas e promotor u WE01 0 802000038735 0 0000-0002-5561-5323 | ||
852 | x WE b WE01 | ||
700 | a Bovykin, Andrey e copromotor | ||
650 | a Mathematics and Statistics | ||
653 | a unprovability | ||
653 | a phase transitions | ||
653 | a Ramsey theory | ||
856 | 3 Full Text u https://biblio.ugent.be/publication/1230584/file/4335572 z [open] y PhDthesis-MichielDeSmet.pdf | ||
920 | a phd | ||
852 | x WE b WE01 | ||
922 | a UGENT-WE |
All data below are available with an Open Data Commons Open Database License. You are free to copy, distribute and use the database; to produce works from the database; to modify, transform and build upon the database. As long as you attribute the data sets to the source, publish your adapted database with ODbL license, and keep the dataset open (don't use technical measures such as DRM to restrict access to the database).
The datasets are also available as weekly exports.