¿Es computable la teoría de la categoría de espacios topológicos?

Question

Esta pregunta está inspirada en este Mathoverflow pregunta.

Ignorando los problemas de tamaño, no hay una manera natural a la vista de la categoría de primer orden de la estructura en un lenguaje finito. A la luz de esto, podemos preguntar acerca de la complejidad computacional de los de primer orden de teoría de una categoría dada. Tenga en cuenta que una gran cantidad de importante de la estructura se pierde al pasar el primer nivel de la orden; sin embargo, todavía parece interesante para mí.

Un montón de categorías que se pueden comprobar fácilmente a tener muy complicado de primer orden teorías - por ejemplo, suponiendo que el axioma de elección en el fondo podemos identificar los conjuntos finitos como aquellos para los cuales cada auto-inyectable es un surjection, y dado que los productos Cartesianos y los distintos sindicatos de la aritmética habitual tenemos que el primer orden de teoría de la categoría de Conjuntos no es computable.

Por cierto, la elección no es necesario aquí, pero la no-elección argumento es un poco más tedioso.

Mi pregunta es:

Es el primer orden de teoría de la categoría Superior de espacios topológicos (con morfismos continua mapas) computable?

Mi sospecha es que la respuesta es no. Una manera obvia de probar este sería mostrar que el finito espacios discretos son de primer orden caracterizables aquí, y desde entonces se podría correr el mismo argumento como para Conjuntos; sin embargo, no veo cómo hacerlo. (En particular, la noción de "pacto objcet" de una categoría no es, obviamente, de primer orden se puede expresar, por lo que la caracterización de los limitados espacios discretos , no parece ayudar.)

---

Hay versiones más débiles de esta pregunta que se le podría preguntar:

• Podemos enfocarnos en la teoría de la equivalencia categorial de la clase de la parte Superior , es decir, el conjunto de sentencias verdaderas en cada una de las categorías que se categorially equivalente a la parte Superior. En general categorial de equivalencia no implica primaria de equivalencia (desde una a dos elementos, la categoría puede ser categorially equivalente a un solo elemento de la categoría), por lo que este es un trivial de debilitamiento.

• También podemos restringir la atención a una subcolección de categorías, es decir, precisar algunos no de primer orden categorial de la propiedad $P$ de la parte Superiory, a continuación, pedir a una de primer orden de la teoría que distingue a la teoría de la parte Superior (o la teoría de la equivalencia categorial de la clase de la parte Superior) dentro de esta clase. Por ejemplo, Lawvere del ETCS caracteriza a los Conjuntos de hasta categorial de equivalencia entre el nivel local pequeño categorías completas.

Yo también estoy interesado en comentarios a lo largo de estas líneas; sin embargo, mi principal pregunta es específicamente sobre el primer orden de teoría de la parte Superior.

EDICIÓN: David Roberts traído a mi atención Schlomiuk papel de Una teoría elemental de la categoría de espacios topológicos; entre otras cosas, esto le da una computable (de hecho, finito) la teoría de la caracterización de la parte Superior hasta categorial de equivalencia entre categorías completas, así como en una más sutil sentido (en cualquier tipo de categoría es equivalente a la Cima$^\mathfrak{S}$ para algunos modelos de $\mathfrak{S}$ de ETCS).

Answer 1

Permítanme asumir elección. Es posible distinguir espacios discretos de otros espacios: esos son, precisamente, los espacios de $X$ tal que para cualquier epimorphism $f:Y\to X$ admite una sección de $g:X\to Y$ (es decir, $g\circ f=\mathrm{id}_Y$). Para ver esto, recordemos primero que epimorphisms en la parte Superior son sólo el surjective continua de los mapas.

Si $X$ es discreto, entonces para cualquier epimorphism $Y\to X$ hay una sección teórica por AC, que es automáticamente continua.

