Misplaced Pages

#930069

69-622: WFO may refer to: Well-founded ordering, in mathematics, see well-founded relation W.F.O. (album) , a 1994 album by the thrash metal band Overkill Workforce optimization , strategy for managing contact center staffing, processes, and workflows. Weather Forecast Office, a local forecasting and warning office of the United States National Weather Service: See List of National Weather Service Weather forecast offices Washington Field Office, of

138-410: A = b . The two concepts are equivalent although in some circumstances one can be more convenient to work with than the other. It is reasonable to consider functions between partially ordered sets having certain additional properties that are related to the ordering relations of the two sets. The most fundamental condition that occurs in this context is monotonicity . A function f from a poset P to

207-479: A and b in P , we have that: A partial order with this property is called a total order . These orders can also be called linear orders or chains . While many familiar orders are linear, the subset order on sets provides an example where this is not the case. Another example is given by the divisibility (or "is-a- factor -of") relation |. For two natural numbers n and m , we write n | m if n divides m without remainder. One easily sees that this yields

276-468: A is equivalent to b , if a ≤ b and b ≤ a . Preorders can be turned into orders by identifying all elements that are equivalent with respect to this relation. Several types of orders can be defined from numerical data on the items of the order: a total order results from attaching distinct real numbers to each item and using the numerical comparisons to order the items; instead, if distinct items are allowed to have equal numerical scores, one obtains

345-459: A partial order is called well-founded if the corresponding strict order is a well-founded relation. If the order is a total order then it is called a well-order . In set theory , a set x is called a well-founded set if the set membership relation is well-founded on the transitive closure of x . The axiom of regularity , which is one of the axioms of Zermelo–Fraenkel set theory , asserts that all sets are well-founded. A relation R

414-430: A strict weak ordering . Requiring two scores to be separated by a fixed threshold before they may be compared leads to the concept of a semiorder , while allowing the threshold to vary on a per-item basis produces an interval order . An additional simple but useful property leads to so-called well-founded , for which all non-empty subsets have a minimal element. Generalizing well-orders from linear to partial orders,

483-409: A ≤ b implies f ( a ) ≥ f ( b ). An order-embedding is a function f between orders that is both order-preserving and order-reflecting. Examples for these definitions are found easily. For instance, the function that maps a natural number to its successor is clearly monotone with respect to the natural order. Any function from a discrete order, i.e. from a set ordered by the identity order "=",

552-592: A (monotone) Galois connection , which is just the same as a pair of adjoint functors . But category theory also has its impact on order theory on a larger scale. Classes of posets with appropriate functions as discussed above form interesting categories. Often one can also state constructions of orders, like the product order , in terms of categories. Further insights result when categories of orders are found categorically equivalent to other categories, for example of topological spaces. This line of research leads to various representation theorems , often collected under

621-462: A , b and c in P , we have that: A set with a partial order on it is called a partially ordered set , poset , or just ordered set if the intended meaning is clear. By checking these properties, one immediately sees that the well-known orders on natural numbers , integers , rational numbers and reals are all orders in the above sense. However, these examples have the additional property that any two elements are comparable, that is, for all

690-505: A class X that is extensional, there exists a class C such that ( X , R ) is isomorphic to ( C , ∈) . A relation R is said to be reflexive if a R a holds for every a in the domain of the relation. Every reflexive relation on a nonempty domain has infinite descending chains, because any constant sequence is a descending chain. For example, in the natural numbers with their usual order ≤, we have 1 ≥ 1 ≥ 1 ≥ ... . To avoid these trivial descending sequences, when working with

759-416: A complete lattice, more precisely a complete Heyting algebra (or " frame " or " locale "). Filters and nets are notions closely related to order theory and the closure operator of sets can be used to define a topology. Beyond these relations, topology can be looked at solely in terms of the open set lattices, which leads to the study of pointless topology . Furthermore, a natural preorder of elements of

SECTION 10

#1732772590931

