116c- Lecture 20

We showed that implies a weak version of choice, , namely, every countable family of non-empty sets of reals admits a choice function. This implies that is regular and suffices to develop classical analysis in a straightforward fashion (in particular, to construct Lebesgue measure and to prove its basic properties).

Coupled with the fact that all sets of reals have the perfect set property, this implies that for any real and therefore is strongly inaccessible in for any real . 

We closed the course by showing that, in fact, is a measurable cardinal. We proved this result of Solovay by showing Martin’s result that the “cone measure” is indeed a non-atomic measure on the structure of the Turing degrees and then “pulling back” this measure to .

Finally, given any measurable cardinal , let be a (-complete, non-principal) measure on . Then is a model of choice in which is measurable. In particular, . 

Since, under choice, any measurable cardinal is strongly inaccessible and the limit of strongly inaccessible cardinals, this shows that has significant consistency strength.    

116c- Lecture 19

As discussed during Lecture 13, for the theories one encounters when studying set theory, no absolute consistency results are possible, and we rather look for relative consistency statements.  For example, the theories “There is a weakly inaccessible cardinal” and “There is a strongly inaccessible cardinal” are equiconsistent. This means that a weak theory (much less than suffices) can prove . Namely: is a subtheory of , so its inconsistency implies the inconsistency of . Assume is inconsistent and fix a proof of an inconsistency from . Then a proof of an inconsistency from  can be found by showing that each is a theorem of , and this argument can be carried out in a theory (such as ) where the syntactic manipulations of formulas that this involves are possible.

It is a remarkable empirical fact that the combinatorial statements studied by set theorists can be measured against a linear scale of consistency, calibrated by the so called large cardinal axioms, of which strongly inaccessible cardinals are perhaps the first natural example. Hypotheses as unrelated as the saturation of the nonstationary ideal or determinacy have been shown equiconsistent with extensions of by large cardinals. One direction (that models with large cardinals generate models of the hypothesis under study) typically involves the method of forcing and won’t be discussed further here. The other direction, just as in the very simple example of weak vs strong inaccessibility, typically requires showing that certain transitive classes (like ) must have large cardinals of the desired sort. We will illustrate these ideas by obtaining large cardinals from determinacy in the last lecture of the course. 

We defined the axiom of determinacy . It contradicts choice but it relativizes to the model . This is actually the natural model to study and, in fact, from large cardinals one can prove that .

We illustrated basic consequences of for the theory of the reals by showing that it implies that every set of reals has the perfect set property (and therefore a version of is true under ). Similar arguments give that implies that all sets of reals have the Baire property and are Lebesgue measurable. In the last lecture of the course we will use the perfect set property of sets of reals to show that the consistency of implies the consistency of strongly inaccessible cardinals.        

Relativizations of P vs NP

In Relativizations of the question by Theodore Baker, John Gill and Robert Solovay, SIAM J. Comput. 4 (1975), no. 4, 431-442 (available through JSTOR) it is shown that the question of whether P equals NP cannot be solved with the kind of arguments typical in computability theory, since these arguments relativize to Turing machines with oracles. Among the results shown there, two oracles and are found such that and . I discussed these results during 117c, the course on decidability in computability theory.

There has been some recent attempts (not very successful, and not too serious in my opinion) to show that the P vs NP question is independent of or even stronger systems. Apparently, part of the motivation for trying to show independence comes from the results in the Baker-Gill-Solovay paper.

I reproduce below a posting by Timothy Chow to the Foundations of Mathematics list where this motivation is shown lacking.

[FOM] Amusing observation about independence of complexity results
Thursday, May 22, 2008 8:33 PM
From: Timothy Y. Chow

Here is an amusing observation regarding the idea that the existence of contradictory relativizations of assertions such as is evidence that said assertions are independent of some strong theory.  I doubt this observation is new, but I haven’t seen it explicitly before.