Por el contrario, supongamos que cada epimorphism en $X$ se divide. Deje $Y$ tienen el mismo subyacente espacio como $X$, pero la topología discreta. Entonces la identidad en los puntos es un mapa continuo de $Y\to X$, y ya que es un epimorphism, se admite una sección, que muestra que $X$ es discreto.

La subcategoría de discretos espacios topológicos es equivalente a la categoría de conjuntos, y usted ya sabe que es uncomputable. De ello se desprende el primer orden de teoría de la parte Superior es indecidible.

No me queda claro si esta prueba puede ser modificado para evitar el uso de corriente ALTERNA.

Edit: una prueba sin el uso de AC: vamos a volver a distinguir la subcategoría de espacios discretos. Deje $1$ , un punto en el espacio (un terminal de objeto) y $2$ dos puntos discretos en el espacio (un espacio con exactamente dos mapas de $1$ a, $4$ mapas de ella misma) y $i:1\to 2$ cualquier mapa. A continuación, $X$ es discreto iff para cualquier mapa de $f:1\to X$ hay un mapa de $g:X\to 2$ tal que $g\circ f=i$, y para cualquier $f':1\to X,f'\neq f$, tenemos $g\circ f'\neq i$.

De esta manera se expresa que para cualquier punto de $x\in X$, hay un mapa de $X\to 2$ que se lleva a $x$ a un punto, y todos los otros puntos a uno diferente. Desde $2$ fue discreta, esto implica $\{x\}$ es abierto, por lo $X$ es discreto.

Ya te digo que sé Conjunto ha uncomputable teoría, incluso sin AC, deducimos que el mismo por la parte Superior.

Answer 2

Aquí es un método de definición de los números naturales en $\mathbf{Set}$ (sin Elección) que generaliza inmediatamente a $\mathbf{Top}$. Es decir, podemos expresar la segunda orden axiomas de Peano directamente en nuestro categórico idioma. Fijemos un terminal objeto de $1$. Entonces podemos definir los números naturales como un triple $(N,s,0)$ donde $N$ es un objeto, $0:1\to N$ es una de morfismos, y $s:N\to N$ es una de morfismos tales que satisfagan los de segundo orden axiomas de Peano, a saber:

• $s$ es inyectiva (es decir, monic).
• $0$ no está en la imagen de $s$ (es decir, $0$ no puede ser factorizado como una composición $s\circ f$ cualquier $f:1\to N$).
• No subobjeto de $N$ contiene $0$ y es cerrado bajo $s$. Es decir, si $i:A\to N$ es cualquier monic de morfismos tal que $0$ factores a través de $i$ e $s\circ i$ factores a través de $i$, a continuación, $i$ es un isomorfismo.

Para $\mathbf{Set}$, estas propiedades elegir la estructura más habitual de los números naturales (hasta el isomorfismo), y para $\mathbf{Top}$, escoger los números naturales con la topología discreta (prueba: dado cualquier espacio de $N$ con el elemento $0$ y un mapa de $s:N\to N$ la satisfacción de las dos primeras condiciones, el subgrupo generado por a$0$ bajo $s$ se puede dar la topología discreta para conseguir un espacio $A$ y una continua inyección de $i:A\to N$, y, a continuación, la tercera condición implica $i$ es un isomorfismo).

(Un inciso, mientras que estos axiomas de trabajo en $\mathbf{Set}$ o $\mathbf{Top}$, hay otros axiomas de los números naturales, además de los axiomas de Peano, que son más naturales desde una perspectiva categórica, tales como la noción de los números naturales objeto.)

A continuación, podemos arreglar cualquier $(N,s,0)$ y definir un número natural como morfismos $1\to N$. Podemos definir morfismos $+:N\times N\to N$ e $\cdot:N\times N\to N$ como el único morfismos la satisfacción de las habituales definiciones recursivas, y estos dan operaciones binarias en nuestra números naturales, por lo que podemos interpretar de la aritmética en nuestra categoría.