ordered pair See SET THEORY. ordering, an arrangement of the elements of a set so that some of them come before others. If X is a set, it is useful to identify an ordering R of X with a subset R of X$X, the set of all ordered pairs with members in X. If ‹ x,y ( 1 R then x comes before y in the ordering of X by R, and if ‹ x,y ( 2 R and ‹ y,x ( 2 R, then x and y are incomparable. Orders on X are therefore relations on X, since a relation on a set X is any subset of X $ X. Some minimal conditions a relation must meet to be an ordering are (i) reflexivity: (Ex)Rxx; (ii) antisymmetry: (Ex)(Ey)((Rxy & Ryx) / x % y); and (iii) transitivity: (Ex)(Ey)(Ez)((Rxy & Ryz) / Rxz). A relation meeting these three conditions is known as a partial order (also less commonly called a semi-order), and if reflexivity is replaced by irreflexivity, (Ex)-Rxx, as a strict partial order.
Other orders are strengthenings of these. Thus a tree-ordering of X is a partial order with a distinguished root element a, i.e. (Ex)Rax, and that satisfies the backward linearity condition that from any element there is a unique path back to a: (Ex)(Ey)(Ez)((Ryx & Rzx) / (Ryz 7 Rzy). A total order on X is a partial order satisfying the connectedness requirement: (Ex)(Ey)(Rxy 7 Ryx). Total orderings are sometimes known as strict linear orderings, contrasting with weak linear orderings, in which the requirement of antisymmetry is dropped. The natural number line in its usual order is a strict linear order; a weak linear ordering of a set X is a strict linear order of levels on which various members of X may be found, while adding antisymmetry means that each level contains only one member.
Two other important orders are dense (partial or total) orders, in which, between any two elements, there is a third; and well-orders. A set X is said to be well-ordered by R if R is total and every non-empty subset of Y of X has an R-least member: (EY 0 X)[Y & / / (Dz 1 Y)(Ew 1 Y)Rzw]. Well-ordering rules out infinite descending sequences, while a strict well-ordering, which is irreflexive rather than reflexive, rules out loops. The best-known example is the membership relation of axiomatic set theory, in which there are no loops such as x 1 y 1 x or x 1 x, and no infinite descending chain. . . x2 1 x1 1 x0.
See also RELATION, SET THEORY. G.Fo.