teoría de dominios

Como se mencionó anteriormente, la teoría de dominios se ocupa de conjuntos parcialmente ordenados para modelar un dominio de computación. El objetivo es interpretar los elementos de dicho orden como piezas de información o resultados (parciales) de una computación , donde los elementos de mayor orden extienden la información de los elementos inferiores de manera consistente. A partir de esta simple intuición, resulta evidente que los dominios a menudo no tienen un elemento máximo , ya que esto implicaría que existe un elemento que contiene la información de todos los demás, una situación poco interesante.

Un concepto fundamental en la teoría es el de subconjunto dirigido de un dominio; un subconjunto dirigido es un subconjunto no vacío del orden en el que cualesquiera dos elementos tienen una cota superior que pertenece a dicho subconjunto. Desde nuestra intuición sobre los dominios, esto significa que cualesquiera dos datos dentro del subconjunto dirigido se extienden de forma consistente mediante algún otro elemento del mismo. Por lo tanto, podemos considerar los subconjuntos dirigidos como especificaciones consistentes , es decir, como conjuntos de resultados parciales en los que no existen dos elementos contradictorios. Esta interpretación se puede comparar con la noción de sucesión convergente en análisis , donde cada elemento es más específico que el anterior. De hecho, en la teoría de espacios métricos , las sucesiones desempeñan un papel que, en muchos aspectos, es análogo al de los conjuntos dirigidos en la teoría de dominios.

Ahora bien, al igual que en el caso de las secuencias, nos interesa el límite de un conjunto dirigido. Según lo expuesto anteriormente, este sería un elemento que representa la información más general que extiende la información de todos los elementos del conjunto dirigido; es decir, el único elemento que contiene exactamente la información presente en el conjunto dirigido, y nada más. En la formalización de la teoría del orden, esto se denomina simplemente cota superior mínima del conjunto dirigido. Al igual que en el caso del límite de una secuencia, la cota superior mínima de un conjunto dirigido no siempre existe.

Naturalmente, existe un interés especial en aquellos dominios de computación en los que convergen todas las especificaciones consistentes , es decir, en los órdenes en los que todos los conjuntos dirigidos tienen una cota superior mínima. Esta propiedad define la clase de órdenes parciales dirigidos completos , o dcpo por sus siglas en inglés. De hecho, la mayoría de los estudios de teoría de dominios solo consideran órdenes que son al menos dirigidos completos.

Partiendo de la idea subyacente de que los resultados parcialmente especificados representan conocimiento incompleto, se deriva otra propiedad deseable: la existencia de un elemento mínimo . Dicho elemento modela el estado de ausencia de información, punto de partida de la mayoría de los cálculos. También puede considerarse como el resultado de un cálculo que no devuelve ningún resultado.

Ahora que tenemos algunas descripciones formales básicas de lo que debe ser un dominio de computación, podemos pasar a las computaciones en sí. Claramente, estas deben ser funciones que toman entradas de algún dominio de computación y devuelven salidas en algún dominio (posiblemente diferente). Sin embargo, también se esperaría que la salida de una función contenga más información cuando aumenta el contenido informativo de la entrada. Formalmente, esto significa que queremos que una función sea monótona .

Al trabajar con dcpos , también se busca que los cálculos sean compatibles con la formación de límites de un conjunto dirigido. Formalmente, esto significa que, para alguna función f , la imagen f ( D ) de un conjunto dirigido D (es decir, el conjunto de las imágenes de cada elemento de D ) es nuevamente dirigida y tiene como cota superior mínima la imagen de la cota superior mínima de D. También se podría decir que f preserva los supremos dirigidos . Cabe señalar que, al considerar conjuntos dirigidos de dos elementos, dicha función también debe ser monótona. Estas propiedades dan lugar a la noción de función continua de Scott . Dado que esto a menudo no es ambiguo, también se puede hablar de funciones continuas .

La teoría de dominios es un enfoque puramente cualitativo para modelar la estructura de los estados de información. Se puede decir que algo contiene más información, pero no se especifica la cantidad de información adicional. Sin embargo, existen situaciones en las que se desea hablar de elementos que, en cierto sentido, son mucho más simples (o mucho más incompletos) que un estado de información dado. Por ejemplo, en el orden de inclusión de subconjuntos natural en algún conjunto potencia , cualquier elemento infinito (es decir, conjunto) es mucho más "informativo" que cualquiera de sus subconjuntos finitos .

Si se desea modelar dicha relación, se podría considerar primero el orden estricto inducido < de un dominio con orden ≤. Sin embargo, si bien esta noción es útil en el caso de órdenes totales, no aporta mucha información en el caso de conjuntos parcialmente ordenados. Retomando los órdenes de inclusión de conjuntos, un conjunto es estrictamente menor que otro, posiblemente infinito, si contiene tan solo un elemento menos. No obstante, difícilmente se estaría de acuerdo en que esto capture la noción de ser "mucho más simple".

