Teorema del buen orden y lógica de segundo orden

Question

Me confunde esta frase del artículo de la Wikipedia sobre el "Teorema del buen orden":

...el teorema del buen orden es equivalente al axioma de la elección, en el sentido de que cualquiera de los dos, junto con los axiomas de Zermelo-Fraenkel, es suficiente para demostrar el otro, en la lógica de primer orden (Lo mismo se aplica al lema de Zorn.) . En la lógica de segundo orden, sin embargo, el teorema del buen orden es estrictamente más fuerte que el axioma de elección: del teorema del buen orden se puede deducir el axioma de elección, pero del axioma de elección no se puede deducir el teorema del buen orden

¿No es la lógica de segundo orden más fuerte que la de primer orden? ¿Cómo es que la prueba de equivalencia en la lógica de primer orden ya no es válida en la lógica de segundo orden?

Answer 1

Si sigues las referencias dadas en el artículo de Wikipedia, descubrirás que el contexto de este teorema es muy diferente.

Aunque muchas matemáticas se hacen dentro de los modelos de $\sf ZFC$ con la lógica de primer orden (y así podemos hacer afirmaciones sobre la lógica de alto orden dentro del modelo). Sin embargo, se puede utilizar la lógica de segundo orden (o más bien algunos sistemas de lógica de segundo orden) como base para las matemáticas. Es decir, ya no trabajamos en $\sf ZFC$ Trabajamos en un contexto de lógica de segundo orden.

En ciertos sistemas que incluyen el axioma de elección, el principio de buen ordenamiento no es demostrable. Sin embargo, sin utilizar el axioma de elección, no es difícil demostrar que el principio de ordenación implica el axioma de elección.

Esto es esencialmente el teorema 5.4 que puedes encontrar en la página 107 del libro de Shapiro.

Answer 2

Hay otro problema al tratar de interpretar esta afirmación del artículo de la Wikipedia:

En la lógica de segundo orden, sin embargo, el teorema del buen orden es estrictamente más fuerte que el axioma de la elección: del teorema del buen orden se puede deducir el axioma de la elección, pero del axioma de la elección no se puede deducir el teorema del buen orden

En la aritmética de segundo orden, el "teorema del buen orden" es trivial: suele entenderse que todo conjunto de números naturales tiene un elemento mínimo, que es una consecuencia trival de un axioma de inducción. Es difícil incluso afirmar en la aritmética de segundo orden que "existe una ordenación bien de la clase $S$ de todos los subconjuntos de $\mathbb{N}$ " porque, sintácticamente, es una afirmación de tercer orden. Se podría afirmar que existe una ordenación definible de $S$ refiriéndose a una fórmula particular que define el ordenamiento del pozo, pero no hay ninguna razón para sospechar que existe, de hecho, un ordenamiento del pozo definible de $S$ a menos que también asumamos algo como $V = L$ .

Sin embargo, en la aritmética de segundo orden, el "axioma de elección" se formula típicamente como un esquema axiomático. Y se suele estudiar en una forma en la que los objetos que se eligen son conjuntos, no números naturales. Una instancia típica del esquema dice: $$ (\forall n)(\exists Y)\Phi(n,Y) \to (\exists Z)(\forall m)\Phi(m,(Z)_m) $$ donde $(Z)_m = \{ k : \langle m,k\rangle \in Z\}$ . Ver Simpson, Subsistemas de aritmética de segundo orden , sección VII.6.

Ahora el teorema del buen orden para los números no implica el esquema para el axioma de elección para los conjuntos que acabo de describir. De hecho, el sistema axiomático completo para la aritmética de segundo orden, con comprensión para todas las fórmulas, ni siquiera demuestra todos los casos del axioma de elección en los que $\Phi$ es $\Sigma^1_3$ (Simpson VII.6.3).

La cuestión clave aquí es que, aunque el "axioma de elección" tiene mucho sentido en términos de teoría de tipos, como la aritmética de segundo orden y la lógica de segundo orden en general, no significa en absoluto lo mismo que en el lenguaje "no tipificado" que se suele utilizar para la teoría de conjuntos.