Prev: variance of product of uncorrelated variables
Next: How many Primes?
From: Dave L. Renfro on 4 Jul 2005 14:46
[This is a slightly corrected re-post of my original post.]

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), (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

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: William Elliot on 5 Jul 2005 00:55
From: Dave L. Renfro <renfr1dl(a)cmich.edu>

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
> 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.]

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

----

From: Butch Malahide on 5 Jul 2005 01:22


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.

From: William Elliot on 5 Jul 2005 03:42
-- 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).

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}

----

From: Keith Ramsay on 5 Jul 2005 19:44
Dave L. Renfro wrote:
[...]
| 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

First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: variance of product of uncorrelated variables
Next: How many Primes?