|
|
| Line 1: |
Line 1: |
| {{About|the binary relation|the graph vertex ordering|Depth-first search|other uses}}
| | In [[mathematics]], '''pointless topology''' (also called '''point-free''' or '''pointfree topology''') is an approach to [[topology]] that avoids mentioning points. The name 'pointless topology' is due to [[John von Neumann]].<ref>Garrett Birkhoff, ''VON NEUMANN AND LATTICE THEORY'', ''John Von Neumann 1903-1957'', J. C. Oxtoley, B. J. Pettis, American Mathematical Soc., 1958, page 50-5 </ref> The ideas of pointless topology are closely related to [[mereotopology| mereotopologies]] in which regions (sets) are treated as foundational without explicit reference to underlying point sets. |
|
| |
|
| In [[mathematics]], especially in [[order theory]], a '''preorder''' or '''quasi-order''' is a [[binary relation]] that is [[reflexive relation|reflexive]] and [[transitive relation|transitive]]. All [[partial order]]s and [[equivalence relation]]s are preorders, but preorders are more general.
| | ==General concepts== |
| | Traditionally, a [[topological space]] consists of a [[Set (mathematics)|set]] of [[point (topology)|points]], together with a system of [[open set]]s. These open sets with the operations of [[intersection (set theory)|intersection]] and [[union (set theory)|union]] form a [[lattice (order)|lattice]] with certain properties. Pointless topology then studies lattices like these abstractly, without reference to any underlying set of points. Since some of the so-defined lattices do not arise from topological spaces, one may see the [[category theory|category]] of pointless topological spaces, also called [[Frames and locales|locales]], as an extension of the category of ordinary topological spaces. |
|
| |
|
| The name 'preorder' comes from the idea that preorders are 'almost' (partial) orders, but not quite; they're neither [[anti-symmetric relation|anti-symmetric]] nor [[symmetric relation|symmetric]]. Because a preorder is a binary relation, the symbol ≤ can be used as the notational device for the relation. However, because they are not anti-symmetric, some of the ordinary intuition that a student may have with regards to the symbol ≤ may not apply. On the other hand, a pre-order can be used, in a straightforward fashion, to define a partial order and an equivalence relation. Doing so, however, is not always useful or worth-while, depending on the problem domain being studied.
| | ==Categories of frames and locales== |
| | Formally, a '''frame''' is defined to be a [[lattice (order)|lattice]] ''L'' in which finite [[meet]]s [[Distributivity (order theory)|distribute]] over arbitrary [[join]]s, i.e. every (even infinite) subset {''a''<sub>i</sub>} of ''L'' has a [[supremum]] ⋁''a''<sub>''i''</sub> such that |
|
| |
|
| In words, when ''a'' ≤ ''b'', one may say that ''b'' ''covers'' ''a'' or that ''b'' ''precedes'' ''a'', or that ''b'' ''reduces'' to ''a''. Occasionally, the notation ← or <math>\lesssim</math> is used instead of ≤.
| | :<math>b \wedge \left( \bigvee a_i\right) = \bigvee \left(a_i \wedge b\right)</math> |
|
| |
|
| To every preorder, there corresponds a [[directed graph]], with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. The converse is not true: most directed graphs are neither reflexive nor transitive. Note that, in general, the corresponding graphs may be [[cyclic graph]]s: preorders may have cycles in them. A preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a [[directed acyclic graph]]. A preorder that is symmetric is an equivalence relation; it can be thought of as having lost the direction markers on the edges of the graph. In general, a preorder may have many disconnected components. The [[diamond lemma]] is an important result for certain kinds of preorders.
| | for all ''b'' in ''L''. These frames, together with lattice homomorphisms that respect arbitrary suprema, form a category. The [[dual (category theory)|dual]] of the '''category of frames''' is called the '''category of locales''' and generalizes the category '''[[category of topological spaces|Top]]''' of all topological spaces with continuous functions. The consideration of the dual category is motivated by the fact that every [[continuous function (topology)|continuous map]] between topological spaces ''X'' and ''Y'' induces a map between the lattices of open sets ''in the opposite direction'' as for every continuous function ''f'': ''X'' → ''Y'' and every open set ''O'' in ''Y'' the [[inverse image]] ''f''<sup> -1</sup>(''O'') is an open set in ''X''. |
|
| |
|
| Many order theoretical definitions for partially ordered sets can be generalized to preorders, but the extra effort of generalization is rarely needed.{{Citation needed|date=July 2010}}
| | ==Relation to point-set topology== |
| | It is possible to translate most concepts of point-set topology into the context of locales, and prove analogous theorems. While many important theorems in point-set topology require the [[axiom of choice]], this is not true for some of their analogues in locale theory. This can be useful if one works in a [[topos]] that does not have the axiom of choice. |
|
| |
|
| ==Formal definition== | | The concept of "product of locales" diverges slightly from the concept of "[[Product_topology|product of topological spaces]]", and this divergence has been called a disadvantage of the locale approach. |
| | Others{{who|date=November 2010}} claim that the locale product is more natural, and point to several "desirable" properties{{Which?|date=November 2010}} not shared by products of topological spaces. |
|
| |
|
| Consider some [[Set (mathematics)|set]] ''P'' and a [[binary relation]] ≤ on ''P''. Then ≤ is a '''preorder''', or '''quasiorder''', if it is [[reflexive relation|reflexive]] and [[transitive relation|transitive]], i.e., for all ''a'', ''b'' and ''c'' in ''P'', we have that:
| | For almost all spaces (more precisely for [[sober space]]s), the topological product and the localic product have the same set of points. The products differ in how equality between sets of open rectangles, the canonical base for the product topology, is defined: equality for the topological product means the same set of points is covered; |
| | equality for the localic product means provable equality using the frame axioms. As a result, two open sublocales of a localic product may contain exactly the same points without being equal. |
|
| |
|
| :''a'' ≤ ''a'' (reflexivity)
| | A point where locale theory and topology diverge much more strongly is the concept of subspaces vs. sublocales. |
| : if ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (transitivity)
| | The rational numbers have ''c'' subspaces but 2<sup>''c''</sup> sublocales. The proof for the latter statement is due to [[John Isbell]], and uses the fact that the rational numbers have ''c'' many pairwise almost disjoint (= finite intersection) closed subspaces. |
| | |
| ''Note that an alternate definition of preorder requires the relation to be [[irreflexive relation|irreflexive]]. However, as this article is examining preorders as a logical extension of non-strict partial orders, the current definition is more intuitive.''
| |
| | |
| A set that is equipped with a preorder is called a '''preordered set''' (or '''proset'''). | |
| | |
| If a preorder is also [[antisymmetric relation|antisymmetric]], that is, ''a'' ≤ ''b'' and ''b'' ≤ ''a'' implies ''a'' = ''b'', then it is a [[partially ordered set|partial order]].
| |
| | |
| On the other hand, if it is [[symmetric relation|symmetric]], that is, if ''a'' ≤ ''b'' implies ''b'' ≤ ''a'', then it is an [[equivalence relation]].
| |
| | |
| A preorder which is preserved in all contexts (i.e. respected by all functions on ''P'') is called a '''precongruence'''.
| |
| A precongruence which is also [[symmetric relation|symmetric]] (i.e. is an [[equivalence relation]]) is a [[congruence relation]].
| |
| | |
| Equivalently, a preordered set ''P'' can be defined as a [[category theory|category]] with [[object (category theory)|objects]] the elements of ''P'', and each [[hom-set]] having at most one element (one for objects which are related, zero otherwise).
| |
| | |
| Alternately, a preordered set can be understood as an [[enriched category]], enriched over the category '''2''' = (0→1).
| |
| | |
| ==Examples==
| |
| * The [[reachability]] relationship in any [[directed graph]] (possibly containing cycles) gives rise to a preorder, where ''x'' ≤ ''y'' in the preorder if and only if there is a path from ''x'' to ''y'' in the directed graph. Conversely, every preorder is the reachability relationship of a directed graph (for instance, the graph that has an edge from ''x'' to ''y'' for every pair (''x'', ''y'') with ''x'' ≤ ''y''). However, many different graphs may have the same reachability preorder as each other. In the same way, reachability of [[directed acyclic graph]]s, directed graphs with no cycles, gives rise to [[partially ordered set]]s (preorders satisfying an additional anti-symmetry property).
| |
| * Every [[finite topological space]] gives rise to a preorder on its points, in which ''x'' ≤ ''y'' if and only if ''x'' belongs to every neighborhood of ''y'', and every finite preorder can be formed as the [[Specialization_(pre)order|specialization preorder]] of a topological space in this way. That is, there is a [[bijection|1-to-1 correspondence]] between finite topologies and finite preorders. However, the relation between infinite topological spaces and their specialization preorders is not 1-to-1.
| |
| * A [[net (mathematics)|net]] is a [[directed set|directed]] preorder, that is, each pair of elements has an [[upper bound]]. The definition of convergence via nets is important in [[topology]], where preorders cannot be replaced by [[partially ordered set]]s without losing important features.
| |
| * The relation defined by <math>x \le y</math> [[iff]] <math>f(x) \le f(y)</math>, where ''f'' is a function into some preorder.
| |
| * The relation defined by <math>x \le y</math> [[iff]] there exists some [[injective function|injection]] from ''x'' to ''y''. Injection may be replaced by [[surjection]], or any type of structure-preserving function, such as [[ring homomorphism]], or [[permutation]].
| |
| * The [[embedding]] relation for countable [[total order]]ings.
| |
| * The [[graph-minor]] relation in [[graph theory]].
| |
| * A [[category (mathematics)|category]] with at most one [[morphism]] between any pair of objects is a preorder. Such categories are called [[thin category|thin]]. In this sense, categories "generalize" preorders by allowing more than one relation between objects: each morphism is a distinct (named) preorder relation.
| |
| | |
| In computer science, one can find examples of the following preorders.
| |
| * The [[Subtype|subtyping]] relations are usually preorders.
| |
| * [[Simulation preorder]]s are preorders (hence the name).
| |
| * [[Reduction relation]]s in [[abstract rewriting system]]s.
| |
| | |
| Example of a [[Strict weak ordering#Total preorders|total preorder]]:
| |
| * [[Preference]], according to common models.
| |
| | |
| ==Uses==
| |
| Preorders play a pivotal role in several situations:
| |
| * Every preorder can be given a topology, the [[Alexandrov topology]]; and indeed, every preorder on a set is in one-to-one correspondence with an Alexandrov topology on that set.
| |
| * Preorders may be used to define [[interior algebra]]s.
| |
| * Preorders provide the [[Kripke semantics]] for certain types of [[modal logic]].
| |
| | |
| ==Constructions==
| |
| | |
| Every binary relation R on a set S can be extended to a preorder on S by taking the [[transitive closure]] and [[Binary relation#Operations on binary relations|reflexive closure]], R<sup>+=</sup>. The transitive closure indicates path connection in R: ''x'' R<sup>+</sup> ''y'' if and only if there is an R-[[Path (graph theory)|path]] from ''x'' to y.
| |
| | |
| Given a preorder <math>\lesssim</math> on S one may define an [[equivalence relation]] ~ on S such that ''a'' ~ ''b'' if and only if ''a'' <math>\lesssim</math> ''b'' and ''b'' <math>\lesssim</math> ''a''. (The resulting relation is reflexive since a preorder is reflexive, transitive by applying transitivity of the preorder twice, and symmetric by definition.)
| |
| | |
| Using this relation, it is possible to construct a partial order on the quotient set of the equivalence, S / ~, the set of all [[equivalence class]]es of ~. Note that if the preorder is R<sup>+=</sup>, S / ~ is the set of R-[[Cycle (graph theory)|cycle]] equivalence classes: ''x'' ∈ [''y''] if and only if ''x'' = ''y'' or ''x'' is in an R-cycle with y. In any case, on S / ~ we can define [''x''] ≤ [''y''] if and only if ''x'' <math>\lesssim</math> ''y''. By the construction of ~, this definition is independent of the chosen representatives and the corresponding relation is indeed well-defined. It is readily verified that this yields a partially ordered set.
| |
| | |
| Conversely, from a partial order on a partition of a set S one can construct a preorder on S. There is a 1-to-1 correspondence between preorders and pairs (partition, partial order).
| |
| | |
| For a preorder "<math>\lesssim</math>", a relation "<" can be defined as ''a'' < ''b'' if and only if (''a'' <math>\lesssim</math> ''b'' and not ''b'' <math>\lesssim</math> ''a''), or equivalently, using the equivalence relation introduced above, (''a'' <math>\lesssim</math> ''b'' and not ''a'' ~ ''b''). It is a [[strict partial order]]; every strict partial order can be the result of such a construction. If the preorder is anti-symmetric, hence a partial order "≤", the equivalence is equality, so the relation "<" can also be defined as ''a'' < ''b'' if and only if (''a'' ≤ ''b'' and ''a'' ≠ ''b'').
| |
| | |
| (Alternatively, for a preorder "<math>\lesssim</math>", a relation "<" can be defined as ''a'' < ''b'' if and only if (''a'' <math>\lesssim</math> ''b'' and ''a'' ≠ ''b''). The result is the reflexive reduction of the preorder. However, if the preorder is not anti-symmetric the result is not transitive, and if it is, as we have seen, it is the same as before.)
| |
| | |
| Conversely we have ''a'' <math>\lesssim</math> ''b'' if and only if ''a'' < ''b'' or ''a'' ~ ''b''. This is the reason for using the notation "<math>\lesssim</math>"; "≤" can be confusing for a preorder that is not anti-symmetric, it may suggest that ''a'' ≤ ''b'' implies that ''a'' < ''b'' or ''a'' = ''b''.
| |
| | |
| Note that with this construction multiple preorders "<math>\lesssim</math>" can give the same relation "<", so without more information, such as the equivalence relation, "<math>\lesssim</math>" cannot be reconstructed from "<". Possible preorders include the following:
| |
| *Define ''a'' ≤ ''b'' as ''a'' < ''b'' or ''a'' = ''b'' (i.e., take the reflexive closure of the relation). This gives the partial order associated with the strict partial order "<" through reflexive closure; in this case the equivalence is equality, so we don't need the notations <math>\lesssim</math> and ~.
| |
| *Define ''a'' <math>\lesssim</math> ''b'' as "not ''b'' < ''a''" (i.e., take the inverse complement of the relation), which corresponds to defining ''a'' ~ ''b'' as "neither ''a'' < ''b'' nor ''b'' < ''a''"; these relations <math>\lesssim</math> and ~ are in general not transitive; however, if they are, ~ is an equivalence; in that case "<" is a [[strict weak order]]. The resulting preorder is [[total relation|total]], that is, a [[total preorder]].
| |
| | |
| ==Number of preorders==
| |
| {{Number of relations}}
| |
| | |
| As explained above, there is a 1-to-1 correspondence between preorders and pairs (partition, partial order). Thus the number of preorders is the sum of the number of partial orders on every partition. For example:
| |
| *for n=3:
| |
| **1 partition of 3, giving 1 preorder
| |
| **3 partitions of 2+1, giving 3 × 3 = 9 preorders
| |
| **1 partition of 1+1+1, giving 19 preorders
| |
| :i.e. together 29 preorders.
| |
| *for n=4:
| |
| **1 partition of 4, giving 1 preorder
| |
| **7 partitions with two classes (4 of 3+1 and 3 of 2+2), giving 7 × 3 = 21 preorders
| |
| **6 partitions of 2+1+1, giving 6 × 19 = 114 preorders
| |
| **1 partition of 1+1+1+1, giving 219 preorders
| |
| :i.e. together 355 preorders.
| |
| | |
| ==Interval==
| |
| For ''a'' <math>\lesssim</math> ''b'', the [[interval (mathematics)|interval]] [''a'',''b''] is the set of points ''x'' satisfying ''a'' <math>\lesssim</math> ''x'' and ''x'' <math>\lesssim</math> ''b'', also written ''a'' <math>\lesssim</math> ''x'' <math>\lesssim</math> ''b''. It contains at least the points ''a'' and ''b''. One may choose to extend the definition to all pairs (''a'',''b''). The extra intervals are all empty.
| |
| | |
| Using the corresponding strict relation "<", one can also define the interval (''a'',''b'') as the set of points ''x'' satisfying ''a'' < ''x'' and ''x'' < ''b'', also written ''a'' < ''x'' < ''b''. An open interval may be empty even if ''a'' < ''b''.
| |
| | |
| Also [''a'',''b'') and (''a'',''b''] can be defined similarly.
| |
|
| |
|
| ==See also== | | ==See also== |
| *[[partially ordered set|partial order]] - preorder that is [[antisymmetric relation|antisymmetric]] | | * [[Heyting algebra]]. A locale is a [[complete Heyting algebra]]. |
| *[[equivalence relation]] - preorder that is [[Symmetric relation|symmetric]] | | * Details on the relationship between the category of topological spaces and the category of locales, including the explicit construction of the duality between [[sober space]]s and spatial locales, are to be found in the article on [[Stone duality]]. |
| *[[Strict weak ordering#Total preorders|total preorder]] - preorder that is [[Total relation|total]]
| | * [[Point-free geometry]] |
| *[[total order]] - preorder that is antisymmetric and total | | * [[Mereology]] |
| *[[directed set]]
| | * [[Mereotopology]] |
| *[[category of preordered sets]]
| | * [[Tacit programming]] |
| *[[prewellordering]]
| |
| *[[preordered class]] | |
| *[[Well-quasi-ordering]] | |
| *[[Newman's lemma]] | |
|
| |
|
| ==References== | | ==References== |
| {{refbegin}} | | {{reflist}} |
| * {{Citation | | *[[Peter Johnstone (mathematician)|Johnstone, Peter T.]], 1983, "[http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183550014 The point of pointless topology,]" ''Bulletin of the American Mathematical Society 8(1)'': 41-53. |
| | last = Schröder | first = Bernd S. W.
| |
| | title = Ordered Sets: An Introduction
| |
| | place = Boston
| |
| | publisher = Birkhäuser
| |
| | year = 2002
| |
| | isbn = 0-8176-4128-9}}
| |
| {{refend}}
| |
|
| |
|
| [[Category:Order theory]] | | [[Category:Category theory]] |
| [[Category:Mathematical relations]] | | [[Category:General topology]] |
|
| |
|
| [[cs:Kvaziuspořádání]]
| | [[es:Topología sin puntos]] |
| [[da:Præordning]]
| |
| [[de:Quasiordnung]]
| |
| [[es:Conjunto preordenado]] | |
| [[fr:Pré-ordre]]
| |
| [[it:Preordine]]
| |
| [[he:קדם סדר]]
| |
| [[pl:Praporządek]]
| |
| [[ru:Предпорядок]]
| |
| [[sk:Kváziusporiadanie]]
| |
| [[uk:Передпорядок]]
| |
| [[zh:预序关系]]
| |
In mathematics, pointless topology (also called point-free or pointfree topology) is an approach to topology that avoids mentioning points. The name 'pointless topology' is due to John von Neumann.[1] The ideas of pointless topology are closely related to mereotopologies in which regions (sets) are treated as foundational without explicit reference to underlying point sets.
General concepts
Traditionally, a topological space consists of a set of points, together with a system of open sets. These open sets with the operations of intersection and union form a lattice with certain properties. Pointless topology then studies lattices like these abstractly, without reference to any underlying set of points. Since some of the so-defined lattices do not arise from topological spaces, one may see the category of pointless topological spaces, also called locales, as an extension of the category of ordinary topological spaces.
Categories of frames and locales
Formally, a frame is defined to be a lattice L in which finite meets distribute over arbitrary joins, i.e. every (even infinite) subset {ai} of L has a supremum ⋁ai such that
for all b in L. These frames, together with lattice homomorphisms that respect arbitrary suprema, form a category. The dual of the category of frames is called the category of locales and generalizes the category Top of all topological spaces with continuous functions. The consideration of the dual category is motivated by the fact that every continuous map between topological spaces X and Y induces a map between the lattices of open sets in the opposite direction as for every continuous function f: X → Y and every open set O in Y the inverse image f -1(O) is an open set in X.
Relation to point-set topology
It is possible to translate most concepts of point-set topology into the context of locales, and prove analogous theorems. While many important theorems in point-set topology require the axiom of choice, this is not true for some of their analogues in locale theory. This can be useful if one works in a topos that does not have the axiom of choice.
The concept of "product of locales" diverges slightly from the concept of "product of topological spaces", and this divergence has been called a disadvantage of the locale approach.
OthersTemplate:Who claim that the locale product is more natural, and point to several "desirable" propertiesTemplate:Which? not shared by products of topological spaces.
For almost all spaces (more precisely for sober spaces), the topological product and the localic product have the same set of points. The products differ in how equality between sets of open rectangles, the canonical base for the product topology, is defined: equality for the topological product means the same set of points is covered;
equality for the localic product means provable equality using the frame axioms. As a result, two open sublocales of a localic product may contain exactly the same points without being equal.
A point where locale theory and topology diverge much more strongly is the concept of subspaces vs. sublocales.
The rational numbers have c subspaces but 2c sublocales. The proof for the latter statement is due to John Isbell, and uses the fact that the rational numbers have c many pairwise almost disjoint (= finite intersection) closed subspaces.
See also
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
es:Topología sin puntos
- ↑ Garrett Birkhoff, VON NEUMANN AND LATTICE THEORY, John Von Neumann 1903-1957, J. C. Oxtoley, B. J. Pettis, American Mathematical Soc., 1958, page 50-5