¿Podemos reconocer cuándo una categoría es equivalente a la categoría de modelos de una teoría de primer orden?

Question

Muchos de los primeros ejemplos canónicos de categorías surgen como la colección de modelos de un primer orden fijo con el concepto de homomorfismo de la teoría de modelos. homomorfismo. Por ejemplo, la categoría de Grupos, la categoría de Anillos y la categoría Conjunto, con sus habituales morfismos, surgen de este modo. En términos más generales, para cualquier teoría de primer orden T en un lenguaje de primer orden L, la colección colección Mod(T) de todos los modelos de T es un foco central de la teoría de modelos, conocido como primaria clase y es naturalmente una categoría con el concepto teórico de modelo de L-homorfismo. Una categoría estrechamente relacionada, que es muy natural en muchos usos teóricos de modelos, tiene los mismos pero requiere que los morfismos sean incrustaciones elementales.

Mi pregunta es:

• ¿Podemos saber, mirando una categoría (viéndola sólo como puntos y flechas), si es equivalente como categoría a Mod(T) para alguna teoría de primer orden T? En otras palabras, ¿es ser Mod(T) un concepto teórico-categorial?

Nótese que Mod(T) no es el mismo concepto que categoría concreta, aunque todo Mod(T) es, por supuesto, concreto.

La pregunta invita a una restricción natural a los lenguajes contables. En este caso, hay algunas condiciones necesarias fáciles en la categoría categoría. El teorema de Lowenheim Skolem muestra que si una teoría teoría en un lenguaje contable tiene un modelo infinito, entonces tiene modelos de cualquier cardinalidad. Así, si Mod(T) es incontable, debe ser una clase propia. Por tanto, si su categoría es incontable, pero no una clase propia, no puede ser Mod(T) para cualquier T contable. Una observación similar se aplica para cualquier cardinal κ sobre el lenguaje, mostrando que si hay al menos κ + muchos objetos en Mod(T), entonces debe haber existir una clase propia de objetos en Mod(T).

Otra restricción surge del concepto de cadena elemental, que nos dice que la categoría debe admitir ciertos límites, si quiere ser Mod(T).

La respuesta ideal sería un criterio necesario y suficiente plenamente teórico de las categorías.

Por último, una versión de juguete de la pregunta se refiere únicamente a las categorías finitas. ¿Qué categorías finitas son equivalentes a Mod(T) para alguna teoría de primer orden T?

Answer 1

Las categorías de modelos con incrustaciones elementales son categorías accesibles . (El cardinal κ está relacionado con el tamaño del lenguaje a través de Löwenheim-Skolem; los objetos κ-presentables, también conocidos como κ-compactos, son modelos de tamaño inferior a κ). Michael Makkai y Bob Paré describieron originalmente esta idea en Categorías accesibles: los fundamentos de la teoría de modelos categoriales (Matemáticas contemporáneas 104, AMS, 1989). Sin embargo, aún se pueden encontrar más en obras posteriores como las de Adámek y Rosický, Categorías localmente presentables y accesibles (LMS Lecture Notes 189, CUP, 1994).

En términos más generales, las clases elementales abstractas también pueden considerarse categorías accesibles. Así, las categorías accesibles incluyen categorías de modelos de teorías infinitas, teorías con cuantificadores generalizados, etc. De hecho, siempre se pueden adjuntar categorías accesibles a tales estructuras, pero no conozco la caracterización exacta de las categorías que surgen de modelos de teorías de la lógica de primer orden. La incrustación de Yoneda puede utilizarse a veces para adjuntar modelos de primer orden a categorías accesibles, como cuando la categoría accesible es fuertemente categórica (Rosický, Categorías accesibles, saturación y categoricidad JSL 62, 1997). Por otra parte, se pueden reformular muchos conceptos de la teoría de modelos en categorías generales accesibles. Hay más de un problema por el camino y no se ha hecho todo, pero cuanto más aprendo, más me doy cuenta de que se trata de una forma muy interesante y poderosa de abordar la teoría de modelos.

---

Intentaré explicar la situación con más detalle. Supongo que las correspondencias se explican mejor en términos de bocetos . (Esta página de nLab necesita ampliarse; Adámek y Rosický ofrecen una buena descripción de los bocetos; puede encontrarse otra descripción en Barr y Wells .) Un esbozo afirma la existencia de ciertos límites y colímites, o sólo límites en el caso de un esbozo de límite, en conjunto estas afirmaciones pueden formularse como una sentencia en L _∞,∞ (detalles incompletos a continuación). Al igual que las oraciones, cada esbozo S tiene una categoría Mod(S) de modelos. Los esbozos y las categorías accesibles van de la mano.

• Si S es un esbozo, entonces Mod(S) es un categoría accesible y toda categoría accesible es equivalente a la categoría de modelos de un esbozo.

