# Blog de Frédéric

## Tag - set theory

Saturday, April 11 2015

## Exercises in Set Theory

As mentioned in a previous blog post, I've been working on the exercises of chapter 1 of Kunen's Set Theory book. I finally uploaded my solutions this morning.

Saturday, January 31 2015

## The canonical well-ordering of α×α (part 2)

In a my previous blog post, I discussed the canonical well-ordering on $\alpha\times\alpha$ and stated theorem 0.5 below to calculate its order-type $\gamma(\alpha)$. Subsequent corollaries provided a bound for $\gamma(\alpha)$, its fixed points and a proof that infinite cardinals were among these fixed points (and so that cardinal addition and multiplication is trivial). In this second part, I’m going to provide the proof of this theorem.

First, we note that for all $n<\omega$, there is only one order-type for $n\times n$, since the notion of cardinal and ordinal is the same for finite sets. So indeed

 $\forall n<\omega,\gamma(n)={|n\times n|}=n^{2}$

and taking the limit, we get our first infinite fixed point:

 $\gamma(\omega)=\sup_{n<\omega}{\gamma(n)}=\omega$

For all $\alpha$ the ordering on ${(\alpha+1)}\times{(\alpha+1)}$ is as follows: first the elements of $\alpha\times\alpha$ ordered as $\gamma(\alpha)$, followed by the elements $(\xi,\alpha)$ for $0\leq\xi<\alpha$, followed by the elements $(\alpha,\xi)$ for $0\leq\xi\leq\alpha$. Hence

 $\forall\alpha,{\gamma(\alpha+1)}={\gamma(\alpha)}+\alpha\cdot 2+1$

From this, we can try to calculate the next values of $\gamma$ after $\omega$:

 ${\gamma(\omega+1)}=\omega+{\omega\cdot 2}+1={\omega\cdot 3}+1$
 ${\gamma(\omega+2)}={\omega\cdot 3+1}+\omega+1+\omega+1+1={\omega\cdot 5}+2$

The important point is $1+\omega=\omega$ ; in general we will use several times the property $\alpha+\omega^{\beta}=\omega^{\beta}$ if $\alpha<\omega^{\beta}$. By a simple recurrence (see proposition 0.1), we can generalize the expression to arbitrary $n$:

 ${\gamma(\omega+n)}=\omega\left(2n+1\right)+n$

and so taking the limit

 ${\gamma(\omega\cdot 2)}=\omega^{2}$

which is a limit ordinal not fixed by $\gamma$. We note another point that will be used later: taking the limit “eliminates” the smallest terms. More generally, we can perform the same calculation, starting from any arbitrary $\alpha\geq\omega$:

###### Proposition 0.1.

For any limit ordinal $\alpha$ and $1\leq n<\omega$ we have

 $\gamma(\alpha+n)=\gamma(\alpha)+{\alpha\cdot{2n}}+n$
###### Proof.

For $n=1$ this is the relation for $\gamma(\alpha+1)$ explained above. If the relation is true for $n$ then

 $\gamma(\alpha+n+1)=\gamma(\alpha+n)+{\left(\alpha+n\right)\cdot 2}+1$
 $\gamma(\alpha+n+1)=\gamma(\alpha)+{\alpha\cdot{2n}}+n+\alpha+n+\alpha+n+1$

and since $\alpha\geq\omega$ we have $n+\alpha=\alpha$ and so

 $\gamma(\alpha+n+1)=\gamma(\alpha)+{\alpha\cdot{(2n+1)}}+n+1$

Which shows the result at step $n+1$. ∎

As above, we can take the limit and say ${\gamma(\alpha+\omega)}=\sup_{n<\omega}{\gamma(\alpha+n)}=\gamma(\alpha)+% \alpha\cdot\omega$ which is consistent with ${\gamma(\omega\cdot 2)}=\omega+\omega^{2}=\omega^{2}$. However, if we consider the Cantor Normal Form $\alpha=\omega^{\beta_{1}}n_{1}+...+\omega^{\beta_{k}}n_{k}$, then for all $n<\omega$ we have can use the fact that “$\omega^{\beta_{1}}$ will eliminate smaller terms on its left” that is $\alpha\cdot n=\omega^{\beta_{1}}{(n_{1}n)}+\omega^{\beta_{2}}n_{2}+...+\omega^% {\beta_{k}}n_{k}$. Then using the fact that “taking the limit eliminates the smallest terms” we get $\alpha\cdot\omega=\sup_{n<\omega}\alpha\cdot n=\omega^{\beta_{1}+1}$. So actually, we have a nicer formula where $\alpha\cdot\omega$ is put in Cantor Normal Form:

 $\forall\alpha\geq\omega,{\gamma(\alpha+\omega)}=\gamma(\alpha)+\omega^{\log_{% \omega}(\alpha)+1}$

