La 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 de dominios puede considerarse como una rama de la teoría del orden . Este 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 de dominios formaliza las ideas intuitivas de aproximación y convergencia de una manera muy general y está estrechamente relacionada con la topología .
La motivación principal para el estudio de dominios, iniciado por Dana Scott a finales de la década de 1960, fue la búsqueda de una semántica denotacional del cálculo lambda . En este formalismo, se consideran "funciones" especificadas por ciertos términos del lenguaje. De una manera puramente sintáctica , se puede pasar de funciones simples a funciones que toman otras funciones como argumentos de entrada. Utilizando nuevamente sólo 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 dicha semántica denotacional, primero se podría intentar construir un modelo para el cálculo lambda, en el que una función genuina (total) esté asociada con cada término lambda. Un modelo así formalizaría un vínculo entre el cálculo lambda como un sistema puramente sintáctico y el cálculo lambda como un sistema de notación para manipular funciones matemáticas concretas. El cálculo combinador es uno de esos modelos. Sin embargo, los elementos del cálculo combinador son funciones de funciones en funciones; Para que los elementos de un modelo del cálculo lambda sean de dominio y rango arbitrarios, no pueden ser funciones verdaderas, sólo funciones parciales .
Scott solucionó esta dificultad formalizando una noción de información "parcial" o "incompleta" para representar cálculos que aún no han arrojado un resultado. Esto se modeló considerando, para cada dominio de cálculo (por ejemplo, los números naturales), un elemento adicional que representa una salida indefinida , es decir, el "resultado" de un cálculo que nunca termina. Además, el dominio de la computación está equipado con una relación de ordenamiento , 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 sólo aquellas funciones (en un conjunto parcialmente ordenado) que garantizan tener menos puntos fijos . El conjunto de estas funciones, junto con un ordenamiento apropiado, es nuevamente 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 contienen sus propios espacios funcionales , es decir, se obtienen funciones que se pueden aplicar a sí mismas.
Además de estas propiedades deseables, la teoría de dominios también permite una interpretación intuitiva atractiva. Como se mencionó anteriormente, los dominios de cálculo siempre están parcialmente ordenados. Este orden representa una jerarquía de información o conocimiento. Cuanto más alto esté un elemento dentro del orden, más específico es y más información contiene. Los elementos inferiores representan conocimientos incompletos o resultados intermedios.
Luego, la computación se modela aplicando funciones monótonas repetidamente sobre elementos del dominio para refinar un resultado. Llegar a un punto fijo equivale a finalizar un cálculo. Los dominios proporcionan un entorno 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.
En esta sección, se introducirán los conceptos centrales y las definiciones de la teoría de dominios. Se enfatizará la intuición anterior de que los dominios son ordenamientos de información 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 también incluyen nociones de teoría del dominio . No obstante, los conceptos más importantes de la teoría de dominios se introducirán a continuación.
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 un cálculo , donde los elementos que están más arriba en el orden extienden la información de los elementos debajo de ellos de manera consistente. A partir de esta simple intuición ya queda 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 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 sobre los dominios, esto significa que dos piezas cualesquiera de información dentro del subconjunto dirigido se amplían consistentemente con algún otro elemento del subconjunto. Por 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 secuencia convergente en 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 secuencias desempeñan un papel que es en muchos aspectos análogo al papel de los conjuntos dirigidos en la teoría de dominios.
Ahora, como en el caso de las sucesiones, nos interesa 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 extiende la información de todos los elementos del conjunto dirigido, es decir, el elemento único que contiene exactamente la información que estaba presente en el conjunto dirigido, y nada mas. En la formalización de la teoría del orden, este es simplemente el límite superior mínimo del conjunto dirigido. Como en el caso del límite de una secuencia, el límite superior mínimo de un conjunto dirigido no siempre existe.
Naturalmente, uno tiene un interés especial en aquellos dominios de cálculo en los que convergen todas las especificaciones consistentes , 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 completas dirigidas , o dcpo para abreviar. De hecho, la mayoría de las consideraciones de la teoría de dominios sólo consideran órdenes que al menos son dirigidas y completas.
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 . Un elemento de este tipo modela ese estado de falta de información, el lugar donde comienzan la mayoría de los cálculos. También puede considerarse como el resultado de un cálculo que no arroja ningún resultado en absoluto.
Ahora que tenemos algunas descripciones formales básicas de lo que debería ser un dominio de computación, podemos pasar a los cálculos en sí. Claramente, estas tienen que ser funciones, que toman entradas de algún dominio computacional y devuelven salidas en algún dominio (posiblemente diferente). Sin embargo, también se esperaría que la salida de una función contuviera más información cuando aumenta 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 es posible que desee 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 dirigida y tiene como límite superior mínimo la imagen del menor límite superior de D . También se podría decir que f conserva la supremacía dirigida . Tenga en cuenta también 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 función continua de Scott . Dado que esto no es a menudo ambiguo, también se puede hablar de funciones continuas .
La teoría de 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 potenciado , 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 considerar el orden estricto inducido < de un dominio con orden ≤. Sin embargo, si bien esta es una noción útil en el caso de pedidos totales, no nos dice mucho en el caso de conjuntos parcialmente ordenados. Considerando nuevamente el orden de inclusión de los conjuntos, un conjunto ya es estrictamente más pequeño que otro conjunto, posiblemente infinito, si contiene sólo un elemento menos. Sin embargo, difícilmente estaríamos de acuerdo en que esto capta 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 de manera más sugerente también se denomina relación de camino a continuación . Un elemento x está muy por debajo de un elemento y , si, para cada conjunto dirigido D con supremo tal que
hay algún elemento d en D tal que
Entonces también se dice que x se aproxima a y y se escribe
Esto implica que
ya que el conjunto singleton { y } está dirigido. 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
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 por sí solo. Por ejemplo, a uno le gustaría caracterizar los conjuntos finitos desde el punto de vista de la teoría 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 ellos mismos, es decir
Un elemento con esta propiedad también se llama compacto . Sin embargo, tales elementos no tienen que ser "finitos" ni "compactos" en ningún otro uso matemático de los términos. No obstante, la notación está motivada por ciertos paralelos con las nociones respectivas en teoría de conjuntos y 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 existan ya.
Muchos otros resultados importantes sobre la relación camino abajo 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 puedan obtenerse 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 aproximarnos a ellos de manera arbitraria.
De manera más general, nos gustaría restringirlo a un determinado subconjunto de elementos como suficiente para obtener todos los demás elementos como mínimo como límites superiores. Por lo tanto, se define una base de un poset P como un subconjunto B de P , de modo 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 x supremo . El poset P es un poset continuo si tiene alguna base. Especialmente, P en sí es una base en esta situación. En muchas aplicaciones, uno se limita a (d)cpos continuos como objeto principal de estudio.
Finalmente, una restricción aún más fuerte sobre un conjunto parcialmente ordenado viene dada al requerir la existencia de una base de elementos finitos . Tal poset se llama algebraico . Desde el punto de vista de la semántica denotacional, los posets algebraicos se comportan particularmente bien, ya que permiten la aproximación de todos los elementos incluso cuando se restringen a los finitos. Como se señaló antes, no todo elemento finito es "finito" en el 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 . En consecuencia, si la base contable consta enteramente de elementos finitos, obtenemos un orden ω-algebraico .
Un caso especial simple de un dominio se conoce como dominio elemental o plano . Este consta de un conjunto de elementos incomparables, como los números enteros, junto con un único elemento "inferior" 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 posets continuos y posets algebraicos. Las versiones más especiales de ambos son cpos continuo y algebraico . Agregando aún más propiedades de completitud se obtienen redes continuas y redes algebraicas , que son simplemente redes completas con las propiedades respectivas. Para el caso algebraico, encontramos clases más amplias de posets que todavía vale la pena estudiar: históricamente, los dominios de Scott fueron las primeras estructuras que se estudiaron en la teoría de dominios. Clases de dominios aún más amplias están constituidas por dominios SFP, dominios L y dominios bifinitos.
Todas estas clases de órdenes se pueden dividir 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í no es exacto y, por lo tanto, sólo se utiliza como abreviatura cuando se ha dado una definición formal antes o cuando los detalles son irrelevantes.
Un poset D es un dcpo si y sólo 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 mínimo fijo, dado como el límite superior mínimo de todas las iteraciones finitas de f en el elemento mínimo ⊥:
Este es el teorema del punto fijo de Kleene . El símbolo es la unión dirigida .
{{cite journal}}: Citar diario requiere |journal=( ayuda )