¿Podemos rechazar la elección finita?

Question

Cuando la gente trabaja con conjuntos infinitos, hay a quien (con razón) no le gusta utilizar el axioma de elección. Esto es defendible, ya que el axioma es independiente de los otros axiomas de la teoría de conjuntos ZF.

Cuando la gente trabaja con conjuntos finitos, todavía hay algunas personas a las que no les gusta utilizar el "axioma finito de elección", es decir, no les gusta escoger un elemento distinguido de un conjunto, o un isomorfismo distinguido entre un conjunto con $n$ elementos y $\{0, 1, \ldots, n-1\}$ (sin algún algoritmo que lo elija, claro). Ésta sigue siendo una posición estéticamente defendible, ya que a menudo las pruebas que proceden de esa manera no dan tanta información como las pruebas que no utilizan la elección finita. Pero la teoría de conjuntos ZF nos permite hacer esto para conjuntos finitos.

¿Existe un marco general en el que podamos desautorizar, si así lo deseamos, el método del elemento distinguido? Tengo la corazonada de que el hecho de que, incluso para un espacio vectorial de dimensión finita $V$ , $V$ y $V^\ast$ no son naturalmente isomorfas es el primer paso hacia la "respuesta correcta", pero no veo realmente por dónde seguir a partir de ahí.

(Para que quede claro, como señala Ilya, me estoy refiriendo principalmente a la teoría de conjuntos; sé que/cómo la teoría de categorías nos habla de la no naturalidad del isomorfismo del espacio vectorial dual, en particular. Mi pregunta es: ¿hay algo que subsuma esto o que lo paralelice para construcciones más combinatorias)?

Answer 1

Quizá te interese la teoría de los topos. Un topos es algo así como la categoría de conjuntos, pero la lógica interna de un topos general es mucho más débil que ZF; ni siquiera tiene por qué ser booleana. Un ejemplo de topos es la categoría de tramas de conjuntos en un espacio topológico. Se puede utilizar la teoría de topos para convertir enunciados vudú de las matemáticas constructivas en enunciados matemáticos ordinarios que se puedan entender: por ejemplo, "un conjunto no vacío S podría no tener ningún elemento" se convierte en "una gavilla S que no es la gavilla vacía podría no tener ninguna sección global" (o posiblemente "podría no tener secciones locales en todas partes"), lo que por supuesto es cierto. Una referencia canónica sobre este tema es Mac Lane & Moerdijk, Sheaves in Geometry and Logic.

Answer 2

Esto es posible en la matemática constructiva, porque distingue entre conjuntos finitos y conjuntos con un número contado de elementos. (Aunque no estoy muy seguro de cuál es la terminología estándar).

Un conjunto $S$ es finito si existe un número natural $n$ tal que existe un mapa suryectivo desde $[0, \ldots, n-1]$ a $S$ . Un conjunto $T$ se cuenta, si hay un $m$ tal que existe un isomorfismo entre ella y los números $[0, \ldots, m-1]$ .

Ahora, observe que la finitud limita el número de elementos en $S$ -- no puede haber más que $n$ . Sin embargo, no necesariamente sabemos exactamente cuántos elementos hay, ya que la igualdad puede no ser decidible en $S$ . (Es decir, podríamos no saber cómo mostrar para cada $s$ y $s'$ que $s = s'$ o $s \not= s'$ .) Por supuesto, el recuento implica finitud (basta con tomar la mitad de la iso). También implica igualdad decidible en los elementos (ya que podemos convertir dos $T$ s a números naturales, y compararlos). Del mismo modo, la finitud y la igualdad decidible implican contabilidad (iterar sobre los elementos de $S$ y utilizar la igualdad para identificar los duplicados). Pero la finitud por sí sola no es suficiente para implicar el recuento.

Esto me parece que capta la intuición de que no siempre podemos disponer del isomorfismo distinguido. Un argumento combinatorio da un método para conjuntos contados (constructivos). Uno que no utiliza la elección da un método que también funcionará (constructiva) conjuntos finitos.

Answer 3

En realidad, puede evitar horrores arcanos como las categorías y los topoi. Cuando se pasa de infinito a finito, gran parte de la dificultad (en mi opinión) radica en averiguar 1) hasta qué punto el enunciado original era realmente algorítmico por naturaleza y 2) cuáles eran los límites de recursos implícitos. Una vez que se descifran estos enunciados, queda mucho más claro lo que el oráculo AC está haciendo en realidad por el algoritmo, y entonces se llega a límites de recursos análogos.