This can be generalized by the following proposition:

###### Proposition 0.2.

For any $\alpha\geq\omega$ and $\beta\geq 1$ such that $\log_{\omega}(\alpha)+1\geq\beta$ we have

 ${\gamma(\alpha+\omega^{\beta})}=\gamma(\alpha)+\omega^{\log_{\omega}(\alpha)+\beta}$
###### Proof.

We prove by induction on $\beta$ that for all such $\alpha$ the expression is true. We just verified $\beta=1$ and the limit case is obvious by continuity of $\gamma$ and of the sum/exponentiation in the second variable. For the successor step, if $\log_{\omega}(\alpha)+1\geq\beta+1$ then a fortiori $\forall 1\leq n<\omega,\log_{\omega}(\alpha+\omega^{\beta}\cdot n)+1\geq\beta+% 1\geq\beta$. We can then use the induction hypothesis to prove by induction on $1\leq n<\omega$ that ${\gamma(\alpha+{\omega^{\beta}\cdot n})}=\gamma(\alpha)+\omega^{\log_{\omega}(% \alpha)+\beta}\cdot n$. For $n=1$, this is just the induction hypothesis of $\beta$ (for the same $\alpha$!). For the successor step, we need to use the induction hypothesis of $\beta$ (for $\alpha+\omega^{\beta}\cdot n$) which is ${\gamma(\alpha+{\omega^{\beta}\cdot{(n+1)}})}={\gamma(\alpha+{\omega^{\beta}% \cdot n})}+\omega^{\log_{\omega}(\alpha)+\beta}$. Finally, ${\gamma(\alpha+{\omega^{\beta+1}})}={\sup_{1\leq n<\omega}{\gamma(\alpha+{% \omega^{\beta}\cdot n})}}=\gamma(\alpha)+\omega^{\log_{\omega}(\alpha)+\beta+1}$, as wanted. ∎

For all $\alpha\geq 1$, $\log_{\omega}(\omega^{\alpha})+1=\alpha+1$ so the previous paragraph also gives ${\gamma(\omega^{\alpha+1})}=\gamma\left(\omega^{\alpha}+\omega^{\alpha+1}% \right)={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2+1}$. Then, we find

 $\gamma(\omega^{2})=\omega+\omega^{3}=\omega^{3}$
 $\gamma(\omega^{3})=\omega^{3}+\omega^{5}=\omega^{5}$

And more generally by induction on $n<\omega$, we can show that

 $\gamma(\omega^{n+1})=\omega^{2n+1}$

Then we deduce another fixed point

 $\gamma(\omega^{\omega})={\sup_{1\leq n<\omega}\gamma\left({\omega^{n}}\right)}% =\omega^{\omega}$

The following proposition tries to generalize the expression of ${\gamma(\omega^{\alpha+1})}$.

###### Proposition 0.3.

For any $\alpha,\beta\geq 1$ such that $\log_{\omega}(\alpha)>\log_{\omega}(\beta)$ we have

 ${\gamma(\omega^{\alpha+\beta})}={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2% +\beta}$
###### Proof.

This is done by induction on $\beta<\alpha$ for a fixed $\alpha$. We already verified the case $\beta=1$ in the previous paragraph and the limit case is obvious by continuity of $\gamma$ and of the sum/exponentiation in the second variable. For the successor step, we have ${\gamma(\omega^{\alpha+\beta+1})}={\gamma(\omega^{\alpha+\beta})}+\omega^{{(% \alpha+\beta)}\cdot 2+1}$ and by induction hypothesis, ${\gamma(\omega^{\alpha+\beta})}={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2% +\beta}$. Since $\log_{\omega}(\alpha)>\log_{\omega}(\beta+1)=\log_{\omega}(\beta)$ we have ${(\alpha+\beta)}\cdot 2+1=\alpha+\beta+\alpha+\beta+1=\alpha\cdot 2+\beta+1>% \alpha\cdot 2+\beta$ and so $\omega^{\alpha\cdot 2+\beta}+\omega^{\alpha\cdot 2+\beta+1}=\omega^{\alpha% \cdot 2+\beta+1}$. Finally, ${\gamma(\omega^{\alpha+\beta+1})}={\gamma(\omega^{\alpha+\beta})}+\omega^{% \alpha\cdot 2+\beta+1}$ as wanted. ∎

