Seetapun

@Roger: d'après les liens, il s'agit d'une conjecture très technique qui est à cheval entre la calculabilité et la logique. Elle s'intéresse à la possibilité de démontrer le lemme de Koenig (si j'ai bien compris) à partir d'un fragment partiel du théorème de Ramsey, précisément celui qui concerne n=2.

Pour te situer le thème, je résume en gros de quoi il s'agit:

Soit $n\in \N$. Soit $m$ un autre entier. Notons $[X]^n$ l'ensemble des parties de $X$ de cardinal exactement $n$. L'énoncé $Ramsey(n,m,k)$ est pour toute partition $P$ de $[\N]^n$ telle que $card(P)=m$, il existe une partie $X$ de $\N$ vérifiant $card(X)\geq k$, et un $Y\in P$ tel que $[X]^n\subseteq Y$. Si on remplace $k$ par $\infty$, $card(X)=\infty$ voudra juste dire $X$ est infini (ici tout est dénombrable, vu le thème "effectif" dans lequel les gens qui en parlent semblent se placer)

Le "bien connu" théorème de Ramsey dit $\forall (n,m)\in (\N^*)^2: ramsey(n,m,\infty)$.

C'est un théorème qui est très fort. En particulier, ce n'est pas parce que tu choisis une partition P récursive, ni même à priori qui se calcule en temps polynomial que tu vas trouver un ensemble récursif $X$ infini tel que $X$ est inclus dans un des morceaux de $P$, même si $m=2$.

Il est très facile de trouver des partitions très simples*** tel qu'aucun $X$ infini et calculable n'existe (je te mets un exemple plus bas***).

Les auteurs semblent s'intéresser au cas n=2 et m=2, plus ou moins (si j'ai capté, j'ai juste survolé quelques sec) redémontrer (ou démontrer) qu'on peut descendre jusqu'à n=2 dans les contre-exemples de type ***, puis se demander si des axiomes du genre ramsey(2,2,\infty) entraine des lemmes comme le lemme de Koenig. Bien entendu, pour que ça ait un sens, il faut se placer dans des théories très faibles et je pense que dans les liens ils précisent les théories dans lesquelles ils se placent. Par contre, ils ont l'air d'utiliser moult et moult sigles qui appartiennent à la spécialité "recursion theory et calculabilité" sans les redéfinir, ça fait de cette question une question très spécialisée dont les lecteurs sont un peu exclus.

*** Pour savoir si un énoncé de la forme $\forall x_1\exists x_2\forall x_3...\forall x_n: R(x_1,..,x_n)$ est vrai ou faux (donc t'imagines la puissance, c'est tout l'ensemble vérité de $(\N,+,\times)$ qui est réductible à des Ramsey questions), il suffit de savoir si oui ou non il existe une partie infinie $A$ de $\N$ vérifiant:

pour tous uplet $(a_1,..,a_n)$ strictement croissant d'éléments de $A$, $\forall x_1\leq a_1\exists x_2\leq a_2\forall x_3\leq a_3...\forall x_n\leq a_n: R(x_1,..,x_n)$

Or vérifier, pour un tel uplet si oui ou non $\forall x_1\leq a_1\exists x_2\leq a_2\forall x_3\leq a_3...\forall x_n\leq a_n: R(x_1,..,x_n)$ se calcule aisément par ordinateur (c'est PSPACE) en l'entrée.

S'il n'existe pas de tel ensemble $A$ infini alors il en existe un infini qui vérifie
pour tous uplet $(a_1,..,a_n)$ strictement croissant d'éléments de $A$, $non(\forall x_1\leq a_1\exists x_2\leq a_2\forall x_3\leq a_3...\forall x_n\leq a_n: R(x_1,..,x_n))$.

Donc la dichotomie est parfaite, et connaitre la vérité arithmétique se ramène à connaitre pour quelles parties récursives (et même comme vu ci-dessus PSPACE) $T\subseteq [\N]^n$ il existe une partie infinie $A$ de $\N$ telle que $[A]^n\subseteq T$.

La conjecture signalée semble être une conjecture qui se ramène (d'après les auteurs) à "existe-t-il telle ou telle partions de telle nature telle que on ne peut trouver de solution récursvie en ceci ou cela?" de sorte qu'on sort d'une question du genre "est-il démontrable dans.. que.." pour avoir une question du genre "ceci est-il Turing-réductible à cela"**.

** un élément $a\in \N^\N$ est Turing réductible à $b\in \N^\N$ quand il existe un programme utilisant $b$ comme oracle qui calcule $a$.