MONOTONE SET FUNCTIONS, FIXED POINTS, AND CECH CLOSURE FUNCTIONS
in [Math]
|
From: Dave L. Renfro on 3 Jul 2005 13:29 I'm starting a new thread because others who might be interested may overlook this post if I put it in the thread "Finite topology spaces", and to make this post easier to show up for anyone in the future using the sci.math archives in order to look up something about what I discuss here. Herman Rubin wrote: >> What one can do with spaces with weak separation axioms? >> In some work of mine on the topology of random variables >> on topological spaces, I found it convenient to use finite >> non-Hausdorff spaces, and the results of assignment >> programming. William Elliot replied: > In a brief exploration of spaces with finite topology, > I discovered they are Scott spaces and their structure > depends upon the collection of minimally open sets. > > Have others experience with finite topologies or finite > spaces and their topology? What was discovered? > Of what use are they? The Zariski topology for commutative rings (each closed set is the collection of all prime ideals containing a given prime ideal) is very important in algebraic geometry and is almost never Hausdorff and rarely even T_1. For example, in the case of an integral domain, the point corresponding to the prime ideal {0} is a dense subset of the space. This space is always T_0, however. For some other ways that non-T_2 spaces can arise, see the sci.math.research thread "Non-Hausdorff Topological Spaces" (google for it). In the early 1960's Preston C. Hammer was motivated by some problems in convex geometry to a study of more general topological notions that he collectively called "extended topology". Much of this was published in 1961-62 in the journal Nieuw Archief voor Wiskunde (Series 3), and then continued in the next two to three years in some other journals. An early summary of his work was published in Proceedings of Symposia in Pure Mathematics (American Mathematical Society) 7 (1963), 305-316. Also: (a) google the phrase "extended topology" together with the word "hammer"; (b) search mathematical reviews (if you have access) using "anywhere=hammer" AND "anywhere=extended topology"; (c) search Euler (publicly available) for Preston Hammer as the author, http://www.emis.de/projects/EULER/search?q=cr%3Apreston+Hammer Eduard Cech extensively studied a generalization of topology that arises by using closure functions that satisfy all the axioms of the Kuratowski closure functions except idempotency. See his 893 page book "Topological Spaces", the revised English edition published by John Wiley & Sons in 1966. (Hammer's "extended topology" involves closure functions that are, for the most part, more general still.) These developments were separate, as were some others I'm aware of, but in recent years it seems that they're now being applied to systems theory and some other areas I know next to nothing about, and in many of these applications finite "spaces" are about the only types considered. For a nice abstract survey of these generalized topological notions, see the manuscript "Basic properties of closure spaces" by Bärbel M. R. Stadler and Peter F. Stadler (the union in their equation 11 on p. 7 should be an intersection, by the way): http://www.tbi.univie.ac.at/papers/Abstracts/01-pfs-007-subl2.pdf I've written a manuscript based on a problem set I gave in a second semester general topology class a couple of years ago that attempts to organize this zoo of generalized topological notions into something that would be of more mathematical appeal than anything I've come across. However, it's not finished. (It's one of the many things I've spent a lot of time on and, for some reason, grew tired of working on before getting it completely finished. My goal in the next few years is to go back to some of these manuscripts that aren't stale anymore and finish them.) In outline form, leaving out many of the side-issues and the numerous references, here's my attempt at organizing these notions in a way that I think would have some appeal to a pure mathematician. TABLE OF CONTENTS 1. CRITERIA FOR A SET FUNCTION TO BE MONOTONE 2. THE MONOTONE CLOSURE OF A SET FUNCTION 3. THE LEAST AND GREATEST FIXED POINTS OF A MONOTONE FUNCTION 4. SOME EXAMPLES OF FIXED POINTS OF MONOTONE FUNCTIONS 5. THE LEAST FIXED POINT OF A MONOTONE FUNCTION BY TRANSFINITE INDUCTION 6. MONOTONE FUNCTIONS DO NOT HAVE TO PRESERVE UNIONS 7. CECH CLOSURE FUNCTIONS 8. KURATOWSKI CLOSURE FUNCTIONS 9. AN UNSOLVED PROBLEM NOTATION: P(X) is the collection of all subsets of the set X. leq is "less than or equal to" geq is "greater than or equal to" 1. CRITERIA FOR A SET FUNCTION TO BE MONOTONE Let X be a set and T:P(X) --> P(X) be an arbitrary set function on X. The following properties are equivalent: (a) For all A,B in P(X), we have A subset B ==> T(A) subset T(B). (b) For all A,B in P(X), we have T(A) union T(B) subset T(A union B). (c) For all A,B in P(X), we have T(A intersect B) subset T(A) intersect T(B). If T satisfies any of these equivalent conditions, we say that T is monotone (or isotone). 2. THE MONOTONE CLOSURE OF A SET FUNCTION Let X be a set, T:P(X) --> P(X) be arbitrary, and b in X. We define the T-interior function T_i:P(X) --> P(X), the collection N(T,b) (a subset of P(X)) of T-neighborhoods at b, and the T-closure function T_c:P(X) --> P(X) by T_i(A) = complement of T(complement of A) [complements are relative to X] N(T,b) = the collection of all elements N in P(X) such that b belongs to T_i(N) T_c(A) = {b in X: A intersect N is nonempty for each N belonging to N(T,b)} If T_1 and T_2 are set functions on X, we say that T_1 leq T_2 ("less than or equal to") iff for each A in P(X) we have T_1(A) subset T_2(A). Then we have the following results. Note that (b), (d), and (e) can be summarized by saying that T_c is the largest monotone function less than or equal to T. (a) T_c(A) = union{T(B): A subset B} (b) T_c leq T (c) T_1 leq T_2 ==> (T_1)_c leq (T_2)_c (d) T_c:P(X) --> P(X) is monotone (e) If T' is monotone and T' leq T, the T' leq T_c. Hence: (1) T monotone ==> T = T_c (2) (T_c)_c = T_c 3. THE LEAST AND GREATEST FIXED POINTS OF A MONOTONE FUNCTION Let X be a set and T:P(X) --> P(X) be monotone. Define E- and E+ by E- = intersect{A in P(X): T(A) subset A} E+ = union{A in P(X): A subset T(A)} Then we have the following: (a) T(E-) = E- (b) T(E+) = E+ (c) T(E) = E ==> E- subset E subset E+ 4. SOME EXAMPLES OF FIXED POINTS OF MONOTONE FUNCTIONS See if you can characterize their fixed points, or at least tell what their smallest and largest fixed points are. (a) The identity map from P(X) to P(X). (b) The closure function and interior function of a topological space. (c) Let V be a vector space and define T:P(V) --> P(V) by T(A) = the linear span of A. (d) Define T:P(R^n) --> P(R^n) by letting T(A) be the collection of all points in R^n that lie between each pair of points in A. That is, T(A) is the union of all the (closed) line segments whose endpoints belong to A. (e) Let X be a set and define T:P(P(X)) --> P(P(X)) by T(U) = {union(k=1 to inf): A_k in U for each k} union {complement of A: A in U} (f) Let X be a set and V be an element of P(P(X)). Define T_V:P(P(X)) --> P(P(X)) by (T_V)(U) = {empty set, X} union V union T(U), where T is the function in (e) above. Show that E- in this case is the sigma-algebra generated by V. (g) Let f:X --> Y and g:Y --> X be one-to-one functions and define T:P(X) --> P(X) by T(A) = X-complement of g[Y-complement of f[A]]. (By f[A], I mean {f(a): a in A}, and similarly for g.) Note: The Schroder-Bernstein Theorem can be proved by considering any fixed point of T. See Abraham A. Fraenkel's book "Abstract Set Theory" (pp. 76-77) for some history of this method. See also Francis P. Callahan and Samuel G. Kneale, "A note on the Schroeder-Bernstein theorem", Amer. Math. Monthly 64 (1957), 423-424 and Ignace I. Kolodner, "A simple proof of the Schroder-Bernstein theorem", Amer. Math. Monthly 74 (1967), 995-996. It's also in some textbooks, such as Willard's "Topology" (Exercise 1J) and Hrbacek and Jech's "Introduction to Set Theory", 3'nd edition (Exercises 1.10 to 1.14 on p. 69). 5. THE LEAST FIXED POINT OF A MONOTONE FUNCTION BY TRANSFINITE INDUCTION Let X be a set and T:P(X) --> P(X) be monotone. For each ordinal alpha we define the alpha'th iterate T^alpha:P(X) --> P(X) of T by T^alpha(A) = T(union{T^beta(A): beta < alpha}) Then we have the following: (a) T^alpha is monotone for each ordinal alpha. (b) alpha leq beta ==> T^alpha leq T^beta. (c) There exists an ordinal lambda < 'the successor cardinal of the cardinality of X' such that for all alpha geq lambda ("greater than or equal to") we have T^alpha = T^lambda. (d) T^lambda(empty set) = E-, where lambda is from (c) and E- is the least fixed point of T. Note: The least such ordinal lambda that satisfies (c) is called the "closure ordinal" for T, and this ordinal is often denoted by |T|. For example, the closure ordinals for (b), (c), and (d) (with V = open sets) in #4 above are 1, omega_0, and omega_1, respectively. The definition of E- given in #3 above is often called "impredicative" because the collection of sets that we intersect in order to get E- includes the set E- itself. Impredicative, as I understand it, roughly means "circular from a constructive point of view". A set is impredicatively defined if membership to it is defined by using a property or a condition that involves all the elements of the set being defined. The ordinal |T| is a measure of the "degree of defineability" of E-. Axiomatic theories in mathematical logic often contain many definitions that can be cast into the form of "E- exists" for various suitably chosen monotone functions. This is the "top-down" version of an inductive definition, where something is defined as the "smallest such-and-such object satisfying something-or-other". The proof-theoretic ordinal of an axiomatic theory is defined to be the supremum of all the closure ordinals of monotone functions that are (strictly) needed for that theory. The proof-theoretic ordinal of Peano Arithmetic, for instance, is known to be the ordinal epsilon_0 = w^w^w^... I've written several posts that touch on these issues and their connection with the Cantor-Bendixson theorem. These three are probably the most detailed: http://groups-beta.google.com/group/sci.math/msg/a31647549c87f4cf http://groups-beta.google.com/group/sci.math/msg/0f845bd02470ee2b Math Forum sci.math post on January 29, 2002 http://mathforum.org/kb/message.jspa?messageID=360417 6. MONOTONE FUNCTIONS DO NOT HAVE TO PRESERVE UNIONS From #1 we know that T:P(X) --> P(X) is monotone if and only if T(A) union T(B) is a subset of T(A union B). Give an example of a monotone set function T such that T(A) union T(B) is not equal to T(A union B). 7. CECH CLOSURE FUNCTIONS We say that T:P(X) --> P(X) is a "Cech closure function" if T satisfies the following for all A,B in P(X): (K1) T(empty set) = empty set (K2) T(A union B) = T(A) union T(B) (K3) A subset T(A) Then we have the following: (a) There exists a function T:P(X) --> P(X) satisfying (K1) and (K2), but not (K3). Note: Spaces defined by a "closure function" satisfying (K1) and (K2) are called "base operator spaces" in the book "Fine Topology Methods in Real Analysis and Potential Theory" by Jaroslav Lukes, Jan Maly, and Ludek Zajicek (Springer-Verlag Lecture Notes in Mathematics #1189, 1986). (b) Assume T:P(X) --> P(X) satisfies (K1) and (K2). Define T':P(X) --> P(X) by T'(A) = A union T(A). Then we have: (1) T' is a Cech closure function. (2) If T* is a Cech closure function such that T leq T*, then T' leq T*. Thus, T' is the smallest Cech closure function larger than T. (Compare with #2(e) above.) (c) If T_1 and T_2 are Cech closure functions, then their composition (T_1)(T_2) is a Cech closure function. (d) If {T_j: j in J} is a nonempty collection of Cech closure functions, then T is a Cech closure function where T(A) = union{(T_j)(A): j in J}. In other words, if each T_j is a Cech closure function, then sup{T_j: j in J} exists and is a Cech closure function. Note: "leq" defines a partial ordering on the collection of functions from P(X) to P(X). Hence, "leq" defines a partial ordering on the subcollection of Cech closure functions on X. It is easy to prove that the supremum of a set of elements in a partially ordered set is unique if it exists. By definition, S = sup{T_j: j in J} (if it exists) is a function from P(X) to P(X) such that (1) T_j leq S for each j in J, and (2) T_j leq S* for each j in J implies S leq S*. (e) Let X be a set and d:X^2 --> [0, inf) satisfy d(x,x) = 0 and d(x,y) = d(y,x) for all x,y in X. Then T:P(X) --> P(X) is a Cech closure function, where T(A) = {x in X: inf{d(x,a): a in A} = 0}. Note: If d additionally satisfies the triangle inequality, then (X,d) would be a pseudometric space. In Cech's book these spaces (X,d) (without the triangle inquality having to hold) are called "semi-pseudometric spaces". Semi-metric spaces are "metric spaces without the triangle inequality having to hold" (i.e. semi-pseudometric spaces such that d(x,y) = 0 implies x=y). Each pseudometric space gives rise to a topological space (define the open sets the same way you do for metric spaces), but this is not the case for semi-metric spaces. However, each semi-metric space does give rise to a Cech closure space. Indeed, this is even the case for semi-pseudometric spaces. I briefly discussed semi-metric spaces and gave several references for them in this sci.math post (which never made it to google, so many of you probably never saw it): Math Forum sci.math post on October 28, 2004 http://mathforum.org/kb/message.jspa?messageID=3388836 (f) If T:P(X) --> P(X) is a Cech closure function, we call its fixed points the T-closed sets of X, and the complements of these fixed points the T-open sets of X. The collection tau_T defined by tau_T = {A in P(X): A is T-open} defines a topology on X. 8. KURATOWSKI CLOSURE FUNCTIONS We say that T:P(X) --> P(X) is a "Kuratowski closure function" if T is a Cech closure function that satisfies (K4) TT = T. The main point of the following results is that every ordinal-iterate T^alpha of a Cech closure function T is a Cech closure function, and each T^alpha generates the _same_ topology on X. These iterates are distinct from each other until they ultimately stabilize, and the set function they stabilize to is the Kuratowski closure function associated to this topology on X. (a) Find a Cech closure function T on the reals such that all of its finite iterates T, T^2, T^3, ... are distinct and none of these iterates is a Kuratowski closure function. (b) Let T:P(X) --> P(X) be a Cech closure function. For each ordinal alpha, we define the alpha'th iterate T^alpha of T by transfinite induction: T^0 = T T^(alpha + 1) = T(T^alpha) T^lambda = sup{T^alpha: alpha < lambda}, if lambda is a nonzero limit ordinal Then alpha leq beta ==> T^alpha leq T^beta. (c) For each ordinal alpha we have tau_(T_alpha) = tau_T. That is, all the iterates of T give rise to the same topology on X. (d) Let T:P(X) --> P(X) be a Cech closure function and let T^alpha be the alpha'th iterate of T. Then there exists an ordinal lambda < 'the successor cardinal of the cardinality of X' such that, for all alpha greater than or equal to lambda, we have T^alpha = T^lambda. (e) Let |T| be the least such ordinal in (d) above. Then 0 leq alpha and beta leq |T|, with alpha different from beta, implies T^alpha is not equal to T^beta. That is, all the iterates of T before the least such ordinal lamda in (d) are pairwise different. (f) Let T:P(X) --> P(X) be a Cech closure function and let lambda be an ordinal satisfying the condition in (d) above. Then T^lambda = Cl_tau, where Cl_tau is the Kuratowski closure function for the topology defined by the T-closed sets. (g) Let (X,tau) be a topological space and Cl_tau be the Kuratowski closure function associated with (X,tau). Then Cl_tau = sup{T: T is a Cech closure function on X such that tau_T = tau}. Note: Each T^alpha belongs to the set {T: T is a Cech closure function on X such that tau_T = tau}, but since there might be other Cech closure functions besides the T^alpha's belonging to this set, (g) is not automatic from (f). 9. AN UNSOLVED PROBLEM On p. 332 of Fundamenta Mathematicae 34 (1947) http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=34 Cech posed the following problem: "Does there exist a surjective Cech closure function on an infinite set X that isn't the identity function?" Roderick A. Price proved that such a function exists for X = 'natural numbers' if the Continuum Hypothesis is assumed in "On a problem of Cech", Topology and its Applications 14 (1982), 319-329. [Price gave a more complicated proof in his 1979 Ph.D. Dissertation (under Mary Ellen Rudin at the University of Wisconsin) that such a function exists for X = 'natural numbers' under a hypothesis known to imply Martin's Axiom (and hence, strictly weaker than the Continuum Hypothesis).] As far as I can determine, it is still not known whether such a function can be proved to exist in ZFC, even for X = 'natural numbers'. Dave L. Renfro
From: Dave L. Renfro on 3 Jul 2005 14:54 Dave L. Renfro wrote (in part): > (b) The closure function and interior function > of a topological space. > > (c) Let V be a vector space and define T:P(V) --> P(V) > by T(A) = the linear span of A. > > (d) Define T:P(R^n) --> P(R^n) by letting T(A) be > the collection of all points in R^n that lie > between each pair of points in A. That is, > T(A) is the union of all the (closed) line > segments whose endpoints belong to A. > > (e) Let X be a set and define T:P(P(X)) --> P(P(X)) by > > T(U) = {union(k=1 to inf): A_k in U for each k} > > union {complement of A: A in U} > > (f) Let X be a set and V be an element of P(P(X)). > Define T_V:P(P(X)) --> P(P(X)) by > > (T_V)(U) = {empty set, X} union V union T(U), > > where T is the function in (e) above. Show that > E- in this case is the sigma-algebra generated > by V. [snip] > Note: The least such ordinal lambda that satisfies (c) is > called the "closure ordinal" for T, and this ordinal is > often denoted by |T|. For example, the closure ordinals > for (b), (c), and (d) (with V = open sets) in #4 above > are 1, omega_0, and omega_1, respectively. Just above it should have been (b,c), (d), and (f). Also, if I want |T| = w_1 for (f), I should have said more than just let V be the open sets. I should have said let X be R^n, or at least let X be a complete separable metric space. Incidentally, the fixed points in (d) are the convex sets. You can get the convex hull of a set B by finding E- (the least fixed point) for the monotone set function T_B defined by (T_B)(A) = B union T(A), where T is the function in (d), or as the omega'th iterate of T applied to B (i.e. union{(T^n)(B): n = 1, 2, 3, ...}). Dave L. Renfro
From: William Elliot on 4 Jul 2005 03:00 On Sun, 3 Jul 2005, Dave L. Renfro wrote: > Dave L. Renfro wrote (in part): > Whew, it's going to take awhile to plow thru this. Glancing at your post reminds me of the Knaster-Tarski fixed point theorem for complete lattices. As for the patch below, I'm some puzzle it's exact application. Would you have the grace to repost your original essay amended as described at end? > > (b) The closure function and interior function > > of a topological space. > > > > (c) Let V be a vector space and define T:P(V) --> P(V) > > by T(A) = the linear span of A. > > > > (d) Define T:P(R^n) --> P(R^n) by letting T(A) be > > the collection of all points in R^n that lie > > between each pair of points in A. That is, > > T(A) is the union of all the (closed) line > > segments whose endpoints belong to A. > > > > (e) Let X be a set and define T:P(P(X)) --> P(P(X)) by > > > > T(U) = {union(k=1 to inf): A_k in U for each k} > > > > union {complement of A: A in U} > > > > (f) Let X be a set and V be an element of P(P(X)). > > Define T_V:P(P(X)) --> P(P(X)) by > > > > (T_V)(U) = {empty set, X} union V union T(U), > > > > where T is the function in (e) above. Show that > > E- in this case is the sigma-algebra generated > > by V. > > [snip] > > > Note: The least such ordinal lambda that satisfies (c) is > > called the "closure ordinal" for T, and this ordinal is > > often denoted by |T|. For example, the closure ordinals > > for (b), (c), and (d) (with V = open sets) in #4 above > > are 1, omega_0, and omega_1, respectively. > > Just above it should have been (b,c), (d), and (f). Also, > if I want |T| = w_1 for (f), I should have said more than > just let V be the open sets. I should have said let X be > R^n, or at least let X be a complete separable metric space. > Incidentally, the fixed points in (d) are the convex sets. > You can get the convex hull of a set B by finding E- > (the least fixed point) for the monotone set function T_B > defined by (T_B)(A) = B union T(A), where T is the function > in (d), or as the omega'th iterate of T applied to B > (i.e. union{(T^n)(B): n = 1, 2, 3, ...}). > > Dave L. Renfro > >
From: William Elliot on 4 Jul 2005 07:57 From: Dave L. Renfro <renfr1dl(a)cmich.edu> Newsgroups: sci.math Subject: MONOTONE SET FUNCTIONS, FIXED POINTS, AND CECH CLOSURE FUNCTIONS > The Zariski topology for commutative rings (each closed set > is the collection of all prime ideals containing a given > prime ideal) is very important in algebraic geometry and > is almost never Hausdorff and rarely even T_1. For example, > in the case of an integral domain, the point corresponding > to the prime ideal {0} is a dense subset of the space. This > space is always T_0, however. For some other ways that non-T_2 > spaces can arise, see the sci.math.research thread > "Non-Hausdorff Topological Spaces" (google for it). "Counterexamples in Topology" by Steen, space #56, Prime Ideal Topology (of integers) > In outline form, leaving out many of the side-issues and the > numerous references, here's my attempt at organizing these notions > in a way that I think would have some appeal to a pure > mathematician. -- sci.math.research Non-Hausdorff Topological Spaces Are there any standard interesting non-Hausdorff spaces? Algebraic varieties with their Zariski topology are not Hausdorff and, more generally so are schemes (except in trivial cases). Any reflexive transitive relation induces a non-Hausdorff topology iff it is different from the identity relation. But this is studied within the theory of posets and their generalizations. For any locally compact group, the set of (equivalence classes of) irreducible unitary representations carries a normally non-Hausdorff topology, the so-called Fell topology. One very important example comes from algebraic geometry: if R is an arbitrary commutative ring, let Spec(R) be the set of its prime ideals, and put the following topology on Spec(R): a set is closed iff it can be written as {p : p contains A} where A is a subset of R. This topology is called the ``Zariski topology'', and it is quite seldom Hausdorff. In fact, it is generally not even T1 (it is T0 though). If R is an integral domain, then the point corresponding to the prime ideal {0} of R is dense in Spec(R) (it is called the ``generic point''). The topological spaces that are used as model of the untyped lambda calculus, and more generally the spaces used in semantics are embedded with the scott topology which is never hausdorff. see any book on semantics of lambda calculus for references, or domain theory. If X is a (non-compact) complex space, and S is a coherent sheaf on X with an infinite-dimensional cohomology group $H^k(X,S)$, then often this cohomology group is a non-Hausdorff space, because it arises as a quotient of an infinite-dimensional Frechet vector space by some non-closed subvectorspace. More generally non-Hausdorff spaces often occur as quotient spaces of Hausdorff spaces by not-too-nice equivalence relations. In the 1930's, Marshall Stone discovered the famous duality between Boolean algebras and a category of topological spaces (now referred to as Stone spaces). These spaces are, in general, non-T2. In fact, they belong to a special class of topological space, known as *sober* spaces (sobriety is a separation property sitting somewhere between T0 and T1). In recent years, a large body of work dealing with sober spaces has appeared. In particular, there now exist Stone-type duality theorems for a number of categories of partially-ordered sets, and sub-categories of Sob (the category of sober spaces). This area of study has even received its own name: "Pointless topology". ----
From: Dave L. Renfro on 4 Jul 2005 14:19 Dave L. Renfro wrote (in part): >>> (b) The closure function and interior function >>> of a topological space. >>> >>> (c) Let V be a vector space and define T:P(V) --> P(V) >>> by T(A) = the linear span of A. >>> >>> (d) Define T:P(R^n) --> P(R^n) by letting T(A) be >>> the collection of all points in R^n that lie >>> between each pair of points in A. That is, >>> T(A) is the union of all the (closed) line >>> segments whose endpoints belong to A. >>> >>> (e) Let X be a set and define T:P(P(X)) --> P(P(X)) by >>> >>> T(U) = {union(k=1 to inf): A_k in U for each k} >>> >>> union {complement of A: A in U} >>> >>> (f) Let X be a set and V be an element of P(P(X)). >>> Define T_V:P(P(X)) --> P(P(X)) by >>> >>> (T_V)(U) = {empty set, X} union V union T(U), >>> >>> where T is the function in (e) above. Show that >>> E- in this case is the sigma-algebra generated >>> by V. [snip] >>> Note: The least such ordinal lambda that satisfies (c) is >>> called the "closure ordinal" for T, and this ordinal is >>> often denoted by |T|. For example, the closure ordinals >>> for (b), (c), and (d) (with V = open sets) in #4 above >>> are 1, omega_0, and omega_1, respectively. Dave L. Renfro corrected the above with: >> Just above it should have been (b,c), (d), and (f). Also, >> if I want |T| = w_1 for (f), I should have said more than >> just let V be the open sets. I should have said let X be >> R^n, or at least let X be a complete separable metric space. >> Incidentally, the fixed points in (d) are the convex sets. >> You can get the convex hull of a set B by finding E- >> (the least fixed point) for the monotone set function T_B >> defined by (T_B)(A) = B union T(A), where T is the function >> in (d), or as the omega'th iterate of T applied to B >> (i.e. union{(T^n)(B): n = 1, 2, 3, ...}). William Elliot commented: > Whew, it's going to take awhile to plow thru this. Glancing > at your post reminds me of the Knaster-Tarski fixed point > theorem for complete lattices. As for the patch below, > I'm some puzzle it's exact application. Would you have > the grace to repost your original essay amended as > described at end? Yes, I'm pretty sure the Knaster-Tarski fixed point theorem fits into this format. If anything, I suppose this is a little more general, since P(X) is a complete lattice under inclusion. Actually, the additional generality is probably not especially profound, because I'd bet that the additional lattice properties that P(X) has, such as being completely distributive, don't play a role in the proof that monotone functions on P(X) have fixed points. (More precisely, there exists such a proof, since we can always obtain a proof where distributivity is involved simply by adjoining in an ad hoc manner a distributive law in the middle of any proof of the fixed point theorem for monotone set functions.) The convex hull of a subset A in Euclidean n-space R^n can be defined in a top-down manner (i.e. impredicatively) as the intersection of all the convex sets in R^n that contain A. Note the similarity with other top-down "constructions", such as the subgroup generated by a subset (intersection of all subgroups containing that set), the closure of a set in a topological space (intersection of all closed sets containing that set), the linear span of a subset in a vector space (intersection of all subspaces containing that set), etc. Note also the key role that closure under arbitrary intersections plays, which translates into an arbitrary union of the corresponding generalized open sets being open. The convex hull of a subset in R^n can also be defined in a bottom-up manner in the following way. Define T:P(R^n) --> P(R^n) by letting T(A) be the union of all the line segments (including their endpoints) joining any two points in A. Then I claim that A union T(A) union T(T(A)) union ... (the union is over all finite iterates of T) is equal to the intersection of all the convex sets containing A. The proof is not difficult. Show each is a subset of the other, and make use of the fact that an arbitrary intersection of convex sets is convex. The neat thing about the convex hull example is that it provides an example where precisely omega_0 many steps are required. Typically, one step is required [the linear span by taking the collection of all linear combinations, the subgroup generated by a set by taking all words using elements from the set, etc.] or omega_1 many steps [the Borel sets by alterations of countable union and countable intersection operations (with unions at the limit ordinal stages) to the collection of open sets, the topological closure of a set in a separable metric space by iterating omega_1 many times the operation of taking limit points (and intersections, at the limit ordinal stages)]. Now that I think about it, the well formed formulas in propositional logic can also be built in exactly omega_0 stages. See Enderton's "A Mathematical Introduction to Logic", Section 1.2 ("Induction and Recursion"), where he discusses both the top-down and the bottom-up methods of generating the well formed formulas. He even calls the two methods "from the top down" and "from the bottom up". [Regarding his notion of an "inductive set of formulas", this plays the role of "closed set", "convex set", "subspace", "subgroup", etc.] Incidentally, there are two natural examples of operations that stabilize after precisely _two_ applications, the boundary operation in topology and the pointwise oscillation of a function (sometimes called the "saltus function"). For more about the oscillation example, see my post http://groups-beta.google.com/group/sci.math/msg/0fb519fc069d1fc9 After this post, I'll repost a corrected version of the full essay. I'll also include among the three posts I gave URL's for at the end of Section 5 another relevant post that I just now remembered making a few years ago. Dave L. Renfro
|
Next
|
Last
Pages: 1 2 3 Prev: variance of product of uncorrelated variables Next: How many Primes? |