For any $1\leq n<\omega$ and $\alpha\geq 1$, if $1\leq\beta<\omega^{\alpha}$ then $\log_{\omega}(\beta)<\alpha=\log_{\omega}(\omega^{\alpha}\cdot n)$. Hence proposition 0.3 gives ${\gamma(\omega^{{\omega^{\alpha}\cdot n}+\beta})}={\gamma(\omega^{{\omega^{% \alpha}\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{2n}}+\beta}$ Then by continuity of $\gamma$ and of the sum/exponentiation in the second variable, we can consider the limit $\beta\rightarrow\omega^{\alpha}$ to get ${\gamma(\omega^{{\omega^{\alpha}\cdot(n+1)}})}={\gamma(\omega^{{\omega^{\alpha% }\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{(2n+1)}}}$. So continuing our calculation we have

 ${\gamma(\omega^{\omega\cdot 2})}=\omega^{\omega}+\omega^{\omega\cdot 3}=\omega% ^{\omega\cdot 3}$
 ${\gamma(\omega^{\omega\cdot 3})}=\omega^{\omega\cdot 3}+\omega^{\omega\cdot 5}% =\omega^{\omega\cdot 5}$

and taking the limit we find another fixed point

 ${\gamma(\omega^{\omega^{2}})}=\omega^{\omega^{2}}$

then again

 ${\gamma(\omega^{\omega^{2}\cdot 2})}=\omega^{\omega^{2}}+\omega^{\omega^{2}% \cdot 3}=\omega^{\omega^{2}\cdot 3}$
 ${\gamma(\omega^{\omega^{2}\cdot 3})}=\omega^{\omega^{2}\cdot 3}+\omega^{\omega% ^{2}\cdot 5}=\omega^{\omega^{2}\cdot 5}$

and taking the limit we find another fixed point

 ${\gamma(\omega^{\omega^{3}})}=\omega^{\omega^{3}}$

More generally, we have the following proposition:

###### Proposition 0.4.

For any ordinal $\alpha$ and $1\leq n<\omega$ we have

 ${\gamma(\omega^{{\omega^{\alpha}\cdot n}})}=\omega^{{\omega^{\alpha}\cdot{(2n-% 1)}}}$
###### Proof.

From the relation ${\gamma(\omega^{{\omega^{\alpha}\cdot(n+1)}})}={\gamma(\omega^{{\omega^{\alpha% }\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{(2n+1)}}}$, we deduce by induction on $n$ that

 $\forall n\geq 2,{\gamma(\omega^{{\omega^{\alpha}\cdot n}})}={\gamma(\omega^{{% \omega^{\alpha}}})}+\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}$

Taking the limit $n\rightarrow\omega$,we obtain

 ${\gamma(\omega^{{\omega^{\alpha+1}}})}={\gamma(\omega^{{\omega^{\alpha}}})}+% \omega^{{\omega^{\alpha+1}}}$

We can then show by induction that all the $\omega^{\omega^{\alpha}}$ are actually fixed points, using the previous relation at successor step, the continuity of $\gamma$ at limit step and the fact that $\gamma(\omega)=\omega$. This means

 ${\gamma(\omega^{{\omega^{\alpha}}})}=\omega^{{\omega^{\alpha}}}=\omega^{{% \omega^{\alpha}\cdot{(2\times 1-1)}}}$

Then for $n\geq 2$, we get

 ${\gamma(\omega^{{\omega^{\alpha}\cdot n}})}={\gamma(\omega^{{\omega^{\alpha}}}% )}+\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}={\omega^{{\omega^{\alpha}}}}+\omega% ^{{\omega^{\alpha}\cdot{(2n-1)}}}=\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}$

Equipped with these four propositions, we have a way to recursively calculate $\gamma$. We are ready to prove the main theorem:

###### Theorem 0.5.

For all ordinal $\alpha$, we denote $\gamma(\alpha)$ the order-type of the canonical ordering of $\alpha\times\alpha$. Then $\gamma$ can be calculated as follows:

1. (1)

Finite Ordinals: For any $n<\omega$ we have

 $\gamma(n)=n^{2}$
2. (2)

Limit Ordinals: For any limit ordinal $\alpha$,

1. (a)

If $\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}$ does not divide $\log_{\omega}(\alpha)$ then

 $\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\alpha$
2. (b)

Otherwise, we write $\alpha={\omega^{\log_{\omega}(\alpha)}n}+\rho$ for some $n\geq 1$. If $n\geq 2$ then

 $\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\left({\omega^{\log_{\omega}% (\alpha)}\cdot{(n-1)}}+\rho\right)$

(like the first case but we “decrement $n$ in the second factor”)

3. (c)

Otherwise, $\alpha={\omega^{\log_{\omega}(\alpha)}}+\rho$ and we write $\log_{\omega}(\alpha)=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha% \right)\right)}m$ for some $m\geq 1$. We have

 $\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\left(\omega^{\omega^{\log_{% \omega}\left(\log_{\omega}\left(\alpha\right)\right)}\cdot\left(m-1\right)}+% \rho\right)$

