MONOTONE SET FUNCTIONS, FIXED POINTS, AND CECH CLOSURE FUNCTIONS
Dave L. Renfro
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
Dave L. Renfro
> (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
William Elliot
> Dave L. Renfro wrote (in part):
>
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?
William Elliot
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".
----
Dave L. Renfro
>>> (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
Dave L. Renfro
Herman Rubin wrote:
William Elliot replied:
http://www.tbi.univie.ac.at/papers/Abstracts/01-pfs-007-subl2.pdf
TABLE OF CONTENTS
7. CECH CLOSURE FUNCTIONS
8. KURATOWSKI CLOSURE FUNCTIONS
9. AN UNSOLVED PROBLEM
(b) T_c leq T
(a) T(E-) = E-
(b) T(E+) = E+
for (b,c), (d), and (f) (with X = R^n and 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 four 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 math-teach post on May 18, 2001
http://mathforum.org/kb/thread.jspa?messageID=1480989
William Elliot
From my readings, not that I ever read this one thru to the end:
Unification approach to the separation axioms between T_0
and completely Hausdorff. arxiv.org/abs/math.GN/9810074
> (a) T_c(A) = union{T(B): A subset B}
Should this be intersection? Were T identity function I, then
I_c is constant map I_c(A) = X. In general, T(X) subset T_c(A).
> (b) T_c <= T
Oh oh, I_c <= I ??
What if I define order dual notions for f:L -> L a complete lattice?
f_i(a) = sup{ f(x) | x <= a }
f_c(a) = inf{ f(x) | a <= x }
Then f_i <= f <= f_c for ascending f
f is diminutive when f(x) <= x
f is augmentive when x <= f(x)
> 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.
P(X) is a completely distributitive, complete atomic Boolean algebra.
The lattice of topologies over a set is complete atomic, non-distributive
complemented.
> (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.)
I dubiate.
> 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.
This akin to the application of the construction used to prove a complete
lower semilattice or a complete upper semilattice is a complete lattice.
> 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
Top down definition of wff?
> 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
----
Butch Malahide
Dave L. Renfro wrote:
>
> 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'.
I think you meant to say that Price used a hypothesis *implied by*
Martin's axiom.
William Elliot
> 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).
P(X), nulset, X
> (b) The closure function and interior function
> of a topological space.
closed sets, nulset, X; open sets, nulset, X
> (c) Let V be a vector space and define T:P(V) -> P(V)
> by T(A) = the linear span of A.
A is subspace, {0}, V
> (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.
convex sets, nulset, R^n
> (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}
This is muddled. U is a collection of subsets of X.
Is U countable? Is P(X) countable? Are {,} inaccurate?
My Guess:
T(U) = { \/{ A | A in U }, \/{ X\A | A in U } }
a two set element of PP(X).
> (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]].
I was content when proving the Cantor-Bernstein's theorem to notice
that T is an ascending function over a complete lattice, hence has
fixed point. One f mapped X into Y then remainder g mapped back
again into X. This made a descending chains of sets both in X and
in Y, which I now presume stabilized to a fixed set. Beyond that I
was willing to let Tarski's fixed point theorem rescue me from the
visualization.
(h). Let T be the lattice of topologies for S. T subset PP(S)
f:T -> T, tau -> topology generated by tau \/ { cl U | U in tau }
f is ascending; f(usual R) = discrete R
indiscrete, cofinite, discrete topologies fixed points
extremally disconnected spaces fixed points
for all tau in T, f(tau) fixed point
-- 6. MONOTONE FUNCTIONS DO NOT HAVE TO PRESERVE UNIONS
nor intersections
> 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).
f:P(S) -> P(S), A -> nulset if x,y not in A
-> {x,a} if x in A, y not in A
-> {y,a} if x not in A, y in A
-> S if x,y in A
S = f({x} \/ {y}); f({x}) \/ f({y}) = {x,y,a}
nulset = f({x} /\ {y}); f({x}) /\ f({y}) = {a}
----
Keith Ramsay
[...]
| 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".
Roughly.
There's a loose sense in which the impredicativity here
is relatively mild. When logicians want to add just a little
impredicativity to an otherwise predicative axiom system,
they seem often to add an axiom of "inductive definition",
asserting the existence of a least fixed-point for a monotone
set-function.
| 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.
I suspect you have the right idea, but I wouldn't put it
that way. A mathematical object S is defined impredicatively
if the definition refers to a set R of which the object is a
member. So, for example, if we define a set of integers S
using number theory, i.e. the theory of the integers, that's
not impredicative. The criterion for being a member of S may
involve all the elements of S without being impredicative.
What would make the definition impredicative is if one gave
a criterion for membership in S with reference to the set
of all sets of integers. For logicians' purposes, the real
line R is essentially the same as the set of all subsets of
the integers, so this is essentially the same as defining a
set of integers S or a real number in terms of properties
of the real line.
"Construction" is not a bad metaphor for explaining why some
people have qualms about impredicative definitions. If we
use a constructive metaphor, the problem is with trying
to construct "new" elements of a set that can be defined only
after the set has been defined. By contrast, people who accept
impredicative definitions often have a "realist" view of the
objects. F.P. Ramsey, during his realist period, argued for
the soundness of impredicative definitions by saying that the
the elements of the set were all present already; one merely
hadn't had the means of identifying some of them yet. The
possible relationship with realism is one reason why
philosophers have shown interest in impredicativity.
Generally speaking, however, I wouldn't say that this qualm
is an essential part of the constructive point of view, in
the sense of mathematical constructivism. I consider
constructivity and predicativity separate issues. I don't
have any polling data, but I doubt there's a consensus among
constructive mathematicians over whether a proof is
invalidated by being impredicative. There also have been
a number of mathematicians like Poincare who felt that
impredicativity was a problem, without having any general
qualms about nonconstructive principles.
Weyl wrote a famous book, _Das Kontinuum_ (The Continuum)
in which he explains why he saw impredicativity as a
problem, and offers a way to redo real analysis to make it
predicative. Anyone who wants to understand concerns about
impredicativity should have a look at that book.
---
Constructivity and predicativity have different costs and
benefits.
They differ in their effect on some familiar measures of
"strength" of systems. Roughly, impredicativity can increase
the strength of a system in a way that the use of
nonconstructive principles doesn't. One can show, for
example, that neither of the two standard nonconstructive
principles, the law of excluded middle and the axiom of
choice, will be necessary. If there is a proof in one of
the standard axiom systems, there will be a proof that is
constructive at least in the sense of not using either of
those principles. There is no similar guarantee for
impredicativity. It's possible that the Riemann hypothesis
can be proven, but only with the help of impredicative
methods. The same story holds for many other conjectures
in number theory and combinatorics. (More specifically, no
result in first-order number theory or elementary
combinatorics needs the axiom of choice. No result
equivalent to the claim that a certain algorithm halts on
every possible input needs the law of excluded middle.)
Philosophers use these results as arguments in both
directions. If using an axiom allows one to prove more
results of this kind, then this fact is potentially the
basis of an "indespensibility" argument in favor of using
it. On the other hand, if using an axiom doesn't enable
you to prove any more results of that kind, this guarantees
a certain kind of "safety" in using it. One will at least
not have an internal inconsistency in one's axioms unless
there was an inconsistency already without the axiom. Thus
people argue for impredicativity on the grounds that we
might need it, but the qualms of people who worry that it
might secretly be leading us into an inconsistency can't be
settled in any simple way. Some impredicative systems can
apparently only be proven consistent by using impredicative
methods.
Likewise, the axiom of choice and the law of excluded
middle have been defended as being at least "safe", but
by the same token aren't needed for the same kind of results
as impredicativity sometimes is.
The difference between constructive and nonconstructive
systems is more a difference in meaning rather than a
difference in power. The usual reason why a nonconstructive
theorem can't be proven constructively is that when one is
doing constructive mathematics, one is interpreting certain
basic terms in a different way. The statement of a theorem,
interpreted in a constructive way, tends to be much stronger.
One of the primary reasons for doing mathematics
constructively is for the sake of this enriched meaning.
The difference between predicative and impredicative methods
seems not to correspond to a difference in interpretation in
the same way. There's a trivial sense in which, if you tell
me that a result has a predicative proof, you are giving me
more information about it than if you just told me that it's
true. But I don't know of any bread-and-butter mathematical
significance that this fact has. As far as I know the
conclusion is the same, just proven with more restrictive
means. If we get a constructive proof that a set is finite,
it gives us a means in principle of determining how many
elements it has. If we get a predicative proof, it may be
more convincing to some people, but I don't know that we
get anything more significant than that out of having it.
Keith Ramsay
Dave L. Renfro
> From my readings, not that I ever read this one thru
> to the end: Unification approach to the separation axioms
> between T_0 and completely Hausdorff.
> arxiv.org/abs/math.GN/9810074
Thanks for the reference. I'm usually not very interested
(and this is quite an understatement) in the fringe type
stuff that deals with semi-locally quasi-sub-open T_(2/5)
pseudo-regular Kothe-Cech spaces of the 5'th type, but this
paper seems to have aspects in it that might be of interest
to me. At least, I've printed it out and filed it away
in my topology preprint/paper notebooks.
William Elliot wrote (in part, on 4 Jul 2005 21:55:50):
>> (a) T_c(A) = union{T(B): A subset B}
>
> Should this be intersection? Were T identity function
> I, then I_c is constant map I_c(A) = X. In general,
> T(X) subset T_c(A).
Ooops, I got this wrong. In this case, it was a
typo when I converted/summarized my manuscript into
ASCII for Usenet posting (i.e. I had intersection in
my LaTex manuscript).
Butch Malahide wrote (on 4 Jul 2005 22:22:49):
> I think you meant to say that Price used a hypothesis
> *implied by* Martin's axiom.
Yep, you're right. This wasn't a typo generated when I
converted/summarized my manuscript into ASCII for Usenet
posting either -- I had this misstated in my manuscript
version also.
William Elliot wrote (in part, on 5 Jul 2005 00:42:16):
>> (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}
>
> This is muddled. U is a collection of subsets of X.
> Is U countable? Is P(X) countable? Are {,} inaccurate?
> My Guess:
> T(U) = { \/{ A | A in U }, \/{ X\A | A in U } }
> a two set element of PP(X).
T(U) is supposed to be the collection of all sets that
can be formed by taking countable unions and complements
of sets that belong (as elements) to U. Note this is not
the same thing as the collection of all sets _generated_
by the operations of countable union and complementation.
Also, since we're considering unions of _sequences_ of
elements belonging to U, we get finite unions as well
(i.e. A union B union C is equal to A union B union C
union C union C ...).
If you still think I have some details wrong, let me
know and I'll stick a note to this effect in my manuscript
to remind me to look into this matter when I get around
to working on it at some future time. (I explain later
why I don't have time to dig very deep into certain things
right now.)
William Elliot wrote (in part, on 5 Jul 2005 00:42:16):
>> 6. MONOTONE FUNCTIONS DO NOT HAVE TO PRESERVE UNIONS
>
> nor intersections
Yep. I suppose this could (and should) have been mentioned
in passing, even though my primary focus was on building
up to the Kuratowski closure axioms using the most direct
route that I could, meaning that the presence or absence
of preserving unions is a key issue but not the presence or
absence of preserving intersections (since even Kuratowski
closure functions don't have to preserve intersections).
Keith Ramsay wrote (in part, on 5 Jul 2005 16:44:02):
>> 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.
>
> I suspect you have the right idea, but I wouldn't
> put it that way. A mathematical object S is defined
> impredicatively
Thanks. I've printed out your comments and filed them
away where I'll see them when I get around to working
on this at some future time. In the near future, however,
I'll be pretty busy because I'm getting ready to move to
another state for another job. One of the reasons I've
posted a few essays recently (e.g. my June 22 post on
hypervolumes of n-balls references, my June 4 post on
separate and joint continuity, my May 13 post on
intersections of collections measurable sets) is that
I've been going through and organizing a lot of the
stuff laying around in my office for this upcoming move,
and occasionally I'll happen to see a sci.math post
just when I need to take a break from these other
activities and which gives me an idea for writing one
of these essays. This explains why I'm so late with
the present replies, by the way.
Dave L. Renfro