Similitudes entre el problema de Post y el forzamiento de Cohen

Question

Observación: Posteriormente he sabido que G.H. Moore aborda esta cuestión en la tercera referencia que aparece al final de este post, a partir de la p. 157, en la que cita una carta de Kreisel a Gödel fechada el 15/4/63, seguida de la nota parentética: Así, Kreisel vio una analogía entre el forzamiento y el argumento de prioridad de Friedberg [1957]. La siguiente página sugiere que otros lógicos están de acuerdo que el forzamiento estaba implícito en los argumentos prioritarios de la teoría de la recursión (p. 158) y menciona a Kunen (que se cita en una de las respuestas aquí). En la misma página, se menciona que Kreisel afirmó tenía una forma de forzar en su interpretación del intuicionismo en el artículo de 1961 "Set-theoretic problems suggested by the notion of potential infinity". Sin embargo, Moore sostiene que Cohen fue el primero en utilizar el forzamiento y las ideas relacionadas en la Teoría de Conjuntos. No obstante, agradezco las respuestas recibidas hasta ahora, y agradecería que otros expertos en el área de la Teoría de Conjuntos y/o la Lógica Matemática me aclararan mi pregunta.

---

Antecedentes: Paul Cohen comenzó a reflexionar profundamente sobre la Hipótesis del Continuo en 1962, y publicó su prueba de su independencia (en dos partes) al año siguiente. Por supuesto, hubo momentos matemáticos anteriores que le llevaron a su "descubrimiento del forzamiento", incluida su familiaridad con el trabajo de Skolem (en particular, el Teorema de Löwenheim-Skolem ) y el deseo de pensar en términos de "procedimientos de decisión". Incluiré algunas referencias relevantes al final de esta pregunta, incluyendo un artículo retrospectivo/introspectivo del propio Cohen.

Mi pregunta se refiere a un hecho ocurrido en 1957, cuando Richard Friedberg aportó una solución al problema de Post. En primer lugar, permítanme transcribir un extracto de la charla de Cohen en el Centenario de Gödel 2006 :

En aquella época, Raymond [Smullyan] y otras personas estaban muy interesados en el problema del correo. Y ese es un problema que podría haberme interesado; tenía un sabor matemático. Pero nunca pensé en ello, y de vez en cuando tomábamos un café y oía a esta gente hablar de ello. Pero un día, alguien vino a mi oficina y dijo: "Este problema ha sido resuelto". Y yo dije: "¿En serio?" "Sí, aquí está la carta. No puedo creer que sea verdad". Y me la dio y la leí. Fui a la pizarra, tomé un poco de tiza y dije: "Bueno, parece correcto". Esta es la prueba de Friedberg - y así fue mi único contacto con la lógica en ese momento. Pero nunca perdí esta idea de pensar de alguna manera en los fundamentos de las matemáticas: tratar de encontrar algún tipo de técnica inductiva para simplificar las proposiciones; tal vez conducir a un procedimiento de decisión, cuando sea imposible.

Esta charla se resume en la introducción de una reimpresión de "Set Theory and the Continuum Hypothesis" (Cohen, 2008) en la que se encuentran las observaciones correspondientes al extracto anterior:

Un pequeño grupo de estudiantes estaba muy interesado en el problema de Emil Post sobre el grado máximo de insolubilidad. Yo me quedé con la idea de trabajar en él, pero al final no lo hice. De repente, un día llegó una carta que contenía un boceto de la solución de Richard Friedberg (Friedberg, 1957), y me la trajeron a mi despacho. En medio de un cierto escepticismo, comprobé la prueba y no encontré nada malo. Era exactamente el tipo de cosa que me hubiera gustado hacer. Resolví mentalmente que no volvería a dejar pasar una oportunidad así.

La última frase de esta última cita me parece bastante interesante, sobre todo porque se refiere a una época cinco años anterior al inicio oficial del trabajo de Cohen en ~CH. Una rápida comprobación de Wikipedia ofrece un planteamiento y una solución del problema (es decir, el método de la prioridad) que suenan notablemente similares, al menos a nivel superficial, al trabajo posterior de Cohen con el forzamiento. Desgraciadamente, el trabajo sobre los grados de Turing queda fuera de mi ámbito.

Pregunta: ¿Puede alguien especializado en Teoría de Conjuntos o Lógica Matemática comentar las similitudes entre el problema de Post/el método de la prioridad y el forzamiento de ~CH/Cohen? En particular, ¿hay razones para creer que lo que fue el "único contacto con la lógica" de Cohen en 1957 habría contribuido de manera significativa (matemática) a su trabajo media década después?

---

Referencias:

Cohen, P. (2002). El descubrimiento del forzamiento. Rocky Mountain Journal of Mathematics, 32(4).

