dole@spar.UUCP (Harry Dole) (11/14/85)
Enough of the equatorial polar bears and the machine
protoplasm, time for some math. There has been some recent discussion
on transcendental cardinals and I recall an old request for what
category theory has to say about the Continuum Hypothesis (CH). I once
did a seminar session at grad school about Tierney's proof on
the independence of CH so I thought I would try to distill the
essence of the proof for the readers of this net. The original
proof appeared in Springer Lecture Notes series number 274
( commonly referred to as the yellow-peril series ) under the
title "Sheaf Theory and the Continuum Hypothesis." I cannot find my
original copy of the article so I am relying on Peter Johnstone's book
<Topos Theory> from Academic Press, pp323-329. This book is not for
the casual reader of category theory but it is the single best reference
on topos theory. Topos theory is essentially that part of category
theory that models set theory. In fact, part of the reason for deriving
topos theory to begin with was to handle the categorical version of CH
( the original topos theory work was done by Lawvere and Tierney ).
I assume that not all readers of this net are familiar with
categorical terms ( there certainly are plenty of mathematicians
that are not familiar ) so I will attempt some deliberatly fuzzy
definitions. If you know more accurate definitions then write down
the dual definition and the evident diagram, apply the obvious
argument and obtain the usual result. First of all, a category
is a set of objects, and a set of arrows called the morphisms
of the category. Any given morphism f has a domain object and a
codomain object. Also given with the category is a composition rule
on morphisms such that when given two morphisms f and g ( written
as arrows ) such that the codomain of f is the domain of g:
f g
A----->B----->C
then there exists a morphism gf:A----->C called the composite of g
and f. The properties that must be satisfied are that composition
is associative and for every object A there must be an identity
morphism 1A so that composing with the identity yields the same
morphism back. For example, the category of sets S is described
as having for objects all sets and for morphisms all functions
between sets ( note that the range of a function is contained
within the codomain but is not necessarily equal to the codomain).
A topos is a cartesian closed category with finite
limits and a subobject classifier. Cartesian closed means that
for any two given objects A and B in the category, then there
is an object in the category that can be regarded as the set of
all morphisms from A to B ( the real definition involves adjoint
functors and I am going to avoid saying anything about them for
as long as I can ). Essentially, cartesian closed means that
hom-sets can be internalized. In the category of sets S the hom-sets
are given for any two objects A and B as hom(A,B)={f|domain(f)=A and
codomain(f)=B } and since a hom-set is a set the category of sets
is cartesian closed. Typically, exponents are used to denote hom-sets
in a general cartesian closed category so hom(A,B)=B**A in this
ASCIIese. Finite limits means you can do finite products and
pullbacks which intuitively means you can do cartesian
products and (sortof) intersections of sets (actually pullbacks).
A subobject classifier is a fancy way of saying you have an
object in the category that can thought of as the set of truth
values for the set theory that the topos models.
As it happens, S is a topos with the subobject classifier being
the set 2={T,F} containing T for true and F for
false. There are many examples of toposes ( or topoi ) that are
not Boolean like S--e.g., given any topological space U there exists
a topos that is constructed by Grothendieck topologies whose
truth values are the open sets of U ( warning: the math semantics
of the latter instance of the word "topology" does not coincide
with the former; I only mention Grothendieck here because
this building of new toposes from old by Grothendieck topologies
is used in the construction of a "set theory" that negates CH ).
Now for the CH. What we want to come up with is a topos
that looks like ordinary set theory--i.e., satisfies the axioms
of set theory--but has an object X in it such that there is a
one-to-one ( monomorphism ) map from the natural numbers N to X,
a one-to-one map from X to the power set of N, denoted 2**N,
such that there is no onto ( epimorphism ) map from P(N) to X
and no onto map from X to N. Such an X implies that there is
a cardinal number strictly between aleph-0 and aleph-1. This is
the categorical form of Schroeder-Bernstein.
The basic form of attack is to start with an internal form
of the problem expressed in the internal language of an arbitrary
topos as we have done somewhat in the previous paragragh. We take
a two-valued model of set theory, say the S from above, choose a
partially ordered set (poset) P in S ( as Johnstone puts it: normally the
poset of "finite partial models" of the thing one is trying to
construct ). One then constructs from S and P the topos consisting
of the double-negation sheaves of the functor category S**P.
This new category ( whatever it is ), denoted E, is also a
topos but the subobject classifier is only known to be Boolean
and not necessarily to be of just two elements as we expect
for "standard" set theory. Assuming P was chosen correctly,
the hypothesis to be proven ( for us, the negation of CH, or, more
explicitly, the existence of that object X ) is then shown to
be true in the new topos E. To get to a two-valued system of set
theory, there is a general method ( the ultrapower construction )
of getting a two-valued set theory ( or topos ) from any Boolean
topos such that the properties of the object X are preserved from
the old topos E to the new two-valued topos, denoted S' ( this
preservation of cardinals from the Boolean topos to the two-valued
topos comes from the "logical" functor that maps E to S' ). The
two-valued topos S' satisfies the same axioms that S did but it
does not satisfy CH, thus yielding the independence of CH.
Now for some details on that poset P. We assume that S
contains an object N that "resembles" the natural numbers--i.e.,
the topos S satifies the axiom of infinity. Let I denote an object
in S such that 2**N ( the power set of N ) is strictly contained
in I. More explicitly, there is a one-to-one map from 2**N into I
but there is no onto map from 2**N to I so that the cardinal number
of 2**N is strictly less than that of I. The set P consists of all
functions from a finite subset of the cartesian product of N and I
to 2--i.e., the domain of any such function f consists of a finite
number of ordered pairs of the form (n,i) where n is in N and i is
in I, and each such ordered pair is sent by f to T or F in 2={T,F}.
Given two such functions f and g in P, we say f<=g if g extends f,
which means to say that the domain of g contains the domain of f
and the values of g coincide with those of f on those elements
that are in common. In Johnstone's words: We think of an element
of P as a finite set of "forcing conditions", each of which says
that a particular element n of N either is or is not in the
particular element i of I.
We use the notation card(x) to denote the cardinality of
the object x. Without going into the technical lemmas or proofs, the
following leaps of faith provide the mileposts to the independence
of CH:
A> Show that P satisfies the countable chain condition.
This means that if A is a subset of P and no two elements
of A have a common extension in P, then A is countable.
B> Construct the topos of double-negation sheaves of the
functor category S**P. This may be a little hard to explain.
The functor category S**P is the set of all functors from
P considered as a category to S. An object of the category
S**P can then be thought of as attaching to each element p
in P a set Yp in S such that if p<=q in P then there is a
given one-to-one map from Yp to Yq in S. From general
principles it follows that S**P is a topos but not necessarily
a Boolean one. Since S**P is a topos it has a subobject
classifier ( intuitively, the set of truth values for S**P )
so denote it by M. It is known that M is a Heyting algebra
so it has a negation map not:M--->M ( the subobject classifier
of a topos is always a Heyting algebra; a Boolean algebra
is an example of a Heyting algebra). From the map not-not
( not composed with itself once ) we can construct a
Grothendieck topology from which we obtain the topos of
double-negation sheaves, denoted E. This construction is
"nice" so that many facts that hold in S also hold in E.
More to the point, E is a Boolean topos even though it is
not a two-valued model of set theory ( remember, we get to
the two-valued one via the ultrapower construction ).
In particular, the construction provides a mapping ( functor )
from S to E and it can be shown that this mapping preserves
cardinals. Denote this mapping as G:S--->E.
C> Let W denote the subobject classifier in E. We transport the
set I from S to E by the mapping G to obtain the object G(I)
in E. It can be shown that there is a one-to-one mapping
of G(I) to the object W**N ( this gives card(G(I)) <= card(W**N) ).
The object W**N can be thought of ( in E, not S! ) as the
set of subsets of the natural numbers ( the natural numbers in
the topos E look very different from the natural numbers in
S but still satisfy properties of natural numbers ). In the
set theory E card(N) is aleph-0 and card(W**N) is aleph-1.
This step is where the countable chain condition properties of
the poset P get exercised. Remember that in the standard
set theory topos S we have card(2**N) <= card(I). This should
lead you to believe that G(2) is not the same as W in the
topos E so it is clear that G does *not* preserve subobject
classifiers.
D> Next it has to be shown that in the topos E, the object G(2**N)
negates the Continuum Hypothesis ( we get this when we can
assert card(N) < card(G(2**N)) < card(W**N) ). Note that
in both toposes S and E we use the same symbol N for the
natural numbers despite the fact that they are quite
different. This can be forgiven since G(N in S) is
isomorphic to N in E ( isomorphism means intuitively that
there is a one-to-one and onto map between the two; more
to the point, G preserves natural number objects). First,
we have the following sequence of one-to-one maps
( monomorphisms ):
N iso G(N) -----> G(2**N) -----> G(I) -----> W**N
where the first two come from the assumptions about I in S
and the last one comes from step C above. From the above
we get:
card(N)=card(G(N))<=card(G(2**N))<=card(G(I))<=card(W**N)
All we need now is that the first two of the above inequalities
are strict and that the last is an equality.
Let Epi(A,B) denote the set of epimorphisms from the set A
to the set B. Note that Epi(A,B) is empty iff the cardinal
number of A is strictly less than that of B. From our
previous assumptions in S, we know that Epi(N,2**N) and
Epi(2**N,I) are both empty. It follows in E that Epi(N,G(2**N))
and Epi(G(2**N),G(I)) are both empty ( the functor G does
preserves epimorphisms). At this point we know
card(N) < card(G(2**N)) < card(G(I)).
By suitable magic ( injectives and global elements ) we can
obtain an onto map ( epimorphism ) q:W**N---->G(I). This last
epimorphism gives card(G(I))=card(W**N). Thus, in the Boolean
topos E ( or Boolean set theory if you
prefer ), we have
card(N) < card(G(2**N)) < card(W**N).
E> Using the ultrapower construction, we can reduce the Boolean
topos E to a two-valued topos S'. This gives a mapping L from
the topos E to S' that preserves cardinals *and* preserves
subobject classifiers. Thus, L(W)=2 where this 2 is the
subobject classifier in S', and moreover, L(N)=N where this
last N is the natural number object in S'. It follows that
card(L(N))=card(N) < card(L(G(2**N))
< card(L(W**N))
= card(L(W)**L(N))
= card(2**N).
We now set X=L(G(2**N)). Thus, we have constructed a set
theory S'=L(G(S)) that has a cardinal number strictly between
aleph-0 and aleph-1.
Now that the smoke has cleared and the reader's brain is
suitably fused, one might ask what is the difference between this
"proof" and Cohen's. By and large, the difference is that the
fundamental terms in Cohen's come from set theory and those here
come from category theory. So depending on what you already know,
the set theory version may make more sense. However, many of the
constructions used in the categorical version are standard and
should be known by most users in the field ( perhaps not the
ultrapower construction, but the functor categories for sure and
most should at least know of Grothendieck topologies ). I would
maintain that the categorical version of CH does not bring any
new light on CH itself, but for someone who is versed in category
theory as myself, the categorical version of the proof is far
easier to read than the original Cohen paper ( yes, I had to
read both for the seminar that I gave so I could tell the
interested spectator what the differences were ). Moreover,
the categorical techniques are quite easily generalizable
and one can hope that other independence results can be
categorically "forced" rather than having to deal with the
drudgery of set theory. So far to my knowledge, only one
other result has been shown to be independent
via category theory and that was Souslin's Hypothesis shown
by Marta Bunge at McGill University, Montreal. I did a
seminar on that one as well but there is a glaring error that
had passed others by: An arbitrary union of finite trees
is a finite tree. Since I was giving the seminar, I was expected
by prof Mac Lane ) to fix the error. I did this by reading the
original independence proof written in set theory and laboriously
performing a translation to categorical terms. The resulting
categorical argument was smaller than the original
( blessed is the hindsight ) but this categorical treatment did
not win any points with the logicians at my school. In other
words, those people who make a living at "forcing" do not use
categorical techniques.
Long Live the Categorical Imperative.
Harry Dole
{decwrl,hplabs}!spar!dolecolonel@sunybcs.UUCP (Col. G. L. Sicherman) (12/13/85)
["Antiset: a mathematical structure that contains none of its elements."]
I've seen models of ^CH that were easier than Cohen's but didn't use
category theory either. (Of course they used _some_ algebra! e.g.,
ultrafilters.)
--
Col. G. L. Sicherman
UU: ...{rocksvax|decvax}!sunybcs!colonel
CS: colonel@buffalo-cs
BI: csdsicher@sunyabva