Total order

















In mathematics, a linear order, total order, simple order, or (non-strict) ordering is a binary relation on some set X{displaystyle X}X, which is antisymmetric, transitive, and a connex relation. A set paired with a total order is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain.


Formally, a binary relation ≤{displaystyle leq }leq is a total order on a set X{displaystyle X}X if the following statements hold for all a,b{displaystyle a,b}a,b and c{displaystyle c}c in X{displaystyle X}X:



If a≤b{displaystyle aleq b}aleq b and b≤a{displaystyle bleq a}{displaystyle bleq a} then a=b{displaystyle a=b}a=b (antisymmetry);

If a≤b{displaystyle aleq b}aleq b and b≤c{displaystyle bleq c}{displaystyle bleq c} then a≤c{displaystyle aleq c}{displaystyle aleq c} (transitivity);


a≤b{displaystyle aleq b}aleq b or b≤a{displaystyle bleq a}{displaystyle bleq a} (connex property).


Antisymmetry eliminates uncertain cases when both a{displaystyle a}a precedes b{displaystyle b}b and b{displaystyle b}b precedes a{displaystyle a}a.[1] A relation having the "connex" property means that any pair of elements in the set of the relation are comparable under the relation. This also means that the set can be diagrammed as a line of elements, giving it the name linear.[2] The connex property also implies reflexivity, i.e., a ≤ a. Therefore, a total order is also a (special case of a) partial order, as, for a partial order, the connex property is replaced by the weaker reflexivity property. An extension of a given partial order to a total order is called a linear extension of that partial order.




Contents






  • 1 Strict total order


  • 2 Examples


  • 3 Further concepts


    • 3.1 Chains


    • 3.2 Lattice theory


    • 3.3 Finite total orders


    • 3.4 Category theory


    • 3.5 Order topology


    • 3.6 Completeness


    • 3.7 Sums of orders




  • 4 Orders on the Cartesian product of totally ordered sets


  • 5 Related structures


  • 6 See also


  • 7 Notes


  • 8 References


  • 9 External links





Strict total order


For each (non-strict) total order ≤ there is an associated asymmetric (hence irreflexive) relation <, called a strict total order, which can be defined in two equivalent ways:




  • a < b if a ≤ b and a ≠ b


  • a < b if not b ≤ a (i.e., < is the inverse of the complement of ≤)


Properties:



  • The relation is transitive: a < b and b < c implies a < c.

  • The relation is trichotomous: exactly one of a < b, b < a and a = b is true.

  • The relation is a strict weak order, where the associated equivalence is equality.


We can work the other way and start by choosing < as a transitive trichotomous binary relation; then a total order ≤ can be defined in two equivalent ways:




  • a ≤ b if a < b or a = b


  • a ≤ b if not b < a


Two more associated orders are the complements ≥ and >, completing the quadruple {<, >, ≤, ≥}.


We can define or explain the way a set is totally ordered by any of these four relations; the notation implies whether we are talking about the non-strict or the strict total order.



Examples



  • The letters of the alphabet ordered by the standard dictionary order, e.g., A < B < C etc.

  • Any subset of a totally ordered set X is totally ordered for the restriction of the order on X.

  • The unique order on the empty set, ∅, is a total order.

  • Any set of cardinal numbers or ordinal numbers (more strongly, these are well-orders).

  • If X is any set and f an injective function from X to a totally ordered set then f induces a total ordering on X by setting x1 < x2 if and only if f(x1) < f(x2).

  • The lexicographical order on the Cartesian product of a family of totally ordered sets, indexed by a well ordered set, is itself a total order.

  • The set of real numbers ordered by the usual less than (<) or greater than (>) relations is totally ordered, hence also the subsets of natural numbers, integers, and rational numbers. Each of these can be shown to be the unique (to within isomorphism) smallest example of a totally ordered set with a certain property, (a total order A is the smallest with a certain property if whenever B has the property, there is an order isomorphism from A to a subset of B):

    • The natural numbers comprise the smallest totally ordered set with no upper bound.

    • The integers comprise the smallest totally ordered set with neither an upper nor a lower bound.

    • The rational numbers comprise the smallest totally ordered set which is dense in the real numbers. The definition of density used here says that for every a and b in the real numbers such that a < b, there is a q in the rational numbers such that a < q < b.

    • The real numbers comprise the smallest unbounded totally ordered set that is connected in the order topology (defined below).




  • Ordered fields are totally ordered by definition. They include the rational numbers and the real numbers. Every ordered field contains an ordered subfield that is isomorphic to the rational numbers. Any Dedekind-complete ordered field is isomorphic to the real numbers.