Kanamori, A. (2008). Cohen y la teoría de conjuntos. The Bulletin of Symbolic Logic, 351-378.

Moore, G. H. (1988). Los orígenes del forzamiento, Coloquio de Lógica '86. Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 143-173.

Answer 1

En esta edición, se añade una nota histórica al final.

La siguiente cita del texto clásico de Kunen Teoría de conjuntos tal vez sea de su interés. Nótese que Kunen está señalando que ciertas construcciones clásicas de la teoría de la recursión pueden ser vistas como precursoras del forzamiento; pero no afirma que argumentos prioritarios caen dentro de esta categoría (por otro lado, ha habido intentos de formular argumentos de prioridad como argumentos de forzamiento, por ejemplo, por parte de Nerode y Remmel a mediados de la década de 1980).

"Hay dos importantes precursores de la moderna teoría del forzamiento uno en la teoría de la recursión y otro en la teoría de los modelos. En la teoría de la recursividad, muchos resultados clásicos pueden verse, en retrospectiva como argumentos de forzamiento. Consideremos, por ejemplo, el teorema de Kleene-Post de que hay grados de Turing incomparables. Sea $\Bbb{P}$ = Fn $(2$ x $\omega, 2)$ , dejemos que $G$ sea $\Bbb{P}$ -generico sobre $M$ y pensar en $G$ como codificación $f_0$ y $f_1\in2^{\omega}$ , donde $f_i(n) =\cup G(i,n)$ . Además, para concluir la incomparabilidad recursiva de $f_0$ y $f_1$ no es necesario que $G$ sea genérico sobre todos los $M$ ; es suficiente con que $G$ intersecan sólo algunos de los conjuntos densos aritméticamente definidos de $M$ ; tan pocos que de hecho $G$ y, por tanto, también $f_0$ y $f_1$ puede considerarse recursivo en $0'$ . Este argumento para forzar la producción de grados incomparables por debajo de $0'$ es de hecho precisamente el argumento original de Kleene-Post, con un ligero cambio de notación. Véase [Sacks 1971] para algunas aplicaciones más profundas del forzamiento a la teoría de la recursión y una comparación de estos métodos con las técnicas anteriores (de preforzamiento)". [De Teoría de conjuntos , por Kenneth Kunen, p.236]

Nota histórica: Cohen no desarrolló el forzamiento en términos de órdenes parciales generales. Su maquinaria de forzamiento fue desarrollada (1) sólo sobre modelos de la teoría de conjuntos que satisfagan el axioma de constructibilidad de Gödel (V=L), y (2 ) y para ciertos conjuntos de orden parcial [concretamente los de la forma Fn( $\kappa, 2$ ) en la terminología moderna]. La maquinaria de forzamiento sobre modelos arbitrarios fue desarrollada por primera vez por Solovay y Scott bajo la forma de modelos de valor booleano. Su enfoque fue simplificado posteriormente por Shoenfield para dar lugar a las formulaciones actuales de los libros de texto en términos de órdenes parciales arbitrarios.

Por lo tanto, aunque los argumentos de prioridad pueden ser vistos como argumentos de forzamiento (como fueron desarrollados por Nerode y Remmel, y descritos en la respuesta de Noah S.) el trabajo de Cohen sobre el forzamiento, sólo cuando fue extendido por las nuevas ideas de Solovay, Scott y Shoenfield (y quizás otros, por ejemplo, Rowbottom) condujo a una tecnología suficientemente poderosa que subsume (al menos formalmente) los argumentos de prioridad.

Answer 2

La principal diferencia entre los argumentos de forzamiento en la teoría de conjuntos y las construcciones de prioridad es que estas últimas se preocupan por la complejidad del filtro genérico de una manera que las primeras no lo hacen. En particular, el forzamiento en la teoría de conjuntos implica golpear cada conjunto denso en un modelo dado, por lo que el genérico no puede ser un miembro de ese modelo (a menos que el poset sea trivial), mientras que si se enmarcan las construcciones prioritarias como argumentos forzados el objetivo es dar con un contable conjunto de conjuntos densos con un genérico que es computable (o casi) como conjunto de condiciones (el conjunto codificado por el genérico, en cambio, no será computable).