(like the first case but we “decrement $m$ in the second factor”)

3. (3)

Infinite Successor Ordinals: For any limit ordinal $\alpha$ and $1\leq n<\omega$ we have

 $\gamma(\alpha+n)=\gamma(\alpha)+{\alpha\cdot{2n}}+n$

where $\gamma(\alpha)$ is determined as in the previous point.

###### Proof.

The “Finite Ordinals” has been discussed at the beginning and the “Infinite Successor Ordinals” is proposition 0.1. Now let’s consider the Cantor Normal Form $\omega^{\beta_{1}}n+...+\omega^{\beta_{k}}n_{k}$ of a limit ordinal $\alpha\geq\omega$ (so $\beta_{k}\geq 1$ and $\beta_{1}=\log_{\omega}(\alpha)$). First, from proposition 0.2 we can make successively extract the $n_{k}$ terms $\omega^{\beta_{k}}$ (by left-multiplying them by $\omega^{\beta_{1}}$), then the $n_{k-1}$ terms $\omega^{\beta_{k-1}}$, … then the $n_{2}$ terms $\omega^{\beta_{2}}$ and finally $n-1$ terms $\omega^{\beta_{1}}$. We obtain:

 ${\gamma(\alpha)}={\gamma(\omega^{\beta_{1}})}+{\omega^{\beta_{1}}\left(\omega^% {\beta_{1}}{(n-1)}+\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}\right)}$

We now write $\beta_{1}=\omega^{\delta}m+\sigma$ where $\delta=\log_{\omega}{\beta_{1}}$ and $m,\sigma$ are the quotient and remainder of the Euclidean division of $\beta_{1}$ by $\omega^{\delta}$. We can then use proposition 0.3 to extract $\sigma$:

 $\sigma=0\implies{\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{\delta}m})}$
 $\sigma\neq 0\implies{\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{% \delta}m})}+\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}$

Finally, using proposition 0.4 we obtain

 ${\gamma(\omega^{\omega^{\delta}m})}=\omega^{{\omega^{\delta}\cdot{(2m-1)}}}$

$\sigma\neq 0$ means that $\omega^{\delta}=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)% \right)}$ does not divide $\beta_{1}={\log_{\omega}(\alpha)}$. In that case, $\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}>\omega^{{\omega^{\delta}\cdot{(2m-1% )}}}$ and so ${\gamma(\omega^{\beta_{1}})}=\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}$. We note that $\beta_{1}\cdot 2=\omega^{\delta}m+\sigma+\omega^{\delta}m+\sigma=\omega^{% \delta}{(2m)}+\sigma$ since the remainder $\sigma$ is less than $\omega^{\delta}$. So actually ${\gamma(\omega^{\beta_{1}})}=\omega^{\beta_{1}}\omega^{\beta_{1}}$. Coming back to the expression of $\gamma(\alpha)$, this term can be grouped with $\omega^{\beta_{1}}{(n-1)}$ to recover the Cantor Normal Form of $\alpha$ and we finally get $\gamma(\alpha)=\omega^{\beta_{1}}\alpha$.

Otherwise, $\sigma=0$, $\beta_{1}=\omega^{\delta}m$ and

 ${\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{\delta}m})}=\omega^{{% \omega^{\delta}\cdot{(2m-1)}}}={\omega^{\beta_{1}}{\omega^{\omega^{\delta}% \cdot{(m-1)}}}}$

But then $\beta_{1}=\omega^{\delta}m>{\omega^{\delta}{(m-1)}}$ and so $\omega^{\beta_{1}}\omega^{\beta_{1}}>\omega^{\beta_{1}}\omega^{{\omega^{\delta% }\cdot{(m-1)}}}$. Hence if $n\geq 2$, the term ${\gamma(\omega^{\beta_{1}})}$ is eliminated in the expression of $\gamma(\alpha)$ and it remains

 ${\gamma(\alpha)}={\omega^{\beta_{1}}\left(\omega^{\beta_{1}}{(n-1)}+\rho\right)}$

where $\rho=\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}$. If instead $n=1$, then the term $\omega^{\beta_{1}}{(n-1)}$ is zero and it remains

 ${\gamma(\alpha)}={\omega^{\beta_{1}}\left(\omega^{{\omega^{\delta}\cdot{(m-1)}% }}+\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}\right)}$

Friday, January 30 2015

## The canonical well-ordering of α×α

