En matemáticas , especialmente en teoría del orden , un conjunto ordenado por prefijo generaliza el concepto intuitivo de árbol al introducir la posibilidad de progreso continuo y ramificación continua. Los órdenes prefijados naturales suelen aparecer cuando se consideran sistemas dinámicos como un conjunto de funciones desde el tiempo (un conjunto totalmente ordenado ) hasta algún espacio de fases . En este caso, los elementos del conjunto suelen denominarse ejecuciones del sistema.
El nombre orden de prefijo proviene del orden de prefijo en 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étrica , transitiva , reflexiva y total hacia abajo , es decir, para todos a , b y c en P , tenemos que:
Mientras que entre órdenes parciales es usual considerar funciones preservadoras de orden , el tipo más importante de funciones entre órdenes de prefijo son las llamadas funciones preservadoras de historia . Dado un conjunto ordenado por prefijo P , una 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 órdenes de prefijo P y Q es entonces preservadora de 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 por prefijo) p + = { q | p ≤ q } y f es preservadora de futuro si para todo p ∈ P encontramos f ( p +) = f ( p )+.
Toda función que preserva la historia y toda función que preserva el futuro también preserva el orden, pero no al revés. En la teoría de sistemas dinámicos, las funciones 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 sobreyecciones que preservan la historia y el futuro capturan la noción de bisimulación entre sistemas y, por lo tanto, la intuición de que un refinamiento dado es correcto con respecto a una especificación.
El rango de una función que preserva la historia es siempre un subconjunto cerrado por prefijo , donde un subconjunto S ⊆ P es cerrado por prefijo si para todo s,t ∈ P con t∈S y s≤t encontramos s∈S .
Tomar los mapas que preservan 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 entrelazamiento arbitrario de los órdenes de prefijo originales. La unión de dos órdenes de prefijo es la unión disjunta , como sucede con los órdenes parciales.
Cualquier función biyectiva que preserva la historia es un isomorfismo de orden . Además, si para un conjunto ordenado por prefijo dado P construimos el conjunto P- ≜ { p- | p∈ P} encontramos que este conjunto está ordenado por prefijo 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 ).