Weak ordering

A strict weak order is an order relation, which allows several similar objects, but otherwise defines a unique order.

For example, the relation A costs less than B is a strict weak ordering: Two or more different objects may be the same cost a lot, but otherwise is always clear which object costs less.

Mathematical definition

< A strict weak ordering is a Strict Rules, applies to the additional negative transitivity:

For example, if milk is not less expensive than bread, and bread is not less than cakes, milk will cost not less than cake.

It follows in particular that the relation

Is an equivalence relation. The strict weak ordering it induces a strict total order on the equivalence classes of this relation.

In this example: "A cost no less than B, and B does not cost less than A" is an equivalence relation: " A and B cost the same ." The equivalence classes contain all the products with the same price, and it induced strict total order is simply the order of prices.

Is < beyond a strict total order, the equivalence relation is equality.

The complement of a total quasi-ordering is a strict weak ordering, and vice versa.

The corresponding non- strict relationship is called preference relation (see Preferences ). A preference relation is thus a partial order for which it holds that the relation " x = y or x, y are incomparable " is an equivalence relation. Each strict weak ordering induced (as just described ) a preference relation, and every preference relation induces a strict weak ordering vice versa.

Each strict total ordering is a strict weak ordering. In addition, you can from strict weak ordering according to the following rules more strict weak orders construct:

• If you have a picture, and is defined on the set of the strict weak ordering, as well as the order is a strict weak ordering.

• Funds are subject to strict total ordering. The price is a function of the amount of merchandise reflects on the amount of funds ( every commodity is a sum of money, the price of the goods assigned ). Thus, the corresponding relation is ( costs less than ) a strict weak ordering.
• Also, selecting an element from a tuple is a function. A strict weak ordering on this element thus provides a strict weak ordering on the tuples. Thus one comes from eg the alphabetical order of the names on an order of addresses by name.

• Are weak and strict orders to, so is a strict weak ordering.

Application

The usual sorting methods work not only for total orders, but also for strict weak orders. A distinction is made between stable and unstable sorting method: Change Stable sorting algorithms not the order of equivalent elements when sorting, unstable can change this.

Example: The set of all words, the relation A has fewer letters than B a strict weak ordering. Now Is the unordered list

Dog cat mouse elephant hornbill before, thus providing a stable sorting algorithm for this relation always

Mouse dog cat bird elephant rhino during a sorting algorithm also unstable, for example,

Mouse Dog Bird Cat rhino elephant can deliver.

Other examples

In Newtonian physics, the causal order (time order ) of events forms a strict weak ordering. With regard to the order of time equivalent events are called simultaneously. In relativity theory, this is no longer true.

• Order structure
• Order theory