116c- Lecture 9

April 30, 2008

We proved König’s theorem and results of Hausdorff and Tarski on cardinal exponentiation, indicated some of their consequences (for example, {\mathfrak c}\ne\aleph_\omega), and showed how to compute under {\sf GCH} the function (\kappa,\lambda)\mapsto\kappa^\lambda.

We stated Easton’s result essentially saying that without additional assumptions, in {\sf ZFC} nothing can be said about the exponential function 2^\lambda beyond monotonicity and König’s theorem.

For singular cardinals the situation is much more delicate. We stated as a sample result Shelah’s theorem that if \aleph_\omega is strong limit, then 2^{\aleph_\omega} is regular and smaller than \aleph_{\min(\omega_4,{\mathfrak c}^+)}.

This result is beyond the scope of this course. Instead, we will prove a particular case of an earlier result of Silver, namely, that \aleph_{\omega_1} is not the first counterexample to {\sf GCH}.

In order to prove Silver’s result, we need to develop the theory of club and stationary sets. We defined these notions and proved some of their basic properties.

2 Comments | 116c: Set theory | Permalink
Posted by andrescaicedo

116c- Homework 4

April 29, 2008

Homework 4.

Due Wednesday, May 7 at 2:30 pm.

Update. In exercise 2, \lambda=\mu, of course. In exercise 3, (\kappa)^\lambda in the right hand side must be (<\kappa)^\lambda.

Hint for exercise 5: Consider the smallest \alpha such that \alpha+\beta>\beta (ordinal addition).