• Si S es un esbozo límite, entonces Mod(S) es una categoría localmente presentable y la categoría muy localmente presentable es equivalente a la categoría de modelos de un esbozo límite.

Cuando se traduce a L _∞,∞ un esbozo de límite se convierte en una teoría con axiomas de la forma

$\forall\bar{x}(\phi(\bar{x})\to\exists!\bar{y}\psi(\bar{x},\bar{y})),$

donde $\phi$ y $\psi$ son conjunciones de fórmulas atómicas (y las listas de variables $\bar{x}$ y $\bar{y}$ puede ser infinita). Cuando la categoría es localmente finitamente presentable, entonces estos axiomas pueden enunciarse en L _ω,ω . Las teorías con axiomas de este tipo se caracterizan esencialmente por el hecho de que Mod(T) tiene límites finitos.

• Si T es una teoría en L _ω,ω y Mod(T) que es cerrada bajo límites finitos (computados en Mod(∅)), entonces Mod(T) es categoría localmente finitamente presentable (y por tanto finitamente admisible).

• Toda categoría localmente finitamente presentable es equivalente a una categoría Mod(T) donde T es una teoría límite en L _ω,ω (es decir, con axiomas como los descritos anteriormente).

Es natural conjeturar que esta equivalencia continúa cuando ω se sustituye por ∞. Adámek y Rosický han demostrado en Una observación sobre las teorías accesibles y axiomatizables (Comment. Math. Univ. Carolin. 37, 1996) es que para una completa siendo equivalente a una categoría (completa) de modelos de una frase en L _∞,∞ y ser accesible son equivalentes siempre que se cumpla el Principio de Vopenka. De hecho, esta equivalencia es a su vez equivalente al Principio de Vopenka. (Aparentemente se desconoce si accesible puede reforzarse a localmente presentable).

Ahora bien, si T es una frase en L _∞,∞ entonces la categoría Elem(T) (modelos de T bajo incrustaciones elementales) es siempre una categoría accesible. Lamentablemente, la categoría Mod(T) no es necesariamente accesible. Cuando se traduce a L _∞,∞ los esbozos se convierten en frases de una forma especial. Una fórmula en L _∞,∞ es existencial positiva si tiene la forma

$\bigvee_{i \in I} \exists\bar{y}_i \phi_i(\bar{x},\bar{y}_i)$

donde cada $\phi_i$ es una conjunción de fórmulas atómicas. Una oración básica en L _∞,∞ es la conjunción de frases de la forma

$\forall\bar{x}(\phi(\bar{x})\to\psi(\bar{x}))$

donde $\phi$ y $\psi$ son fórmulas existenciales positivas.

• Una categoría es accesible si y sólo si es equivalente a una categoría Mod(T) donde T es una sentencia básica en L _∞,∞ .

Sería estupendo poder sustituir simplemente accesible por finitamente accesible y sentencia en L _∞,∞ por teoría en L _ω,ω como en el caso localmente presentable anterior. Por desgracia, esto no es cierto. La categoría de modelos de la oración básica $\forall x\exists y(x \mathrel{E} y)$ en el lenguaje de grafos es accesible pero no finitamente accesible. Un contraejemplo en la otra dirección es la categoría de modelos de $\bigvee_{n<\omega} f^{n+1}(a) = f^n(a)$ que es finitamente accesible pero no axiomatizable en L _ω,ω .

Answer 2

Durante mucho tiempo, he estado pensando en esta cuestión para la categoría Mod*(T) de todos los modelos de T con elemental como morfismos (pongo un asterisco para distinguirlo de Mod(T) en la pregunta original). Todavía tengo más conjeturas que respuestas sobre estas categorías, pero puedo decir algunas cosas sobre ellas. Por ejemplo:

Proposición: Si Mod*(T) está "linealmente ordenado" -es decir, para cualesquiera dos M, N en Mod*(T), o bien M es incrustable en N, o viceversa- entonces Mod*(T) debe tener la propiedad Schroeder-Bernstein (cualesquiera dos modelos bi-incrustables son isomorfos).

[Boceto de la prueba: Primero, nótese que T debe ser completo. Por un resultado de Shelah, T debe ser superestable - de lo contrario, una de sus construcciones da que hay muchos pares de modelos "incomparables" ninguno de los cuales puede ser incrustado en el otro. Por algunos otros resultados de Shelah de Teoría de la clasificación, podemos deducir que T debe ser unidimensional (no puede tener un par de tipos regulares ortogonales) y omegaestable. Pero cualquier teoría omega-estable y unidimensional es categórica en aleph_1, y por tanto categórica en cualquier cardinal incontable por el Teorema de Morley. Por el análisis Baldwin-Lachlan de tales teorías, cualquier modelo de T está determinado hasta el isomorfismo por una única "dimensión" cardinal-valorada, y los modelos bi-embeddables deben tener la misma dimensión, QED].

