Order theory

In mathematics, order relations are generalizations of the " less than or equal " relationship. They allow us to compare elements of a set together.

An order relation is formally a binary relation

On a set M with certain properties listed below, by which is always the transitivity.

Is a set M given with an order relation R, then it is called the pair is an ordered set. Usually one prefers the so-called infix notation instead of the notation. In addition, an icon as used for ordering relations in the rarest of cases. Instead, one often uses the symbol "" or similar symbols. The notation is used as an abbreviation for " and". This proves to be useful because mostly apply to relations calculation rules that correspond to those in ( with his usual "").

The following is a list of different types of order relations with examples. For definitions of the properties see transitive, reflexive and irreflexive, asymmetric, antisymmetric or the item relation ( mathematics).

Total ordering

An order is called totally if the following properties are satisfied:

• Is transitive, that is,
• Is reflexive, that is,
• Is antisymmetric, that is,
• Is total, that is,

A total order on a set provides an array of elements in a particular order, for example, the arrangement of the letters A to Z in the Latin alphabet or the linear array of real numbers.

One therefore refers to the total order as order or linear order. The term linear is based on the idea that the whole lot in a sequence similar to enumerate the real numbers. Therefore, the term chain for a totally ordered set is derived.

An example of the relation ( " less than" ) in the whole numbers. An opposite example is the subset relation on the power set of: it is not total, because it is neither.

Strict total ordering

An order is called strict total order if the following applies;

• Is transitive
• Is trichotomisch, that is,

Since a strict total ordering is not reflexive, it is not a total ordering. However, a total ordering in the sense explained above is to the associated partial order

With the help of the axiom of choice one can prove that any partial order can be embedded into a total ordering. For finite sets, the axiom of choice one must not assume, and in this case it is for the construction of such total ordering and explicit algorithms (see topological sorting ).

Quasi-ordering

A quasi-ordering is transitive and reflexive.

Example:

For complex numbers, the information about the absolute amount by fixed relation is a quasi-ordering.

This quasi-ordering is not anti- symmetric - so no partial order, because amount equal numbers need not be identical.

However, there is a total quasi-ordering, since each 2 elements are comparable.

Partial order

A partial ordering - also called partial ordering, partial ordering or partial order - is transitive, reflexive and antisymmetric. Partially ordered sets can be visualized in a Hasse diagrams. A subset of a partially ordered set is called Above quantity when each of its elements and all subsequent elements ( that is, all that might be the right of the relation symbol ) includes.

Examples:

Each subset relationship on a system of sets is a partial order, because it is

• Transitive because the subset of a subset of A and A is a subset of:

• Reflexive, because a lot of their own is a subset:

• And anti- symmetric since only A itself both subset and superset of A is:

Other examples are the component-wise relation - less - or - equal in a space of n- tuples and the splitter line between the natural numbers, which are defined as follows:

Further application of the partial order

To measure the degree of Pre-sorted awareness a lot, you can specify the number of possible continuations of a partial order to a linear order. For example, if the ordered set with and, if so there are three possible continuations: , and. The degree of Pre-sorted is therefore done in this case. After the efficient comparison theorem are for complete sorting of presorted amount then only comparisons required. In computer science, for example, uses the sorting procedure mergesort this property.

The minimum, maximum, and other items

Let T be a subset of a partially ordered set P.

If m in T has the property that it is with no x in T, then m is called minimal element of T. If there is an element m in T, that is all the other elements of T, then m is called the smallest element of T. A least element of T ( if there is, for example, the set of integers not a least element ) is always uniquely determined (because of anti-symmetry ) and of course minimal. In a total ordering " least element " and " minimal element " means the same thing, but in general partial orders may have a lot more minimal elements, none of which is the smallest then.

It may even happen that an ( infinite) set T does have a single minimal element, but this is not the smallest element of the set ( then T has no smallest element ). example:

If T is a subset of P and P to P has the property that for all t in T, the relationship p ≤ T holds, then P is a lower limit for T. (p may or may not be an element of T. ) If there is a greatest lower bound of the set T, then we call this the lower limit or the infimum of T. a lower bound is therefore less than or equal to the infimum.

The terms maximal element, greatest element, upper bound and upper bound or supremum are defined analogously.

A lot of that both an upper and a lower bound has to say, limited. ( Analogously, " bounded from above " and defines " bounded from below ". )

We call a function f which an arbitrary set X in a semi - or totally ordered set (see below) P maps, limited, if the set of function values ​​is limited, so if there is a p and q in P are such that for all x in x

Applies.

Locally finite partially ordered set

A partially ordered set is called locally finite if every interval is a finite set.

Strict Rules

A strict order or Strict order is transitive and asymmetric. The term asymmetry summarizes the terms irreflexivity and antisymmetry together. Irreflexivity distinguishes the strictness order of the partial order, and means that no element is related to itself. A Strict order is therefore transitive, irreflexive and antisymmetric

Examples:

• The relation " ( really ) small " on
• The relation " True subset " in a power set
• The relation " componentwise smaller, but not" on the vector space.

Strict weak ordering

A strict weak ordering R is a strictly order applies to the additional negative transitivity:

A strict weak ordering is a total quasi-ordering complementary and vice versa.

Inductive order

A partially ordered set is called inductively ordered if every linearly ordered subset of A has an upper bound. It is called strictly inductively ordered if every linearly ordered subset has a least upper bound.

By the lemma of Zorn has every inductive ordered set a maximal element.

Founded ordering

A well-founded order is a partial order, where there is no infinite, truly are descending chains ( or, equivalently formulated: in every non-empty subset has a minimal element ). For example, the divisibility relation | between natural numbers.

Well- quasi-ordering

A well- quasi-ordering is a quasi-ordering with the property that there are to each episode two natural numbers, such that.

Well-ordering

A well-ordering is a total order in which each non-empty subset has a least element. A few examples:

• " Less than or equal " on the natural numbers.
• The integers with the order 0 < 1 < -1 <2 < -2 <3 < -3 <. ...
• The integers with the order 0 <1 <2 < 3 <. .. < -1 < -2 < -3 <. ...

The well-ordering theorem guarantees the existence of a well-ordering for any amount, for example, for the real numbers. He is the axiom of choice are equivalent.

Tree

A tree is a partially ordered set in which is well ordered for each the set of predecessors.

Association Rules

An association order is a partial order in which it v and w are any two elements always a supremum and an infimum.

Through each association order the algebraic structure of an association is given in which one defines v and w for each two elements:

Conversely, by in each dressing

Define for any two elements v and w is an association order so that

A combined ordered set is therefore often called association, but she herself is in contrast to the association no algebraic structure.

Complete partial order

A complete partial order ( engl. complete partial order, cpo) is a partial order with a least element and the property that every subset that forms an ascending chain has a supremum. The supremum need not lie in the subset in yourself.

In a directed complete partial order ( engl. directed complete partial order, DCPO ) must, in contrast to the complete partial order is the empty set do not have a supremum. There must therefore be no smallest element.

These two completeness notions play a role in evidence with the help of the lemma of Zorn. To distinguish → Of is the ajar to the topology concept system completeness.

Homomorphisms

Be and minor amounts. A mapping is called isotonic, order-preserving, order-preserving or Ordnungshomomorphismus if applies.

Use of the terms

The authors use the term "order" in different ways. It can denote a partial order or a total order. Probably induced by the polarities "half" and " total", one thus finds often the demarcation

Or