(Permítanme escribirlo explícitamente, en el caso de Friedberg-Muchnik: el poset en cuestión es el conjunto de pares $(p, \rho)$ , donde $p$ es el conjunto construido hasta ahora (es decir, $p\in 2^{<\omega}$ ) y $\rho$ es el conjunto de restricciones impuestas hasta el momento (así $\rho$ es un subconjunto finito de $\omega\times(\omega\cup\lbrace -1\rbrace$ ) con cada elemento de $\omega$ que se presenta como el componente izquierdo de como máximo un elemento de $\rho$ ). El poset se ordena de la siguiente manera: $(p, \rho)\le(q, \pi)$ si

1. $\vert p\vert\ge\vert q\vert$ y $\forall n<\vert q\vert, q(n)\le p(n)$ (esta es la condición c.e. - no se nos permite eliminar elementos del conjunto que estamos construyendo);

2. para todos $(n, m)\in\pi$ con $m>-1$ , ya sea $p\upharpoonright m+1=q\upharpoonright m+1$ o para algunos $k<n$ y $j>-1$ tenemos $(k, j)\in \rho-\pi$ (esta es la condición que faltaba y que Francois señaló, que estipula que las restricciones sólo pueden ser violadas por las acciones de los requisitos de mayor prioridad); y

3. $$ \forall n\in dom(\rho), \rho(n)\not=\pi(n)\implies \exists m < n[(\rho(m)=-1\vee m\not\in dom(\rho))\wedge \pi(m)\downarrow>-1).$$ (Esto sólo dice que $\rho$ "podría ocurrir de $\pi$ por lesión").

Obsérvese que las condiciones de este poset pueden codificarse mediante números naturales, por lo que tiene sentido hablar de que un conjunto de condiciones -es decir, un filtro- es computable. Ahora los requisitos del argumento de Friedberg-Muchnik pueden representarse mediante conjuntos densos (que son no computables) en este poset, dos por cada $\Phi_e$ y el teorema se convierte en "hay un filtro computable a través de este poset genérico para esta colección de conjuntos densos". De hecho, creo que el poset descrito anteriormente es "universal" para los argumentos de lesión finita, en el sentido de que cada argumento de lesión finita puede ser tratado por venir con una lista apropiada de subconjuntos densos de este poset y luego argumentar que hay un filtro computable que es genérico para esa colección de conjuntos, pero no estoy seguro de eso).

Una posible analogía más fuerte: los argumentos prioritarios son como los axiomas forzosos. Los axiomas de forzamiento dicen "para tal o cual poset y colección de conjuntos densos, ya existe un filtro genérico en el modelo". Por ejemplo, el axioma de Martin dice que para cualquier poset $\mathbb{P}$ con el c.c.c. y cualquier colección $\mathcal{D}$ de $< 2^{\aleph_0}$ -muchos conjuntos densos, ya hay un $\mathcal{D}$ -Filtro genérico. Por analogía, el remate de un argumento de prioridad suele ser "para este poset particular y estos conjuntos densos, hay un filtro genérico computable". En ambos casos, partimos del teorema de Rasiowa-Sikorski ("podemos dar con un número contable de conjuntos densos") y tratamos de reforzarlo: en el caso de la teoría de conjuntos, ampliando la clase de conjuntos densos, y en el caso de la teoría de la computabilidad, restringiendo la colección de filtros que consideramos. De hecho, esta es una analogía en la que he pasado mucho tiempo pensando a lo largo del último año; no me ha ayudado a entender los argumentos de prioridad, pero sí los axiomas de forzamiento.

Dicho esto, pienso en las construcciones prioritarias como un tipo de forzamiento; sólo que me doy cuenta de que esto no es necesariamente convincente.

---

Ahora permítanme abordar brevemente la cuestión de qué papel, si es que hay alguno, desempeñó Friedberg/Muchnik (o el trabajo anterior relacionado de Kleene/Post) en el desarrollo del forzamiento de Cohen. Por un lado, en su artículo "The Discovery of Forcing" (que usted cita), Cohen describe su proceso como algo principalmente autónomo, pero en un momento clave reforzado por la lectura de la monografía de Goedel sobre $L$ . No se hace ninguna referencia a la teoría de la computabilidad y, de hecho, las palabras "Friedberg", "Muchnik", "Post", "prioridad" y "recursión" no aparecen en ninguna parte del artículo. ("Kleene" aparece una vez, pero sólo en referencia al hecho de que el tomo de Kleene sobre lógica matemática no incluía nada especialmente relevante para el proyecto de Cohen). Por otra parte, me parece recordar un artículo en el que Cohen describía su imagen del forzamiento como algo que implicaba un oráculo adaptable, que él relacionaba con la teoría de la computabilidad, lo que sugeriría una influencia real. Pero no puedo encontrar esa cita en este momento; todo lo que puedo encontrar es un comentario de Chad Groft en el blog de Terry Tao http://terrytao.wordpress.com/2010/03/19/a-computational-perspective-on-set-theory/ que dice que Cohen explicó el forzamiento de esta manera en sus últimos años. Pero es posible que Cohen haya cambiado su intuición sobre el forzamiento a lo largo del tiempo, de modo que es muy posible que Cohen llegara a considerar sus argumentos sobre el forzamiento como relacionados en espíritu con la teoría de la recursión, aunque en realidad no se haya inspirado en el tema originalmente.