Creo que enfocar los problemas de este modo será más útil y satisfactorio que suponer que algún día funcionará una batería de armas enormes.

Para referencias específicas, puede consultar el trabajo de Blass, Gurevich y Shelah sobre "Choiceless Polynomial Time" (Tiempo polinómico sin elección), que consiste esencialmente en calcular utilizando los conjuntos hereditariamente finitos sobre un conjunto finito de átomos. La literatura sobre teoría de modelos finitos está repleta de trabajos sobre la potencia de varios modelos de computación con y sin orden lineal. También hay un trabajo (en gran parte incomprensible, pero qué se le va a hacer) de Shelah sobre la clasificación de cuantificadores de segundo orden sobre universos finitos.

Answer 4

Ya que todos estamos generando ideas, he aquí una forma de diferenciar entre un conjunto con n elementos y un conjunto con una enumeración elegida, es decir, una biyección elegida con {1,..., n }. A saber, considérese el endofunctor sobre el agrupoide de conjuntos finitos (por lo que sólo se admiten isomorfismos) que asigna a cada conjunto finito su conjunto de permutaciones, y por otro lado considérese el endofunctor que asigna a cada conjunto S de tamaño n el conjunto de biyecciones entre S y {1,..., n }. Entonces cada functor asigna un conjunto de tamaño n a cada conjunto de tamaño n pero los funtores no son isomorfos, sino que se comportan de forma diferente con los morfismos. Sin embargo, son isomorfos en el grupo de conjuntos con enumeraciones elegidas, porque este grupo no tiene automorfismos no triviales.

¿Qué sentido tiene? La mayoría de las construcciones combinatorias pueden expresarse como endofunctores en el grupo de conjuntos finitos. Y redactarlas así requiere, como mínimo, que estés muy atento a si has elegido algunos elementos. Si puedes redactar tu prueba como un isomorfismo de endofunctores, entonces probablemente sea buena sin "axioma de elección finita".

Answer 5

Sí, este marco se llama teoría de categorías .

Empecemos con el ejemplo de los espacios vectoriales. Lo que se hace es decir que algunas operaciones son natural . Estas operaciones deben tener sentido no sólo para el propio espacio, sino también para cualquier mapa entre dos espacios vectoriales.

He aquí un ejemplo: la "máxima potencia" $\bigwedge^{\mathrm{top}}$ de un espacio vectorial de dimensión finita $V$ es el espacio unidimensional $$V\wedge V\wedge \dots \wedge V$$ (donde la operación de cuña se toma con $\dim V$ copias de $V$ .) Se trata de un funcionamiento natural porque si coges un mapa $V\to W$ entonces hay un mapa natural $\bigwedge^{\mathrm{top}}V\to \bigwedge^{\mathrm{top}}W$ (dada por el determinante).

Esto impide la elección arbitraria de la siguiente manera: si la operación es natural, no se le permite elegir un elemento distinguido para construirlo, porque si lo hace, se romperá la propiedad para un mapa de un espacio en sí mismo que cambia elemento distinguido.

En $V$ y $V^* $ también encaja aquí, aunque con un ligero giro: para cualquier mapa $V\to W$ existe un mapa dual que va desde $W^ * \to V^ * $ (este será un contravariante a diferencia de una covariante operación anterior).

A partir de esta observación, la teoría de categorías procede a aprender mucho sobre las propiedades generales que categorías (de los cuales espacios vectoriales es el primer ejemplo) y operaciones naturales (explicado anteriormente) podría tener. Es un área grande y vibrante de las matemáticas representada aquí bajo la etiqueta category-theory .

Hay muchas buenas introducciones, la estándar es

Categorías para el matemático en activo de Mac Lane ( Springer Amazon )