828-529: A concept can be defined by just inverting the ordering in a former definition. This is the case for "least" and "greatest", for "minimal" and "maximal", for "upper bound" and "lower bound", and so on. This is a general situation in order theory: A given order can be inverted by just exchanging its direction, pictorially flipping the Hasse diagram top-down. This yields the so-called dual , inverse , or opposite order . Every order theoretic definition has its dual: it

897-416: A finite sub-order. This works well for the natural numbers, but it fails for the reals, where there is no immediate successor above 0; however, quite often one can obtain an intuition related to diagrams of a similar kind . In a partially ordered set there may be some elements that play a special role. The most basic example is given by the least element of a poset . For example, 1 is the least element of

966-413: A new operation ~ called negation . Both structures play a role in mathematical logic and especially Boolean algebras have major applications in computer science . Finally, various structures in mathematics combine orders with even more algebraic operations, as in the case of quantales , that allow for the definition of an addition operation. Many other important properties of posets exist. For example,

1035-467: A pair of two functions in converse directions, which are "not quite" inverse to each other, but that still have close relationships. Another special type of self-maps on a poset are closure operators , which are not only monotonic, but also idempotent , i.e. f ( x ) = f ( f ( x )), and extensive (or inflationary ), i.e. x ≤ f ( x ). These have many applications in all kinds of "closures" that appear in mathematics. Besides being compatible with

1104-425: A partial order ≤, it is common to apply the definition of well foundedness (perhaps implicitly) to the alternate relation < defined such that a < b if and only if a ≤ b and a ≠ b . More generally, when working with a preorder ≤, it is common to use the relation < defined such that a < b if and only if a ≤ b and b ≰ a . In the context of the natural numbers, this means that

1173-436: A partial order. For example neither 3 divides 13 nor 13 divides 3, so 3 and 13 are not comparable elements of the divisibility relation on the set of integers. The identity relation = on any set is also a partial order in which every two distinct elements are incomparable. It is also the only relation that is both a partial order and an equivalence relation because it satisfies both the antisymmetry property of partial orders and

1242-439: A poset Q is monotone , or order-preserving , if a ≤ b in P implies f ( a ) ≤ f ( b ) in Q (Noting that, strictly, the two relations here are different since they apply to different sets.). The converse of this implication leads to functions that are order-reflecting , i.e. functions f as above for which f ( a ) ≤ f ( b ) implies a ≤ b . On the other hand, a function may also be order-reversing or antitone , if

1311-466: A poset is locally finite if every closed interval [ a , b ] in it is finite . Locally finite posets give rise to incidence algebras which in turn can be used to define the Euler characteristic of finite bounded posets. In an ordered set, one can define many types of special subsets based on the given order. A simple example are upper sets ; i.e. sets that contain all elements that are above them in

1380-585: A relation is well-founded if: ( ∀ S ⊆ X ) [ S ≠ ∅ ⟹ ( ∃ m ∈ S ) ( ∀ s ∈ S ) ¬ ( s R m ) ] . {\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].} Some authors include an extra condition that R

1449-633: A set S one writes sup( S ) or ⋁ S {\displaystyle \bigvee S} for its least upper bound. Conversely, the greatest lower bound is known as infimum or meet and denoted inf( S ) or ⋀ S {\displaystyle \bigwedge S} . These concepts play an important role in many applications of order theory. For two elements x and y , one also writes x ∨ y {\displaystyle x\vee y} and x ∧ y {\displaystyle x\wedge y} for sup({ x , y }) and inf({ x , y }), respectively. For example, 1

SECTION 20

#1732772590931

1518-402: A set is well partially ordered if all its non-empty subsets have a finite number of minimal elements. Many other types of orders arise when the existence of infima and suprema of certain sets is guaranteed. Focusing on this aspect, usually referred to as completeness of orders, one obtains: However, one can go even further: if all finite non-empty infima exist, then ∧ can be viewed as

