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 (rankings without ties) and are in turn generalized by (strictly) partially ordered sets and preorders.
There are several common ways of formalizing weak orderings, that are different from each other but cryptomorphic (interconvertable with no loss of information): they may be axiomatized as strict weak orderings (strictly partially ordered sets in which incomparability is a transitive relation), as total preorders (transitive binary relations in which at least one of the two possible relations exists between every pair of elements), or as ordered partitions (partitions of the elements into disjoint subsets, together with a total order on the subsets). In many cases another representation called a preferential arrangement based on a utility function is also possible.
Weak orderings are counted by the ordered Bell numbers. They are used in computer science as part of partition refinement algorithms, and in the C++ Standard Library.
In horse racing, the use of photo finishes has eliminated some, but not all, ties or (as they are called in this context) dead heats, so the outcome of a horse race may be modeled by a weak ordering. In an example from the Maryland Hunt Cup steeplechase in 2007, The Bruce was the clear winner, but two horses Bug River and Lear Charm tied for second place, with the remaining horses farther back; three horses did not finish. In the weak ordering describing this outcome, The Bruce would be first, Bug River and Lear Charm would be ranked after The Bruce but before all the other horses that finished, and the three horses that did not finish would be placed last in the order but tied with each other.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
This seminar teaches the participants to use advanced Python concepts for writing easier to read, more flexible and faster code.
It teaches concepts in a hands-on and tangible fashion, providing examp
Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis
We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring t ...
In mathematics, a homogeneous relation (also called endorelation) on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people. Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations.
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary 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. There are several variants and generalizations of the lexicographical ordering. One variant applies to sequences of different lengths by comparing the lengths of the sequences before considering their elements.
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms, if and are sets and is a relation from to then is the relation defined so that if and only if In set-builder notation, The notation is analogous with that for an inverse function. Although many functions do not have an inverse, every relation does have a unique converse.
We prove an NP upper bound on a theory of integer-indexed integer-valued arrays that extends combi- natory array logic with an ordering relation on the index set and the ability to express sums of elements. We compare our fragment with seven other fragment ...
Interface stress is a fundamental descriptor for interphase boundaries and is defined in strict relation to the interface energy. In nanomultilayers with their intrinsically high interface density, the functional properties are dictated by the interface st ...