New solutions to exercises from Thomas Jech’s book “Set Theory”:
Wednesday, July 24 2013
By fredw on Wednesday, July 24 2013, 22:37
Saturday, June 1 2013
By fredw on Saturday, June 1 2013, 18:29
New solutions to exercises from Thomas Jech’s book “Set Theory”:
Last November, I tried to provide some details of the proof given in chapter 7, regarding the fact that the continuum hypothesis implies the existence of a Ramsey ultrafilter. Peter Krautzberger pointed out that the proof could probably work assuming only Martin’s Axiom. This was indeed proved by Booth in 1970 and the missing argument is actually given in exercise 16.16. For completeness, I copy the details on this blog post.
Remember that the proof involves contructing a sequence of infinite subsets of . The induction hypothesis is that at step , for all we have is finite. It is then easy to show the result for the successor step, since the construction satisfies . However at limit step, to ensure that is finite for all , the proof relies on the continunum hypothesis. This is the only place where it is used.
Assume instead Martin’s Axiom and consider a limit step . Define the forcing notion and iff , and for all . It is clear that the relation is reflexive and antisymmetric. The transitivity is almost obvious, just note that if and then for all we have .
The forcing notion satisfies ccc or even property (K): since is countable, for any uncountable subset there is such that is uncountable. Then any have a common refinement .
For all , define . Let the elements of . We show by induction on that is infinite. This is true for by assumption. If it is true for then
The left hand side is infinite by induction hypothesis. The second term of the right hand side is included in and thus is finite. Hence the first term is infinite and the result is true for . Finally, for , we get that is infinite. Pick distinct elements from that set and define . We have , , and for all , . This shows that is dense. For each , the set is also dense: for any consider .
By Martin’s Axiom there is a generic filter for the family of size . Let . For all , there is and so . Hence is infinite. Let and . For any , there is such that . Hence there is a refinement of . We have and . Hence is finite and the induction hypothesis is true at step .
Friday, May 3 2013
By fredw on Friday, May 3 2013, 22:04
New solutions to exercises from Thomas Jech’s book ‘‘Set Theory’’:
The exercises from this chapter was a good opportunity to play a bit more with the forcing method. Exercise 15.15 seemed a straightforward generalization of Easton’s forcing but turned out to be a bit technical. I realized that the forcing notion used in that exercise provides a result in ZFC (a bit like Exercises 15.31 and 15.32 allow to prove some theorems on Boolean Algebras by Forcing).
Remember that is the normal sequence built by application of the continuum function at successor step. One may wonder: is regular?
First consider the case where is limit. The case is clear ( is regular) so assume . If is an inacessible cardinal, it is easy to prove by induction that for all we have : at step we use that is uncountable, at successor step that it is strong limit and at limit step that it is regular. Hence and so is regular. If is not a cardinal then so is singular. If is a cardinal but not strong limit then there is such that . Since there is such that . Then . So and is singular. Finally, if is a singular cardinal, then again and is singular.
What about the successor case i.e. ? By Corollary 5.3 from Thomas Jech’s book any , we can show that is a regular cardinal. The Generalized Continuum Hypothesis says that . Since it holds in we can not prove in ZFC that for some , is singular.
The generic extension constructed in exercise 15.15 satisfies GCH and so it’s another way to show that can not be proved to be singular for some . However, it provides a better result: by construction, and so . Since ‘‘regular cardinal’’ is a notion we deduce that is a regular cardinal in .
Now the question is: is there any ‘‘elementary’’ proof of the fact that is regular i.e. without using the forcing method?
--update: of course, I forgot to mention that by König’s theorem, so the singularity of would imply the failure of the continuum hypothesis for the cardinal and this is not provable in ZFC.
Thursday, April 4 2013
By fredw on Thursday, April 4 2013, 10:09
In a previous blog post, I mentioned the classical independence results regarding the Axiom of Choice and the Generalized Continuum Hypothesis. Here, I’m going to talk about a slightly less known problem that is undecidable in ZFC. It is about a characterization of the set of reals and its formulation does not involve at all cardinal arithmetics or the axiom of choice, but only properties of ordered sets.
First, the set of rationals is well-known to be countable. It is linearly ordered (for any either or ), unbounded (for any there is such that and ) and dense (for any if we can find such that ). It turns out that can be characterized by these order properties:
Let be a countable, dense, unbounded linearly ordered set. Then is isomorphic to .
Let and be enumerations of and . We shall construct by induction a sequence of functions such that for all , , and . Then is a function: if then there is large enough such that and since is a function . Moreover, and . Finally, for any there is large enough such that and so . Hence is an isomorphism between and .
Thus let . If is defined, we construct as follows. Suppose . If then because is unbounded we can consider the least such that and set . Similarly if . Otherwise, let such that with respectively the largest and smallest possible. Because is dense we can consider the least such that and again set . Similarly, if we use the fact that is unbounded and dense to find that allows to define and ensures is order-preserving.
We now notice that is linearly ordered, unbounded, dense and has the least upper-bound property (that is any nonempty bounded subset of has a least upper-bound). Moreover, the subset is countable and dense in (that is for any such that we can find such that ). Using the previous lemma, we deduce again that these order properties give a characterization of the set of reals:
Let be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that has a dense countable subset . Then is isomorphic to .
is countable by assumption and since it is also linearly ordered. If and then by density of in there is such that . So is actually dense. Similarly, if then since is unbounded there is such that and again by density of in we can find such that . So is unbounded. By the previous lemma, there is an isomorphism of ordered sets .
We define for all , . Because is dense in and has the least upper bound property this is well-defined. If then for all such that we have and so . If we could find (by density of in ) an element such that . For we get and so . A contradiction. So .
Let such that . Because is increasing we get . By density of in we can find such that . Again, we get and . Hence we actually have . In particular, is one-to-one.
We shall prove that is surjective. Of course so let’s consider . Define . This is well-defined because is dense in and has the the least upper bound property. Then for all such that we have by definition. By density of in we can actually find such that and so . We have and so . Hence . Suppose that and consider (by density of in ) some such that and let . If then there is , , such that . Then a contradiction. If instead then which is again a contradiction.
Finally, let such that . Because is totally ordered either or . But the latter is impossible since we saw above that it implied . Hence is an isomorphism between and .
Now consider a totally ordered set . For any we define the open interval . Suppose is a dense subset of . If is a family of pairwise disjoint open intervals then we can associate to any the least such that (by density of in ). Since the family is disjoint the function obtained is one-to-one and so the family is at most countable. One naturally wonders what happens if we replace in theorem 0.1 the existence of a countable dense subset by this weaker property on open intervals:
Problem 0.1 (Suslin’s Problem).
Let be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that any family of disjoint open intervals in is at most countable. Is isomorphic to ?
We have seen how this problem arises from a natural generalization of a characterization of . We note that we did not use the Axiom of Choice in the above analysis and that the problem can be expressed using only definitions on ordered sets. However, in order to answer Suslin’s Problem we will need to introduce more concepts. We will assume familiarity with basic notions of Set Theory like ordinals, cardinals or the Axiom of Choice. The first five chapters of Thomas Jech’s book ‘‘Set Theory’’ should be enough. In addition, we will rely on the axiom and on the Diamond Principle , that we define here:
Definition 0.1 (Martin’s Axiom , Diamond Principle).
and are defined as follows:
Let be a partially ordered set. Two elements are compatible if there is such that and . Note that comparable implies compatible.
is dense in if for any there is such that .
is a filter if:
For any such that and we have
Any there is such that .
: Let be a partially ordered set such that any subset of paiwise incompatible elements of is at most countable. Then for any family of at most dense subsets there is a filter that has a nonempty intersection with each element of this family.
A set is closed unbounded if
It is unbounded in the sense that for any there is such that
It is closed for the order topology, or equivalently if for any and any -sequence of elements of , is in .
A set is stationary if for any closed unbounded, .
: There is an -sequence of sets such that for every the set is stationary.
First we show that if holds, then we get a positive answer to Suslin’s problem:
Assume Martin’s axiom holds. Let be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that any disjoint family of open intervals in is at most countable. Then is isomorphic to .
Suppose is not isomorphic to and in particular does not have any countable dense subset (otherwise we could apply theorem 0.1). We define closed intervals by induction on . If is defined for all then the set is countable and thus is not dense in . Then there is such that is disjoint from . We define the set . Clearly, and is partially ordered. We note that if then by construction and so either or . In particular, comparable is the same as compatible in and any family of pairwise incomparable/incompatible elements of is a family of pairwise disjoint intervals of so at most countable.
Let and define . Let nonempty. Let the least ordinal such that . If then and . Hence by the previous remark . So is well-ordered by and we define the order-type of . We note that the set can be enumerated by for some and so . Moreover for any , if then is an initial segment of and so . Hence for each the set has pairwise incomparable elements and so is at most countable.
For any , define and let . Let and suppose that . Then and since the are at most countable for and the are at most countable for we would have at most countable, a contradiction. So for each , there is and in particular . We note that if and then and so . In particular, and thus without loss of generality we may assume that .
For any let . For any , and . The first term is at most countable and so the second is uncountable and a fortiori nonempty. So is a dense subset of .
Using , we find a filter that intersects each . By definition, elements of a filter are pairwise compatible and so pairwise comparable. Let us construct by induction on , some sets . If is constructed for any then and we can pick . We obtain a decreasing -sequence of intervals . If then this gives an increasing sequence . The sets form an uncountable family of disjoint open intervals. A contradiction.
Finally, we show that the principle provides a negative answer to Suslin’s problem:
Assume the principle holds. Then there is a linearly ordered set not isomorphic to , unbounded, dense, that has the least upper-bound property and such that any family of disjoint open intervals is at most countable.
Let be a -sequence. We first construct a partial ordering of . We define for all an ordering on initial segments and obtain the ordering on .
Each will be a tree i.e. for any in the tree the set is well-ordered. As in the proof of 0.2 we can define the order-type of . The level is the set of elements such that . The height of a tree is defined as the supremium of the . In a tree, a branch is a maximal linearly ordered subset and an antichain a subset of pairwise incomparable elements. A branch is also well-ordered and so we can define its length as its order-type. is constructed such that its height is and for each there is some at each higher level less than .
We let . If is a limit ordinal then is the union of for . If is a successor ordinal, then the highest level of is . is obtained by adding immediate successors to each element of . These successors are taken from in a way that is an initial segment of .
Let is a limit ordinal. Let if it is a maximal antichain in and take an arbitrary maximal antichain of otherwise. Then for each there is such that either or . Let be a branch that contains . We construct by adding for each branch some that is greater than all the elements of . We can choose in way that it contains an element of each level less than and so and the height of is . We note that each is either in (so comparable with some element of ) or greater than (a fortiori comparable with) one element of . So is an antichain in .
Now consider a maximal antichain and the set of ordinals such that ‘‘ is a maximal antichain in and ’’. Let () be a sequence of elements in and consider the limit ordinal . By construction, . If , there is such that and so is comparable with some . So is a maximal antichain in . Finally and is closed.
We note that . If then is obtained by adding at least one element at the end of the initial segment and so . Finally if is limit and for each then . Moreover by definition, each is at most countable. Let’s come back to the closed set above. Let be arbitrary. For each , we let be the limit of the sequence . By definition, . Because is a maximal antichain in , for each we can find some and that is comparable with . Because is countable we can define . Then any is comparable with some element of . Let . With the same method as to prove the fact that is closed, the equality shows that while the equality shows that is a maximal antichain in . So and is closed unbounded.
Using the Diamond principle, . If is in the intersection, then is a maximal antichain in . By construction, it is also a maximal antichain in . Each element of is at level . Any is comparable with some element of . Moreover, by contruction any has some predecessor at level and there is that is comparable with . Necessarily, and so . Thus is maximal in and is at most countable.
Let be a branch in . It is clear that is nonempty. Actually it is infinite: otherwise there is some limit ordinal such that and by construction we can find some contradicting the maximality of . By construction, each has infinitely many successors at the next level and so these successors are pairwise incomparable. Hence if then we can pick one among these succcessors. Let be two elements of . Then so is impossible. Suppose . We also have by definition. If then we would have because is a branch. If we would get . Hence are incomparable (in particular distinct) and the set is an antichain in and so is countable.
Finally, we define the set of all branches of . By construction, each has countably many immediate successors and we order them as . Let be two branches and the least level where they differ. The level 0 is so . If is limit then the restriction of the branches to is the same branch and has been contructed in a way that there is only one possible element at level to extend this branch and this is a contradiction. So is actually a successor ordinal . Hence if and are the immediate successors of the point in at level , we order according to whether or , using the -isomorphic order we just defined. Clearly, this gives a linear ordering . It is also unbounded: for any , if is the element at level 1 pick greater (or smaller) than for the -isomorphic order on successors of and consider a branch extending .
Now consider two branches . Let be as above. We can find an immediate successor of such that for the -isomorphic order on immediate successors of . Let . Any contains . Moreover and so . is nonempty (we can extend to a maximal branch) and so is dense. If then are incomparable. So from any collection of disjoint open intervals we get an antichain and so is at most countable.
Let be a countable set of branches in . Since these branches are countable, we can find larger than the length of any branches in . If is at level greater than then for all , so . Finally and is not dense.
Now let be the Dedekind-MacNeille completion of . It is unbounded, linearly ordered, has the least upper-bound property and is dense in . Using the fact that is dense in we deduce that is dense. Similarly, if is any collection of disjoint open intervals in we can find such that . Then is a collection of disjoint open intervals in and so is at most countable.
Finally, it remains to prove that is not isomorphic to and it suffices to show that does not have any countable dense subset . If is a countable subset of , then for any elements in we pick such that . This gives a countable subset of . If are elements of , we can find such that and so such that . Thus would be a countable dense subset of . A contradiction.
The principle holds in the model of constructible sets. Using iterated forcing, we can construct a model of ZFC in which holds. Using theorems 0.2 and 0.3 we deduce that both the positive and negative answers to Suslin’s problem are consistent with ZFC and so Suslin’s problem is undecidable in ZFC. It’s remarkable that a problem that only involves linearly ordered set can be solved using sophisticated methods from Set Theory. The above proofs follow chapters 4, 9, 15 and 16 from Thomas Jech’s book ‘‘Set Theory’’. In particular:
Theorem 0.2 is based on the proofs of theorem 16.16 and lemma 9.14 (a).
Theorem 0.3 is based on the proofs of lemma 15.24, lemma 15.25, theorem 15.26, lemma 15.27 and lemma 9.14 (b).
Theorem 0.2 implicitely uses theorem 4.4 about the Dedekind-MacNeille completion of a dense unbounded linearly ordered.
In addition, theorem 0.2 also contains the proof of lemma 8.2 (the intersection of two closed unbounded sets is closed unbounded) the solutions to exercise 2.7 (any normal sequence has arbitrarily large fixed points) and exercise 9.7 (if all the antichains of a normal -tree are at most countable then so are its branches).
Finally, and are proved to be consistent with ZFC in theorems 13.21 and 16.13.
Wednesday, March 20 2013
By fredw on Wednesday, March 20 2013, 00:01
Here are new solutions to exercises from Thomas Jech’s book ‘‘Set Theory’’:
Doing the exercises from these chapters gave me the opportunity to come back to the ‘‘classical’’ results about the independence of the Axiom of Choice and (Generalized) Continuum Hypothesis by Kurt Gödel and Paul Cohen. It’s funny to note that it’s easier to prove that AC holds in (essentially, the definition by ordinal induction provides the well-ordering of the class of contructible sets) than to prove that GCH holds in (you rely on AC in and on the technical condensation lemma). Actually, I believe Gödel found his proof for AC one or two years after the one for GCH. On the other hand, it is easy to make GCH fails (just add Cohen reals by Forcing) but more difficult to make AC fails (e.g. AC is preserved by Forcing). This can be interpreted as AC being more ‘‘natural’’ than GCH.
After reading the chapters again and now I analyzed in details the claims, I’m now convinced about the correctness of the proof. There are only two points I didn’t verify precisely about the Forcing method (namely that all axioms of predicate calculus and rules of inference are compatible with the Forcing method ; that the Forcing/Generic Model theorems can be transported from the Boolean Algebra case to the general case) but these do not seem too difficult. Here are some notes about claims that were not obvious to me at the first reading. As usual, I hope they might be useful to the readers of that blog:
In the first page of chapter 13, it is claimed that for any set , and . The first statement is always true because and is by definition. However, the second statement can only be true if is transitive (since that implies ). Indeed, if is transitive then for all we have and since is we get . If moreover we consider then so and is also transitive. Hence the transitivity of the can still be shown by ordinal induction.
The proof of lemma 13.7 can not be done exactly by induction on the complexity of , as suggested. For example to prove (ii) for , we would consider and would like to say that is . Nevertheless, we can not deduce that from the induction hypothesis. Hence the right thing to do is to prove the lemma for first and deduce the lemma for (and ). Then we can proceed by induction.
In the proof of theorem 13.18, it is mentioned that the assumption
implies that if then . To show that, we consider the least ordinal such that . In particular, is not limit ( and if for some limit then there is such that ) and we can write it . We have so there is a formula and elements such that . Hence . Moreover by minimality of , so by (ii) we have and by (i) .
In lemma 14.18, we have expressions that seem ill-defined for example where . This happens in other places, like lemma 14.17 or definition 14.27. The trick is to understand that the functions are extended by 0. Indeed, for any if and then
and similarly we get . Then we can use the inequality page 207 () to replace by its extension .
In lemma 14.23, the inequality
seems obvious but I don’t believe that it can be proved so easily at that point. For example the proof from chapter 2 requires at least the Separation axiom and the formulation from chapter 10 is based on the Axiom of Regularity. To solve that issue, it seems to me that the lemma should be moved after the proof that axioms of ZFC are valid in . This is not an issue since lemma 14.23 is only used much later in lemma 14.31.
Many details could be added to the proof of theorem 14.24, but let’s just mention Powerset. For any , some is defined and satisfies (this follows from the definitions, using the Boolean inequality to conclude). Since moreover we get
In theorem 14.34, we prove that any regular in remains regular in (the hard case is really uncountable and this assumption is implicitely used later to say that is bounded). It may not be obvious why this is enough. First recall that for any ordinal , , , and any (regular) cardinal in is a (regular) cardinal in . Next we have,
that is is equivalent to ‘‘ and have the same regular cardinals’’. Similarly, we can prove that is equivalent to ‘‘ and have the same cardinals’’.
The proof of theorem 14.34 shows that ‘‘ and have the same regular cardinals’’ and so to complete the proof, it is enough to show that implies . So suppose and assume that there is such that . Consider the least such . If then so . By minimality of , and so is a cardinal in . is actually regular in . Otherwise, suppose and let such that . By minimality of , we have and . Then , a contradiction. Finally, we get . This is again a contradiction and so .
« previous entries - page 1 of 3