It is well-known that the cartesian product of two infinite sets of cardinality $\aleph_{\alpha}$ is also of cardinality $\aleph_{\alpha}$. Equivalently, the set $\omega_{\alpha}\times\omega_{\alpha}$ can be well-ordered in order-type $\omega_{\alpha}$. However, the standard ordering on $\omega_{\alpha}\times\omega_{\alpha}$ does not work, since it is always of order type $\omega_{\alpha}^{2}$. Instead, we introduce for each ordinal $\alpha$ the canonical well-ordering of $\alpha\times\alpha$ as follows: ${(\xi_{1},\xi_{2})}\lhd{(\eta_{1},\eta_{2})}$ if either ${\max{(\xi_{1},\xi_{2})}}<{\max{(\eta_{1},\eta_{2})}}$ or ${\max{(\xi_{1},\xi_{2})}}={\max{(\eta_{1},\eta_{2})}}$ but $(\xi_{1},\xi_{2})$ precedes $(\eta_{1},\eta_{2})$ lexicographically. If we note $\gamma(\alpha)$ the ordinal isomorphic to that well-ordering ordering, then we can prove that $\gamma(\omega_{\alpha})=\omega_{\alpha}$ as wanted (see Corollary 0.4).

Jech’s Set Theory book contains several properties of $\gamma$. For example, $\gamma$ is increasing : for any ordinal $\alpha$, $\alpha\times\alpha$ is a (proper) initial segment of ${(\alpha+1)}\times{(\alpha+1)}$ and of $\lambda\times\lambda$ for any limit ordinal $\lambda>\alpha$. As a consequence, $\forall\alpha,\alpha\leq\gamma(\alpha)$ which can also trivially be seen by the increasing function $\xi\mapsto(\xi,0)$ from $\alpha$ to $\alpha\times\alpha$. Also, $\forall\alpha,\gamma(\alpha)<\gamma(\lambda)$ implies $\sup_{\alpha<\lambda}{\gamma(\alpha)}\leq\gamma(\lambda)$. This can not be a strict equality, or otherwise the element ${(\xi,\eta)}\in\lambda\times\lambda$ corresponding to $\sup_{\alpha<\lambda}{\gamma(\alpha)}$ via the isomorphism between $\lambda\times\lambda$ and $\gamma(\lambda)$ would be an element larger than all $(\alpha,\alpha)$ for $\alpha<\lambda$. Hence $\gamma$ is continuous and by exercise 2.7 of the same book, $\gamma$ has arbitrary large fixed points. Exercise 3.5 shows that $\gamma(\alpha)\leq\omega^{\alpha}$ and so $\gamma$ does not increase cardinality (see Corollary 0.2 for a much better upper bound). Hence starting at any infinite cardinal $\kappa$ the construction of exercise 2.7 provides infinitely many fixed points of $\gamma$ having cardinality $\kappa$. Hence the infinite fixed points of $\gamma$ are not just cardinals and we can wonder what they are exactly…

I recently tried to solve Exercise I.11.7 of Kunen’s Set Theory book which suggests a nice characterization of infinite fixed points of $\gamma$: they are the ordinals of the form $\omega^{\omega^{\alpha}}$. However, I could not find a simple proof of this statement so instead I tried to determine the explicit expression of $\gamma(\alpha)$, from which the result becomes obvious (see Corollary 0.3). My final calculation is summarized in Theorem 0.1, which provides a relatively nice expression of $\gamma(\alpha)$. Recall that any $\alpha\geq 1$ can be written uniquely as $\alpha=\omega^{\beta}q+\rho$ where $\beta$ is (following Kunen’s terminology) the “logarithm in base $\omega$ of $\alpha$” (that we will denote $\log_{\omega}{\alpha}$ for $\alpha\geq\omega$) and $q,\rho$ are the quotient and remainder of the Euclidean division of $\alpha$ by $\omega^{\beta}$. Alternatively, this can be seen from Cantor’s Normal Form: $\beta$ and $q$ are the exponent and coefficient of the largest term while $\rho$ is the sum of terms of smaller exponents.

###### Theorem 0.1.

For all ordinal $\alpha$, we denote $\gamma(\alpha)$ the order-type of the canonical ordering of $\alpha\times\alpha$. Then $\gamma$ can be calculated as follows:

1. (1)

Finite Ordinals: For any $n<\omega$ we have

 $\gamma(n)=n^{2}$
2. (2)

Limit Ordinals: For any limit ordinal $\alpha$,

1. (a)

If $\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}$ does not divide $\log_{\omega}(\alpha)$ then

 $\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\alpha$
2. (b)