Update. Here is a quick sketch of the solutions:

  • 1.(a). Write \kappa=\sum_{\alpha<{\rm cf}(\kappa)}\kappa_\alpha for some (not necessarily strictly) increasing {\rm cf}(\kappa)-sequence of cardinals \kappa_\alpha<\kappa. (If \kappa is regular, take \kappa_\alpha=1 for all \alpha. If \kappa is singular, let the \kappa_\alpha be increasing and cofinal in \kappa.) Then 2^\kappa=2^{\sum_{\alpha<{\rm cf}(\kappa)}\kappa_\alpha}=\prod_\alpha2^{\kappa_\alpha}\le\prod_\alpha2^{<\kappa}=(2^{<\kappa})^{{\rm cf}(\kappa)} but also (2^{<\kappa})^{{\rm cf}(\kappa)}\le (2^\kappa)^\kappa=2^\kappa and the result follows. If \kappa is strong limit, then 2^{<\kappa}=\kappa, and we get 2^\kappa=\kappa^{{\rm cf}(\kappa)}.
  • 1.(b). Under the assumption, we may choose the \kappa_\alpha as in 1.(a) such that {\rm cf}(\kappa)<\kappa_0 and 2^{\kappa_\alpha}=2^{\kappa_\beta} for all \alpha<\beta<{\rm cf}(\kappa). Then 2^\kappa=(2^{<\kappa})^{{\rm cf}(\kappa)}=(2^{\kappa_0})^{{\rm cf}(\kappa)}=2^{\kappa_0}=2^{<\kappa}.

 

  • 2. Write \mu as a disjoint union of \mu sets A_\alpha, \alpha<\mu, each of size \mu. This is possible since \mu\times\mu=\mu. Since each A_\alpha has size \mu, it is necessarily cofinal in \mu. We then have \kappa^\mu\ge\prod_{i\in\mu}\kappa_i=\prod_{\alpha\in\mu}\prod_{i\in A_\alpha}\kappa_i\ge\prod_\alpha\kappa=\kappa^\mu.

 

  • 3. If \kappa\le 2^\lambda, then 2^\lambda\le\kappa^\lambda\le(2^\lambda)^\lambda=2^\lambda.
  • If \lambda<{\rm cf}(\kappa) then any function f:\lambda\to\kappa is bounded, so {}^\lambda\kappa=\bigcup_{\alpha<\kappa}{}^\lambda\alpha, and \kappa^\lambda\le\sum_\alpha|\alpha|^\lambda\le\kappa\cdot(<\kappa)^\lambda; the other inequality is clear.
  • Suppose that {\rm cf}(\kappa)\le\lambda, 2^\lambda<\kappa, and \rho\mapsto\rho^\lambda is eventually constant as \rho approaches \kappa. Choose a strictly increasing sequence (\kappa_\alpha:\alpha<{\rm cf}(\kappa)) cofinal in \kappa such that \kappa_\alpha^\lambda=\kappa_\beta^\lambda for \alpha<\beta<{\rm cf}(\kappa). Then \kappa^\lambda\le(\prod_\alpha\kappa_\alpha)^\lambda=\prod_\alpha\kappa_\alpha^\lambda=\prod_\alpha \kappa_0^\lambda=\kappa_0^{\lambda\cdot{\rm cf}(\kappa)}=\kappa_0^\lambda=(<\kappa)^\lambda. The other inequality is clear.
  • Finally, suppose that {\rm cf}(\kappa)\le\lambda, 2^\lambda<\kappa, and \rho\mapsto\rho^\lambda is not eventually constant as \rho approaches \kappa. Notice that if \rho<\kappa then \rho^\lambda<\kappa. Otherwise, \tau^\lambda=(\tau^\lambda)^\lambda\ge\kappa^\lambda\ge\tau^\lambda for any \rho\le\tau<\kappa, and the map \rho\mapsto\rho^\lambda would be eventually constant below \kappa after all. Hence, (<\kappa)^\lambda=\kappa. Choose an increasing sequence of cardinals (\kappa_\alpha:\alpha<{\rm cf}(\kappa)) cofinal in \kappa. Then \kappa^\lambda\le(\prod_\alpha\kappa_\alpha)^\lambda=\prod_\alpha\kappa_\alpha^\lambda\le\prod_\alpha (<\kappa)^\lambda=\prod_\alpha\kappa=\kappa^{{\rm cf}(\kappa)}. The other inequality is clear.

 

  • 5. Suppose that \beta\ge\omega and for all \alpha, 2^{\aleph_\alpha}=\aleph_{\alpha+\beta}. Let \alpha be least such that \beta<\alpha+\beta; \alpha exists since \beta<\beta+\beta. On the other hand, \alpha is a limit ordinal, since 1+\omega=\omega and \omega\le\beta, so (\lambda+n)+\beta=\lambda+(n+\beta)=\lambda+\beta for any \lambda and any n<\omega, and we would have a contradiction to the minimality of \alpha. Let \gamma<\alpha. Then \gamma+\beta=\beta and 2^{\aleph_{\alpha+\gamma}}=\aleph_{\alpha+\beta}. By exercise 1.(b), 2^{\aleph_{\alpha+\alpha}}=\aleph_{\alpha+\beta} since \aleph_{\alpha+\alpha} is singular (it has cofinality {\rm cf}(\alpha)\le\alpha<\alpha+\alpha\le\aleph_{\alpha+\alpha}). This is a contradiction, since by assumption, 2^{\aleph_{\alpha+\alpha}}=\aleph_{\alpha+\alpha+\beta}>\aleph_{\alpha+\beta}.

 

  • 4. We want to show that \prod_{\xi<\beta}\aleph_\xi=\aleph_\beta^{|\beta|} for all limit ordinals \beta. Write \beta=|\beta|+\alpha where \alpha=0 or a limit ordinal, and proceed by induction on \alpha, noticing that the case \alpha=0 follows from exercise 2.
  • Notice that any limit ordinal \alpha can be written as \alpha=\omega\cdot\delta for some nonzero ordinal \delta. This is easily established by induction. If \delta is a limit ordinal, then any sequence converging to \delta gives rise in a natural way to a sequence of limit ordinals converging to \alpha. On the other hand, if \delta is a successor, then \alpha=\lambda+\omega for some \lambda=0 or limit. In summary: any limit ordinal is either a limit of limit ordinals, or else it has the form \lambda+\omega for \lambda=0 or limit.
  • We divide our induction on \alpha in two cases. Suppose first \alpha=\lambda+\omega, as above. Then \prod_{\xi<\beta}\aleph_\xi=\aleph_{|\beta|+\lambda}^{|\beta|}\prod_n\aleph_{|\beta|+\lambda+n}, by induction. Since |\beta|=|\beta|\aleph_0, we have \aleph_{|\beta|+\lambda}^{|\beta|}\prod_n\aleph_{|\beta|+\lambda+n}=\prod_n\aleph_{|\beta|+\lambda}^{|\beta|}\aleph_{|\beta|+\lambda+n}=\prod_n\aleph_{|\beta|+\lambda+n}^{|\beta|}, where the last equality holds by Hausdorff’s result that (\kappa^+)^\tau=\kappa^+\cdot\kappa^\tau. Finally, \prod_n\aleph_{|\beta|+\lambda+n}^{|\beta|}=(\prod_n\aleph_{|\beta|+\lambda+n})^{|\beta|}=(\aleph_\beta)^{\aleph_0\cdot|\beta|}=\aleph_\beta^{|\beta|} as wanted, where the previous to last equality is by exercise 2.
  • Now suppose that \alpha is a limit of limit ordinals. Choose a strictly increasing sequence (\gamma_\nu:\nu<{\rm cf}(\alpha)) of limit ordinals cofinal in \alpha. We argue according to which of the four possibilities described in exercise 3 holds. If \aleph_\beta\le 2^{|\beta|} then \aleph_\beta^{|\beta|}=2^{|\beta|}\le\prod_{\xi<\beta}\aleph_\xi\le\aleph_\beta^{|\beta|}.
  • Notice that {\rm cf}(\alpha)={\rm cf}(\beta)={\rm cf}(\aleph_\beta) and {\rm cf}(\beta)\le|\beta|, so the second possibility does not occur.
  • Suppose now that we are in the third possibility, i.e., 2^{|\beta|}<\aleph_\beta and \rho\mapsto\rho^{|\beta|} is eventually constant as \rho approaches \aleph_\beta. Then \aleph_\beta^{|\beta|}=(<\aleph_\beta)^{|\beta|}=\sup_{\nu<{\rm cf}(\alpha)}\aleph_{|\beta|+\gamma_\nu}^{|\beta|}=\sup_\nu\prod_{\xi<|\beta|+\gamma_\nu}\aleph_\xi, by induction (it is here that we used the assumption that \alpha is a limit of limit ordinals). And \sup_\nu\prod_{\xi<|\beta|+\gamma_\nu}\aleph_\xi\le\prod_{\xi<\beta}\aleph_\xi\le\aleph_\beta^{|\beta|}.
  • Finally, if 2^{|\beta|}<\aleph_\beta and \rho\mapsto\rho^{|\beta|} is not eventually constant as \rho approaches \aleph_\beta, then \aleph_\beta^{|\beta|}=\aleph_\beta^{{\rm cf}(\alpha)} and \aleph_\beta^{{\rm cf}(\alpha)}=\prod_{\nu<{\rm cf}(\alpha)}\aleph_{|\beta|+\gamma_\nu}, by exercise 2, but \prod_{\nu<{\rm cf}(\alpha)}\aleph_{|\beta|+\gamma_\nu}\le\prod_{\xi<\beta}\aleph_\xi\le\aleph_\beta^{|\beta|}, and we are done.