We can write down (thanks to Levin, I think) an explicit machine with the property that, if , then solves in polynomial time. (Essentially multitasks over all polytime algorithms until it jackpots.) 

Suppose now that a statement such as

“ correctly solves in at most steps on length- inputs”

is independent of (for example).  The statement is stronger than the statement that , but we might imagine that if is independent of then something like will also be independent of .

Now is , so if it is independent of then it is true, and therefore .  It follows that , by the time hierarchy theorem for example.

This line of reasoning can itself be formalized, and this shows that in some system   call it    that is slightly stronger than , we can prove “if is independent of , then .” This in turn means that if we can prove “ is independent of ” in , then we certainly can’t prove “ is independent of .”

Informally speaking, the upshot is that since we know that , it is probably too much to expect that both “” and “” are provably independent of strong systems.  On the other hand, both “” and “” admit contradictory relativizations.  So it seems we should should be wary of drawing too tight a connection between contradictory relativizations and logical independence.

Tim

116c- Lecture 18

We briefly discussed relative constructibility and compared the models where is exclusively treated as a predicate with the models where is an element. In particular, is a model of choice but may fail to be.

An amusing application of the fact that is that the result of Exercise 3 from Homework 7 holds in , although the proof I wrote there uses choice. Namely, work in and consider two well-orderings of a set . We can assume that is an ordinal and the first well-ordering is . Let be the second well-ordering. Then (since is a set of ordered pairs of ordinals). In , where choice holds, (and therefore also in ) there is a subset of of the same size as and where coincides with .

Question. Find a `choice-free’ argument for Exercise 3. 

The main example we will consider of a model of the form is , due to its connection with determinacy.

We introduced the setting to discuss determinacy, namely infinite 2-person games with perfect information. We proved the Gale-Stewart theorem that open games are determined and discussed Martin’s extension to Borel games. A nice reference for the proof of Martin’s result (using the idea of `unraveling‘, which reduces any Borel game to an open game in a different space) is Kechris’s book on descriptive set theory.

116c- Homework 8

Homework 8

Due Thursday, June 5 at 2:30 pm. 

116c- Lecture 17

We verified that the sets form a continuous increasing sequence and are transitive. It follows that the reflection theorem holds for the and . Arguing in , we proved that is a model of , and the reflection theorem allowed us to simplify the proof in a few points.

We then proceeded to argue that is also a model of choice. In fact, there is a globally definable well-ordering of . It is worth emphasizing that the well-ordering is a very natural one, as we simply proceed to enumerate the sets in in the order in which their membership is verified. The definitions of the sequence of sets and of this well-ordering are absolute, and we used this to prove that is a model of the statement “,” and so is any , for limit. Moreover, the well-ordering of , when restricted to , coincides with its interpretation inside .

An easy induction shows that for infinite, . An argument using the Mostowski collapsing theorem allowed us to prove Gödel’s condensation lemma: If for a limit ordinal, then is isomorphic to some . These two facts combine to provide a proof that holds in .

Remark. These arguments prove that implies , but they also indicate that showing that implies ought to be more complicated. The reason is that the absoluteness of the construction of implies that if is a transitive proper class model of , then and in fact , i.e., the result of running the construction of from the point of view of is itself. But, since holds in , we cannot prove in that there is a non-constructible set. If we tried to establish the consistency of with the negation of choice by a similar method, namely, the construction of a transitive class model of , then running the construction inside would give us that , so , which would be a contradiction, since we are assuming that (provably in )  is a model of but is a model of choice.

