ZFC no es finitamente axiomatizable. Pero es, (y sé que esto no es preciso todavía) finitamente axioma-esquematizable. Así que mi pregunta es, ¿qué es exactamente un esquema axiomático de un cálculo lógico como la lógica de primer orden o la lógica proposicional, como ((A Y B) IMPLICA B)? Bueno, supongo que sería un conjunto de enunciados. Pero, ¿qué hace exactamente que un conjunto de enunciados sea un esquema?
Respuestas
¿Demasiados anuncios?
JacobN
Puntos
151
Un esquema axiomático es un conjunto infinito de axiomas, todos los cuales tienen una forma similar.
Por ejemplo, en la Aritmética de Peano, existe el esquema axiomático de inducción; para cada predicado de primer orden $\phi$ en el lenguaje de PA, tenemos un axioma:
$$(\phi(0) \wedge \forall n (\phi(n) \rightarrow \phi(n+1))) \rightarrow \forall n \phi(n)$$
Para diferentes fórmulas $\phi$ obtenemos axiomas completamente separados. Por ejemplo, podemos sustituir $\phi$ con la fórmula $n+1+1 = n+2$ o con la fórmula $\forall m (((\exists l) n + l = m) \vee ((\exists l) n = m + l))$ o cualquier otra fórmula que podamos escribir.
Sin embargo, cada uno de estos axiomas tiene la misma "forma" - se dan sustituyendo alguna fórmula por $\phi$ . Este no es un conjunto finito de axiomas, y se puede demostrar que no puede haber un conjunto finito de axiomas que funcione, pero si permitiéramos un símbolo $\forall^* \phi$ que cuantifica sobre todas las fórmulas $\phi$ (que es básicamente lo que es la lógica de segundo orden), podríamos escribirlo como un único axioma.
Como ya se ha mencionado, "esquema" no es un término totalmente preciso (y, por cierto, véase aquí para un análisis del papel de los esquemas en la historia de la lógica). Sin embargo, hay un candidato natural para lo que esto debería significar, y es básicamente la respuesta de Dorebell (esta respuesta es en realidad una nota a pie de página excesivamente larga) :
En esquema de sentencias en una firma $\Sigma$ es una frase $\sigma$ en el idioma $\Sigma\sqcup\{R\}$ para algunos $k$ símbolo de relación -ario (normalmente unario) $R$ . Un instancia de $\sigma$ es entonces una frase de la forma $$\forall y_1,...,y_n(\sigma[R/\varphi(y_1,...,y_n,x_1,....,x_k)])$$ donde $\varphi$ es algo $(n+k)$ fórmula -aria en la lengua original $\Sigma$ y $\sigma[R/\varphi(y_1,...,y_n,x_1,..., x_k)]$ es el $L$ -obtenida sustituyendo cada " $R(t_1,...,t_k)$ " con " $\varphi(y_1,...,y_n,t_1,...,t_k)$ "en todo $\sigma$ .
El complemento $y_i$ s y el más externo $\forall$ equivale a permitir parámetros del objeto en el régimen.
Por ejemplo, veamos el lenguaje de la aritmética $\Sigma_{arith}=\{0,1,+,\cdot, \le\}$ . Elegimos algún símbolo de relación unario aún no utilizado $U$ y el plan de inducción $\eta$ es entonces sólo (representado por) el $\Sigma_{arith}\sqcup\{U\}$ -fórmula $$[U(0)\wedge \forall x(U(x)\rightarrow U(x+1))]\rightarrow \forall xU(x).$$ En $\varphi(y,x)$ la fórmula $$y\le x$$ obtenemos el $\eta$ -instancia $$\forall y([\varphi(y,0)\wedge \forall x(\varphi(y,x)\rightarrow \varphi(y,x+1))]\rightarrow\forall x\varphi(y,x)),$$ o más sencillamente $$\forall y([y\le 0\wedge\forall x(y\le x\rightarrow y\le x+1)]\rightarrow \forall x(y\le x)).$$ Por supuesto, es una tontería (aunque cierta), pero es un buen ejemplo de esquema.
Para la mayoría de los propósitos, no nos importa realmente esta noción precisa - la ampliamente noción más débil de teoría axiomatizable computacionalmente suele ser suficiente para nuestros fines. Sin embargo, hay una situación particular en la que los esquemas definidos anteriormente brillan, y es la siguiente teoría de modelos abstractos .
Un plan $\sigma$ se formula en una "lógica básica", por ejemplo, la lógica de primer orden. Sin embargo, podemos interpretar $\sigma$ en más grande lógicas (por ejemplo, la lógica de segundo orden) al permitir la instancias de $\sigma$ venir de $\varphi$ s en esa lógica más amplia. Fijándonos de momento en la lógica de primer orden, esto equivale a decir lo siguiente:
A partir de un esquema $\sigma$ en una firma $\Sigma$ obtenemos un mapa $M_\sigma$ asignando a cada lógica $\mathcal{L}$ que es al menos tan fuerte como la lógica de primer orden un conjunto $M_\sigma(\mathcal{L})$ de $\mathcal{L}$ -sentencias de firma $\Sigma$ es decir, el conjunto de todos los casos de $\sigma$ obtenido por permitir $\mathcal{L}$ -(y no sólo fórmulas FOL) como entrada $\varphi$ s.
(Ignoro aquí la cuestión de la definición precisa de "lógica", pero véase, por ejemplo, el último capítulo de Ebbighaus/Flum/Thomas).
Esto nos permite tratar teorías "esquemáticas" como PA o ZFC como instancias de una construcción más amplia:
-
$\mathcal{PA}$ es el mapa que envía una lógica $\mathcal{L}$ que contiene lógica de primer orden a la $\mathcal{L}$ -teoría $$P^-+M_\eta(\mathcal{L}),$$ donde $\eta$ es el esquema de inducción anterior y $P^-$ es el axioma para semirings ordenados discretos.
-
$\mathcal{ZFC}$ es el mapa que envía una lógica $\mathcal{L}$ que contiene lógica de primer orden a la $\mathcal{L}$ -teoría $$PPIUECR+M_\rho(\mathcal{L})+M_\xi(\mathcal{L}),$$ donde $PPUECR$ es la conjunción de los axiomas Powerset, Pairing, Infinity, Union, Extensionality, Choice y Regularity y $\rho$ y $\xi$ son esquemas correspondientes a Sustitución y Separación respectivamente.
(Por cierto, esta idea de "parametrización por lógica" también se da en otros contextos, como en análogos del universo construible de Godel .)
Personalmente, me gusta esta refundición de las teorías "esquemáticas" como teorías "parametrizadas" porque nos ayuda a separar limpiamente dos cuestiones a menudo enredadas:
-
¿Cuáles son nuestras intuiciones matemáticas básicas para los números naturales/conjuntos/lo que sea?
-
¿Cuál es el sistema lógico correcto para analizar números naturales/conjuntos/lo que sea?
Podemos decir "Bueno, los números naturales son un semiring ordenado discreto + inducción" en una respuesta vaga pero convincente al primer punto sin decantarnos todavía por la lógica de primer orden como respuesta correcta al segundo. El mapa $\mathcal{PA}$ descrita anteriormente constituye una formalización de esta respuesta sin comprometerse con una respuesta al segundo punto. El dominio absoluto de la lógica de primer orden significa que esto no es algo que nos preocupe demasiado, pero es un ejemplo de una idea muy simple facilitada por la noción precisa de "esquema" articulada más arriba, para la que nociones más generales como "teoría axiomatizable computacionalmente" no dan la talla.
Mark Struzinski
Puntos
11288
"Esquema" no es un término preciso, pero la intención bienintencionada es que sea fácil enumerar los axiomas y decidir si una fórmula concreta es un axioma o no. Por ejemplo, normalmente queremos poder verificar las pruebas en tiempo polinómico, por lo que deberíamos exigir lo mismo de cualquier "esquema axiomático".
