Forzamiento (computabilidad)

El forzamiento en la teoría de la computabilidad es una modificación de la técnica original de teoría de conjuntos de Paul Cohen para abordar cuestiones de computabilidad.

Conceptualmente, las dos técnicas son bastante similares: en ambas se intenta construir objetos genéricos (intuitivamente, objetos que son de alguna manera "típicos") al cumplir con conjuntos densos . Ambas técnicas se describen como una relación (habitualmente denotada como ) entre "condiciones" y oraciones. Sin embargo, mientras que el forzamiento teórico de conjuntos generalmente está interesado en crear objetos que cumplan con cada conjunto denso de condiciones en el modelo base, el forzamiento teórico de computabilidad solo apunta a cumplir con conjuntos densos que sean definibles aritmética o hiperaritméticamente. Por lo tanto, parte de la maquinaria más difícil utilizada en el forzamiento teórico de conjuntos se puede eliminar o simplificar sustancialmente al definir el forzamiento en computabilidad. Pero si bien la maquinaria puede ser algo diferente, el forzamiento teórico de computabilidad y el forzamiento teórico de conjuntos se consideran adecuadamente como una aplicación de la misma técnica a diferentes clases de fórmulas. ${\displaystyle \Vdash }$

Terminología

En este artículo utilizamos la siguiente terminología.

real

un elemento de . En otras palabras, una función que asigna cada entero a 0 o 1. ${\displaystyle 2^{\omega }}$

cadena

un elemento de . En otras palabras, una aproximación finita a un real. ${\displaystyle 2^{<\omega }}$

noción de forzar

Una noción de forzamiento es un conjunto y un orden parcial en , con un elemento mayor . ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \succ _{P}}$ ${\displaystyle 0_{P}}$

condición

Un elemento de una noción de fuerza. Decimos que una condición es más fuerte que otra condición sólo cuando ... ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle q\succ _{P}p}$

condiciones compatibles

Las condiciones dadas dicen que y son compatibles si hay una condición tal que con respecto a , tanto y como pueden satisfacerse simultáneamente si son verdaderas o se permite que coexistan. ${\displaystyle p,q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle q}$

${\displaystyle p\mid q}$

significa y son incompatibles. ${\displaystyle p}$ ${\displaystyle q}$

Filtrar

Un subconjunto de una noción de forzamiento es un filtro si , y . En otras palabras, un filtro es un conjunto compatible de condiciones cerradas bajo condiciones de debilitamiento. ${\displaystyle F}$ ${\displaystyle P}$ ${\displaystyle p,q\in F\implies p\nmid q}$ ${\displaystyle p\in F\land q\succ _{P}p\implies q\in F}$

Ultrafiltro

Un filtro maximalista, es decir, es un ultrafiltro si es un filtro y no hay ningún filtro que contenga adecuadamente . ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F'}$ ${\displaystyle F}$

Cohen forzando

La noción de forzar donde las condiciones son elementos de y ) ${\displaystyle C}$ ${\displaystyle 2^{<\omega }}$ ${\displaystyle (\tau \succ _{C}\sigma \iff \sigma \supset \tau }$

Obsérvese que, para Cohen, el forzamiento es el inverso de la relación de contención. Esto conduce a una desafortunada confusión notacional en la que algunos teóricos de la computabilidad invierten la dirección del orden parcial de forzamiento (intercambiándolo con , que es más natural para el forzamiento de Cohen, pero está en desacuerdo con la notación utilizada en la teoría de conjuntos). ${\displaystyle \succ _{C}}$ ${\displaystyle \succ _{P}}$ ${\displaystyle \prec _{P}}$

Objetos genéricos

La intuición que subyace a la imposición es que nuestras condiciones son aproximaciones finitas a algún objeto que deseamos construir y que es más fuerte que cuando concuerda con todo lo que dice sobre el objeto que estamos construyendo y agrega algo de información propia. Por ejemplo, en la imposición de Cohen, las condiciones pueden verse como aproximaciones finitas a un valor real y si entonces nos dice el valor del valor real en más lugares. ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \tau \succ _{C}\sigma }$ ${\displaystyle \sigma }$

En un momento definiremos una relación (léase fuerza ) que se cumple entre condiciones (elementos de ) y oraciones, pero primero debemos explicar el lenguaje para el que se usa una oración. Sin embargo, forzar es una técnica, no una definición, y el lenguaje para el que se usa dependerá de la aplicación que uno tenga en mente y de la elección de . ${\displaystyle \sigma \Vdash _{P}\psi }$ ${\displaystyle \sigma }$ ${\displaystyle \psi }$ ${\displaystyle P}$ ${\displaystyle \psi }$ ${\displaystyle \psi }$ ${\displaystyle P}$

La idea es que nuestro lenguaje exprese hechos sobre el objeto que deseamos construir con nuestra construcción forzada.

Relación de fuerza

La relación de forzamiento fue desarrollada por Paul Cohen , quien introdujo el forzamiento como una técnica para demostrar la independencia de ciertas afirmaciones de los axiomas estándar de la teoría de conjuntos, particularmente la hipótesis del continuo (CH). ${\displaystyle \Vdash }$

La notación se utiliza para expresar que una condición particular o un conjunto genérico obliga a que una determinada proposición o fórmula sea verdadera en la extensión forzada resultante. Aquí representa el universo original de conjuntos (el modelo básico), denota la relación forzada y es un enunciado en la teoría de conjuntos. Cuando , significa que en una extensión forzada adecuada, el enunciado será verdadero. ${\displaystyle V\Vdash \phi }$ ${\displaystyle \phi }$ ${\displaystyle V}$ ${\displaystyle \Vdash }$ ${\displaystyle \phi }$ ${\displaystyle V\Vdash \phi }$ ${\displaystyle \phi }$

Referencias

• Fitting, Melvin (1981). Fundamentos de la teoría de la recursión generalizada . Estudios de lógica y fundamentos de las matemáticas. Vol. 105. Ámsterdam, Nueva York y Oxford: North-Holland Publishing Company. págs. 1078-1079. doi :10.2307/2273928. JSTOR  2273928. S2CID  118376273.
• Odifreddi, Piergiorgio (1999). Teoría de la recursión clásica. Vol. II . Estudios de lógica y fundamentos de las matemáticas. Vol. 143. Ámsterdam: North-Holland Publishing Company. ISBN 978-0-444-50205-6.Señor 1718169  .