HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, given two preordered sets A and B, the product order (also called the coordinatewise orderDavey & Priestley, ''
Introduction to Lattices and Order ''Introduction to Lattices and Order'' is a mathematical textbook on order theory by Brian A. Davey and Hilary Priestley. It was published by the Cambridge University Press in their Cambridge Mathematical Textbooks series in 1990, with a second ...
'' (Second Edition), 2002, p. 18
or componentwise order) is a partial ordering on the
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\t ...
A \times B. Given two pairs \left(a_1, b_1\right) and \left(a_2, b_2\right) in A \times B, declare that \left(a_1, b_1\right) \leq \left(a_2, b_2\right)
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
a_1 \leq a_2 and b_1 \leq b_2. Another possible ordering on A \times B is the
lexicographical order 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 ...
, which is a total ordering. However the product order of two
totally ordered In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive ...
sets is not in general total; for example, the pairs (0, 1) and (1, 0) are incomparable in the product order of the ordering 0 < 1 with itself. The lexicographic order of totally ordered sets is a
linear extension In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear ext ...
of their product order, and thus the product order is a subrelation of the lexicographic order. The Cartesian product with the product order is the categorical product in the
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
of partially ordered sets with
monotone function In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
s. The product order generalizes to arbitrary (possibly infinitary) Cartesian products. Suppose A \neq \varnothing is a set and for every a \in A, \left(I_a, \leq\right) is a preordered set. Then the on \prod_ I_a is defined by declaring for any i_ = \left(i_a\right)_ and j_ = \left(j_a\right)_ in \prod_ I_a, that :i_ \leq j_ if and only if i_a \leq j_a for every a \in A. If every \left(I_a, \leq\right) is a partial order then so is the product preorder. Furthermore, given a set A, the product order over the Cartesian product \prod_ \ can be identified with the inclusion ordering of subsets of A. The notion applies equally well to
preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...
s. The product order is also the categorical product in a number of richer categories, including
lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...
s and
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
s.


References


See also

* Direct product of binary relations * Examples of partial orders * Star product, a different way of combining partial orders * Orders on the Cartesian product of totally ordered sets *
Ordinal sum In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
of partial orders * {{math-stub Order theory