1587-631: A straightforward generalization: instead of displaying lesser elements below greater ones, the direction of the order can also be depicted by giving directions to the edges of a graph. In this way, each order is seen to be equivalent to a directed acyclic graph , where the nodes are the elements of the poset and there is a directed path from a to b if and only if a ≤ b . Dropping the requirement of being acyclic, one can also obtain all preorders. When equipped with all transitive edges, these graphs in turn are just special categories , where elements are objects and each set of morphisms between two elements

1656-528: A total binary operation in the sense of universal algebra . Hence, in a lattice, two operations ∧ and ∨ are available, and one can define new properties by giving identities, such as This condition is called distributivity and gives rise to distributive lattices . There are some other important distributivity laws which are discussed in the article on distributivity in order theory . Some additional order structures that are often specified via algebraic operations and defining identities are which both introduce

1725-448: Is converse well-founded , upwards well-founded or Noetherian on X , if the converse relation R is well-founded on X . In this case R is also said to satisfy the ascending chain condition . In the context of rewriting systems, a Noetherian relation is also called terminating . An important reason that well-founded relations are interesting is because a version of transfinite induction can be used on them: if ( X , R )

1794-428: Is greater than 5", or "Does Tom have fewer cookies than Sally?". This intuitive concept can be extended to orders on other sets of numbers , such as the integers and the reals . The idea of being greater than or less than another number is one of the basic intuitions of number systems (compare with numeral systems ) in general (although one usually is also interested in the actual difference of two numbers, which

1863-399: 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 . Orders are everywhere in mathematics and related fields like computer science . The first order often discussed in primary school is the standard order on the natural numbers e.g. "2 is less than 3", "10

1932-414: Is set-like , i.e., that the elements less than any given element form a set. Equivalently, assuming the axiom of dependent choice , a relation is well-founded when it contains no infinite descending chains , which can be proved when there is no infinite sequence x 0 , x 1 , x 2 , ... of elements of X such that x n +1 R x n for every natural number n . In order theory ,

2001-410: Is a least element, then it is the only minimal element of the order. Again, in infinite posets maximal elements do not always exist - the set of all finite subsets of a given infinite set, ordered by subset inclusion, provides one of many counterexamples. An important tool to ensure the existence of maximal elements under certain conditions is Zorn's Lemma . Subsets of partially ordered sets inherit

2070-431: Is a monotone bijective function that has a monotone inverse. This is equivalent to being a surjective order-embedding. Hence, the image f ( P ) of an order-embedding is always isomorphic to P , which justifies the term "embedding". A more elaborate type of functions is given by so-called Galois connections . Monotone Galois connections can be viewed as a generalization of order-isomorphisms, since they constitute of

2139-451: Is a unique function G such that for every x ∈ X , G ( x ) = F ( x , G | { y : y R x } ) . {\displaystyle G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right).} That is, if we want to construct a function G on X , we may define G ( x ) using the values of G ( y ) for y R x . As an example, consider

WFO - Misplaced Pages Continue

2208-683: Is a well-founded relation, P ( x ) is some property of elements of X , and we want to show that it suffices to show that: That is, ( ∀ x ∈ X ) [ ( ∀ y ∈ X ) [ y R x ⟹ P ( y ) ] ⟹ P ( x ) ] implies ( ∀ x ∈ X ) P ( x ) . {\displaystyle (\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implies}}\quad (\forall x\in X)\,P(x).} Well-founded induction

2277-406: Is also monotone. Mapping each natural number to the corresponding real number gives an example for an order embedding. The set complement on a powerset is an example of an antitone function. An important question is when two orders are "essentially equal", i.e. when they are the same up to renaming of elements. Order isomorphisms are functions that define such a renaming. An order-isomorphism

2346-407: Is at most singleton. Functions between orders become functors between categories. Many ideas of order theory are just concepts of category theory in small. For example, an infimum is just a categorical product . More generally, one can capture infima and suprema under the abstract notion of a categorical limit (or colimit , respectively). Another place where categorical ideas occur is the concept of