Otherwise, we write $\alpha={\omega^{\log_{\omega}(\alpha)}n}+\rho$ for some $n\geq 1$. If $n\geq 2$ then

 $\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\left({\omega^{\log_{\omega}% (\alpha)}\cdot{(n-1)}}+\rho\right)$

(like the first case but we “decrement $n$ in the second factor”)

3. (c)

Otherwise, $\alpha={\omega^{\log_{\omega}(\alpha)}}+\rho$ and we write $\log_{\omega}(\alpha)=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha% \right)\right)}m$ for some $m\geq 1$. We have

 $\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\left(\omega^{\omega^{\log_{% \omega}\left(\log_{\omega}\left(\alpha\right)\right)}\cdot\left(m-1\right)}+% \rho\right)$

(like the first case but we “decrement $m$ in the second factor”)

3. (3)

Infinite Successor Ordinals: For any limit ordinal $\alpha$ and $1\leq n<\omega$ we have

 $\gamma(\alpha+n)=\gamma(\alpha)+{\alpha\cdot{2n}}+n$

where $\gamma(\alpha)$ is determined as in the previous point.

###### Proof.

In a future blog post ;-) ∎

From this theorem, we deduce several corollaries:

###### Corollary 0.2.

For any ordinal $\alpha$, we have

 $\alpha\leq{\gamma(\alpha)}\leq{{\omega^{\log_{\omega}(\alpha)}\cdot\left({% \alpha-r}\right)}+{\alpha\cdot{2r}}}\leq\alpha\left(\alpha+r\right)$

where $r=\alpha\mod\omega$ is the remainder in the Euclidean division of $\alpha$ by $\omega$ (i.e. the constant term in the Cantor Normal Form).

###### Proof.

The “Limit Ordinals” case is $r=0$ i.e. $\alpha\leq{\gamma(\alpha)}\leq{{\omega^{\log_{\omega}(\alpha)}\cdot\alpha}}$, which is readily seen by the previous theorem. Then we deduce for the “Infinite Successor Ordinals” case: ${\gamma(\alpha+n)}=\gamma(\alpha)+{\alpha\cdot{2n}}+n\leq{{\omega^{\log_{% \omega}(\alpha)}\cdot\alpha}}+{\left(\alpha+n\right)\cdot{2n}}$ where ${\log_{\omega}(\alpha+n)}={\log_{\omega}(\alpha)}$ and $n=\left(\alpha+n\mod\omega\right)$. Since $\omega^{\log_{\omega}(\alpha)}\leq\alpha$ we can write ${{\omega^{\log_{\omega}(\alpha)}\cdot\left({\alpha-r}\right)}+{\alpha\cdot{2r}% }}\leq{\alpha\cdot\left(\alpha-r+2r\right)}={\alpha\cdot{(\alpha+r)}}$. ∎

Hence the order type of the canonical ordering $\lhd$ of $\alpha\times\alpha$ (i.e. $\gamma(\alpha)\leq\alpha{(\alpha+\omega)}$) is never significantly bigger than the one of the standard lexical ordering (i.e. $\alpha^{2}$), and even never larger for limit ordinals. Moreover, for many ordinals $\alpha$ the canonical ordering is of order type $\alpha$:

###### Corollary 0.3.

The fixed points of $\gamma$ are $0,1$ and $\omega^{\omega^{\alpha}}$ for all ordinals $\alpha$.

###### Proof.

For the “Finite Ordinals” case, we have $\gamma(n)=n^{2}=n$ iff $n=0$ or $n=1$. For the “Infinite Successor Ordinals” case, we have $\alpha\cdot{2n}>\alpha$ if $n\geq 1$ so $\gamma(\alpha+n)>\alpha+n$. Now we look at the three subcases of the “Limit Ordinals” case. For the first one, we have $\log_{\omega}(\alpha)\geq 1$ and so $\omega^{\log_{\omega}(\alpha)}\alpha\geq\omega\alpha>\alpha$. For the second one, we note that ${\log_{\omega}(\alpha)}2>\log_{\omega}(\alpha)$ and so $\omega^{{\log_{\omega}(\alpha)}2}>\alpha$ (compare the Cantor Normal Form). Since $n-1\geq 1$ by assumption, we have $\gamma(\alpha)>\alpha$. Similarly in the third case, if we expand the parenthesis the first term is $\omega$ raised to the power ${\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}\cdot\left% (2m-1\right)}$ which is stricly greater than $\log_{\omega}(\alpha)=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha% \right)\right)}m$ if $m\geq 2$. Now if $m=1$, we obtain $\gamma(\alpha)={\omega^{\log_{\omega}(\alpha)}+{\omega^{\log_{\omega}(\alpha)}% \rho}}$ and $\alpha={\omega^{\log_{\omega}(\alpha)}}+\rho$. Hence $\gamma(\alpha)>\alpha$ if $\rho>0$ and $\gamma(\alpha)=\alpha$ if $\rho=0$. Finally for $\alpha\geq\omega$, $\gamma(\alpha)=\alpha$ iff $\alpha=\omega^{\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)% \right)}}$ iff $\alpha=\omega^{\omega^{\beta}}$ for some ordinal $\beta$. ∎