Leave a Comment » | 116c: Set theory | Tagged: | Permalink
Posted by andrescaicedo

116c- Lecture 8

April 24, 2008

We defined infinite sums and products and showed that if \max\{2,\kappa_i\}\le\lambda_i for all i\in I, then \sum_{i\in I}\kappa_i\le\prod_{i\in I}\lambda_i.

We also showed that if (\kappa_i:i<\mbox{cf}(\kappa)) is an increasing sequence of cardinals cofinal in \kappa, then \prod_{i\in\mbox{\small cf}(\kappa)}\kappa_i=\kappa^{\mbox{\small cf}(\kappa)}. In particular, \prod_n\aleph_n=\aleph_\omega^{\aleph_0}.

We defined singular cardinals and showed that (with choice) all successor cardinals are regular and all limit cardinals \aleph_\alpha are singular unless \alpha=\aleph_\alpha. We showed that, indeed, there are fixed points of the aleph function, as a particular case of a result about normal functions. We defined (weakly) inaccessible cardinals as the regular limit cardinals (thus, regular fixed points of the aleph function).

Correction. I believe during lecture I mixed two arguments by mistake, making one of the proofs come out unnecessarily confusing, so I will present the correct argument here, for clarity.

In lecture we showed that if F is a normal function, then it has a proper class of fixed points. Thus, we can enumerate them in increasing order. Let G be this enumeration.