2415-489: Is different from Wikidata All article disambiguation pages All disambiguation pages Well-founded relation In mathematics , a binary relation R is called well-founded (or wellfounded or foundational ) on a set or, more generally, a class X if every non-empty subset S ⊆ X has a minimal element with respect to R ; that is, there exists an m ∈ S such that, for every s ∈ S , one does not have s R m . In other words,

2484-412: Is given by the correspondence between Boolean algebras and Boolean rings . Other issues are concerned with the existence of free constructions , such as free lattices based on a given set of generators. Furthermore, closure operators are important in the study of universal algebra. In topology , orders play a very prominent role. In fact, the collection of open sets provides a classical example of

2553-455: Is not given by the order). Other familiar examples of orderings are the alphabetical order of words in a dictionary and the genealogical property of lineal descent within a group of people. The notion of order is very general, extending beyond contexts that have an immediate, intuitive feel of sequence or relative quantity. In other contexts orders may capture notions of containment or specialization. Abstractly, this type of order amounts to

2622-472: Is smaller than (precedes) y then there exists a path from x to y that is directed upwards. It is often necessary for the edges connecting elements to cross each other, but elements must never be located within an edge. An instructive exercise is to draw the Hasse diagram for the set of natural numbers that are smaller than or equal to 13, ordered by | (the divides relation). Even some infinite sets can be diagrammed by superimposing an ellipsis (...) on

2691-413: Is sometimes called Noetherian induction, after Emmy Noether . On par with induction, well-founded relations also support construction of objects by transfinite recursion . Let ( X , R ) be a set-like well-founded relation and F a function that assigns an object F ( x , g ) to each pair of an element x ∈ X and a function g on the initial segment { y : y R x } of X . Then there

2760-445: Is that of a directed subset , which like an ideal contains upper bounds of finite subsets, but does not have to be a lower set. Furthermore, it is often generalized to preordered sets. A subset which is - as a sub-poset - linearly ordered, is called a chain . The opposite notion, the antichain , is a subset that contains no two comparable elements; i.e. that is a discrete order. Although most mathematical areas use orders in one or

2829-699: Is the Scott topology , which is coarser than the Alexandrov topology. A third important topology in this spirit is the Lawson topology . There are close connections between these topologies and the concepts of order theory. For example, a function preserves directed suprema if and only if it is continuous with respect to the Scott topology (for this reason this order theoretic property is also called Scott-continuity ). The visualization of orders with Hasse diagrams has

WFO - Misplaced Pages Continue

2898-404: Is the infimum of the positive integers as a subset of integers. For another example, consider again the relation | on natural numbers. The least upper bound of two numbers is the smallest number that is divided by both of them, i.e. the least common multiple of the numbers. Greatest lower bounds in turn are given by the greatest common divisor . In the previous definitions, we often noted that

2967-432: Is the least element since it divides all other numbers. In contrast, 0 is the number that is divided by all other numbers. Hence it is the greatest element of the order. Other frequent terms for the least and greatest elements is bottom and top or zero and unit . Least and greatest elements may fail to exist, as the example of the real numbers shows. But if they exist, they are always unique. In contrast, consider

3036-440: Is the notion one obtains by applying the definition to the inverse order. Since all concepts are symmetric, this operation preserves the theorems of partial orders. For a given mathematical result, one can just invert the order and replace all definitions by their duals and one obtains another valid theorem. This is important and useful, since one obtains two theorems for the price of one. Some more details and examples can be found in

3105-403: Is well-founded is also known as the well-ordering principle . There are other interesting special cases of well-founded induction. When the well-founded relation is the usual ordering on the class of all ordinal numbers , the technique is called transfinite induction . When the well-founded set is a set of recursively-defined data structures, the technique is called structural induction . When

3174-733: The United States Secret Service Washington Field Office, of the Federal Bureau of Investigation World Flora Online Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title WFO . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=WFO&oldid=1210889638 " Category : Disambiguation pages Hidden categories: Short description