This also suggests that in order to show that is independent of , one should try first to show that is consistent with . The remarkable solution found by Paul Cohen in 1963, the method of forcing, allows us to prove the consistency of both statements, and also to do this while working with transitive models. The method of forcing is beyond the scope of this course, but good explanations can be found in a few places, there is for example a book by Cohen himself, or look at Kunen’s book mentioned at the beginning of the course. Richard Zach has compiled in his blog a list of papers providing an introduction to the method (search for `forcing’).

116c- Lecture 16

We showed that  formulas are absolute among transitive models of (enough) set theory, and used this to prove that satisfiability for transitive sets is absolute. More precisely, let  mean that  is a transitive set , codes a formula ,  is a tuple of elements of , and . Then is . Using this and the reflection theorem we can conclude that is actually the extent of absoluteness in set theory, meaning that whenever there is a finite such that is absolute for transitive models of , then is .

We exhibited a few formulas that are not absolute. For example, “ is a cardinal” and “,” although both are and therefore relativize downwards.

The main application of the absoluteness of satisfiability is that it allows us to define the constructible hierarchy and Gödel’s constructible universe .

Remark. On the other hand, we cannot define in general satisfiability for transitive classes, by Tarski’s undefinability of truth theorem. The difference with the case of sets is that with sets the recursive definition of involves several bounded quantifiers, ranging over finite powers of . With general proper classes , these quantifiers would be unbounded. An easy inductive argument shows that we can define partial satisfiability predicates (and therefore partial truth predicates), meaning that for each natural number and each class  we can find a formula that defines satisfiability for formulas with respect to ; although we cannot in general find a uniform definition that works simultaneously for all .  

116c- Lecture 15

We presented a list of statements, definable relations, functions, and constants, that are absolute for transitive models of enough set theory. We showed that absolute functions are closed under composition, although functions are not. We also verified that being a well-ordering is absolute. The same argument actually shows:

Theorem. The statement “ is a well-founded relation on ” is absolute for transitive models of .

This is a key result very useful in a variety of situations. Notice that we are not claiming that being well-orderable is absolute; in fact, it is not. The difference is that in the first case we are given a witness to the well-orderability, and claim that no matter in which transitive model the witness is observed, in all of them it has the property of being a well-ordering. The second case only states that there is a witness, and a given model may very well fail to produce such a witness unless it is a model of the axiom of choice.

116c- Homework 7

Homework 7

Due Wednesday, May 28 at 2:30 pm.

Update. I present here a quick sketch of the solution of Exercise 3.(b). See Lecture 18, where it is shown that the result actually holds in , although the proof uses choice.

 Let and be two well-orderings of a set . We want to find a subset of of the same size as where the two well-orderings coincide. Let . By combining with an isomorphism between and its order type, we may assume that is an ordinal and . By restricting attention to the subset  of , we may assume is a well-ordering of . By further restricting to the subset of of order type under , we may assume that as well. 

Assume first that is regular. The result follows easily. The desired set can be built by a straightforward recursion: Given and  a sequence of elements of increasing under both well-orderings, regularity ensures that the sequence is bounded under both well-orderings, and we can find which is larger than all the previous under both orderings.

The argument for singular is slightly more delicate. Namely, we may not be able to carry out the construction above since the sequence could be unbounded in one of the orderings when . We circunvent the problem by only considering ordinals whose cofinality is larger than the cofinality of . Notice that if an increasing sequence of order type   is unbounded in an ordinal of cofinality , then .

To implement this idea, let be an increasing sequence of regular cardinals cofinal in , with . Consider the subset . It must contain a subset of size where coincides with . By the remark above, this subset is bounded in . Let denote the shortest initial segment of containing . By removing from the set , we are left with a set of size , and any ordinal there is larger than the elements of under both orderings. The induction continues this way, by considering at stage a set of size .

116c- Lecture 14

We defined absoluteness of formulas with respect to two classes ; for example, every formula is absolute with respect to and , if is transitive. Once we establish a sufficiently long list of properties that are absolute with respect to a transitive model of (enough of) and , we will be able to prove a few relative consistency results. The main application will be in the proof that Gödel’s constructible universe is a model of (and of choice and ), but a few other examples will be presented as well.

We proved the reflection theorem and some of its consequences, in particular, that no consistent extension of is finitely axiomatizable.

An important application of these techniques is the use of basic model theoretic tools to establish combinatorial facts. Some examples will be explored in the next homework set.