Further concepts



Chains


While chain is sometimes merely a synonym for totally ordered set, it can also refer to a totally ordered subset of some partially ordered set. The latter definition has a crucial role in Zorn's lemma.
The height of a poset denotes the cardinality of its largest chain in this sense.


For example, consider the set of all subsets of the integers partially ordered by inclusion. Then the set { In : n is a natural number}, where In is the set of natural numbers below n, is a chain in this ordering, as it is totally ordered under inclusion: If n≤k, then In is a subset of Ik.



Lattice theory


One may define a totally ordered set as a particular kind of lattice, namely one in which we have



{a∨b,a∧b}={a,b}{displaystyle {avee b,awedge b}={a,b}}{avee b,awedge b}={a,b} for all a, b.

We then write a ≤ b if and only if a=a∧b{displaystyle a=awedge b}a=awedge b. Hence a totally ordered set is a distributive lattice.



Finite total orders


A simple counting argument will verify that any non-empty finite totally ordered set (and hence any non-empty subset thereof) has a least element. Thus every finite total order is in fact a well order. Either by direct proof or by observing that every well order is order isomorphic to an ordinal one may show that every finite total order is order isomorphic to an initial segment of the natural numbers ordered by <. In other words, a total order on a set with k elements induces a bijection with the first k natural numbers. Hence it is common to index finite total orders or well orders with order type ω by natural numbers in a fashion which respects the ordering (either starting with zero or with one).



Category theory


Totally ordered sets form a full subcategory of the category of partially ordered sets, with the morphisms being maps which respect the orders, i.e. maps f such that if a ≤ b then f(a) ≤ f(b).


A bijective map between two totally ordered sets that respects the two orders is an isomorphism in this category.



Order topology


For any totally ordered set X we can define the open intervals (a, b) = {x : a < x and x < b}, (−∞, b) = {x : x < b}, (a, ∞) = {x : a < x} and (−∞, ∞) = X. We can use these open intervals to define a topology on any ordered set, the order topology.


When more than one order is being used on a set one talks about the order topology induced by a particular order. For instance if N is the natural numbers, < is less than and > greater than we might refer to the order topology on N induced by < and the order topology on N induced by > (in this case they happen to be identical but will not in general).


The order topology induced by a total order may be shown to be hereditarily normal.



Completeness


A totally ordered set is said to be complete if every nonempty subset that has an upper bound, has a least upper bound. For example, the set of real numbers R is complete but the set of rational numbers Q is not.


There are a number of results relating properties of the order topology to the completeness of X:



  • If the order topology on X is connected, X is complete.


  • X is connected under the order topology if and only if it is complete and there is no gap in X (a gap is two points a and b in X with a < b such that no c satisfies a < c < b.)


  • X is complete if and only if every bounded set that is closed in the order topology is compact.


A totally ordered set (with its order topology) which is a complete lattice is compact. Examples are the closed intervals of real numbers, e.g. the unit interval [0,1], and the affinely extended real number system (extended real number line). There are order-preserving homeomorphisms between these examples.



Sums of orders


For any two disjoint total orders (A1,≤1){displaystyle (A_{1},leq _{1})}(A_{1},leq _{1}) and (A2,≤2){displaystyle (A_{2},leq _{2})}(A_{2},leq _{2}), there is a natural order ≤+{displaystyle leq _{+}}leq _{+} on the set A1∪A2{displaystyle A_{1}cup A_{2}}A_{1}cup A_{2}, which is called the sum of the two orders or sometimes just A1+A2{displaystyle A_{1}+A_{2}}A_{1}+A_{2}:


For x,y∈A1∪A2{displaystyle x,yin A_{1}cup A_{2}}x,yin A_{1}cup A_{2}, x≤+y{displaystyle xleq _{+}y}xleq _{+}y holds if and only if one of the following holds:


  1. x,y∈A1{displaystyle x,yin A_{1}}x,yin A_{1} and x≤1y{displaystyle xleq _{1}y}xleq _{1}y


  2. x,y∈A2{displaystyle x,yin A_{2}}x,yin A_{2} and x≤2y{displaystyle xleq _{2}y}xleq _{2}y


  3. x∈A1{displaystyle xin A_{1}}xin A_{1} and y∈A2{displaystyle yin A_{2}}yin A_{2}



Intutitively, this means that the elements of the second set are added on top of the elements of the first set.


More generally, if (I,≤){displaystyle (I,leq )}(I,leq ) is a totally ordered index set, and for each i∈I{displaystyle iin I}iin I the structure (Ai,≤i){displaystyle (A_{i},leq _{i})}(A_{i},leq _{i}) is a linear order, where the sets Ai{displaystyle A_{i}}A_{i} are pairwise disjoint, then the natural total order on ⋃iAi{displaystyle bigcup _{i}A_{i}}bigcup _{i}A_{i} is defined by


For x,y∈⋃i∈IAi{displaystyle x,yin bigcup _{iin I}A_{i}}x,yin bigcup _{iin I}A_{i}, x≤y{displaystyle xleq y}xleq y holds if:

  1. Either there is some i∈I{displaystyle iin I}iin I with x≤iy{displaystyle xleq _{i}y}xleq _{i}y

  2. or there are some i<j{displaystyle i<j}i<j in I{displaystyle I}I with x∈Ai{displaystyle xin A_{i}}xin A_{i}, y∈Aj{displaystyle yin A_{j}}yin A_{j}




Orders on the Cartesian product of totally ordered sets


In order of increasing strength, i.e., decreasing sets of pairs, three of the possible orders on the Cartesian product of two totally ordered sets are:




  • Lexicographical order: (a,b) ≤ (c,d) if and only if a < c or (a = c and b ≤ d). This is a total order.

  • (a,b) ≤ (c,d) if and only if a ≤ c and b ≤ d (the product order). This is a partial order.

  • (a,b) ≤ (c,d) if and only if (a < c and b < d) or (a = c and b = d) (the reflexive closure of the direct product of the corresponding strict total orders). This is also a partial order.


All three can similarly be defined for the Cartesian product of more than two sets.


Applied to the vector space Rn, each of these make it an ordered vector space.


See also examples of partially ordered sets.


A real function of n real variables defined on a subset of Rndefines a strict weak order and a corresponding total preorder on that subset.



Related structures


A binary relation that is antisymmetric, transitive, and reflexive (but not necessarily total) is a partial order.


A group with a compatible total order is a totally ordered group.


There are only a few nontrivial structures that are (interdefinable as) reducts of a total order. Forgetting the orientation results in a betweenness relation. Forgetting the location of the ends results in a cyclic order. Forgetting both data results in a separation relation.[3]



See also



  • Order theory

  • Well-order

  • Suslin's problem

  • Countryman line


  • Prefix order – a downward total partial order



Notes





  1. ^ Nederpelt, Rob (2004). "Chapter 20.2: Ordered Sets. Orderings". Logical Reasoning: A First Course. Texts in Computing. 3 (3rd, Revised ed.). King's College Publications. p. 325. ISBN 0-9543006-7-X..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  2. ^ Nederpelt, Rob (2004). "Chapter 20.3: Ordered Sets. Linear orderings". Logical Reasoning: A First Course. Texts in Computing. 3 (3rd, Revisied ed.). King's College Publications. p. 330. ISBN 0-9543006-7-X.


  3. ^ Macpherson, H. Dugald (2011), "A survey of homogeneous structures" (PDF), Discrete Mathematics, doi:10.1016/j.disc.2011.01.024, retrieved 28 April 2011




