Teoría del dominio

Teoría de dominios es una rama de las matemáticas que estudia tipos especiales de conjuntos parcialmente ordenados (posets) comúnmente llamados dominios. En consecuencia, la teoría del dominio puede considerarse como una rama de la teoría del orden. El campo tiene importantes aplicaciones en informática, donde se utiliza para especificar la semántica denotacional, especialmente para lenguajes de programación funcionales. La teoría del dominio formaliza las ideas intuitivas de aproximación y convergencia de una manera muy general y está estrechamente relacionada con la topología.

Motivación e intuición

La principal motivación para el estudio de los dominios, que fue iniciado por Dana Scott a fines de la década de 1960, fue la búsqueda de una semántica denotacional del cálculo lambda. En este formalismo, uno considera "funciones" especificado por ciertos términos en el lenguaje. De una manera puramente sintáctica, se puede pasar de funciones simples a funciones que toman otras funciones como argumentos de entrada. Usando nuevamente solo las transformaciones sintácticas disponibles en este formalismo, se pueden obtener los llamados combinadores de punto fijo (el más conocido de los cuales es el combinador Y); estos, por definición, tienen la propiedad de que f(Y(f)) = Y( f) para todas las funciones f.

Para formular una semántica denotacional de este tipo, primero se podría intentar construir un modelo para el cálculo lambda, en el que se asocia una función genuina (total) con cada término lambda. Tal modelo formalizaría un vínculo entre el cálculo lambda como un sistema puramente sintáctico y el cálculo lambda como un sistema notacional para manipular funciones matemáticas concretas. El cálculo combinador es un modelo de este tipo. Sin embargo, los elementos del cálculo combinador son funciones de funciones a funciones; para que los elementos de un modelo del cálculo lambda sean de dominio y rango arbitrarios, no pueden ser funciones verdaderas, solo funciones parciales.

Scott superó esta dificultad al formalizar una noción de "parcial" o "incompleto" información para representar cálculos que aún no han devuelto un resultado. Esto se modeló considerando, para cada dominio de computación (por ejemplo, los números naturales), un elemento adicional que representa una salida indefinida, es decir, el "resultado" de un cómputo que nunca termina. Además, el dominio de computación está equipado con una relación de orden, en la que el "resultado indefinido" es el elemento mínimo.

El paso importante para encontrar un modelo para el cálculo lambda es considerar solo aquellas funciones (en un conjunto parcialmente ordenado) que se garantiza que tienen menos puntos fijos. El conjunto de estas funciones, junto con un ordenamiento adecuado, vuelve a ser un "dominio" en el sentido de la teoría. Pero la restricción a un subconjunto de todas las funciones disponibles tiene otro gran beneficio: es posible obtener dominios que contengan sus propios espacios de funciones, es decir, se obtienen funciones que se pueden aplicar a sí mismas.

Además de estas propiedades deseables, la teoría del dominio también permite una interpretación intuitiva atractiva. Como se mencionó anteriormente, los dominios de computación siempre están parcialmente ordenados. Este orden representa una jerarquía de información o conocimiento. Cuanto más arriba está un elemento dentro de la orden, más específico es y más información contiene. Los elementos inferiores representan conocimientos incompletos o resultados intermedios.

La computación luego se modela aplicando funciones monótonas repetidamente en elementos del dominio para refinar un resultado. Llegar a un punto fijo equivale a terminar un cálculo. Los dominios proporcionan una configuración superior para estas ideas, ya que se puede garantizar la existencia de puntos fijos de funciones monótonas y, bajo restricciones adicionales, se pueden aproximar desde abajo.

Una guía para las definiciones formales

En esta sección, se presentarán los conceptos centrales y las definiciones de la teoría del dominio. La intuición anterior de que los dominios son ordenamientos de información se enfatizará para motivar la formalización matemática de la teoría. Las definiciones formales precisas se encuentran en los artículos dedicados a cada concepto. En el glosario de teoría del orden se puede encontrar una lista de definiciones generales de la teoría del orden, que incluyen también nociones de la teoría del dominio. No obstante, los conceptos más importantes de la teoría del dominio se presentarán a continuación.

Conjuntos dirigidos como especificaciones convergentes