Tengo la fuerte sospecha de que hay algún resultado dicotómico para Mod*(T) (y probablemente también para Mod(T)) que dice que o bien es extremadamente salvaje (por ejemplo, cuando T es inestable) o relativamente "manso" (como cuando T es incontablemente categórico, y Mod*(T) es sólo una gran torre, módulo isomorfismos). Pero no estoy seguro de cuál es la mejor manera de precisar esto.

Como ejemplo del tipo de dicotomía que puede ser cierta: Conjeturo que si Mod*(T) no tiene la propiedad Schroeder-Bernstein, entonces de hecho Mod*(T) contiene una colección infinita de modelos que son bi-embeddable pairwise pero pairwise no isomórficos. Puedo demostrarlo en algunos casos especiales (por ejemplo, cuando T es débilmente mínimo), pero no en general.

Answer 3

No estoy seguro de si esto es exactamente lo que buscas, pero llama a una categoría "logos booleanos" por si tiene límites finitos, los subobjetos de cualquier objeto forman un álgebra booleana bajo inclusión, y el pullback a lo largo de cualquier morfismo induce un homomorfismo de tales álgebras booleanas con adjuntos a izquierda y derecha. [Gran parte de esta definición es redundante, pero no importa]. Las logoses booleanas, los functores entre ellas que preservan toda la estructura definitoria, y las transformaciones naturales arbitrarias entre ellas comprenden una bicategoría, que llamaré BoolLog.

Hasta la equivalencia, las categorías de todos los modelos de alguna teoría en lógica de primer orden clásica multiordenada con igualdad y las incrustaciones elementales entre ellas son precisamente las de la forma BoolLog[B, Set]. Es decir, una categoría C es equivalente a una de la forma Mod*(T) sólo en el caso de que exista algún logos booleano B tal que C sea equivalente a la subcategoría completa de Set^B consistente en aquellos functores que preservan la estructura del logos booleano.

En realidad, esto no es decir mucho (la definición de un logos booleano es una representación categórica muy directa de la definición de la lógica de primer orden clásica multiordenada con igualdad [aunque, como he dicho, podría reducirse un poco. Y, por supuesto, podemos fácilmente ajustar la primera definición un poco para que corresponda a variantes de la segunda (por ejemplo, el caso de orden simple, el caso intuicionista, etc.)]), pero, tal vez tal interpretación categórica es todo lo que estabas buscando (aunque, releyendo la respuesta que diste a mi comentario anterior, sospecho que estabas buscando un tipo diferente de respuesta. En fin).

EDIT: También puedo añadir ahora un resumen de la definición. Otra forma (equivalente) de definir un logos booleano es como una categoría con límites finitos, un derecho adjunto a pullback de subobjetos a lo largo de cualquier morfismo, y un objeto inicial, de tal manera que ciertos mapas construidos a partir de esta estructura tienen inversas (se explica más adelante). La categoría BoolLog tiene esto como celdas 0, funtores que preservan límites finitos, objetos iniciales y adjuntos a la derecha del subobjeto-pullback como celdas 1, y transformaciones naturales arbitrarias como celdas 2; como antes, las Hom-categorías BoolLog[B, Set] son las categorías de modelos de B e incrustaciones elementales entre ellas. El requisito de preservación de los objetos iniciales destruye muchas de las propiedades de completitud/cocompletitud de los modelos que de otro modo habríamos esperado del álgebra universal; por ejemplo, no habrá necesariamente límites finitos de modelos o modelos "libres" (es decir, iniciales).

Hay dos condiciones de isomorfismo para completar esta definición de un logos booleano: 1) los mapas únicos de un objeto inicial a su producto con cualquier otro objeto deben ser isomorfismos [es decir, los productos se distribuyen sobre coproductos 0-arios], y 2) de la estructura anterior se deduce que los subobjetos de cualquier objeto forman un preorden cerrado cartesiano con un objeto inicial. En estos preórdenes, los objetos iniciales deben ser dualizantes [lo que basta para que sean álgebras booleanas].

No he añadido condiciones para obligar a las logosis booleanas a representar teorías completas, pero eso es bastante fácil: esto ocurre sólo en el caso de que los únicos subobjetos del objeto terminal sean los mapas únicos hacia él desde sí mismo y el objeto inicial. Y, por supuesto, la consistencia equivale a pedir que estos dos mapas sean distintos; equivalentemente, la categoría terminal es el logos booleano único que representa una teoría inconsistente.

EDIT2: Whoops, también, en ambas definiciones, se me olvidó añadir la condición de Beck-Chevalley: para cada objeto A, el derecho adjunto al subobjeto pullback a lo largo de la proyección A x - $\rightarrow$ - debería ser una transformación natural (de Sub(A x -) a Sub(-)).

Answer 4

Parece que dicha categoría equivale a una categoría accesible. Véase http://archive.numdam.org/article/DIA_1981__6__A5_0.pdf y también http://www.numdam.org/article/DIA_1982__7__A4_0.pdf