3243-583: The finest such topology is the Alexandrov topology , given by taking all upper sets as opens. Conversely, the coarsest topology that induces the specialization order is the upper topology , having the complements of principal ideals (i.e. sets of the form { y in X | y ≤ x } for some x ) as a subbase . Additionally, a topology with specialization order ≤ may be order consistent , meaning that their open sets are "inaccessible by directed suprema" (with respect to ≤). The finest order consistent topology

3312-411: The subset relation , e.g., " Pediatricians are physicians ," and " Circles are merely special-case ellipses ." Some orders, like "less-than" on the natural numbers and alphabetical order on words, have a special property: each element can be compared to any other element, i.e. it is smaller (earlier) than, larger (later) than, or identical to. However, many other orders do not. Consider for example

3381-450: The symmetry property of equivalence relations. Many advanced properties of posets are interesting mainly for non-linear orders. Hasse diagrams can visually represent the elements and relations of a partial ordering. These are graph drawings where the vertices are the elements of the poset and the ordering relation is indicated by both the edges and the relative positioning of the vertices. Orders are drawn bottom-up: if an element x

3450-440: The article on duality in order theory . There are many ways to construct orders out of given orders. The dual order is one example. Another important construction is the cartesian product of two partially ordered sets, taken together with the product order on pairs of elements. The ordering is defined by ( a , x ) ≤ ( b , y ) if (and only if) a ≤ b and x ≤ y . (Notice carefully that there are three distinct meanings for

3519-403: The concepts of set theory , arithmetic , and binary relations . Orders are special binary relations. Suppose that P is a set and that ≤ is a relation on P ('relation on a set' is taken to mean 'relation amongst its inhabitants', i.e. ≤ is a subset of the cartesian product P x P ). Then ≤ is a partial order if it is reflexive , antisymmetric , and transitive , that is, if for all

SECTION 50

#1732772590931

3588-493: The divisibility relation | on the set {2,3,4,5,6}. Although this set has neither top nor bottom, the elements 2, 3, and 5 have no elements below them, while 4, 5 and 6 have none above. Such elements are called minimal and maximal , respectively. Formally, an element m is minimal if: Exchanging ≤ with ≥ yields the definition of maximality . As the example shows, there can be many maximal elements and some elements may be both maximal and minimal (e.g. 5 above). However, if there

3657-478: The following example: Let X be the union of the positive integers with a new element ω that is bigger than any integer. Then X is a well-founded set, but there are descending chains starting at ω of arbitrary great (finite) length; the chain ω, n − 1, n − 2, ..., 2, 1 has length n for any n . The Mostowski collapse lemma implies that set membership is a universal among the extensional well-founded relations: for any set-like well-founded relation R on

3726-437: The intuition of orders that arises from such examples in a general setting. This is achieved by specifying properties that a relation ≤ must have to be a mathematical order. This more abstract approach makes much sense, because one can derive numerous theorems in the general setting, without focusing on the details of any particular order. These insights can then be readily transferred to many less abstract applications. Driven by

3795-439: The label of limit-preserving functions . Finally, one can invert the view, switching from functions of orders to orders of functions . Indeed, the functions between two posets P and Q can be ordered via the pointwise order . For two functions f and g , we have f ≤ g if f ( x ) ≤ g ( x ) for all elements x of P . This occurs for example in domain theory , where function spaces play an important role. Many of

3864-525: The mere order relations, functions between posets may also behave well with respect to special elements and constructions. For example, when talking about posets with least element, it may seem reasonable to consider only monotonic functions that preserve this element, i.e. which map least elements to least elements. If binary infima ∧ exist, then a reasonable property might be to require that f ( x ∧ y ) = f ( x ) ∧ f ( y ), for all x and y . All of these properties, and indeed many more, may be compiled under

3933-420: The order. For example, -5 is a lower bound of the natural numbers as a subset of the integers. Given a set of sets, an upper bound for these sets under the subset ordering is given by their union . In fact, this upper bound is quite special: it is the smallest set that contains all of the sets. Hence, we have found the least upper bound of a set of sets. This concept is also called supremum or join , and for

4002-448: The order. Formally, the upper closure of a set S in a poset P is given by the set { x in P | there is some y in S with y ≤ x }. A set that is equal to its upper closure is called an upper set. Lower sets are defined dually. More complicated lower subsets are ideals , which have the additional property that each two of their elements have an upper bound within the ideal. Their duals are given by filters . A related concept

4071-475: The order. We already applied this by considering the subset {2,3,4,5,6} of the natural numbers with the induced divisibility ordering. Now there are also elements of a poset that are special with respect to some subset of the order. This leads to the definition of upper bounds . Given a subset S of some poset P , an upper bound of S is an element b of P that is above all elements of S . Formally, this means that Lower bounds again are defined by inverting

4140-505: The other way, there are also a few theories that have relationships which go far beyond mere application. Together with their major points of contact with order theory, some of these are to be presented below. As already mentioned, the methods and formalisms of universal algebra are an important tool for many order theoretic considerations. Beside formalizing orders in terms of algebraic structures that satisfy certain identities, one can also establish other connections to algebra. An example

4209-419: The positive integers and the empty set is the least set under the subset order. Formally, an element m is a least element if: The notation 0 is frequently found for the least element, even when no numbers are concerned. However, in orders on sets of numbers, this notation might be inappropriate or ambiguous, since the number 0 is not always least. An example is given by the above divisibility order |, where 1

SECTION 60

#1732772590931

4278-431: The relation <, which is well-founded, is used instead of the relation ≤, which is not. In some texts, the definition of a well-founded relation is changed from the definition above to include these conventions. Order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations . It provides a formal framework for describing statements such as "this

4347-400: The relation symbol ≤ in this definition.) The disjoint union of two posets is another typical example of order construction, where the order is just the (disjoint) union of the original orders. Every partial order ≤ gives rise to a so-called strict order <, by defining a < b if a ≤ b and not b ≤ a . This transformation can be inverted by setting a ≤ b if a < b or

