2   Transitive Models  Observation  If M is transitive and M     e is empty   then e      This is because if w   e  then w   e and e   M gives us that w   M by transitivity  so M   w   e  so M     e is not empty    Lemma  Assuming that   M is transitive  Then      M   Extensionality   Foundation       Proof  Extensionality    x   y     w   w   x   w   y     x   y    Take x   y  x   y   M  Without loss of generality take z   x   y  Then z   x and x   M so z   M  So M   z   x   z   y  So M       w   w   x   w   y     Foundation    x   x         m   m   x     w     w   m   w   x        Take x   M  M   x     so x is not empty  So find m   x which is   minimal  Then since x   M as well  we have m   M  Therefore x has an   minimal element in M     2 1   Absoluteness for transitive models  Definition   Bounded quantifier   We call a quantifier of the form   x   y     or   x   y     a bounded quantifier    Defined by   x   y           x   x   y       and   x   y         x   x   y          Definition   Closed under bounded quantification   A class of formulas   is closed under bounded quantification  if whenever    is in    then so are   x   y     and   x   y       Definition   Delta0     0 is the smallest class of formulas containing the atomic formulas that is closed under propositional connectives and bounded quantifiers   Let T be any theory  Then   0 T is the class of formulas equivalent to a   0 formula in T   Theorem    0 formulas are absolute for transitive models   Proof  By induction    1    All atomic formulas are absolute by the substructure lemma    2    Propositional connectives  exactly the same proof as in the substructure lemma    3    Assume that   is absolute and show that   x   y     and   x   y     are absolute     x   y      If   x   y     is true for some y   M  then pick a witness x   y  Since y   M  we have x   M  By the induction hypothesis  we have that M       x   y    Thus M     x   x   y       x   y       If M     x   x   y       x   y      then x   y       x   y   is true     x   y      Similar     Corollary  Assuming that   T is any theory  M   T is transitive  Then     0 T formulas are absolute for M   Definition   S i g m a 1  P i 1   A formula is called   1 if it is of the form   x 1       x n     where   is    0   It is called   1 if it is of the form   x 1         x n      where   is    0    same for   1 T    1 T    Proof  Just definition of the semantics of           Example  What is    0   1    x   y  2    x   y  3    x   y      w   x   w   y    4    z     x      x   z     w   z   w   x    5    z     x   y    6    z     x   y         x       x   y      7    z          w   z   w   w    8    z   x   y    x   z   y   z     w   z   w   x   w   y    9    z   x   y  10    z   x   y  11    z   x     x    12    z is transitive  13    z     x  Definition   Absolute function   Let M a transitive set  and F   M n   M  note that this means that M  is closed under F   We say F is absolute  for  M if there is a formula   which is absolute for M such that      F   x 1       x n     z       x 1       x n   z         Observation  So  if M is closed under pairing    x   y   M     x   y     M   then the pairing operation x   y     x   y   is absolute  and therefore M   Pairing   Similarly for union   Lemma  Assuming that     is absolute for M  F   G 1       G n are absolute operations on M  Then          x 1       x m           G 1   x 1       x m         G n   x 1       x m     H   x 1       x m       F   G 1   x 1       x m         G n   x 1       x m         are absolute for M   Proof  Check the definitions     Example  More examples    14    z is an ordered pair         s   z     d   z     x   s     y   d       w   s     w   x       v   d     v   x   v   y       w   z     w   s   w   d            15    z   a   b   16    z is a relation   17    z   dom x   18    z   range x   19    z is a function   20    z is injective   21    z is surjective   22    z is bijective  Ordinals   x is an ordinal  means x is transitive and   x       is a well order   We know  being well founded is not expressible in first order logic  see Example Sheet 1     Because all transitive models satisfy Foundation  we have that if M is transitive  then      M   x is transitive     x       is linearly ordered       characterises ordinals  But this is clearly in    0   So  being an ordinal is absolute for transitive models   Thus M   Ord     x   M   M   x is an ordinal    This is transitive  thus there is     Ord such that     M   Ord   Also absolute     x is a successor ordinal     y   T O D O    x is a limit ordinal    x is a non zero limit ordinal   x     TODO  Cardinals   x is a cardinal  if and only if      x is an ordinal     f     y   x   f   y   x   f is not a surjection     Note that   f is not bounded  while   y   x is bounded    Observe  this is    1 and therefore downwards absolute   Remark    1    We may not want  this to be absolute  If it was  we couldn t change cardinal behaviour    2    We can t obviously bound   f  since the natural bound would be        h   h   y   x       or      P   y   x         These  however  are not  yet    on our list of absolute concepts    3    Not that neither  1  nor  2  is an argument  since there could be an equivalent formula that is    0   2 2   Non absoluteness  Assume that M   ZFC is transitive and countable  Then      M   Ord         1       However  M   ZFC implies M   there are uncountable cardinals   Let       be such that M     is the least uncountable cardinal   But   is a countable ordinal  so not a cardinal   Consequence   All cardinals in M except   0 are going to be fake   So  x is a cardinal  can t be absolute   Note   This also shows that  x   P   y    cannot be absolute   Take y such that M   y   P        Then y   P        but is countable since y   M   Thus y   P        Therefore  x   P   y    is not absolute    Recall the general proof strategy mentioned before   If M is a countable transitive set such that M   ZFC  then there is a a countable transitive set N   M such that N   ZFC     CH   Question   Is this really solving the original problem  i e  Con   ZFC     Con   ZFC     CH     It s not obvious that Con   ZFC   implies that there is a countable transitive model  ctm  of ZFC   Answer   That s not only not obvious  but fake   Let s prove that Con   ZFC       there is a countable transitive model of ZFC   Why  Note that Con   ZFC    or Con   T   for  any T is    0  So  it s absolute for transitive models   So if M is a countable transitive model of ZFC  then Con   ZFC   is true  so by absolute ness  M   Con   ZFC    So M   ZFC   Con   ZFC    This contradicts G del s Incompleteness Theorem  We can get a proof of      Con   ZFC     Con   ZFC     CH       via a trick   Example Sheet 1     Lemma   Cohen Lemma   Assuming that   T   ZFC  Then  there is finite T     ZFC such that if M is a countable  transitive model of T    then there is N   M such that N is a countable transitive model of T     CH   This reduces the problem to   Find countable transitive models of T   for sufficiently large finite T     ZFC   Definition   Hierarchy   We call an assignment     Z   a hierarchy  if   i  Z   is a transitive set   ii  Ord   Z         iii          Z     Z     iv    limit   Z             Z    If   Z         Ord   is a hierarchy  we can define Z           Ord Z    This is a proper class as Ord   Z  We also define   Z   x       min       x   Z      a notion of Z rank   Paradigmatic example  von Neumann hierarchy V    and V is the entire universe   Theorem 2 1   Levy Reflection Theorem    Assuming that   Z is a hierarchy    is a formula  Then  there are unboundedly many   such that   is absolute between Z   and Z   Proposition 2 2   Tarski Vaught Test    Assuming that   M is a substructure of N  Then  M is an elementary substructure  if and only if for any formula     v   w     and a     M  if there is b   N such that N       b   a      then there is c   M such that N       c   a       TVT    Let M   N and   be a collection of formulas closed under subformulas  Then the following are equivalent    i  All formulas in   are absolute between M and N    ii  For all        the TV condition  holds  if       x    then for all y     M if there is a   N sucht hat N       a   y      then there is b   M such that N       b   y       Warm up  let   M         ZFC  Find countable N   M such that   N           M         Suppose p       p 0       p n     M and M     y       y   p      Let w       p     be a witness for this       M       w       p       p          if necessary  use Axiom of Choice     if M       y       y   p      then let w       p            Set      N 0       N i   1       w       p         formula and p     N 1       N       i     N i     Note    1    N is countable    2    M   N by Tarski Vaught Test   Remark   In general  even if M is transitive  N is not   For example  if   1   M  then        x     x is the least countable ordinal       is true in M      w               1       So   1   N  But   1   N  since N is countable    Relevant later   Also see Example Sheet 1   Proof of  Levy Reflection Theorem    Fix   and let   be its collection of subformulas  This is a finite set   Need to show                such that Z         Z       For each       and p       p 0       p n    write     o       p           least   such that   y   Z   with Z       y   p     if it exists 0 otherwise o   p         max       o       p       0         1   i   1     sup   o   p       p     Z   i             sup i       i     Then Tarski Vaught Test implies that Z   and Z agree on       Corollary  If T   ZFC is finite  then there is M transitive such that M   T   Proof  Let             T    Since ZFC       we have that   is true  By Levy Reflection Theorem  we can find   such that V        Note V   is transitive     Remark about the proof of Levy Reflection Theorem   Can you do the same if   is infinite   Of course not  otherwise we colud prove that there exists   such that V     ZFC  and hence get Con   ZFC     The problem is the case distinction in the definition of o       p      it requires to check whether   y     is true   Next goal   Obtain some M   V   countable such that M     and M is transitive   TODO  Theorem   Mostowski s Collapsing Theorem   Let r be a relation on a set a that is well founded and extensional  Then there exists a transitive set b  adn a bijection f   a   b  such that     x   y   a     x r y   f   x     f   y      Moreover  b and f are unique   Proof  See Logic and Set Theory     Corollary  For every T   ZFC finite  there is a countable transitive model of T   Proof  Without loss of generality that T contains the axiom of extensionality  Form M   T transitive by Levy Reflection Theorem  Use warm up to obtain N   M countable  This is extensional and well founded  so by Mostowski find W transitive such that        W           N             Then W   T adn   W          so W is countable     The next few lectures will be spent proving Con   ZFC   CH   using G del s constructible universe   Absoluteness is preserved under transfinite recursion   Let F   G   H be three operations      R   0   x         F   x     R       1   x         G       R       x       x     R       x         H         R       x                 x               Proof  Attempts  set functions satisfying the        L1   All attempts agree on their common domain   L2           r attempt such that       x       dom   r     R       x         y if and only if there exists attempt r with       x       dom   r   and r       x       y     Note that for F   G   H fixed  there is a finite fragment T F   G   H   ZFC that proves the recursion theorem instance for F   G   H   Theorem  If T   T F   G   H and F   G   H are absolute for transitive models of T  then so is R defined by        Want T F   G   H   L 1   F   G   H    T F   G   H   L 2   F   G   H   and T F   G   H proves existence of R   Convention  We say  T is sufficiently strong  if T   ZFC is finite and T proves hte existence of all relevant operations such that they are absolute for transitive models of T   Proof  Observe that by assumption  being an  attempt  is absolute for transitive models of T   Let M   T be transitive    1    To show  If M   R       x       z  then R       x       z  If M   R       x       z  then M     r   r is an attempt and r       x       z  Without the   r  this would be absolute  So when we include the existential quantifier  we get an upwards absolute  sentence   Thus  there is r  such that r is an attempt and r       x       z  So R       x       z    2    Other direction  Assume r is an attempt with r       x       z  Since T F   G   H   L 2   F   G   H    we have      M     r     r   is an attempt and       x       dom r     absolute       Since it is absolute  r   is a real attempt   By      r         x       r       x      Hence M   R       x       z     Note   This uses the fact that    1  concepts are absolute    Definition   Delta1T property   A property is called   1 T if it s both    1 T and    1 T   Observe      0 T concepts are absolute  upwards from    1 and downwards from    1    Typical Applications  Bounding a quantifier by operation   Let F be an operation and T strong enough to prove F is an operation and absolute      T     x     z   F   x     z T     x     z     z     F   x     z   F   x     z     z   z       Then the quantifiers   y   F   x   and   y   F   x   preserve absoluteness        y   F   x         z   z   F   x       y   z       absolute   upwards absolute     z   z   F   x       y   z       absolute   downwards absolute     Applications   1    Encode formulas as elements of                                             v 0   v 1   v 2       0  1  2  3  4  5  6  7  8  9  1 0  1 1        v 0   v 1   v 0   v 1 would be   8   9   7   1 0   6   8   0   1 0     F m l          So  F m l is absolute for some  sufficiently strong  finite fragment of ZFC  see Example Sheet 1      2    If X is any set then        X            which means    X             is defined by the usual  Tarski  recursion and thus also absolute   Example Sheet 1     2 3   The constructible hierarchy  Fix a set X  Define for each      Fml and each p   X      parameter       D       p   X         w   X   X       p   w         the subset of X defined by   with parameter p   For a sufficiently strong T   ZFC finite  we have that T proves that D is an absolute operation  see Example Sheet 1         D   X         D       p   X         Fml   p   X             This is absolute for a sufficiently strong theory  use Replacement to get D   X      This D   X   is sometimes  misleadingly  called the  definable power set of X   it is misleading because it is more like a  definable  by X  power set of X           D   X           Fml     p   X       a   D       p   X     Obvious  D   X     P   X    Also  If X is transitive  then so is D   X        L 0       L     1     D   L     L             L       The constructible hierarchy  We usually write L           Ord L     Claim   L is a hierarchy  in the sense of Lecture   See Example Sheet 1   By closure of absoluteness under transfinite recursion  the L hierarchy is absolute  for transitive models of T   ZFC where T is strong enough to prove that it exists   i e  if M   T transitive and     Ord   M and M   X   L    then X   L    So            Ord   M L     M       The main theorem of next lecture will be   If L   ZF and M   ZF transitive  then            Ord   M L     ZF        Minimal ZF model    Some first idea of what the L hierarchy is like  Clearly  by induction  L     V    and clearly for n      L n   V n  So L     V        L     1           Fml   p   L         D       p   L             If        then       L     1       0     L             0     L           Thus   L         L     1     Therefore       1    L         0 and   L   1       1   This means  V     1   L     1  since the first has size 2   0  while the second has size   0    Note  This does not mean V   L   V   L means   x         x   L      V   L is called the  axiom of constructibility    There is a finite fragment T   of ZF    that proves that all of the operations occuring in the definition of    i e   Fml   X           D   D are well defined and absolute   Thus  if M is a transitive model of T    then            Ord   M         M     and thus       M   So       Ord   M       M   Axioms of ZF  Structural axioms   Extensionality         x     y       w   w   x   w   y     x   y         Foundation         x     v     v   x       m     m   x     w       w   m   w   x             Infinity         i     e       v     v   e   e   i       x     x   i     s     s   i     w     w   s   w   x   w   x             Functional axioms   Pairing         x     y     p     w     w   p   w   x   w   y         Union         x     v     w     w   v     z     z   x   w   z           Powerset         x     p     w     w   p     v     v   w   v   x           Separation          p       x     s     w     w   s   w   x       w   p             Replacement          p         x     y     z       x   y   p           x   z   p       y   z         x     r     w     w   r     y     y   x       y   w   p               Now we check that these hold in     In Lecture 2  we proved Extensionality and Foundation in all transitive structures  so also in     Note that   satisfies the condition of the axiom of infinity  so any M transitive with     M will satisfy the axiom of infinity  TODO  Now do pairing and union   Since the definitions of pairs and unions     z     x   y   z     x     are absolute for transitive models  it s enough to show that       x   y         x   y         x       x         If x   y            w   x   y       w   x   w   y      D         x   y     L         w   L     L         w   x   y         w   L     L     w   x   w   T O D O     Powerset axiom        x     p     w     w   p   w   x           The problem here is that   is not obviously absolute  In particular  z   P   x   is not absolute   Consider       1  we have           1 and P         1 is countable   In       2  we find        a         1   a           which is the best possible answer to the question  what is the power set of     that       1 can give  but unlikely to be the correct answer   Consider instead P               P and define                    a     a   P          reminder        a   is the least   such that a         1   By Replacement    is a set of ordinals  so find        Then P         Therefore P     a         a               1  so P       Separation        p       x     s     w     w   s   w   x       w   p             w   x   p           If x        then     D         x   L           w   L     L           w   x   p           w   L     L     w   x       w   p             w       not a problem       this is a problem   w   x       w   p           If   is not absolute between L   and L  this won t work   Levy Reflection Theorem to the rescue                      such that   is absolute between L   and L   Thus  form     D         x   L         w   L     L     w   x       w   p         absolute   w   L     L   w   x       w   p           Replacement   This will be on Example Sheet 2  The proof is a combination of the ideas from power set and separation   Corollary 2 3   Minimality    Assuming that   T is a transitive model of ZF  Then  for all     T   Ord        T  Axiom of TODO   Remark   Remark on the Axiom of Choice   G del  1938   Con   ZF     Con   ZFC     Note first that everything we did so far only needed ZF in the universe  We will sketch that     AC  In fact a strong version of AC known as GLOBAL CHOICE  there is an absolutely definable bijective operation between   and Ord   Sketch  Recursive construction of bijections                 for some ordinal      and such that for       we have                   If   is a limit and     is defined for        then let            x             x       if x         Suppose         1 and     is given by                   Consider  Fml   L        Well order it in order type       via the induced      well order  Then if x   L    say            x               x   if x   L         if   is the ordinal corresponding to the least       p     such that x   D       p     T O D O       TODO  Cohen     T   ZFC finite    T     ZFC finite such that if M is a countable transitive model of T    then there is N   M countable transitive model of T     CH       We have seen   Example Sheet 1   that     implies Con   ZFC     Con   ZFC     CH     Simplified  If M is a countable transitive model of ZFC  then there is N   M countable transitive model of ZFC h     CH   Idea   If M is a countable transitive model of ZFC          1 M          2 M  f       P       injection  Force N such that f   N  and M   N   Observe that there is a countable transitive model  N such that f   N and M   N  M   tcl     f     is transitive and countable  Thus LSM gives N transitive countable with M   tcl     f       N  Know N     g       P       is an injection  but no clue what   1 and   2 in N are   How do we control what we add