Como se mencionó anteriormente, la teoría del dominio trata con conjuntos parcialmente ordenados para modelar un dominio de computación. El objetivo es interpretar los elementos de tal orden como piezas de información o resultados (parciales) de un cálculo, donde los elementos que están más arriba en el orden amplían la información de los elementos debajo de ellos de manera consistente. De esta simple intuición ya está claro que los dominios a menudo no tienen un elemento mayor, ya que esto significaría que hay un elemento que contiene la información de todos los demás elementos, una situación bastante poco interesante.

Un concepto que juega un papel importante 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 dos elementos cualesquiera tienen un límite superior que es un elemento de este subconjunto. En vista de nuestra intuición acerca de los dominios, esto significa que dos piezas cualesquiera de información dentro del subconjunto dirigido son consistentemente extendidas por algún otro elemento en el subconjunto. Por lo tanto, podemos ver los subconjuntos dirigidos como especificaciones consistentes, es decir, como conjuntos de resultados parciales en los que no hay dos elementos contradictorios. Esta interpretación se puede comparar con la noción de una secuencia convergente en el análisis, donde cada elemento es más específico que el anterior. De hecho, en la teoría de los espacios métricos, las sucesiones juegan un papel que es en muchos aspectos análogo al papel de los conjuntos dirigidos en la teoría del dominio.

Ahora, como en el caso de las sucesiones, estamos interesados en el límite de un conjunto dirigido. Según lo dicho anteriormente, este sería un elemento que es la información más general que amplía la información de todos los elementos del conjunto dirigido, es decir, el único elemento que contiene exactamente la información que fue presente en el conjunto dirigido, y nada más. En la formalización de la teoría del orden, este es solo el límite superior mínimo del conjunto dirigido. Como en el caso del límite de una sucesión, la cota superior mínima de un conjunto dirigido no siempre existe.

Naturalmente, uno tiene un interés especial en aquellos dominios de computación en los que todas las especificaciones consistentes convergen, es decir, en órdenes en los que todos los conjuntos dirigidos tienen un límite superior mínimo. Esta propiedad define la clase de órdenes parciales dirigidas-completas, o dcpo para abreviar. De hecho, la mayoría de las consideraciones de la teoría del dominio solo consideran órdenes que al menos están dirigidas completas.

De la idea subyacente de que los resultados parcialmente especificados representan un conocimiento incompleto, se deriva otra propiedad deseable: la existencia de un menor elemento. Tal elemento modela ese estado sin información, el lugar donde comienzan la mayoría de los cálculos. También se puede considerar como la salida de un cálculo que no arroja ningún resultado.

Cálculos y dominios

Ahora que tenemos algunas descripciones formales básicas de lo que debería ser un dominio de cómputo, podemos pasar a los cómputos mismos. Claramente, estas tienen que ser funciones, tomando entradas de algún dominio computacional y devolviendo salidas en algún dominio (posiblemente diferente). Sin embargo, uno también esperaría que la salida de una función contenga más información cuando se incrementa el contenido de información de la entrada. Formalmente, esto significa que queremos que una función sea monótona.

Cuando se trata de dcpos, también se puede desear 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) está nuevamente dirigido y tiene como límite superior mínimo la imagen del límite superior mínimo de D. También se podría decir que f preserva la supremacía dirigida. También tenga en cuenta que, al considerar conjuntos dirigidos de dos elementos, dicha función también tiene que ser monótona. Estas propiedades dan lugar a la noción de una función Scott-continua. Dado que esto a menudo no es ambiguo, también se puede hablar de funciones continuas.

Aproximación y finitud

La teoría del dominio 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, hay algunas situaciones en las que uno quiere hablar de elementos que son, en cierto sentido, mucho más simples (o mucho más incompletos) que un estado dado de información. Por ejemplo, en el orden natural de inclusión de subconjuntos en algún conjunto potencia, cualquier elemento infinito (es decir, conjunto) es mucho más "informativo" que cualquiera de sus subconjuntos finitos.

Si uno quiere modelar tal relación, primero puede querer considerar el orden estricto inducido < de un dominio con orden ≤. Sin embargo, mientras que esta es una noción útil en el caso de órdenes totales, no nos dice mucho en el caso de conjuntos parcialmente ordenados. Considerando nuevamente los órdenes de inclusión de conjuntos, un conjunto ya es estrictamente más pequeño que otro conjunto, posiblemente infinito, si contiene solo un elemento menos. Sin embargo, uno difícilmente estaría de acuerdo en que esto captura la noción de ser "mucho más simple".