Claim. G was also normal.

Proof. We need to check that G is continuous. Let \gamma be a limit ordinal and suppose that \tau=\sup_{\beta<\gamma}G(\beta). We need to show that G(\gamma)=\tau.

By definition, this means that:

  1. \tau is a fixed point of F, and 
  2. \tau is the \gamma-th fixed point of F.

But, clearly, if \tau is a fixed point, then it must be the \gamma-th one, since we have already enumerated \gamma fixed points below \tau, and any fixed point below \tau is below some G(\beta) with \beta<\gamma, so it is not even the \beta-th one.

So we only need to check that F(\tau)=\tau. But \tau=\sup_{\beta<\gamma}G(\beta) and each G(\beta) is a fixed point of F (again, by definition of G), so \tau=\sup_{\beta<\gamma}F(G(\beta))=F(\sup_{\beta<\gamma}G(\beta))=F(\tau), where the previous to last equality is by continuity of F. {\sf QED}

It follows that G itself has a proper class of fixed points. It is also the case that there is a proper class of fixed points of F that are limits of fixed points of F: Simply notice that the argument above shows that any limit of fixed points of F is itself a fixed point. Thus, we have:

Corollary. The function H:{\sf ORD}\to{\sf ORD} enumerating the limit points of G (i.e., the fixed points of F that are themselves limit of fixed points) is normal.

I believe during lecture I mixed at some point H and G (although I never explicitly mentioned H). Hopefully the above clarifies the argument. For the particular case of F(\alpha)=\aleph_\alpha, we have that G enumerates the ordinals \alpha such that \alpha=\aleph_\alpha, so G(0) is the first such cardinal. The function H enumerates the limit points of G, so H(0)=G(\omega). Notice that \mbox{cf}(H(0))=\mbox{cf}(G(\omega))=\omega. One can easily see that if \kappa is a weakly inaccessible cardinal, then \kappa is a fixed point of F, G and H.

In fact, define F_0(\alpha)=\aleph_\alpha for all \alpha, let F_{\beta+1} be the enumeration of the fixed points of F_\beta, and let F_\gamma (for \gamma limit) enumerate the ordinals \kappa that are simultaneously fixed points of all the F_\beta for \beta<\gamma. Then, if \kappa is weakly inaccessible, then F_\alpha(\kappa)=\kappa for all \alpha<\kappa.           

