# Pigeons do not jump high

Abstract : The infinite pigeonhole principle for 2-partitions asserts the existence, for every set $A$, of an infinite subset of $A$ or of its complement. In this paper, we develop a new notion of forcing enabling a fine analysis of the computability-theoretic features of the pigeonhole principle. We deduce various consequences, such as the existence, for every set $A$, of an infinite subset of it or its complement of non-high degree. We also prove that every $\Delta^0_3$ set has an infinite low${}_3$ solution and give a simpler proof of Liu's theorem that every set has an infinite subset in it or its complement of non-PA degree.
Type de document :
Pré-publication, Document de travail
20 pages. 2018
Domaine :

Littérature citée [20 références]

https://hal.archives-ouvertes.fr/hal-01888793
Contributeur : Ludovic Patey <>
Soumis le : vendredi 5 octobre 2018 - 12:49:46
Dernière modification le : mardi 9 octobre 2018 - 01:13:43

### Fichier

pigeons-jump.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01888793, version 1
• ARXIV : 1803.09771

### Citation

Benoit Monin, Ludovic Patey. Pigeons do not jump high. 20 pages. 2018. 〈hal-01888793〉

### Métriques

Consultations de la notice

## 12

Téléchargements de fichiers