Un enfoque más elaborado conduce a la definición del llamado orden de aproximación , que también se denomina de manera más sugerente la relación de muy por debajo . Un elemento x está muy por debajo de un elemento y si, para todo conjunto dirigido D con supremo tal que

$${\displaystyle y\sqsubseteq \sup D,}$$

existe algún elemento d en D tal que

$${\displaystyle x\sqsubseteq d.}$$

Entonces uno también dice que x se aproxima a y y escribe

$${\displaystyle x\ll y.}$$

Esto implica que

$${\displaystyle x\sqsubseteteq y,}$$

ya que el conjunto unitario { y } es dirigido. Por ejemplo, en un ordenamiento de conjuntos, un conjunto infinito está muy por encima de cualquiera de sus subconjuntos finitos. Por otro lado, consideremos el conjunto dirigido (de hecho, la cadena ) de conjuntos finitos.

$${\displaystyle \{0\},\{0,1\},\{0,1,2\},\ldots }$$

Dado que el supremo de esta cadena es el conjunto de todos los números naturales N , esto demuestra que ningún conjunto infinito está muy por debajo de N.

Sin embargo, estar muy por debajo de algún elemento es una noción relativa y no revela mucho sobre un elemento en sí mismo. Por ejemplo, uno querría caracterizar conjuntos finitos de una manera teórica del orden, pero incluso los conjuntos infinitos pueden estar muy por debajo de algún otro conjunto. La propiedad especial de estos elementos finitos x es que están muy por debajo de sí mismos, es decir

$${\displaystyle x\ll x}$$

Un elemento con esta propiedad también se denomina compacto . Sin embargo, dichos elementos no tienen por qué ser «finitos» ni «compactos» en ningún otro uso matemático de los términos. No obstante, la notación se basa en ciertos paralelismos con las nociones correspondientes en la teoría de conjuntos y la topología . Los elementos compactos de un dominio poseen la importante propiedad especial de que no pueden obtenerse como límite de un conjunto dirigido en el que no aparecieran previamente.

Muchos otros resultados importantes sobre la relación de "muy por debajo" respaldan la afirmación de que esta definición es apropiada para capturar muchos aspectos importantes de un dominio.

Las reflexiones anteriores plantean otra pregunta: ¿es posible garantizar que todos los elementos de un dominio se puedan obtener como límite de elementos mucho más simples? Esto es bastante relevante en la práctica, ya que no podemos calcular objetos infinitos, pero aun así podemos aproximarlos con una precisión arbitraria.

En términos más generales, nos gustaría restringirnos a un subconjunto determinado de elementos como suficiente para obtener todos los demás elementos como cotas superiores mínimas. Por lo tanto, se define una base de un poset P como un subconjunto B de P , tal que, para cada x en P , el conjunto de elementos en B que están muy por debajo de x contiene un conjunto dirigido con supremo x . El poset P es un poset continuo si tiene alguna base. En particular, P mismo es una base en esta situación. En muchas aplicaciones, uno se restringe a los poset continuos (d)cpos como objeto principal de estudio.

Finalmente, una restricción aún más fuerte sobre un conjunto parcialmente ordenado viene dada por la exigencia de la existencia de una base de elementos finitos . Dicho conjunto parcialmente ordenado se denomina algebraico . Desde el punto de vista de la semántica denotacional, los conjuntos parcialmente ordenados algebraicos se comportan particularmente bien, ya que permiten la aproximación de todos los elementos incluso cuando se restringen a los finitos. Como se mencionó anteriormente, no todo elemento finito es "finito" en el sentido clásico y bien podría ser que los elementos finitos constituyan un conjunto no numerable .

En algunos casos, sin embargo, la base de un poset es numerable . En este caso, se habla de un poset ω-continuo . Por consiguiente, si la base numerable consta enteramente de elementos finitos, obtenemos un orden que es ω-algebraico .

Un caso especial y sencillo de dominio se conoce como dominio elemental o plano . Este consiste en un conjunto de elementos incomparables, como los números enteros, junto con un único elemento "inferior" considerado menor que todos los demás.

Se pueden obtener otras clases especiales interesantes de estructuras ordenadas que podrían ser adecuadas como "dominios". Ya mencionamos los posets continuos y los posets algebraicos. Versiones más especiales de ambos son los cpos continuos y algebraicos . Añadiendo aún más propiedades de completitud se obtienen retículos continuos y retículos algebraicos , que son simplemente retículos completos con las propiedades respectivas. Para el caso algebraico, se encuentran clases más amplias de posets que aún merecen ser estudiadas: históricamente, los dominios de Scott fueron las primeras estructuras estudiadas en la teoría de dominios. Clases aún más amplias de dominios están constituidas por los dominios SFP , los dominios L y los dominios bifinitos .

Todas estas clases de órdenes pueden clasificarse en diversas categorías de dcpos, utilizando funciones monótonas, continuas de Scott o incluso más especializadas como morfismos . Finalmente, cabe señalar que el término dominio no es exacto y, por lo tanto, solo se utiliza como abreviatura cuando se ha dado una definición formal previamente o cuando los detalles son irrelevantes.