Remark.

  1.  We did not prove that weakly inaccessible cardinals exist. The examples given in lecture of fixed points of the aleph function have cofinality \omega and, similarly, we can produce fixed points of arbitrarily large cofinality, but the argument falls short of finding regular fixed points (in fact, we can show that each F_\alpha as defined above is normal, but the argument does not show that we can “diagonalize” to obtain a \kappa fixed for all F_\alpha with \alpha<\kappa). In fact, it is consistent with {\sf ZFC} that all limit cardinals are singular. However, it is the general consensus among set theorists that the existence of inaccessible cardinals is one of the axioms of set theory that the original list {\sf ZFC} somehow missed.
  2. We defined normal functions as proper classes; however, we can as well define for any ordinal \alpha a function F:\alpha\to{\sf ORD} to be normal iff it is strictly increasing and continuous. The same argument as in lecture (or above) then shows that if \mbox{cf}(\kappa)>\omega and F:\kappa\to\kappa is normal, then there is a closed and unbounded subset of \kappa consisting of fixed points of F. It turns out that closed unbounded sets are very important in infinitary combinatorics, and we will study them in more detail in subsequent lectures.

Leave a Comment » | 116c: Set theory | Permalink
Posted by andrescaicedo

116c- Lecture 7

April 22, 2008

We presented the proof that “k-trichotomy” implies choice. The following is still open:

Question. ({\sf ZF}) Assume that X is non-well-orderable. Is there a countably infinite family of pairwise size-incomparable sets?

We mentioned a few (familiar) statements that fail in the absence of choice, like the existence of bases for any vector space, Tychonoff’s theorem, or the “surjective” version of the Schröder-Bernstein theorem.

We defined addition, multiplication and exponentiation of cardinals, and verified that addition and multiplication are trivial. We stated the continuum hypothesis {\sf CH}, and the generalized continuum hypothesis {\sf GCH}.

We want to prove (in subsequent lectures) a few non-trivial results about the behavior of exponentiation. In order to do this, we need the key notion of cofinality. We proved a few basic facts about cofinality and defined regular cardinals.

Leave a Comment » | 116c: Set theory | Permalink
Posted by andrescaicedo

116c- Homework 3

April 22, 2008

Homework 3.

Update. Now due Wednesday, April 30 at 2:30 pm.

