**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!dole

**colonel@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