En matemáticas , especialmente en teoría del orden , un conjunto ordenado con prefijo generaliza el concepto intuitivo de árbol al introducir la posibilidad de progreso continuo y ramificación continua. Los órdenes de prefijos naturales a menudo ocurren cuando se consideran sistemas dinámicos como un conjunto de funciones desde el tiempo (un conjunto totalmente ordenado ) hasta algún espacio de fase . En este caso, a los elementos del conjunto se les suele denominar ejecuciones del sistema.
El orden de los prefijos de los nombres surge del orden de los prefijos de las palabras, que es un tipo especial de relación de subcadena y, debido a su carácter discreto, un árbol.
Un orden de prefijo es una relación binaria "≤" sobre un conjunto P que es antisimétrico , transitivo , reflexivo y total descendente , es decir, para todos a , b y c en P , tenemos que:
Mientras que entre órdenes parciales es habitual considerar funciones que preservan el orden , el tipo más importante de funciones entre órdenes de prefijo son las llamadas funciones que preservan el historial . Dado un conjunto ordenado con prefijo P , la historia de un punto p ∈ P es el conjunto (por definición totalmente ordenado) p − = { q | q ≤ p }. Una función f : P → Q entre los órdenes de prefijo P y Q preserva la historia si y solo si para cada p ∈ P encontramos f ( p −) = f ( p )−. De manera similar, un futuro de un punto p ∈ P es el conjunto (ordenado con prefijo) p + = { q | p ≤ q } y f preserva el futuro si para todo p ∈ P encontramos f ( p +) = f ( p )+.
Cada función de preservación de la historia y cada función de preservación del futuro también preserva el orden, pero no al revés. En la teoría de los sistemas dinámicos, los mapas que preservan la historia capturan la intuición de que el comportamiento en un sistema es un refinamiento del comportamiento en otro. Además, las funciones que son sobrejecciones que preservan la historia y el futuro capturan la noción de bisimulación entre sistemas y, por tanto, la intuición de que un refinamiento dado es correcto con respecto a una especificación.
El rango de una función de preservación de la historia es siempre un subconjunto cerrado con prefijo , donde un subconjunto S ⊆ P tiene un prefijo cerrado si para todo s,t ∈ P con t∈S y s≤t encontramos s∈S .
Tomar mapas de preservación de la historia como morfismos en la categoría de órdenes de prefijo conduce a una noción de producto que no es el producto cartesiano de los dos órdenes, ya que el producto cartesiano no siempre es un orden de prefijo. En cambio, conduce a un entrelazado arbitrario de los órdenes de prefijos originales. La unión de dos órdenes de prefijo es la unión disjunta , como ocurre con las órdenes parciales.
Cualquier función biyectiva que preserve la historia es un isomorfismo de orden . Además, si para un conjunto ordenado con prefijo dado P construimos el conjunto P- ≜ { p- | p∈ P} encontramos que este conjunto es un prefijo ordenado por la relación de subconjunto ⊆, y además, que la función max: P- → P es un isomorfismo, donde max(S) devuelve para cada conjunto S∈P- el elemento máximo en términos del orden en P (es decir, max(p-) ≜ p ).