Corrections. (Thanks to Fedor Manin for noticing these.)

  • On Exercise 2.(c), assume in addition that (\lambda,\alpha) satisfies the conditions of (\alpha,\beta) in item 2.(a); this should really be all that is needed of 2.(c) for later parts of the exercise.
  • On Exercise 2.(f), we also need n>0.

    • Update. Here is a quick sketch of the proof of the Milner-Rado paradox.

    First notice that the result is clear if \kappa=\omega, since we can write any \alpha<\omega_1 as a countable union of singletons. So we may assume that \kappa is uncountable.

    Notice that |\kappa^{\cdot\rho}|=\kappa. This can be checked either by induction on \rho<\kappa^+, or by using the characterization of ordinal exponentiation in terms of functions of finite support.

    Notice that the function \alpha\mapsto\omega^{\cdot \alpha} is normal. By the above, it follows that \omega^{\cdot\lambda}=\lambda for all uncountable cardinals \lambda. In particular, it suffices to prove the result for ordinals \alpha that are an ordinal power of \kappa, since these ordinals are cofinal in \kappa^+, and a representation as desired for an ordinal gives (by restriction) such a representation for any smaller ordinal.

    By the above, \kappa^{\cdot\rho}=\omega^{\cdot\kappa\cdot\rho} for any \rho. It is easy to see that for any \delta, if \alpha<\omega^{\cdot\delta}, then the interval \null[\alpha,\omega^{\cdot\delta}) is order isomorphic to \omega^{\cdot\delta}; this can be proved by a straightforward induction on \delta.

    For any \alpha<\kappa^+, we can write \kappa^{\cdot\alpha+1}=\bigcup_{\nu<\kappa}A_\nu, where A_\nu=[\kappa^{\cdot \alpha}\cdot\nu,\kappa^{\cdot\alpha}\cdot(\nu+1)) so it has order type \kappa^{\cdot\alpha}.

    Also, if \alpha is a limit ordinal below \kappa^+, then we can write \alpha=\sup_{\nu<\mbox{\small cf}(\alpha)}\beta_\nu for some strictly increasing continuous sequence (\beta_\nu:\nu<\mbox{cf}(\alpha)) cofinal in \alpha. Let A_0=\kappa^{\cdot\beta_1} and A_\nu=[\kappa^{\cdot\beta_\nu},\kappa^{\cdot\beta_{\nu+1}}) for 0<\nu<\mbox{cf}(\alpha). Then \kappa^{\cdot\alpha}=\bigcup_\nu A_\nu and each A_\nu has order type \kappa^{\cdot\beta_{\nu+1}}.

    [That the sequence \beta_\nu is continuous (at limits) ensures that the A_\nu cover \kappa^{\cdot \alpha}. That they have the claimed order type follows from the ``straightforward inductive argument'' three paragraphs above.]

    So we have written each \kappa^{\cdot\rho} as an increasing union of \sigma many intervals whose order types are ordinal powers of \kappa, and \sigma is either \kappa or \mbox{cf}(\rho). Now proceed by induction. We may assume that each ordinal below \kappa^{\cdot\rho} can be written as claimed in the paradox. In particular, each A_\nu, having order type an ordinal smaller than \kappa^{\cdot\rho}, can be written that way, say A_\nu=\bigcup_n A_{\nu,n} where \mbox{ot}(A_{\nu,n})<\kappa^{\cdot n}.

    If \sigma=\omega, this immediately gives the result for \kappa^{\cdot\rho}: Take X_0=\emptyset and X_{2^m(2n+1)}=A_{m,n}. Clearly their union is \kappa^{\cdot\rho} and they have small order type as required.

    If \sigma>\omega, take X_0=X_1=\emptyset and X_{n+2}=\bigcup_\nu A_{\nu,n}. Again, their union is \kappa^{\cdot\rho}, and \mbox{ot}(X_{n+2}) is at most the order type of concatenating \kappa many copies of \kappa^{\cdot n} [it is here that we use that A_\nu<A_\mu for \nu<\mu], so \mbox{ot}(X_{n+2})\le\kappa^{\cdot n+1}.

    7 Comments | 116c: Set theory | Tagged: | Permalink
    Posted by andrescaicedo

    116c- Lecture 6

    April 18, 2008

    We revisited the proof of the Schröder-Bernstein theorem and showed how arguments using recursion can provide explicit fixed points for the required map. Recall that if f:A\to B and g:B\to A are injective, we consider the monotone map \pi:{\mathcal P}(A)\to{\mathcal P}(A) given by \pi(X)=A\setminus g[B\setminus f[X]], since if X is a  fixed point of \pi, then A\setminus X=g[B\setminus f[X]], and we obtain a bijection h:A\to B by setting h(x)=f(x) if x\in X and h(x)=g^{-1}(x) if x\in A\setminus X.

    We also presented a combinatorial proof considering “paths” along the graphs of f and g (surely folklore, but apparently first recorded by Paul Cohen) and Cantor’s original argument (using choice).

    We then started the proof of the equivalence (in {\sf ZF}) of several versions of choice:

    1. The well-ordering principle (our official version of {\sf AC}).
    2. The existence of choice functions f:{\mathcal P}(X)\setminus\{\emptyset\}\to X for any set X.
    3. Zorn’s lemma.
    4. Trichotomy: Given any sets A and B, one of them injects into the other. (Called trichotomy as it gives that either |A|=|B|, |A|<|B| or |B|<|A|.) 
    5. k-trichotomy (for a fixed 2\le k\in\omega): Given any k sets, at least one of them injects into another.

    (The proof that (5) implies (1) will be given in Tuesday.) 

    1 Comment | 116c: Set theory | Permalink
    Posted by andrescaicedo

    116c- Homework 2

    April 16, 2008

    Homework 2.

    Due Tuesday, April 22 at 2:30 pm.

    Leave a Comment » | 116c: Set theory | Tagged: | Permalink
    Posted by andrescaicedo

    116c- Lecture 5

    April 16, 2008

    We defined addition, multiplication, and exponentiation of ordinals, and stated some basic properties of these operations. They extend into the transfinite the usual operations on natural numbers.

    I made a mistake when indicating how to define these operations “intrinsically” rather than as a consequence of the transfinite recursion theorem: In the definition of ordinal exponentiation \alpha^{\cdot\beta}, we consider the set \{f\in{}^\beta\alpha:f(\xi)=0\mbox{\ for all but finitely many }\xi<\beta\} and order it by setting f<g, for f\ne g in this set, iff f(\xi)<g(\xi) as ordinals, where \xi<\beta is the largest ordinal such that f(\xi)\ne g(\xi). In particular, there is such an ordinal \xi. In class, I mentioned that \xi was the smallest such ordinal, but this does not work. 

    Using Hartog’s function and transfinite recursion we defined the long sequence of (well-ordered) cardinals, the alephs.

    Remark. It was asked in class whether one can make sense of well-orders longer than {\sf ORD} and if one can extend to them the operations we defined.

    Of course, one can define classes that are well-orders of order type longer than {\sf ORD} (for example, one can define the lexicographic ordering on 2\times{\sf ORD}, which would correpsond to the “long ordinal” {\sf ORD}+{\sf ORD}). In {\sf ZFC} this is cumbersome (since classes are formulas) but possible. There is an extension of {\sf GB} that allows these operations to be carried out in a more natural way, Morse-Kelley set theory {\sf MK}, briefly discussed here.

    However, I do not know of any significant advantages of this approach. But a few general (and unfortunately vague) observations can be made:

  • Most likely, any way of extending well-orders beyond {\sf ORD} would also provide a way of extending V to a longer “universe of classes.” The study of these end-extensions (in the context of large cardinals, where it is easier to formalize these ideas) has resulted in an interesting research area originated by Keisler and Silver with recent results by Villaveces and others.
  • I also expect that any sytematic way of doing this would translate with minor adjustments into a treatment of indiscernibles and elementary embeddings (which could potentially turn into a motivation for the study of these important topics and would be interesting at least from a pedagogical point of view).
  • As I said, however, I do not know of any systematic attempt at doing something with these “long ordinals.” With one exception: the work of Reinhardt, with the caveat that I couldn’t make much sense of it in any productive way years ago. But this is an excuse to recommend a couple of excellent papers by Penelope Maddy, Believing the Axioms I and II, that originally appeared in The Journal of Symbolic Logic in 1988 and can be accessed through JSTOR. These papers discuss the intuitions behind the axioms of set theory and end up discussing more recent developments (like large cardinal axioms and determinacy assumptions), and I believe you will appreciate them. During her discussion of very large cardinals, Maddy mentions Reinhardt ideas, so this can also be a place to start if one is interested in the issue of “long ordinals.”    

    • 2 Comments | 116c: Set theory | Permalink
    Posted by andrescaicedo

    116c- Lecture 4

    April 11, 2008

    We showed that every well-ordered set is isomorphic to a unique ordinal. The proof uses replacement in an essential way.

    Example. (V_{\omega+\omega},\in)\models{\sf ZFC}-\mbox{\sf Replacement} and in this model there are well-ordered sets not isomorphic to any ordinal. We will return to this example in the future.

    We defined natural numbers in the context of set theory and showed that \omega, the first limit ordinal, is the set of natural numbers.

    We explained how we understand (proper) classes within {\sf ZFC}. Other formalizations of set theory allow one to handle classes as actual objects, for example Gödel-Bernays-von Neumann set theory, {\sf GB}, the system in which Gödel originally presented his proof of the consistency of the axiom of choice and the generalized continuum hypothesis. See here for a brief description of {\sf GB}. One can show that {\sf GB} is conservative over {\sf ZF}.

    Finally, we stated versions of the theorem of transfinite induction and proved a version of the theorem of transfinite recursion: Given any F:V\to V there is a unique G:{\sf ORD}\to V such that for all ordinals \alpha, G(\alpha)=F(G\upharpoonright\alpha).

    This result is very useful. It allows us, for example, to define operations on the ordinals by recursion. The easiest example is perhaps the definition of addition of ordinals: Let \beta+1=S(\beta) be the successor of \beta.

    • \alpha+0=\alpha.
    • \alpha+(\beta+1)=(\alpha+\beta)+1.
    • \alpha+\lambda=\sup\{\alpha+\beta:\beta<\lambda\} for \lambda limit.

    To see that there is a unique function satisfying these conditions, one can show that this is a particular case of the theorem. For this, define F_\alpha:V\to V as follows: F_\alpha(x)=0 unless x is a sequence. If \mbox{dom}(x)=0, let F_\alpha(x)=\alpha. If \mbox{dom}(x)=\beta+1 for some \beta, let F_\alpha(x)=S(x(\beta)). If \mbox{dom}(x)=\lambda is a limit ordinal, let F_\alpha(x)=\bigcup x. The function G_\alpha whose existence is granted by the theorem is precisely G_\alpha(\beta)=\alpha+\beta.

    We also stated (without proof) Hartog’s theorem. The following definition will be useful.

    Definition. A set X is finite iff there is a natural number n such that |X|=|n|. Otherwise, it is infinite.

    (This is our official defintion. There are several possible ways of defining infinite sets, and they are not necessarily equivalent without choice. One such alternative, Dedekind infinite, is presented in Exercise 2 of the Homework.)

    For completeness, I include a proof of Hartog’s theorem. Recall:

    Theorem (Hartog). ({\sf ZF}) For any set X, let \aleph(X)=\{\alpha: there is an injection of \alpha into X\}. Then \aleph(X) is an ordinal.

    Proof. Clearly the class \aleph(X)\subset{\sf ORD} is transitive (which for ordinals simply means, closed under initial segments). So it suffices to see that it is a set. This uses replacement.

    Notice that if f:\alpha\to Y is a bijection, then there is a well-ordering of Y in order type \alpha: Simply set a<b in Y iff there are \beta<\gamma in \alpha such that f(\beta)=a and f(\gamma)=b.

    By von Neumann’s theorem, conversely, if Y\subset X and (Y,<) is well-ordered, then there is an ordinal \alpha such that \alpha\in\aleph(X) as witnessed by the unique order isomorphism f:Y\to\alpha. Hence, \aleph(X) coincides with the class of ordinals \alpha such that there is a subset Y of X and a well-ordering of Y isomorphic to \alpha. 

    Since a well-ordering of Y is just a subset of Y\times Y, it follows that \aleph(X) is a set, by replacement. {\sf QED}

    The following (important) observation is needed in the homework, I will return to it in Tuesday’s lecture: Suppose now that X itself is well-orderable. Then |X|<|\aleph(X)|. Because since X is well-orderable, there is an ordinal \alpha\in\aleph(X) (thus, \alpha\subseteq\aleph(X)) and a bijection f:X\to\alpha. Hence, |X|\le|\aleph(X)|. However, if g:X\to\aleph(X) is a bijection, we can well-order X isomorphically to \aleph(X) by setting a<b in X iff g(a)<g(b) as ordinals. But this would imply that \aleph(X)\in\aleph(X), a contradiction.

    Remark. In the statement of Exercise 1 in the Homework, \aleph(X) is defined as the union of the set we are calling \aleph(X) here. This makes no difference whenever X is infinite (as one can easily check), so feel free to use either version, we will discuss this issue in lecture.

    1 Comment | 116c: Set theory | Permalink
    Posted by andrescaicedo

    116c- Homework 1

    April 9, 2008

    Homework 1.

    Due Tuesday,  April 15 at 2:30 pm.

    Leave a Comment » | 116c: Set theory | Tagged: | Permalink
    Posted by andrescaicedo

    « Previous Entries
    Follow

    Get every new post delivered to your Inbox.