Relación muy por debajo

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

Sí.⊑ ⊑ SupD{displaystyle ysqsubseteq sup D},

hay algún elemento d en D tal que

x⊑ ⊑ d{displaystyle xsqsubseteq d}.

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

x≪ ≪ Sí.{displaystyle xll y}.

Esto implica que

x⊑ ⊑ Sí.{displaystyle xsqsubseteq y},

ya que se dirige el conjunto singleton {y}. Por ejemplo, en una ordenación de conjuntos, un conjunto infinito está muy por encima de cualquiera de sus subconjuntos finitos. Por otro lado, considere el conjunto dirigido (de hecho, la cadena) de conjuntos finitos

{}0},{}0,1},{}0,1,2},...... {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 muestra 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 solo. Por ejemplo, a uno le gustaría caracterizar los conjuntos finitos en una forma teórica de 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 ellos mismos, es decir

x≪ ≪ x{displaystyle xll x}.

Un elemento con esta propiedad también se llama compacto. Sin embargo, tales elementos no tienen que ser "finitos" ni "compacto" en cualquier otro uso matemático de los términos. No obstante, la notación está motivada por ciertos paralelismos con las nociones respectivas en la teoría de conjuntos y la topología. Los elementos compactos de un dominio tienen la importante propiedad especial de que no pueden obtenerse como límite de un conjunto dirigido en el que no se encuentran ya.

Muchos otros resultados importantes sobre la relación way-below respaldan la afirmación de que esta definición es apropiada para capturar muchos aspectos importantes de un dominio.

Bases de dominios

Los pensamientos 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 aún podemos esperar aproximarlos arbitrariamente.

De manera más general, nos gustaría restringirnos a un cierto subconjunto de elementos como suficiente para obtener todos los demás elementos como límites mínimos superiores. Por 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. La pose P es una pose continua si tiene alguna base. Especialmente, P en sí mismo es una base en esta situación. En muchas aplicaciones, uno se restringe a (d)cpos continuos como principal objeto de estudio.

Finalmente, se da una restricción aún más fuerte en un conjunto parcialmente ordenado al requerir la existencia de una base de elementos finitos. Tal poset se llama algebraica. Desde el punto de vista de la semántica denotacional, las posets algebraicas se comportan particularmente bien, ya que permiten la aproximación de todos los elementos incluso cuando se restringen a elementos finitos. Como se comentó anteriormente, no todos los elementos finitos son "finitos" en un sentido clásico y bien puede ser que los elementos finitos constituyan un conjunto incontable.

En algunos casos, sin embargo, la base de un poset es contable. En este caso, se habla de un poset ω-continuo. Por tanto, si la base contable está formada íntegramente por elementos finitos, obtenemos un orden ω-algebraico.

Tipos especiales de dominios

Un caso especial simple de un dominio se conoce como elemental o dominio plano. Este consta de un conjunto de elementos incomparables, como los números enteros, junto con un único elemento "bottom" elemento considerado más pequeño que todos los demás elementos.

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

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

Resultados importantes

Un poset D es un dcpo si y solo si cada cadena en D tiene un supremo. (La dirección 'si' se basa en el axioma de elección).

Si f es una función continua en un dominio D entonces tiene un punto fijo mínimo, dado como el límite superior mínimo de todas las iteraciones finitas de f en el elemento mínimo ⊥:

arreglar⁡ ⁡ ()f)=⨆ ⨆ n▪ ▪ Nfn()⊥ ⊥ ){displaystyle operatorname {fix} (f)=bigsqcup _{nin mathbb {N}f^{n}(bot)}.

Este es el teorema de punto fijo Kleene. El ⊔ ⊔ {displaystyle sqcup } símbolo es la unión dirigida.

Generalizaciones

• "Teoría de dominio sintética". CiteSeerX10.1.1.55.903. {{cite journal}}: Cite journal requires |journal= (Ayuda)
• Teoría de dominio Topológica
• Un espacio de continuidad es una generalización de espacios métricos y poses que se pueden utilizar para unificar las nociones de espacios métricos y dominios.