Finally, now that we know that infinite fixed points of $\gamma$ are of the form $\alpha=\omega^{\omega^{\beta}}$ we only need to verify that infinite cardinals $\kappa$ are of this form to prove that ${|\kappa\times\kappa|}=\kappa$. This provides an alternative (less straightforward) proof of Theorem 3.5 from Jech’s Set Theory book.

###### Corollary 0.4.

Any infinite cardinal $\kappa$ is a fixed point of $\gamma$. Hence for any infinite cardinal $\kappa_{1},\kappa_{2}$ we have

 $\kappa_{1}+\kappa_{2}=\kappa_{1}\kappa_{2}={\max(\kappa_{1},\kappa_{2})}$
###### Proof.

For any cardinal infinite cardinal $\mu$ that is a fixed point of $\gamma$, the canonical well-ordering provides a bijection between $\mu$ and $\mu\times\mu$ i.e. $\mu^{2}=\mu$. Hence if $\mu_{1}\leq\mu_{2}$ are two fixed points, we have

 $\mu_{2}\leq{\mu_{1}+\mu_{2}}\leq{\mu_{1}\mu_{2}}\leq\mu_{2}^{2}=\mu_{2}$

Suppose that there is a cardinal $\kappa$ which is not a fixed point of $\gamma$ and consider the smallest one. Then any infinite cardinal below $\kappa$ is a fixed point of $\gamma$ and the previous equality is still true below $\kappa$.

Suppose $\kappa>\omega^{\log_{\omega}{\kappa}}$ and write $\kappa=\omega^{\log_{\omega}{\kappa}}+\rho$ where $\rho<\kappa$ corresponds to the remaining terms in Cantor Normal Form. Then $\aleph_{0}\leq\mu_{1}=\left|\omega^{\log_{\omega}{\kappa}}\right|<\kappa$, $\mu_{2}={|\rho|}<\kappa$ and $\mu_{1}+\mu_{2}=\kappa$. But the two first relations imply $\mu_{1}+\mu_{2}=\max(\mu_{1},\mu_{2})<\kappa$ which contradicts the third one. Hence $\kappa=\omega^{\log_{\omega}{\kappa}}$.

Now suppose $\log_{\omega}{\kappa}>\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}$ and write $\log_{\omega}{\kappa}=\omega^{\log_{\omega}{\kappa}}+\rho$ where $\rho<\log_{\omega}{\kappa}$ corresponds to the remaining terms in Cantor Normal Form. Then we have

 $\kappa=\omega^{\log_{\omega}{\kappa}}=\omega^{\omega^{\log_{\omega}{\log_{% \omega}{\kappa}}}}\omega^{\rho}$

where $\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}}<\omega^{\log_{\omega}{% \kappa}}=\kappa$ and $\omega^{\rho}<\omega^{\log_{\omega}{\kappa}}=\kappa$ since $\alpha\mapsto\omega^{\alpha}$ is strictly increasing. Then $\aleph_{0}\leq\mu_{1}=\left|\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa% }}}}\right|<\kappa$, $\mu_{2}={|\omega^{\rho}|}<\kappa$ and $\mu_{1}\mu_{2}=\kappa$. But again, the two first relations imply $\mu_{1}\mu_{2}=\max(\mu_{1},\mu_{2})<\kappa$ which contradicts the third one.

Finally, $\kappa=\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}}$ and so is a fixed point of $\gamma$, a contradiction. Hence all the infinite cardinals are fixed point of $\gamma$ and so the property stated at the beginning is true for arbitrary infinite cardinals $\mu_{1},\mu_{2}$. ∎

Wednesday, July 24 2013

## Exercises in Set Theory: Large Cardinals

New solutions to exercises from Thomas Jech’s book “Set Theory”:

Saturday, June 1 2013

