¿Cuánta inducción se necesita para demostrar el teorema de Ramsey finito en PA?
Busqué durante un tiempo pero fue en vano.
Respuesta
¿Demasiados anuncios?
$I\Sigma_1$ - los axiomas del sembrado ordenado más la inducción para $\Sigma_1$ fórmulas - es ciertamente suficiente. La prueba estándar pasa sin cambios en $I\Sigma_1$ Los puntos clave son:
-
La reducción al caso de dos colores es trivial.
-
La fórmula a la que aplicamos la inducción en el caso bicolor es "Hay algún $n$ de manera que cualquier $2$ -coloración del $s$ -subconjuntos de elementos de $\{0,...,n\}$ tiene un conjunto homogéneo de tamaño $r$ ." Esto pasa en $I\Sigma_1$ (nótese que aquí sólo hay un cuantificador verdaderamente ilimitado, ya que el número de $s$ -y subconjuntos de elementos $2$ -colores de $s$ -subconjuntos de elementos de $\{0,...,n\}$ está limitada por una función cuya totalidad es demostrable en $I\Sigma_1$ ).
Pero podemos hacerlo mejor: demostrando un resultado más fuerte (el límite superior exponencial) nos libramos de ese cuantificador no limitado. Así que $I\Delta_0+exp$ ya es suficiente.
Creo que esto se trata con más detalle en Hajek/Pudlak, Metamatemática de la aritmética de primer orden (y aunque no lo sea recomiendo encarecidamente ese libro, es maravilloso).
