Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Weak ordering
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Mathematical ranking of a set}} {{distinguish|Weak order of permutations}} {{stack|{{Binary relations}}}} [[File:WeakOrder4Elements.png|thumb|A weak order on the set <math>\{a, b, c, d\}</math> where <math>b</math> and <math>c</math> are of equal rank, <math>a</math> is ranked below them, and <math>d</math> is ranked above them. <br/>I) representation as a strict weak order <math>\,<\,</math> where <math>x < y</math> is shown as an arrow from <math>x</math> to <math>y</math>; <br/>II) representation as a total preorder <math>\,\leq\,</math>, shown using arrows; <br/>III) representation as an ordered partition, with the sets of the partition as dotted ellipses and the total order on these sets shown with arrows.]] [[Image:13-Weak-Orders.svg|thumb|The 13 possible strict weak orderings on a set of three elements <math>\{a, b, c\}.</math> The only [[total order]]s are shown in black. Two orderings are connected by an edge if they differ by a single dichotomy.]] In [[mathematics]], especially [[order theory]], a '''weak ordering''' is a mathematical formalization of the intuitive notion of a [[ranking]] of a [[set (mathematics)|set]], some of whose members may be [[Tie (draw)|tied]] with each other. Weak orders are a generalization of [[totally ordered set]]s (rankings without ties) and are in turn generalized by (strictly) [[partially ordered set]]s and [[preorder]]s.<ref name="fr11">{{citation|title=Applied Combinatorics|first1=Fred|last1=Roberts|first2=Barry|last2=Tesman|edition=2nd|publisher=CRC Press|year=2011|isbn=9781420099836|at=Section 4.2.4 Weak Orders, pp. 254β256}}.</ref> There are several common ways of formalizing weak orderings, that are different from each other but [[Cryptomorphism|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''' ([[partition of a set|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 number]]s. They are used in [[computer science]] as part of [[partition refinement]] algorithms, and in the [[C++ Standard Library]].<ref name="cpp">{{citation|title=The C++ Standard Library: A Tutorial and Reference|first=Nicolai M.|last=Josuttis|publisher=Addison-Wesley|year=2012|isbn=9780132977739|url=https://books.google.com/books?id=9DEJKhasp7gC&pg=PT469|page=469}}.</ref>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)