Product order

Last updated
Hasse diagram of the product order on NxN N-Quadrat, gedreht.svg
Hasse diagram of the product order on ×ℕ

In mathematics, given two preordered sets and the product order [1] [2] [3] [4] (also called the coordinatewise order [5] [3] [6] or componentwise order [2] [7] ) is a partial ordering on the Cartesian product Given two pairs and in declare that if and only if and

Another possible ordering on is the lexicographical order, which is a total ordering. However the product order of two totally ordered sets is not in general total; for example, the pairs and are incomparable in the product order of the ordering with itself. The lexicographic order of totally ordered sets is a linear extension of their product order, and thus the product order is a subrelation of the lexicographic order. [3]

The Cartesian product with the product order is the categorical product in the category of partially ordered sets with monotone functions. [7]

The product order generalizes to arbitrary (possibly infinitary) Cartesian products. Suppose is a set and for every is a preordered set. Then the product preorder on is defined by declaring for any and in that

if and only if for every

If every is a partial order then so is the product preorder.

Furthermore, given a set the product order over the Cartesian product can be identified with the inclusion ordering of subsets of [4]

The notion applies equally well to preorders. The product order is also the categorical product in a number of richer categories, including lattices and Boolean algebras. [7]

Related Research Articles

In mathematics, a binary relation over sets X and Y is a subset of the Cartesian product X × Y; that is, it is a set of ordered pairs (x, y) consisting of elements x in X and y in Y. It encodes the common concept of relation: an element x is related to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation. A binary relation is the most studied special case n = 2 of an n-ary relation over sets X1, ..., Xn, which is a subset of the Cartesian product X1 × ... × Xn.

In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one talks about the product in category theory, which formalizes these notions.

In mathematics, a directed set is a nonempty set together with a reflexive and transitive binary relation , with the additional property that every pair of elements has an upper bound. In other words, for any and in there must exist in with and A directed set's preorder is called a direction.

In mathematics, the inverse limit is a construction that generalizes several other constructions that recur throughout various fields of mathematics, including products, pullbacks, intersections, and an endless amount of other related constructions, only some of which have been investigated − profinite groups, p-adic numbers, and solenoids being some prominent examples. Inverse limits are taken of inverse systems in some given category, such as the category Set of sets for example. An inverse system is a collection of objects in the category indexed by some preordered set called the indexing set, together with a collection of morphisms called connecting morphisms that satisfy the following compatibility condition of inverse systems: whenever A cone into this inverse system is pair consisting of an object called its vertex, and an -indexed family of morphisms each of which has prototype and satisfying the compatibility condition: whenever An inverse limit of this inverse system, if it exists, is a cone that also has an additional property known as the universal property of inverse limits. This universal property establishes a one-to-one correspondence between, on one hand, cones into the given inverse system and, on the other hand, a unique morphism into the limit object that is "compatible" with the limit's family of morphisms in that it satisfies the condition: for every index . If a limit of a system exists then in general, it might not be unique although it will always be unique up to a certain unique isomorphism.

In mathematics, more specifically in general topology and related branches, a net or Moore–Smith sequence is a generalization of the notion of a sequence. In essence, a sequence is a function whose domain is the natural numbers. The codomain of this function is usually some topological space.

Partially ordered set Set ordered by a transitive, antisymmetric, and reflexive binary relation

In mathematics, especially order theory, a partially ordered set 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 relation indicating that, for certain pairs of elements in the set, one of the elements precedes the other in the ordering. The relation itself is called a "partial order." The word partial in the names "partial order" and "partially ordered set" is used as an indication that not every pair of elements needs to be comparable. That is, there may be pairs of elements for which neither element precedes the other in the poset. Partial orders thus generalize total orders, in which every pair is comparable.

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 cases of a preorder: an antisymmetric preorder is a partial order, and a symmetric preorder is an equivalence relation.

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 on some set , which satisfies the following for all and in :

  1. (reflexive).
  2. If and then (transitive)
  3. If and then (antisymmetric)
  4. or .
Monotonic function

In mathematics, a monotonic 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 theory.

Category (mathematics) Mathematical object that generalizes the standard notions of sets and functions

In mathematics, a category is a collection of "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose objects are sets and whose arrows are functions.

Inequality (mathematics) Mathematical relation expressed by symbols < or ≤

In mathematics, an inequality is a relation which makes a non-equal comparison between two numbers or other mathematical expressions. It is used most often to compare two numbers on the number line by their size. There are several different notations used to represent different kinds of inequalities:

Maximal and minimal elements An element of a preordered set that is the only element ≥ (respectively, ≤) to itself (in contrast, greatest elements are ≥ all elements).

In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set (poset) is an element of S that is not smaller than any other element in S. A minimal element of a subset S of some partially ordered set is defined dually as an element of S that is not greater than any other element in S.

In mathematics, a monoidal category is a category equipped with a bifunctor

Order theory is a branch of mathematics which investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

In mathematics, the lexicographic or lexicographical 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.

Greatest element and least element An element of a preordered set that is ≥ (respectively, ≤) to all other elements (in contrast, it is maximal if it is the only element ≥ to itself)

In mathematics, especially in order theory, the greatest element of a subset of a partially ordered set (poset) is an element of that is greater than every other element of . The term least element is defined dually, that is, it is an element of that is smaller than every other element of

Weak ordering Generalization of total orderings allowing ties, axiomatized as strict weak orders, total preorders, or ordered partitions

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 and are in turn generalized by partially ordered sets and preorders.

In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.

Ordered vector space

In mathematics, an ordered vector space or partially ordered vector space is a vector space equipped with a partial order that is compatible with the vector space operations.

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 (a, b) where a is in A and b is in B. In terms of set-builder notation, that is


  1. Neggers, J.; Kim, Hee Sik (1998), "4.2 Product Order and Lexicographic Order", Basic Posets, World Scientific, pp. 64–78, ISBN   9789810235895
  2. 1 2 Sudhir R. Ghorpade; Balmohan V. Limaye (2010). A Course in Multivariable Calculus and Analysis. Springer. p. 5. ISBN   978-1-4419-1621-1.
  3. 1 2 3 Egbert Harzheim (2006). Ordered Sets. Springer. pp. 86–88. ISBN   978-0-387-24222-4.
  4. 1 2 Victor W. Marek (2009). Introduction to Mathematics of Satisfiability. CRC Press. p. 17. ISBN   978-1-4398-0174-1.
  5. Davey & Priestley, Introduction to Lattices and Order (Second Edition), 2002, p. 18
  6. Alexander Shen; Nikolai Konstantinovich Vereshchagin (2002). Basic Set Theory. American Mathematical Soc. p. 43. ISBN   978-0-8218-2731-4.
  7. 1 2 3 Paul Taylor (1999). Practical Foundations of Mathematics. Cambridge University Press. pp. 144–145 and 216. ISBN   978-0-521-63107-5.

See also