4416-399: The structures that are studied in order theory employ order relations with further properties. In fact, even some relations that are not partial orders are of special interest. Mainly the concept of a preorder has to be mentioned. A preorder is a relation that is reflexive and transitive, but not necessarily antisymmetric. Each preorder induces an equivalence relation between elements, where

4485-413: The subset order on a collection of sets : though the set of birds and the set of dogs are both subsets of the set of animals, neither the birds nor the dogs constitutes a subset of the other. Those orders like the "subset-of" relation for which there exist incomparable elements are called partial orders ; orders for which every pair of elements is comparable are total orders . Order theory captures

4554-420: The underlying set of a topology is given by the so-called specialization order , that is actually a partial order if the topology is T 0 . Conversely, in order theory, one often makes use of topological results. There are various ways to define subsets of an order which can be considered as open sets of a topology. Considering topologies on a poset ( X , ≤) that in turn induce ≤ as their specialization order,

4623-408: The well-founded relation ( N , S ) , where N is the set of all natural numbers , and S is the graph of the successor function x ↦ x +1 . Then induction on S is the usual mathematical induction , and recursion on S gives primitive recursion . If we consider the order relation ( N , <) , we obtain complete induction , and course-of-values recursion . The statement that ( N , <)

4692-478: The well-founded relation is set membership on the universal class, the technique is known as ∈-induction . See those articles for more details. Well-founded relations that are not totally ordered include: Examples of relations that are not well-founded include: If ( X , <) is a well-founded relation and x is an element of X , then the descending chains starting at x are all finite, but this does not mean that their lengths are necessarily bounded. Consider

4761-500: The wide practical usage of orders, numerous special kinds of ordered sets have been defined, some of which have grown into mathematical fields of their own. In addition, order theory does not restrict itself to the various classes of ordering relations, but also considers appropriate functions between them. A simple example of an order theoretic property for functions comes from analysis where monotone functions are frequently found. This section introduces ordered sets by building upon

#930069