## Exercises in Set Theory: Iterated Forcing and Martin’s Axiom

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 ${(X_{\alpha})}_{{\alpha<2^{{\aleph_{0}}}}}$ of infinite subsets of $\omega$. The induction hypothesis is that at step $\alpha<2^{{\aleph_{0}}}$, for all $\beta_{1},\beta_{2}<\alpha$ we have $\beta_{1}<\beta_{2}\implies X_{{\beta_{2}}}\setminus X_{{\beta_{1}}}$ is finite. It is then easy to show the result for the successor step, since the construction satisfies $X_{{\alpha+1}}\subseteq X_{\alpha}$. However at limit step, to ensure that $X_{\alpha}\setminus X_{\beta}$ is finite for all $\beta<\alpha$, 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 $\alpha<2^{{\aleph_{0}}}$. Define the forcing notion $P_{\alpha}=\{(s,F):s\in{[\omega]}^{{<\omega}},F\in{[\alpha]}^{{<\omega}}\}$ and $(s^{{\prime}},F^{{\prime}})\leq(s,F)$ iff $s\subseteq s^{{\prime}}$, $F\subseteq F^{{\prime}}$ and $s^{{\prime}}\setminus s\subseteq X_{\beta}$ for all $\beta\in F$. It is clear that the relation is reflexive and antisymmetric. The transitivity is almost obvious, just note that if $(s_{3},F_{3})\leq(s_{2},F_{2})$ and $(s_{2},F_{2})\leq(s_{1},F_{1})$ then for all $\beta\in F_{1}\subseteq F_{2}$ we have $s_{3}\setminus s_{1}\subseteq s_{3}\setminus s_{2}\cup s_{2}\setminus s_{1}% \subseteq X_{\beta}$.

The forcing notion satisfies ccc or even property (K): since ${[\omega]}^{{<\omega}}$ is countable, for any uncountable subset $W$ there is $t\in{[\omega]}^{{<\omega}}$ such that $Z=\{(s,F)\in W:s=t\}$ is uncountable. Then any $(t,F_{1}),(t,F_{2})\in Z$ have a common refinement $(t,F_{1}\cup F_{2})$.

For all $n<\omega$, define $D_{n}=\{(s,F):|s|\geq n\}$. Let $\beta_{1}>\beta_{2}>...>\beta_{k}$ the elements of $F$. We show by induction on $1\leq m\leq k$ that $\bigcap_{{i=1}}^{m}X_{{\beta_{i}}}$ is infinite. This is true for $m=1$ by assumption. If it is true for $m-1$ then

 $\bigcap_{{i=1}}^{{m-1}}X_{{\beta_{i}}}=\bigcap_{{i=1}}^{m}X_{{\beta_{i}}}\cup% \bigcap_{{i=1}}^{m}X_{{\beta_{i}}}\setminus X_{{\beta_{m}}}$

The left hand side is infinite by induction hypothesis. The second term of the right hand side is included in $X_{{\beta_{1}}}\setminus X_{{\beta_{m}}}$ and thus is finite. Hence the first term is infinite and the result is true for $m$. Finally, for $m=k$, we get that $\bigcap_{{\beta\in F}}X_{\beta}$ is infinite. Pick $x_{1},x_{2},...,x_{n}$ distinct elements from that set and define $(s^{{\prime}},F^{{\prime}})=(s\cup\{x_{1},...x_{n}\},F)$. We have $(s^{{\prime}},F^{{\prime}})\in D_{n}$, $s\subseteq s^{{\prime}}$, $F\subseteq F^{{\prime}}$ and for all $\beta\in F$, $s^{{\prime}}\setminus s=\{x_{1},...x_{n}\}\subseteq X_{\beta}$. This shows that $D_{n}$ is dense. For each $\beta<\alpha$, the set $E_{\beta}=\{(s,F):\beta\in F\}$ is also dense: for any $(s,F)$ consider $(s^{{\prime}},F^{{\prime}})=(s,F\cup\{\beta\})$.

By Martin’s Axiom there is a generic filter $G$ for the family $\{D_{n}:n<\omega\}\cup\{E_{\beta}:\beta<\alpha\}$ of size $|\alpha|<2^{{\aleph_{0}}}$. Let $X_{\alpha}=\{n<\omega:\exists(s,F)\in G,n\in s\}$. For all $n<\omega$, there is $(s,F)\in G\cap D_{n}$ and so $|X_{\alpha}|\geq|s|\geq n$. Hence $X_{\alpha}$ is infinite. Let $\beta<\alpha$ and $(s_{1},F_{1})\in G\cap E_{\beta}$. For any $x\in X_{\alpha}$, there is $(s_{2},F_{2})\in G$ such that $x\in s_{2}$. Hence there is $(s_{3},F_{3})\in G$ a refinement of $(s_{1},F_{2}),(s_{2},F_{2})$. We have $x\in s_{2}\subseteq s_{3}$ and $s_{3}\subseteq s_{1}\subseteq X_{\beta}$. Hence $X_{\alpha}\setminus X_{\beta}\subseteq s_{1}$ is finite and the induction hypothesis is true at step $\alpha$.

- page 1 of 4