References



  • George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co.
    ISBN 0-7167-0442-0

  • John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988.
    ISBN 0-486-65676-4



External links



  • Hazewinkel, Michiel, ed. (2001) [1994], "Totally ordered set", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4



Comments

Post a Comment

Popular posts from this blog

Information security

Image
This article is part of a series on Information security Related security categories Internet security Cyberwarfare Computer security Mobile security Network security Threats Computer crime Vulnerability Eavesdropping Malware Spyware Ransomware Trojans Viruses Worms Rootkits Bootkits Keyloggers Screen scrapers Exploits Backdoors Logic bombs Payloads Denial of service Defenses Computer access control Application security Antivirus software Secure coding Secure by default Secure by design Secure operating systems Authentication Multi-factor authentication Authorization Data-centric security Encryption Firewall Intrusion detection system Mobile secure gateway Runtime application self-protection (RASP) v t e Information security , sometimes shortened to InfoSec , is the practice of preventing unauthorized access, use, disclosure, disruption, modification, inspection, recording or destruction of information. Th...
Read more

Lambak Kiri

Image
For Lambak Kiri public housing area, see Lambak Kiri Landless Indigenous Citizens' Housing Scheme. Village in Brunei-Muara, Brunei Lambak Kiri Village Location in Brunei Coordinates: 4°59′26″N 114°57′04″E  /  4.990472°N 114.951114°E  / 4.990472; 114.951114 Coordinates: 4°59′26″N 114°57′04″E  /  4.990472°N 114.951114°E  / 4.990472; 114.951114 Country Brunei District Brunei-Muara Mukim Berakas A Government  • Village head Hamdani Omar Postcode BB1214 Lambak Kiri is a populated place in Brunei-Muara District, Brunei. It is officially a village subdivision under Berakas A, a mukim in the district. Lambak Kiri may also refer to the greater area which includes the Lambak Kiri public housing area of the Landless Indigenous Citizens' Housing Scheme (Malay: Skim Tanah Kurnia Rakyat Jati ), although the latter is a separate subdivision. Contents 1 Name 2 Administration 3 See also 4 References Name ...
Read more

章鱼与海女图

Image
本条目 可参照英語維基百科相應條目来扩充 。 （2014/5/25） 若您熟悉来源语言和主题，请协助参考外语维基扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记 {{Translated page}} 标签。 本条目 需要擴充。 （2013年8月15日） 请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 《 章鱼与海女 》（日语： 蛸と海女 ／ たことあま   Tako to ama ）是一幅由日本畫家葛饰北斋创作的浮世绘，出自1814年（文化4年）出版的艳本《喜能会之故真通》（日语： 喜能会之故真通 ／ きのえのこまつ   Kinoe no Komatsu ）。畫中有兩隻章鱼以觸手攻擊一名採珠的海女，並進行擬似戀獸癖的交媾行為。作品尺寸为6½" × 8¾" （16.51 cm × 22.23 cm）。 [1] 在此之前的类似作品还有北尾重政的艳本《謡曲色番組》及勝川春潮的艳本《艳本千夜多女志》等，有被北斋作为参考的可能性。 《章鱼与海女图》有不同英文翻译，一般称The Dream of the Fisherman's Wife，又作Girl Diver and Octopi、Diver and Two Octopi，Richard Douglas Lane称其为 Girl Diver and Octopi [2] ，Mathi Forrer 称其为 Pearl Diver and Two Octopi [3] ，Danielle Talerico 称其为 Diver and Two Octopi 。 [4] 目录 1 作品介绍 1.1 画中对话 1.2 解释 2 评价 3 影响 3.1 模仿作品 4 另见 5 参考来源 6 外部連結 作品介绍 画中对话 原文 译文 大蛸： いつぞハいつぞハとねらいすましてゐたかいがあつて、けふといふけふ、とうとうとらまへたア。てもむつくりとしたいいぼぼだ。いもよりハなをこうぶつだ。サアサア、すつてすつてすいつくして...
Read more