Prefix order

Last updated

In mathematics, especially order theory, a prefix ordered set generalizes the intuitive concept of a tree by introducing the possibility of continuous progress and continuous branching. Natural prefix orders often occur when considering dynamical systems as a set of functions from time (a totally-ordered set) to some phase space. In this case, the elements of the set are usually referred to as executions of the system.

Contents

The name prefix order stems from the prefix order on words, which is a special kind of substring relation and, because of its discrete character, a tree.

Formal definition

A prefix order is a binary relation "≤" over a set P which is antisymmetric, transitive, reflexive, and downward total, i.e., for all a, b, and c in P, we have that:

Functions between prefix orders

While between partial orders it is usual to consider order-preserving functions, the most important type of functions between prefix orders are so-called history preserving functions. Given a prefix ordered set P, a history of a point pP is the (by definition totally ordered) set p = {q | qp}. A function f: PQ between prefix orders P and Q is then history preserving if and only if for every pP we find f(p) = f(p). Similarly, a future of a point pP is the (prefix ordered) set p+ = {q | pq} and f is future preserving if for all pP we find f(p+) = f(p)+.

Every history preserving function and every future preserving function is also order preserving, but not vice versa. In the theory of dynamical systems, history preserving maps capture the intuition that the behavior in one system is a refinement of the behavior in another. Furthermore, functions that are history and future preserving surjections capture the notion of bisimulation between systems, and thus the intuition that a given refinement is correct with respect to a specification.

The range of a history preserving function is always a prefix closed subset, where a subset S ⊆ P is prefix closed if for all s,t ∈ P with t∈S and s≤t we find s∈S.

Product and union

Taking history preserving maps as morphisms in the category of prefix orders leads to a notion of product that is not the Cartesian product of the two orders since the Cartesian product is not always a prefix order. Instead, it leads to an arbitrary interleaving of the original prefix orders. The union of two prefix orders is the disjoint union, as it is with partial orders.

Isomorphism

Any bijective history preserving function is an order isomorphism. Furthermore, if for a given prefix ordered set P we construct the set P- ≜ { p- | p∈ P} we find that this set is prefix ordered by the subset relation ⊆, and furthermore, that the function max: P- → P is an isomorphism, where max(S) returns for each set S∈P- the maximum element in terms of the order on P (i.e. max(p-) ≜ p).

Related Research Articles

In mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain. A binary relation over sets X and Y is a new set of ordered pairs (x, y) consisting of elements x in X and y in Y. It is a generalization of the more widely understood idea of a unary function. It encodes the common concept of relation: an element x is related to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation. A binary relation is the most studied special case n = 2 of an n-ary relation over sets X1, ..., Xn, which is a subset of the Cartesian product

<span class="mw-page-title-main">Equivalence relation</span> Mathematical concept for comparing objects

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equality. Any number a is equal to itself (reflexive). If a = b, then b = a (symmetric). If a = b and b = c, then a = c (transitive).

<span class="mw-page-title-main">Isomorphism</span> In mathematics, invertible homomorphism

In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσοςisos "equal", and μορφήmorphe "form" or "shape".

<span class="mw-page-title-main">Partially ordered set</span> Mathematical set with an ordering

In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.

<span class="mw-page-title-main">Preorder</span> Reflexive and transitive binary relation

In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cases of a preorder: an antisymmetric preorder is a partial order, and a symmetric preorder is an equivalence relation.

In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation on some set , which satisfies the following for all and in :

  1. (reflexive).
  2. If and then (transitive).
  3. If and then (antisymmetric).
  4. or .

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a conditionally complete lattice. Specifically, every non-empty finite lattice is complete. Complete lattices appear in many applications in mathematics and computer science. Being a special instance of lattices, they are studied both in order theory and universal algebra.

In mathematics, equality is a relationship between two quantities or, more generally two mathematical expressions, asserting that the quantities have the same value, or that the expressions represent the same mathematical object. The equality between A and B is written A = B, and pronounced "A equals B". The symbol "=" is called an "equals sign". Two objects that are not equal are said to be distinct.

In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the fundamental theorem of Galois theory about the correspondence between subgroups and subfields, discovered by the French mathematician Évariste Galois.

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics, therefore, excludes topics in "continuous mathematics" such as calculus and analysis.

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

In mathematics, two sets or classes A and B are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from A to B such that for every element y of B, there is exactly one element x of A with f(x) = y. Equinumerous sets are said to have the same cardinality (number of elements). The study of cardinality is often called equinumerosity (equalness-of-number). The terms equipollence (equalness-of-strength) and equipotence (equalness-of-power) are sometimes used instead.

<span class="mw-page-title-main">Cyclic order</span> Alternative mathematical ordering

In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "a < b". One does not say that east is "more clockwise" than west. Instead, a cyclic order is defined as a ternary relation [a, b, c], meaning "after a, one reaches b before c". For example, [June, October, February], but not [June, February, October], cf. picture. A ternary relation is called a cyclic order if it is cyclic, asymmetric, transitive, and connected. Dropping the "connected" requirement results in a partial cyclic order.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

In mathematics, the lexicographic or lexicographical order is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a totally ordered set.

In order theory, a branch of mathematics, an order embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order embeddings constitute a notion which is strictly weaker than the concept of an order isomorphism. Both of these weakenings may be understood in terms of category theory.

<span class="mw-page-title-main">Weak ordering</span> Mathematical ranking of a set

In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered sets and are in turn generalized by (strictly) partially ordered sets and preorders.

This article examines the implementation of mathematical concepts in set theory. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC and in NFU, the version of Quine's New Foundations shown to be consistent by R. B. Jensen in 1969.

In mathematics, a partial order or total order < on a set is said to be dense if, for all and in for which , there is a in such that . That is, for any two elements, one less than the other, there is another element between them. For total orders this can be simplified to "for any two distinct elements, there is another element between them", since all elements of a total order are comparable.

In mathematics, equivalent definitions are used in two somewhat different ways. First, within a particular mathematical theory, a notion may have more than one definition. These definitions are equivalent in the context of a given mathematical structure. Second, a mathematical structure may have more than one definition.

References