# Blog de Frédéric

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}$. ∎

Friday, October 24 2014

## A quick note for Mozillians regarding MathML on Wikipedia

As mentioned some time ago and as recently announced on the MathML and MediaWiki mailing lists, a MathML mode with SVG/PNG fallback is now available on Wikipedia. In order to test it, you need to log in with a Wikipedia account and select the mode in the "Math" section of your preferences.

Some quick notes for Mozillians:

• Although Mozilla intern Jonathan Wei has done some work on MathML accessibility and that there are reports about work in progress to make Firefox work with NVDA / Orca / VoiceOver, we unfortunately still don't have something ready for Gecko browsers. You can instead try the existing solutions for Safari or Internet Explorer (ChromeVox and JAWS 16 beta are supposed to be MathML-aware but fail to read the MathML on Wikipedia at the moment).

• By default, the following MATH fonts are tried: Cambria Math, Latin Modern Math, STIX Math, Latin Modern Math (Web font). In my opinion, our support for Cambria Math (installed by default on Windows) is still not very good, so I'd recommend to use Latin Modern Math instead, which has the same "Computer Modern" style as the current PNG mode. To do that, go to the "Skin" section of your preferences and just add the rule math { font-family: Latin Modern Math; } to your "Custom CSS". Latin Modern Math is installed with most LaTeX distributions, available from the GUST website and provided by the MathML font add-on.

• You can actually install various fonts and try to make the size and style of the math font consistent with the surrounding text. Here are some examples:

/* Asana Math (Palatino style) */
.mw-body, mtext {
font-family: Palatino Linotype, URW Palladio L, Asana Math;
}
math {
font-family: Asana Math;
}

/* Cambria (Microsoft Office style) */
.mw-body, mtext {
font-family: Cambria;
}
math {
font-family: Cambria Math;
}

/* Latin Modern (Computer Modern style) */
.mw-body, mtext {
font-family: Latin Modern Roman;
}
math {
font-family: Latin Modern Math;
}

/* STIX/XITS (Times New Roman style) */
.mw-body, mtext {
font-family: XITS, STIX;
}
math {
font-family: XITS Math, STIX Math;
}

/* TeX Gyre Bonum (Bookman style) */
.mw-body, mtext {
font-family: TeX Gyre Bonum;
}
math {
font-family: TeX Gyre Bonum Math;
}

/* TeX Gyre Pagella (Palatino style) */
.mw-body, mtext {
font-family: TeX Gyre Pagella;
}
math {
font-family: TeX Gyre Pagella Math;
}

/* TeX Gyre Schola (Century Schoolbook style) */
.mw-body, mtext {
font-family: TeX Gyre Schola;
}
math {
font-family: TeX Gyre Schola Math;
}

/* TeX Gyre Termes (Times New Roman style) */
.mw-body, mtext {
font-family: TeX Gyre Termes;
}
math {
font-family: TeX Gyre Termes Math;
}

• We still have bugs with missing fonts and font inflation on mobile devices. If you are affected by these bugs, you can force the SVG fallback instead:

span.mwe-math-mathml-inline, div.mwe-math-mathml-display {
display: none !important;
}
span.mwe-math-mathml-inline + .mwe-math-fallback-image-inline {
display: inline !important;
}
div.mwe-math-mathml-display + .mwe-math-fallback-image-display {
display: block !important;
}

• You might want to install some Firefox add-ons for copying MathML/LaTeX, zooming formulas or configuring the math font.

• Finally, don't forget to report bugs to Bugzilla so that volunteers can continue to improve our MathML support. Thank you!

Wednesday, June 18 2014

Four years ago I started to write some MathML add-ons using Jetpack 0.8, now called Add-on SDK. I've recently made progress on this project, so that all the initial features are now available as Firefox add-ons (my initial hope was that the Add-on SDK would eventually be compatible with all Gecko browsers but unfortunately that still does not seem to be the case at the moment). The Mathzilla collection is available on AMO but some of the add-ons are still undergoing review. Here is an overview:

• The math editor feature is now provided by the TeXZilla add-on. The Arabic math support I experimented a bit later is also available.

• The conversion of content MathML using David Carlisle's XSLT stylesheet is now in its own MathML-ctop add-on. There is another similar add-on to add MathML3 features missing in Gecko called MathML-mml3ff. Note that these add-ons do not rely on the Add-on SDK and will work in any Gecko browsers. However, they should probably be improved.

• Another add-on that does not rely on the Add-on SDK is the one adding mathematical fonts called MathML-fonts. I uploaded version 2.0 to use the new OpenType MATH fonts supported in Gecko 31, but I hope that it will no longer be necessary in the future (more on this later).

• The conversion of PNG images into MathML is now provided by the Image to MathML add-on. At the moment, it is still experimental, see the details on mozilla.dev.tech.mathml if you want to help. It only works for some Web sites using LaTeX in alt text but I wish I can find a solution for Wolfram Websites.

• Since many Web sites are using MathJax and because in the meantime MathJax moved to its slow HTML-CSS output by default I had to write an add-on to force MathJax to use native MathML, which is available here. Actually, it's even better since it disables the mml2jax preprocessor to avoid useless work by MathJax for Web sites that already use MathML in the source code. It also prevents the MathJax menu to override the browser user interface (note that the three add-ons below provide some UI features similar to what one can find in MathJax).

• The feature to copy a MathML formula is now provided by the MathML Copy add-on. Note that it actually copies two flavors (text and html). It is also possible to copy the original TeX source when it is provided (e.g. on MDN).

• A new MathML Zoom add-on provides a zooming feature similar to what MathJax does.

• A new MathML Font Settings add-on allows to configure font-family and font-size of mathematics similar to what MathJax provides. Note however, that the list of font-family choices in the context menu is based on the OpenType MATH fonts that will only be supported in Gecko 31.

I believe splitting the original Mathzilla add-on into many add-ons gives more flexibility to let people choose the desired features. As usual, help to localize the add-ons is very welcome.

Tuesday, June 3 2014

## TeXZilla 0.9.7 Released

Today the Mozilla MathML team released a new version of TeXZilla. You can download a release package or install it with npm. We fixed a few bugs, but there are known issues due to errors in the unicode.xml file of XML Entity Definitions for Characters or inherited from the itex2MML grammar that does not make it ready for version 1.0. The main improvements in this new release are enhancements to the public API and to the command line interface.

TeXZilla can now be used as a stream filter. Each TeX expressions delimited by the classical $...$, $$...$$, $...$ and $$...$$ will be converted into inline or display MathML. Outside these delimiters, you can use \$ and \\ as escaped characters. We offer three ways to apply that stream filter: • From the command line, in a UNIX pipeline: cat foo-tex.html | phantomjs TeXZilla.js streamfilter > foo-mathml.html echo "This is a **Markdown** document with a *math formula*:$ z = \\sqrt{x^2 + y^2} $" | markdown | nodejs TeXZilla.js streamfilter | sed '1s/^/\n<!-- HTML5 document -->\n/' (note: this is not yet supported by slimerjs) • Using the TeXZilla.filterString(aString) function, for example TeXZilla.filterString("blah$x^2$blah") will return the filtered string. • Using the TeXZilla.filterElement(aElement) function. This one will browse recursively the descendants of the DOM element aElement and the stream filter will be applied to the text leaves. By introducting these TeXZilla.filter* function, it becomes tempting to use TeXZilla the same way as MathJax, that is to process all the text nodes in your Web pages and to filter the TeX strings. This is not the intended goal of TeXZilla and it is strongly discouraged: not only the MathML content won't appear in crawlers (e.g. search engines or feed readers) but also browsing all the DOM elements and appending new ones can be very slow for large documents. Instead, it is recommend to filter your static Web page with commonJS TeXZilla.js streamfilter before publishing it or to use a server-side conversion for example using the Web server mode. There are situations where you do not have other choice, though. In that case try to reduce as much as possible the number of elements being processed (see the example in the next section). Of course, if you do not care about performance and MathML availibility outside your web site, you can just use MathJax. ## New Safe and Itex-Identifier parsing modes The most notable difference between TeXZilla and itex2MML is the handling of some expressions like $xy$ or $Func. By default, TeXZilla interprets this as individual MathML identifiers <mi>x</mi><mi>y</mi> (so that as in LaTeX, they will render in italic) while itex2MML interprets this as a single indentifier <mi>Func</mi>. It is now possible to configure TeXZilla to align with itex2MML's behavior. To do that, use TeXZilla.setItexIdentifierMode or pass the appropriate boolean to the command line. Consecutive non-basic letters (like Greek or Arabic) are still treated as individual tokens. With that change, we hope that TeXZilla could be used to parse all the commands supported by itex2MML into an equivalent output. Together with the command line stream filter, this should allow to recover all the nice itex2MML features. Similarly, a safe mode is now available and can be enabled with TeXZilla.setSafeMode or by passing the appropriate boolean to the command line. This mode will forbid commands that could be used for XSS injections like \href. With that mode and the new TeXZilla.filterElement function, I'm now able to remove MathJax's use from my blog (users of browsers without good MathML support can still enable it or choose the lighter mathml.css stylesheet). MathJax was a bit overkill for my blog since I'm only parsing visitor comments. To illustrate how the setSafeMode and filterString functions can be used, I now just have to do // Process TeX fragments in blog comments and comment preview. window.addEventListener("DOMContentLoaded", function() { TeXZilla.setSafeMode(true); var toProcess = document.querySelectorAll("#comments > dl > dd, #comment-form dd.comment-preview"); for (var i = 0; i < toProcess.length; i++) { TeXZilla.filterElement(toProcess[i]); } });  ## Inserting equations in a 2D/WebGL canvas The new function TeXZilla.toImage has been introduced to convert a TeX fragment into a math HTML image with a base64-encoded src attribute. Contrary to other functions of the API, this one needs to do some work to determine the image size and perform the conversion, so it is unlikely to work as expected in a non-browser context. The goal is really only to have a convenient function to generate image of mathematical formulas and insert them into a canvas context to draw 2D or 3D scientific schemas. At the moment, this works well only in Gecko. For instance, var image = TeXZilla.toImage("\\vec{F} = G \\frac{m_1 m_2}{r^2} \\mathbf{u}"); image.onload = function() { canvas.getContext("2d").drawImage(image, (canvas.width - image.width) / 2, (canvas.height - image.height) / 2); }  will insert a mathematical formula in the middle of a 2D canvas. Similarly, you can insert a mathematical formula as a texture in a WebGL canvas. It is recommended to pass aRoundToPowerOfTwo=true to TeXZilla.toImage, so that the image will have dimensions that are power of two. Note that the mathematical formula will be automatically centered in the middle of the generated image. See this example for how to setup the formulas with three.js and make them always oriented in the direction of the camera. ## Integration in Mozilla products • The CKeditor editor plugin is now integrated in MDN, so you can click on the square root logo in the editor toolbar to insert mathematical formulas. By the way, the mathml.css is now used for browsers without MathML support. See for example the pages for acosh, atanh or CSS transform. • The editor/ in comm-central now integrates a small input box to insert mathematical formulas, accessible from the Insert menu. This will be available in Thunderbird 31 and Seamonkey 2.28, so that you can write mathematics in your emails and in the WYSIWYG editors. • Various FirefoxOS Web math apps have been written and use TeXZilla. Raniere is also working on a math keyboard for FirefoxOS as a GSoC project, which will allow to type mathematics faster on mobile devices. Tuesday, February 25 2014 ## TeXZilla 0.9.4 Released update 2014/03/11: TeXZilla is now available as an npm module. ## Introduction For the past two months, the Mozilla MathML team has been working on TeXZilla, yet another LaTeX-to-MathML converter. The idea was to rely on itex2MML (which dates back from the beginning of the Mozilla MathML project) to create a LaTeX parser such that: • It is compatible with the itex2MML syntax and is similarly generated from a LALR(1) grammar (the goal is only to support a restricted set of core LaTeX commands for mathematics, for a more complete converter of LaTeX documents see LaTeXML). • It is available as a standalone Javascript module usable in all the Mozilla Web applications and add-ons (of course, it will work in non-Mozilla products too). • It accepts any Unicode characters and supports right-to-left mathematical notation (these are important for the world-wide aspect of the Mozilla community). The parser is generated with the help of Jison and relies on a grammar based on the one of itex2MML and on the unicode.xml file of the XML Entity Definitions for Characters specification. As suggested by the version number, this is still in development. However, we have made enough progress to present interesting features here and get more users and developers involved. ## Quick Examples \frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 $\frac\left\{x^2\right\}\left\{a^2\right\} + \frac\left\{y^2\right\}\left\{b^2\right\} = 1$ ∑_{n=1}^{+∞} \frac{1}{n^2} = \frac{π^2}{6} $\sum _\left\{n=1\right\}^\left\{+\infty \right\} \frac\left\{1\right\}\left\{n^2\right\} = \frac\left\{\pi ^2\right\}\left\{6\right\}$ س = \frac{-ب\pm\sqrt{ب^٢-٤اج}}{٢ا} $س = \frac\left\{-ب\pm\sqrt\left\{ب^٢-٤اج\right\}\right\}\left\{٢ا\right\}$ ## Live Demo / FirefoxOS Web app A live demo is available to let you test the LaTeX-to-MathML converter with various options and examples. For people willing to use the converter on their mobiles a FirefoxOS Web app is also available. ## Using TeXZilla in a CommonJS program or Web page TeXZilla is made of a single TeXZilla.js file with a public API to convert LaTeX to MathML or extract the TeX source from a MathML element. The converter accepts some options like inline/display mode or RTL/LTR direction of mathematics. You can load it the standard way in any Javascript program and obtain a TeXZilla object that exposes the public API. For example in a commonJS program, to convert a TeX source into a MathML source:  var TeXZilla = require("./TeXZilla"); console.log(TeXZilla.toMathMLString("\\sqrt{\\frac{x}{2}+y}"));  or in a Web Page, to convert a TeX source into a MathML DOM element:  <script type="text/javascript" src="TeXZilla.js"></script> ... var MathMLElement = TeXZilla.toMathML("\\sqrt{\\frac{x}{2}+y}");  ## Using TeXZilla in Mozilla Add-ons One of the goal of TeXZilla is to be integrated in Mozilla add-ons, allowing people to write cool math applications (in particular, we would like to have an add-on for Thunderbird). A simple Firefox add-on has been written and passed the AMO review, which means that you can safely include the TeXZilla.js script in your own add-ons. TeXZilla can be used as an addon-sdk module. However, if you intend to use features requiring a DOMParser instance (for example toMathML), you need to initialize the DOM explicitly:  var {Cc, Ci} = require("chrome"); TeXZilla.setDOMParser(Cc["@mozilla.org/xmlextras/domparser;1"]. createInstance(Ci.nsIDOMParser));  More generally, for traditional Mozilla add-ons, you can do  TeXZilla.setDOMParser(Components. classes["@mozilla.org/xmlextras/domparser;1"]. createInstance(Components.interfaces.nsIDOMParser));  ## Using TeXZilla from the command line TeXZilla has a basic command line interface. However, since CommonJS is still being standardized, this may work inconsistently between commonjs interpreters. We have tested it on slimerjs (which uses Gecko), phantomjs and nodejs. For example you can do  slimerjs TeXZilla.js parser "a^2+b^2=c^2" true
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><...


or launch a Web service (see next section). We plan to implement a stream filter too so that it can behave the same as itex2MML: looking the LaTeX fragments from a text document and converting them into MathML.

## Using TeXZilla as a Web Server

TeXZilla can be used as a Web Server that receives POST and GET HTTP requests with the LaTeX input and sends JSON replies with the MathML output. The typical use case is for people willing to perform some server-side LaTeX-to-MathML conversion.

For instance, to start the TeXZilla Webserver on port 7777:

  $nodejs TeXZilla.js webserver 7777 Web server started on http://localhost:7777  Then you can sent a POST request: $ curl -H "Content-Type: application/json" -X POST -d '{"tex":"x+y","display":"true"}' http://localhost:7777
{"tex":"x+y","mathml":"<math xmlns=\"http://www.w3.org/1998/Math/MathML\"...


or a GET request:

  \$ curl "http://localhost:7777/?tex=x+y&rtl=true"
{"tex":"x+y","mathml":"<math xmlns=\"http://www.w3.org/1998/Math/MathML\"...


Note that client-side conversion is trivial using the public API, but see the next section.

## Web Components Custom Element <x-tex>

We used the X-Tag library to implement a simple Web Components Custom Element <x-tex>. The idea is to have a container for LaTeX expressions like

  <x-tex dir="rtl">س = \frac{-ب\pm\sqrt{ب^٢-٤اج}}{٢ا}</x-tex>

that will be converted into MathML by TeXZilla and displayed in your browser: $س = \frac\left\{-ب\pm\sqrt\left\{ب^٢-٤اج\right\}\right\}\left\{٢ا\right\}$. You can set the display/dir attributes on that <x-tex> element and they will be applied to the [itex] element. Instances of <x-tex> elements also have a source property that you can use to retrieve or set the LaTeX source. Of course, the MathML output will automatically be updated when dynamic changes occur. You can try this online demo.

## CKEditor Plugins / Integration in MDN

Finally, we created a first version of a TeXZilla CKEditor plugin. An online demo is available here. We already sent a pull request to Kuma and we hope it will soon enable users to put mathematical mathematical formulas in MDN articles without having to paste the MathML into the source code view. It could be enhanced later with a more advanced UI.

Wednesday, January 29 2014

## New MathML Firefox add-ons on AMO

While the patches for MathML integration in MediaWiki are progressively being reviewed and merged and while we are working on the support for Open Type fonts with a MATH table in Gecko, I finally found time to check the progress in Mozilla's add-on SDK. In particular, since the last time I tried (some years ago) they have introduced a cleaner interface for content scripts as well as the possibility to use XPCOM for missing features. Hence I have been able to update some of my experimental MathML add-ons. I have submitted two new add-ons to Mozilla's AMO that I hope could be useful to some people:

• MathJax Native MathML, an add-on to force MathJax to switch to Gecko's MathML support without having to use the MathJax menu to change the output mode and works even on Websites where that menu is disabled. This also removes MathJax's automatic rescaling and inline-block span that are currently causing random rendering bugs with Gecko's native MathML (and will confuse possible future line-breaking support anyway).
• MathML Copy (at the moment only partially reviewed by the AMO team), an add-on to copy MathML and TeX into the clipboard. For MathML, two flavors are copied: the source as plain text (to paste in your favorite text editor) and the MathML as HTML (to paste in Thunderbird, MDN, any Gecko-based HTML editor etc). Copying TeX is only possible when it is provided via the standard MathML annotation method, which is the case in e.g. LaTeXML and Instiki documents as well as in Wikipedia in the future.

As usual, there is room for improvements and bug fixes, but that's a start. In particular I would be happy to get translations for the two strings of the MathML Copy add-on: "Copy MathML Formula" and "Copy TeX Source". Also, because I used the add-on SDK these add-ons are unfortunately only available for Firefox at the moment...

Monday, January 13 2014

## Introduction

As mentioned during the Mozilla Summit and recent MathML meetings, progress has recently be made to the way mathematical equations are handled on Wikipedia. This work has mainly be done by the volunteer contributor Moritz Schubotz (alias Physikerwelt), Wikimedia Foundation's developer Gabriel Wicke as well as members of MathJax. Moritz has been particularly involved in that project and he even travelled from Germany to San Francisco in order to meet MediaWiki developers and spend one month to do volunteer work on this project. Although the solution is essentially ready for a couple of months, the review of the patches is progressing slowly. If you wish to speed up the integration of what is probably the most important improvements to MediaWiki Math to happen, please read how you can help below.

## Current Status

The approach that has been used on Wikipedia so far is the following:

• Equations are written in LaTeX or more precisely, using a specific set of LaTeX commands accepted by texvc. One issue for the MediaWiki developers is that this program is written in OCaml and no longer maintained, so they would like to switch to a more modern setup.
• texvc calls the LaTeX program to convert the LaTeX source into PNG images and this is the default mode. Unfortunately, using images for representing mathematical equations on the Web leads to classical problems (for example alignment or rendering quality just to mention a few of them) that can not be addressed without changing the approach.
• For a long time, registered users have been able to switch to the MathJax mode thanks to the help of nageh, a member of the MathJax community. This mode solves many of the issues with PNG images but unfortunately it adds its own problems, some of them being just unacceptable for MediaWiki developers. Again, these issues are intrinsic to the use of a Javascript polyfill and thus yet another approach is necessary for a long-term perspective.
• Finally, registered users can also switch to the LaTeX source mode, that is only display the text source of equations.

## Short Term Plan

Native MathML is the appropriate way to fix all the issues regarding the display of mathematical formulas in browsers. However, the language is still not perfectly implemented in Web rendering engines, so some fallback is necessary. The new approach will thus be:

• The TeX equation will still be edited by hand but it will be possible to use a visual editor.
• texvc will be used as a filter to validate the TeX source. This will ensure that only the texvc LaTeX syntax is accepted and will avoid other potential security issues. The LaTeX-to-PNG conversion as well as OCaml language will be kept in the short term, but the plan is to drop the former and to replace the latter with a a PHP equivalent.
• A LaTeX-to-MathML conversion followed by a MathML-to-SVG conversion will be performed server-side using MathJax.
• By default all the users will receive the same output (MathML+SVG+PNG) but only one will be made visible, according your browser capabilities. As a first step, native MathML will only be used in Gecko and other rendering engines will see the SVG/PNG fallback ; but the goal is to progressively drop the old PNG output and to move to native MathML.
• Registered users will still be able to switch to the LaTeX source mode.
• Registered users will still be able to use MathJax client-side, especially if they want to use the HTML-CSS output. However, this is will no longer be a separate mode but an option to enable. That is, the MathML/SVG/PNG/Source is displayed normally and progressively replaced with MathJax's output.

Most of the features above have already been approved and integrated in the development branch or are undergoing review process.

## How can you help?

The main point is that everybody can review the patches on Gerrit. If you know about Javascript and/or PHP, if you are interested in math typesetting and wish to get involved in an important Open Source project such as Wikipedia then it is definitely the right time to help the MediaWiki Math project. The article How to become a MediaWiki hacker is a very good introduction.

When getting involved in a new open source project one of the most important step is to set up the development environment. There are various ways to setup a local installation of MediaWiki but using MediaWiki-Vagrant might be the simplest one: just follow the Quick Start Guide and use vagrant enable-role math to enable the Math Extension.

The second step is to create a WikiTech account and to set up the appropriate SSH keys on your MediaWiki-Vagrant virtual machine. Then you can check the Open Changes, test & review them. The Gerrit code review guide may helpful, here.

If you need more information, you can ask Moritz or try to reach people on the #mediawiki (freenode) or #mathml (mozilla) channels. Thanks in advance for your help!

Sunday, January 5 2014

## Funding MathML Developments in Gecko and WebKit (part 2)

As I mentioned three months ago, I wanted to start a crowdfunding campaign so that I can have more time to devote to MathML developments in browsers and (at least for Mozilla) continue to mentor volunteer contributors. Rather than doing several crowdfunding campaigns for small features, I finally decided to do a single crowdfunding campaign with Ulule so that I only have to worry only once about the funding. This also sounded more convenient for me to rely on some French/EU website regarding legal issues, taxes etc. Also, just like Kickstarter it's possible with Ulule to offer some "rewards" to backers according to the level of contributions, so that gives a better way to motivate them.

As everybody following MathML activities noticed, big companies/organizations do not want to significantly invest in funding MathML developments at the moment. So the rationale for a crowdfunding campaign is to rely on the support of the current community and on the help of smaller companies/organizations that have business interest in it. Each one can give a small contribution and these contributions sum up in enough money to fund the project. Of course this model is probably not viable for a long term perspective, but at least this allows to start something instead of complaining without acting ; and to show bigger actors that there is a demand for these developments. As indicated on the Ulule Website, this is a way to start some relationship and to build a community around a common project. My hope is that it could lead to a long term funding of MathML developments and better partnership between the various actors.

Because one of the main demand for MathML (besides accessibility) is in EPUB, I've included in the project goals a collection of documents that demonstrate advanced Web features with native MathML. That way I can offer more concrete rewards to people and federate them around the project. Indeed, many of the work needed to improve the MathML rendering requires some preliminary "code refactoring" which is not really exciting or immediately visible to users...

Hence I launched the crowdfunding campaign the 19th of November and we reached 1/3 of the minimal funding goal in only three days! This was mainly thanks to the support of individuals from the MathML community. In mid december we reached the minimal funding goal after a significant contribution from the KWARC Group (Jacobs University Bremen, Germany) with which I have been in communication since the launch of the campaign. Currently, we are at 125% and this means that, minus the Ulule commision and my social/fiscal obligations, I will be able to work on the project during about 3 months.

I'd like to thank again all the companies, organizations and people who have supported the project so far! The crowdfunding campaign continues until the end of January so I hope more people will get involved. If you want better MathML in Web rendering engines and ebooks then please support this project, even a symbolic contribution. If you want to do a more significant contribution as a company/organization then note that Ulule is only providing a service to organize the crowdfunding campaign but otherwise the funding is legally treated the same as required by my self-employed status; feel free to contact me for any questions on the project or funding and discuss the long term perspective.

Finally, note that I've used my savings and I plan to continue like that until the official project launch in February. Below is a summary of what have been done during the five weeks before the holiday season. This is based on my weekly updates for supporters where you can also find references to the Bugzilla entries. Thanks to the Apple & Mozilla developers who spent time to review my patches!

## Collection of documents

The goal is to show how to use existing tools (LaTeXML, itex2MML, tex4ht etc) to build EPUB books for science and education using Web standards. The idea is to cover various domains (maths, physics, chemistry, education, engineering...) as well as Web features. Given that many scientific circles are too much biased by "math on paper / PDF" and closed research practices, it may look innovative to use the Open Web but to be honest the MathML language and its integration with other Web formats is well established for a long time. Hence in theory it should "just work" once you have native MathML support, without any circonvolutions or hacks. Here are a couple of features that are tested in the sample EPUB books that I wrote:

• Rendering of MathML equations (of course!). Since the screen size and resolution vary for e-readers, automatic line breaking / reflowing of the page is "naturally" tested and is an important distinction with respect to paper / PDF documents.
• CSS styling of the page and equations. This includes using (Web) fonts, which are very important for mathematical publishing.
• Using SVG schemas and how they can be mixed with MathML equations.
• Using non-ASCII (Arabic) characters and RTL/LTR rendering of both the text and equations.
• Interactive document using Javascript and <maction>, <input>, <button> etc. For those who are curious, I've created some videos for an algebra course and a lab practical.
• Using the <video> element to include short sequences of an experiment in a physics course.
• Using the <canvas> element to draw graphs of functions or of physical measurements.
• Using WebGL to draw interactive 3D schemas. At the moment, I've only adapted a chemistry course and used ChemDoodle to load Crystallographic Information Files (CIF) and provide 3D-representation of crystal structures. But of course, there is not any problem to put MathML equations in WebGL to create other kinds of scientific 3D schemas.

## WebKit

I've finished some work started as a MathJax developer, including the maction support requested by the KWARC Group. I then tried to focus on the main goals: rendering of token elements and more specifically operators (spacing and stretching).

• I improved LTR/RTL handling of equations (full RTL support is not implemented yet and not part of the project goal).
• I improved the maction elements and implemented the toggle actiontype.
• I refactored the code of some "mrow-like" elements to make them all behave like an <mrow> element. For example while WebKit stretched (some) operators in <mrow> elements it could not stretch them in <mstyle>, <merror> etc Similarly, this will be needed to implement correct spacing around operators in <mrow> and other "mrow-like" elements.
• I analyzed more carefully the vertical stretching of operators. I see at least two serious bugs to fix: baseline alignment and stretch size. I've uploaded an experimental patch to improve that.
• Preliminary work on the MathML Operator Dictionary. This dictionary contains various properties of operators like spacing and stretchiness and is fundamental for later work on operators.
• I have started to refactor the code for mi, mo and mfenced elements. This is also necessary for many serious bugs like the operator dictionary and the style of mi elements.
• I have written a patch to restore support for foreign objects in annotation-xml elements and to implement the same selection algorithm as Gecko.

## Gecko

I've continued to clean up the MathML code and to mentor volunteer contributors. The main goal is the support for the Open Type MATH table, at least for operator stretching.

• Xuan Hu's work on the <mpadded> element landed in trunk. This element is used to modify the spacing of equations, for example by some TeX-to-MathML generators.
• On Linux, I fixed a bug with preferred widths of MathML token elements. Concretely, when equations are used inside table cells or similar containers there is a bug that makes equations overflow the containers. Unfortunately, this bug is still present on Mac and Windows...
• James Kitchener implemented the mathvariant attribute (e.g used by some tools to write symbols like double-struck, fraktur etc). This also fixed remaining issues with preferred widths of MathML token elements. Khaled Hosny started to update his Amiri and XITS fonts to add the glyphs for Arabic mathvariants.
• I finished Quentin Headen's code refactoring of mtable. This allowed to fix some bugs like bad alignment with columnalign. This is also a preparation for future support for rowspacing and columnspacing.
• After the two previous points, it was finally possible to remove the private "_moz-" attributes. These were visible in the DOM or when manipulating MathML via Javascript (e.g. in editors, tree inspector, the html5lib etc)
• Khaled Hosny fixed a regression with script alignments. He started to work on improvements regarding italic correction when positioning scripts. Also, James Kitchener made some progress on script size correction via the Open Type "ssty" feature.
• I've refactored the stretchy operator code and prepared some patches to read the OpenType MATH table. You can try experimental support for new math fonts with e.g. Bill Gianopoulos' builds and the MathML Torture Tests.

MathML developments in Chrome or Internet Explorer is not part of the project goal, even if obviously MathML improvements to WebKit could hopefully be imported to Blink in the future. Users keep asking for MathML in IE and I hope that a solution will be found to save MathPlayer's work. In the meantime, I've sent a proposal to Google and Microsoft to implement fallback content (alttext and semantics annotation) so that authors can use it. This is just a couple of CSS rules that could be integrated in the user agent style sheet. Let's see which of the two companies is the most reactive...

Sunday, December 1 2013

## Decomposition of 2D-transform matrices

Note: some parts of this blog post (especially the Javascript program) may be lost when exported to Planet or other feed aggregators. Please view it on the original page.

I recently took a look at the description of the CSS 2D / SVG transform matrix(a, b, c, d, e, f) on MDN and I added a concrete example showing the effect of such a transform on an SVG line, in order to make this clearer for people who are not familiar with affine transformations or matrices.

This also recalled me a small algorithm to decompose an arbitrary SVG transform into a composition of basic transforms (Scale, Rotate, Translate and Skew) that I wrote 5 years ago for the Amaya SVG editor. I translated it into Javascript and I make it available here. Feel free to copy it on MDN or anywhere else. The convention used to represent transforms as 3-by-3 matrices is the one of the SVG specification.

## Live demo

Enter the CSS 2D transform you want to reduce and decompose or pick one example from the list . You can also choose between LU-like or QR-like decomposition: .

CSS

Here is the reduced CSS/SVG matrix as computed by your rendering engine ? and its matrix representation:

After simplification (and modulo rounding errors), an SVG decomposition into simple transformations is ? and it renders like this:

After simplification (and modulo rounding errors), a CSS decomposition into simple transformations is ? and it renders like this:

CSS

A matrix decomposition of the original transform is:

## Mathematical Description

The decomposition algorithm is based on the classical LU and QR decompositions. First remember the SVG specification: the transform matrix(a,b,c,d,e,f) is represented by the matrix

$\left(\begin{array}{ccc}a& c& e\\ b& d& f\\ 0& 0& 1\end{array}\right)$

and corresponds to the affine transformation

$\left(\begin{array}{c}x\\ y\end{array}\right)↦\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)+\left(\begin{array}{c}e\\ f\end{array}\right)$

which shows the classical factorization into a composition of a linear transformation $\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)$ and a translation $\left(\begin{array}{c}e\\ f\end{array}\right)$. Now let's focus on the matrix $\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)$ and denote $\Delta =ad-bc$ its determinant. We first consider the LDU decomposition. If $a\ne 0$, we can use it as a pivot and apply one step of Gaussian's elimination:

$\left(\begin{array}{cc}1& 0\\ -b/a& 1\end{array}\right)\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)=\left(\begin{array}{cc}a& c\\ 0& \Delta /a\end{array}\right)$

and thus the LDU decomposition is

$\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)=\left(\begin{array}{cc}1& 0\\ b/a& 1\end{array}\right)\left(\begin{array}{cc}a& 0\\ 0& \Delta /a\end{array}\right)\left(\begin{array}{cc}1& c/a\\ 0& 1\end{array}\right)$

Hence if $a\ne 0$, the transform matrix(a,b,c,d,e,f) can be written translate(e,f) skewY(atan(b/a)) scale(a, Δ/a) skewX(c/a). If $a=0$ and $b\ne 0$ then we have $\Delta =-cb$ and we can write (this is approximately "LU with full pivoting"):

$\left(\begin{array}{cc}0& c\\ b& d\end{array}\right)=\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}b& d\\ 0& -c\end{array}\right)=\left(\begin{array}{cc}\mathrm{cos}\left(\pi /2\right)& -\mathrm{sin}\left(\pi /2\right)\\ \mathrm{sin}\left(\pi /2\right)& \mathrm{cos}\left(\pi /2\right)\end{array}\right)\left(\begin{array}{cc}b& 0\\ 0& \Delta /b\end{array}\right)\left(\begin{array}{cc}1& d/b\\ 0& 1\end{array}\right)$

and so the transform becomes translate(e,f) rotate(90°) scale(b, Δ/b) skewX(d/b). Finally, if $a=b=0$, then we already have an LU decomposition and we can just write

$\left(\begin{array}{cc}0& c\\ 0& d\end{array}\right)=\left(\begin{array}{cc}c& 0\\ 0& d\end{array}\right)\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$

and so the transform is translate(e,f) scale(c, d) skewX(45°) scale(0, 1).

As a consequence, we have proved that any transform matrix(a,b,c,d,e,f) can be decomposed into a product of simple transforms. However, the decomposition is not always what we want, for example scale(2) rotate(30°) will be decomposed into a product that involves skewX and skewY instead of preserving the nice factors.

We thus consider instead the QR decomposition. If $\Delta \ne 0$, then by applying the Gram–Schmidt process to the columns $\left(\begin{array}{c}a\\ b\end{array}\right),\left(\begin{array}{c}c\\ d\end{array}\right)$ we obtain

$\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)=\left(\begin{array}{cc}a/r& -b/r\\ b/r& a/r\end{array}\right)\left(\begin{array}{cc}r& \left(ac+bd\right)/r\\ 0& \Delta /r\end{array}\right)=\left(\begin{array}{cc}a/r& -b/r\\ b/r& a/r\end{array}\right)\left(\begin{array}{cc}r& 0\\ 0& \Delta /r\end{array}\right)\left(\begin{array}{cc}1& \left(ac+bd\right)/{r}^{2}\\ 0& 1\end{array}\right)$

where $r=\sqrt{{a}^{2}+{b}^{2}}\ne 0$. In that case, the transform becomes translate(e,f) rotate(sign(b) * acos(a/r)) scale(r, Δ/r) skewX(atan((a c + b d)/r^2)). In particular, a similarity transform preserves orthogonality and length ratio and so $ac+bd=\left(\begin{array}{c}a\\ b\end{array}\right)\cdot \left(\begin{array}{c}c\\ d\end{array}\right)=0$ and $\Delta =\parallel \left(\begin{array}{c}a\\ b\end{array}\right)\parallel \mid \left(\begin{array}{c}c\\ d\end{array}\right)\parallel \mathrm{cos}\left(\pi /2\right)={r}^{2}$. Hence for a similarity transform we get translate(e,f) rotate(sign(b) * acos(a/r)) scale(r) as wanted. We also note that it is enough to assume the weaker hypothesis $r\ne 0$ (that is $a\ne 0$ or $b\ne 0$) in the expression above and so the decomposition applies in that case too. Similarly, if we let $s=\sqrt{{c}^{2}+{d}^{2}}$ and instead assume $c\ne 0$ or $d\ne 0$ we get

$\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)=\left(\begin{array}{cc}\mathrm{cos}\left(\pi /2\right)& -\mathrm{sin}\left(\pi /2\right)\\ \mathrm{sin}\left(\pi /2\right)& \mathrm{cos}\left(\pi /2\right)\end{array}\right)\left(\begin{array}{cc}-c/s& d/s\\ -d/s& -c/s\end{array}\right)\left(\begin{array}{cc}\Delta /s& 0\\ 0& s\end{array}\right)\left(\begin{array}{cc}1& 0\\ \left(ac+bd\right)/{s}^{2}& 1\end{array}\right)$

Hence in that case the transform is translate(e,f) rotate(90° - sign(d) * acos(-c/s)) scale(Delta/s, s) skewY(atan((a c + b d)/s^2)). Finally if $a=b=c=d=0$, then the transform is just scale(0,0).

The decomposition algorithms are now easy to write. We note that none of them gives the best result in all the cases (compare for example how they factor Rotate2 and Skew1). Also, for completeness we have included the noninvertible transforms in our study (that is $\Delta =0$) but in practice they are not really useful (try NonInvertible).

Thursday, November 7 2013

## Gecko-based EPUB Readers and LaTeXML

This morning, Deyan Ginev announced on the LaTeXML mailing list that the first alpha version of LaTeXML with LaTeX to EPUB support is now available. This is a very good news for people willing to encourage researchers to move from offline formats to more modern Web formats. Although, some people had already been successful to combine LaTeX-to-XHTML converters and XHTML-to-EPUB converters, this is the first tool that I'm aware of that can do the direct LaTeX to EPUB3 (XHTML+MathML) conversion. I already mentioned a couple of Gecko-based EPUB tools in my previous blog post, so let's have a look at three of them. Feel free to mention more Gecko-based EPUB tools in the comments, I'm particularly interested to hear about FirefoxOS applications that would be similar to Apple's iBooks.

I have updated the LaTeXML samples based on Boris Zbarsky's thesis that we demonstrated at the Innovation Fairs in Santa Clara & Brussels. This shows how to generate the traditional PDF version, the Web version, the Web version with MathJax fallback and now the EPUB version! Here are some screenshots using the Firefox extension Lucifox:

Boris' Thesis in Lucifox ; page 2

Boris' Thesis in Lucifox ; page 4

I have intentionally not shown the diagram that are incorrectly converted by LaTeXML due to missing Xy-pic support (this is still in development). However, Gecko supports mixing SVG and MathML via the foreignObject element so this would not be a problem for Gecko-based EPUB readers. Here are some screenshots of an ebook about regular polygon that can be constructed with compass and straightedge that I have created with the help of itex2MML. They are viewed in EPUBReader which is another Firefox extension:

Lucifox and EPUBReader have a big drawback: they do not support EPUB pages with the "scripted" property. This means that you can not use Javascript to create dynamic ebooks with live samples or interactive exercices... but this is one of the reason to use Web formats! Fortunately, there is a XUL application called AZARDI that supports this feature. I have created another ebook that shows an interactive course on matrices. Click on the image to see the video on YouTube:

AZARDI, Interactive Course on Matrices

Saturday, October 12 2013

## Funding MathML Developments in Gecko and WebKit

update 2013-10-15: since I got feedback, I have to say that my funding plan is independent of my work at MathJax ; I'm not a MathJax employee but I have an independent contractor status. Actually, I already used my business to fund an intern for Gecko MathML developments during Summer 2011 :-)

## Retrospect

Since last April, I have been allowed by the MathJax Consortium to dedicate a small amount of my time to do MathML development in browsers, until possibly more serious involvement later. At the same time, we mentioned this plan to Google developers but unfortunately they just decided to drop the WebKit MathML code from Blink, making external contributions hard and unwelcome...

Hence I have focused mainly on Gecko and WebKit: You can find the MathML bugs that have been closed during that period on bugzilla.mozilla.org and bugs.webkit.org. For Gecko, this has allowed me to finish some of the work I started as a volunteer before I was involved full-time in MathJax as well as to continue to mentor MathML contributors. Regarding WebKit, I added a few new basic features like MathML lengths, <mspace> or <mmultiscripts> while I was getting familiar with the MathML code and WebKit organization/community. I also started to work on <semantics> and <maction>. More importantly, I worked with Martin Robinson to address the design concerns of Google developers and a patch to fix these issues finally landed early this week.

However, my progress has been slow so as I mentioned in my previous blog post, I am planning to find a way to fund MathML developments...

## Why funding MathML?

Note: I am assuming that the readers of this blog know why MathML is important and are aware of the benefits it can bring to the Web community. If not, please check Peter Krautzberger's Interview by Fidus Writer or the MozSummit MathML slides for a quick introduction. Here my point is to explain why we need more than volunteer-driven development for MathML.

First the obvious thing: Volunteer time is limited so if we really want to see serious progress in MathML support we need to give a boost to MathML developments. e-book publishers/readers, researchers/educators who are stuck outside the Web in a LaTeX-to-PDF world, developers/users of accessibility tools or the MathML community in general want good math support in browsers now and not to wait again for 15 more years until all layout engines catch up with Gecko or that the old Gecko bugs are fixed.

There are classical misunderstandings from people thinking that non-native MathML solutions and other polyfills are the future or that math on the Web could be implemented via PNG/SVG images or Web Components. Just open a math book and you will see that e.g. inline equations must be correctly aligned with the text or participate in line wrapping. Moreover we are considering math on the Web not math on paper, so we want it to be compatible with HTML, SVG, CSS, Javascript, Unicode, Bidi etc and also something that is fast and responsive. Technically, this means that a clean solution must be in the core rendering engine, spread over several parts of the code and must have strong interaction with the various components like the HTML5 parser, the layout tree, the graphic and font libraries, the DOM module, the style tree and so forth. I do not see any volunteer-driven Blink/Gecko/WebKit feature off the top of my head that has this characteristic and actually even SVG or any other kind of language for graphics have less interaction with HTML than MathML has.

The consequence of this is that it is extremely difficult for volunteers to get involved in native MathML and to do quick progress because they have to understand how the various components of the Blink/Gecko/WebKit code work and be sure to do things correctly. Good mathematical rendering is already something hard by itself, so that is even more complicated when you are not writing an isolated rendering engine for math on which you can have full control. Also, working at the Blink/Gecko/WebKit level requires technical skills above the average so finding volunteers who can work with the high-minded engineers of the big browser companies is not something easy. For instance, among the enthusiastic people coming to me and willing to help MathML in Gecko, many got stuck when e.g. they tried to build the Firefox source or do something more advanced and I never heard back from them. In the other direction, Blink/Gecko/WebKit paid developers are generally not familiar with MathML and do not have time to learn more about it and thus can not always provide a relevant review of the code, or they may break something while trying to modify code they do not entirely understand. Moreover, both the volunteers and paid staff have only a small amount of time to do MathML stuff while the other parts of the engine evolve very quickly, so it's sometimes hard to keep everything in sync. Finally, the core layout engines have strong security requirements that are difficult to satisfy in a volunteer-driven situation...

## Beyond volunteer-driven MathML developments

At that point, there are several options. First the lazy one: Give up with native math rendering, only focus on features that have impact on the widest Web audience (i.e. those that would allow browser vendors to get more market share and thus increase their profit), thank the math people for creating the Web and kindly ask them to use whatever hacks they can imagine to display equations on the Web. Of course as a Mozillian, I think people must decide the Web they want and thus exclude this option.

Next there is the ingenuous option: Expect that browser companies will understand the importance of math-on-the-Web and start investing seriously in MathML support. However, Netscape and Microsoft rejected the <MATH> tag from the 1995 HTML 3.0 draft and the browser companies have kept repeating they would only rely on volunteer contributions to move MathML forward, despite the repeated requests from MathML folks and other scientific communities. So that option is excluded too, at least in the short to medium term.

So it remains the ambitious option: Math people and other interested parties must get together and try to fund native MathML developments. Despite the effort of my manager at MathJax to convince partners and raise funds, my situation has not changed much since April and it is not clear when/if the MathJax Consortium can take the lead in native MathML developments. Given my expertise in Gecko, WebKit and MathML, I feel the duty to do something. Hence I wish to reorganize my work time: Decrease my involvement in MathJax core in order to increase my involvement in Gecko/WebKit developments. But I need the help of the community for that purpose. If you run a business with interest for math-on-the-Web and are willing to fund my work, then feel free to contact me directly by mail for further discussion. In the short term, I want to experiment with Crowd Funding as discussed in the next section. If this is successful we can think of a better organization for MathML developments in the long term.

## Crowd Funding

Wikipedia defines Crowd funding as "the collective effort of individuals who network and pool their money, usually via the Internet, to support efforts initiated by other people or organizations". There are several Crowd Funding platforms with similar rule/interface. I am considering Catincan which is specialized in Open Source Crowd Funding, can be used by any backer/developer around the world, can rely on Bugzilla to track the bug status and seems to have good process to collect the fund from backers and to pay developers. You can easily login to the Catincan Website if you have a GitHub, Facebook or Google account (apparently Persona is not supported yet...). Finally, it seems to have a communication interface between backers and developers, so that everybody can follow the development on the funded features.

One distinctive feature of catincan is that only well-established Open Source projects can be funded and only developers from these projects can propose and work on the new features ; so that backers can trust that the features will be implemented. Of course, I have been working on Gecko, WebKit and MathML projects so I hope people believe I sincerely want to improve MathML support in browsers and that I have the skills to do so ;-)

As said in my previous blog post, it is not clear at all (at least to me) whether Crowd Funding can be a reliable method, but it is worth trying. There are many individuals and small businesses showing interest in MathML, without the technical knowledge or appropriate staff to improve MathML in browsers. So if each one fund a small amount of money, perhaps we can get something.

One constraint is that each feature has 60 days to reach the funding goal. I do not have any idea about how many people are willing to contribute to MathML and how much money they can give. The statistical sample of projects currently funded is too small to extract relevant information. However, I essentially see two options: Either propose small features and split the big ones in small steps, so that each catincat submission will need less work/money and improvements will be progressive with regular feedback to backers ; or propose larger features so they look more attractive and exciting to people and will require less frequent submissions to catincat. At the beginning, I plan to start with the former and if the crowd funding is successful perhaps try the latter.

## Status in Open Source Layout Engines

Note: Obviously, Open Source Crowd Funding does not apply to Internet Explorer, which is the one main rendering engine not mentioned below. Although Microsoft has done a great job on MathML for Microsoft Word, they did not give any public statement about MathML in Internet Explorer and all the bug reports for MathML have been resolved "by design" so far. If you are interested in MathML rendering and accessibility in Internet Explorer, please check Design Science blog for the latest updates and tools.

Note: I am actually focusing on the history of Chromium here but of course there are other Blink-based browsers. Note that programs like QtWebEngine (formerly WebKit-based) or Opera (formerly Presto-based) lost the opportunity to get MathML support when they switched to Blink.

Alex Milowski and François Sausset's first MathML implementation did not pass Google's security review. Dave Barton fixed many issues in that implementation and as far as I know, there were not any known security vulnerabilities when Dave submitted his last version. MathML was enabled in Chrome 24 but Chrome developers had some concerns about the design of the MathML implementation in WebKit, which indeed violated some assumptions of WebKit layout code. So MathML was disabled in Chrome 25 and as said in the introduction, the source code was entirely removed when they forked.

Currently, the Chromium Dashboard indicates that MathML is shipped in Firefox/Safari, has positive feedback from developers and is an established standard ; but the Chromium status remains "No active development". If I understand correctly, Google's official position is that they do not plan to invest in MathML development but will accept external contributions and may re-enable MathML when it is ready (for some sense of "ready" to be defined). Given the MathML story in Chrome, it seems really unlikely that any volunteer will magically show up and be willing to submit a MathML patch. Incidentally, note the interesting work of the ChromeVox team regarding MathML accessibility: Their recent video provides a good overview of what they achieve (where Volker Sorge politely regrets that "MathML is not implemented in all browsers").

Although Google's design concerns have now been addressed in WebKit, one most serious remark from one Google engineer is that the WebKit MathML implementation is of too low quality to be shipped so they just prefer to have no MathML at all. As a consequence, the best short term strategy seems to be improving WebKit MathML support and, once it is good enough, to submit a patch to Google. The immediate corollary is that if you wish to see MathML in Chrome or other Blink-based browsers you should help WebKit MathML development. See the next section for more details.

chromatic

Actually, I tried to import MathML into Blink one day this summer. However, there were divergences between the WebKit and Blink code bases that made that a bit difficult. I do not plan to try again anytime soon, but if someone is interested, I have published my script and patch on GitHub. Note there may be even more divergences now and the patch is certainly bit-rotten. I also thought about creating/maintaining a "Chromatic" browser (Chrome + mathematics) that would be a temporary fork to let Blink users benefit from native MathML until it is integrated back in Blink. But at the moment, that would probably be too much effort for one person and I would prefer to focus on WebKit/Gecko developments for now.

### WebKit

The situation in WebKit is much better. As said before, Google's concerns are now addressed and MathML will be enabled again in all WebKit releases soon. Martin Robinson is interested in helping the MathML developments in WebKit and his knowledge of fonts will be important to improve operator stretching, which is one of the biggest issue right now. One new volunteer contributor, Gurpreet Kaur, also started to do some work on WebKit like support for the *scriptshifts attributes or for the <menclose> element. Last but not least, a couple of Apple/WebKit developers reviewed and accepted patches and even helped to fix a few bugs, which made possible to move development forward.

When he was still working on WebKit, Dave Barton opened bug 99623 to track the top priorities. When the bugs below and their related dependencies are fixed, I think the rendering in WebKit will be good enough to be usable for advanced math notations and WebKit will pass the MathML Acid 1 test.

• Bug 44208: For example, in expression like $\mathrm{sin}\left(x\right)$, the "x" should be in italic but not the "sin". This is actually slightly more complicated: It says when the default mathvariant value must be normal/italic. mathvariant is more like the text-transform CSS property in the sense that it remaps some characters to the corresponding mathematical characters (italic, bold, fraktur, double-struck...) for example $\mathfrak{A}$ (mathvariant=fraktur A) should render exactly the same as $𝔄$ (U+1D504). By the way, there is the related bug 24230 on Windows, that prevents to use plane 1 characters. The best solution will probably be to implement mathvariant correctly. See also Gecko's ongoing work by James Kitchener below.
• Bug 99618: Implement <mmultiscripts>, that allows expressions like ${}_{6}{}^{14}\mathrm{C}$ or $R_{i}{}_{j}{}_{;}{}^{j}=\frac{1}{2}S_{;}{}_{i}$. As said in the introduction, this is fixed in WebKit Nightly.
• Bug 99614: Support for stretchy operators like in ${\left(\frac{\overline{{z}_{1}+{z}_{2}}}{3}\right)}^{4}$. Currently, WebKit can only stretch operators vertically using a few Unicode constructions like ⎛ (U+239B) + ⎜ (U+239C) + ⎝ (U+239D) for the left parenthesis. Essentially only similar delimiters like brackets, braces etc are supported. For small sizes like $\left(\text{}$ or for large operators like $∑n2$ it is necessary to use non-unicode glyphs in various math fonts, but this is not possible in WebKit MathML yet. All of this will require a fair amount of work: implementing horizontal stretching, font-specific stuff, largeop/symmetric properties etc
• Bug 99620: Implement the operator dictionary. Currently, WebKit treats all the operators the same way, so for example it will use the same 0.2em spacing before and after parenthesis, equal sign or invisible operators in e.g. $f\left(x\right)={x}^{2}$. Instead it should use the information provided by the MathML operator dictionary. This dictionary also specifies whether operators are stretchy, symmetric or largeop and thus is related to the previous point.
• Bug 119038: Use the code for vertical stretchy operators to draw the radical symbols in roots like $\sqrt{\frac{2}{3}}$. Currently, WebKit uses graphic primitives which do not give a really good rendering.
• Bug 115610: Implement <mspace> which is used by many MathML generators to do some spacing in mathematical formulas. As said in the introduction, this is fixed in WebKit Nightly.

In order to pass the Mozilla MathML torture tests, at least displaystyle and scriptlevel must be implemented too, probably as internal CSS properties. This should also allow to pass Joe Java's MathML test, although that one relies on the infamous <mfenced> that duplicates the stretchy operator features and is implemented inconsistently in rendering engines. I think passing the MathML Acid 2 test will require slightly more effort, but I expect this goal to be achievable if I have more time to work on WebKit:

• Bug 115610: Implement <mspace>. Fixed!
• Bug 120164: Implement negative spacing for <mspace> (I have an experimental patch).
• Bug 85730: Implement <mpadded>, which is also used by MathML generators to do some tweaking of formulas. I have only done some experiments, that would be a generalization of <mspace>
• Bug 85733: Implement the href attribute ; well I guess the name is explicit enough to understand what it is used for! I only have some experimental patch here too. That would be mimicing what is done in SVG or HTML.
• Bug 120059 and bug 100626: Implement <maction> (at least partially) and <semantics>, which have been asked by long-time MathML users Jacques Distler and Michael Kohlhase. I have patches ready for that and this could be fixed relatively soon, I just need to find time to finish the work.

In general passing the MathML Acid 2 test is not too hard, you merely only need to implement those few MathML elements whose exact rendering is clearly defined by the MathML specification. Passing the MathML Acid 3 test is not expected in the medium term. However, the score will naturally increase while we improve WebKit MathML implementation. The priority is to implement what is currently known to be important to users. To give examples of bugs not previously mentioned: Implementing menclose or fixing various DOM issues like bugs 57695, 57696 or 107392.

More advanced features like those mentioned in the next section for Gecko are probably worth considering later (Open type MATH, linebreaking, mlabeledtr...). It is worth noting that Apple has already done some work on accessibility (with MathML being readable by VoiceOver in iOS7), authoring and EPUB (MathML is enabled in WebKit-based ebook readers and ibooks-author has an integrated LaTeX-to-MathML converter).

### Gecko

In general I think I have a good relationship with the Mozilla community and most people have respect for the work that has been done by volunteers for almost 15 years now. The situation has greatly improved since I joined the project, at that time some people claimed the Mozilla MathML project was dead after Roger Sidge's departure. One important point is that Karl Tomlinson has worked on repairing the MathML support when Roger Sidge left the project. Hence there is at least one Mozilla employee with good knowledge of MathML who can review the volunteer patches. Another key ingredient is the work that has recently been made by Mozilla to increase engagement of the volunteer community like good documentation on MDN, the #Introduction channel, Josh Matthews' mentored bugs and of course programs like GSOC. However, as said above, it is one thing to attract enthusiastic contributors and another thing to get long-term contributors who can work independently on more advanced features. So let's go back to my latest Roadmap for the Mozilla MathML Project and see what has been accomplished for one year:

• Font support: Dmitry Shachnev created a Debian package for the MathJax fonts and Mike Hommey added MathJax and Asana fonts in the list of suggested packages for Iceweasel. The STIX fonts have also been updated in Fedora and are installed by default on Mac OS X Lion (10.7). For Linux distributions, it would be helpful to implement Auto Installation Support. The bug to add mathematical fonts to Android has been assigned in June but no more progress has happened so far. Henri Sinoven opened a bug for FirefoxOS but there has not been any progress there either. I had some patches to restore the "missing MathML fonts" warning (using an information bar) but it was refused by Firefox reviewers. However, the code to detect missing MathML font could still be used for the similar bug 648548, which also seems inactive since January. There are still some issues on the MathJax side that prevent to integrate Web fonts for the native MathML output mode. So at the moment the solution is still to inform visitors about MathML fonts or to add MathML Web fonts to your Web site. Khaled Hosny (font and LaTeX expert) recently updated my patches to prepare the support for Open Type fonts and he offered to help on that feature. After James Kitchener's work on mathvariant, we realized that we will probably need to provide Arabic mathematical fonts too.
• Spacing: Xuan Hu continued to work on <mpadded> improvements and I think his patch is close to be accepted. Quentin Headen has done some progress on <mtable> before focusing on his InstantBird GSOC project. He is still far from being able to work on mtable@rowspacing/columnspacing but a work around for that has been added to MathJax. I fixed the negative space regression which was missing to pass the MathML Acid 2 test and is used in MathJax. Again, Khaled Hosny is willing to help to use the spacing of the Open Type MATH, but that will still be a lot of work.
• <mlabeledtr>: A work around for native MathML has been added in MathJax.
• Linebreaking: No progress except that I have worked on fixing a bug with intrinsic width computation. The unrelated printing issues mentioned in the blog post have been fixed, though.
• Operator Stretching: No progress. I tried to analyze the regression more carefully, but nothing is ready yet.
• Tabular elements: As said above, Quentin Headen has worked a bit on cleaning up <mtable> but not much improvements on that feature so far.
• Token elements: My patch for <ms> landed and I have done significant progress on the bad measurement of intrinsic width for token elements (however, the fix only seems to work on Linux right now). James Kitchener has taken over my work on improving our mathvariant support and doing related refactoring of the code. I am confident that he will be able to have something ready soon. The primes in exponents should render correctly with MathJax fonts but for other math fonts we will have to do some glyph substitutions.
• Dynamic MathML: No progress here but there are not so many bugs regarding Javascript+MathML, so that should not be too serious.
• Documentation: It is now possible to use MathML in code sample or directly in the source code. The MathML project pages have been entirely migrated to MDN. Also, Florian Scholz has recently been hired by Mozilla as a documentation writer (congrats!) and will in particular continue the work he started as a volunteer to document MathML on MDN.

I apologize to volunteers who worked on bugs that are not mentioned above or who are doing documentation or testing that do not appear here. For a complete list of activity since September 2012, Bugzilla is your friend. There are two ways to consider the progress above. If you see the glass half full, then you see that several people have continued the work on various MathML issues, they have made some progress and we now pass the MathML Acid 2 test. If you see the glass half empty, then you see that most issues have not been addressed yet and in particular those that are blocking the native MathML to be enabled in MathJax: bug 687807, bug 415413, the math font issues discussed in the first point, and perhaps linebreaking too. That is why I believe we should go beyond volunteer-driven MathML developments.

Most of the bugs mentioned above are tested by the MathML Acid 3 tests and we will win a few points when they are fixed. Again, passing MathML Acid 3 test is not a goal by itself so let's consider what are the big remaining areas it contains:

• Improving Tabular Elements and Operator Stretching, which are obviously important and used a lot in e.g. MathJax.
• Linebreaking, which as I said is likely to become fundamental with small screens and ebooks.
• Elementary Mathematics (you know addition, subtraction, multiplication, and division that kids learn), which I suspect will be important for educational tools and ebooks.
• Alignment: This is the one part of MathML that I am not entirely sure is relevant to work on in the short term. I understand it is useful for advanced layout but most MathML tools currently just rely on tables to do that job and as far as I know the only important engine that implements that is MathPlayer.

Finally there are other features outside the MathML rendering engines that I also find important but for which I have less expertise:

• Transferring MathML that is implementing copy/cut/drag and paste. Currently, we can do that by treating MathML as normal HTML5 code or by using the "show MathML source" feature and copying the source code. However, it would be best to implement a standard way to communicate with other MathML applications like Microsoft Word, Mathematica, Mapple, Windows' Handwriting panel etc I wrote some work-in-progress patches last year.
• Authoring MathML: Essentially implementing things like deletion, insertion etc maybe simple MathML token creation ; in Gecko's core editor, which is used by BlueGriffon, KompoZer, SeaMonkey, Thunderbird or even MDN. Other things like integrating Javascript parsers (e.g. ASCIIMath) or equation panels with buttons like are probably better done at the higher JS/HTML/XUL level. Daniel Glazman already wrote math input panels for BlueGriffon and Thunderbird.
• MathML Accessibility: This is one important application of MathML for which there is strong demand and where Mozilla is behind the competitors. James Teh started some experimental work on his NVDA tool before the summit.
• EPUB reader for FirefoxOS (and other mobile platforms): During the "Co-creating Action Plans" session, the Mozilla Taipei people were thinking about missing features for FirefoxOS and this idea about EPUB reader was my modest contribution. There are a few EPUB readers relying on Gecko and it would be good to check if they work in FirefoxOS and if they could be integrated by default, just like Apple has iBooks. BTW, there is a version of BlueGriffon that can edit EPUB books.

## Conclusion

I hope I have convinced some of the readers about the need to fund MathMLin browsers. There is a lot of MathML work to do on Gecko and WebKit but both projects have volunteers and core engineers who are willing to help. There are also several individuals / companies relying on MathML support in rendering engines for their projects and could support the MathML developments in some way. I am willing to put more of my time on Gecko and WebKit developments, but I need financial help for that purpose. I'm proposing catincan Crowd Funding in the short term so that anyone can contribute at the appropriate level, but other alternatives to fund the MathML development can be found like asking Peter Krautzberger about native MathML funding in MathJax, discussing with Igalia about funding Martin Robinson to work more on WebKit MathML or contacting me directly to establish some kind of part-time consulting agreement.

Please leave a comment on this blog or send me a private mail, if you agree that funding MathML in browsers is important, if you like the crowd funding idea and plan to contribute ; or if you have any opinions about alternative funding options. Also, please tell me what seem to be the priority for you and your projects among what I have mentioned above (layout engines, features etc) or among others that I may have forgotten. Of course, any other constructive comment to help MathML support in browsers is welcome. I plan to submit features on catincan soon, once I have more feedback on what people are interested in. Thank you!

Monday, October 7 2013

## Post-Summit Thoughts on the MathML Project

I'm back from a great Mozilla Summit 2013 and I'd just like to write a quick blog post about the MathML booths at the Innovation Fairs. I did not have the opportunity to talk with the MathML people who ran the booth at Santa Clara yet. However, everything went pretty well at Brussels, modulo of course some demos failing when done in live... If you are interested, the slides and other resources are available on my GitHub page.

Many Mozillians did not know about MathML or that it had been available in Gecko since the early days of the Mozilla project. Many people who use math (or just knowing someone who does) were curious about that feature and excited about the MathML potentials. I appreciated to get this positive feedback from Mozillians willing to use math on the Web and related media, instead of the scorn or hatred I sometimes see by misinformed people. I expect to provide more updates on LaTeXML, MediaWiki Math and MathJax when their next versions are released. The Gecko MathML support improves slowly but there has been interesting work by James Kitchener recently that I'd like to mention too.

Let's do an estimation à la Fermi: only a few volunteers have been contributing regularly and simultaneously to MathML in Gecko while most Mozilla-funded Gecko projects have certainly development teams that are 3 times as large. Let's be optimistic and assume that these volunteers have been able to dedicate a mean of 1 work day per week, compared to 5 for full-time staff. Given that the Mozilla MathML project will celebrate its 15 years next May, that means that the volunteer work transposed in terms of paid-staff time is only $\le \frac{15}{3\cdot 5}=1$ year. To be honest, I'm disregarding here the great work made by the Mozilla NZ team around 2007 to repair MathML after the Cairo migration. But still, what we have achieved in quality and completeness with such limited resources and time is really impressive.

As someone told me at the MathML booth, it's really frustating that something that is so important for the small portion of math-educated people is ignored because it is useless for the vast majority of people. This is not entirely true, since even elementary mathematics taught at school like the one of this blog post are not easily expressed with standard HTML and even less in a way accessible to people with visual disabilities. However, it summarizes well the feeling MathML folks had when they tried to convince Google to accept the volunteer work on MathML, despite its low quality.

As explained at the Summit Sessions, Mozilla's mission is different and the goal is to give people the right to control the Web they want. The MathML project is perhaps one of the oldest and successful volunteer-driven Mozilla project that is still active and demonstrates concretely the idea of the Mozilla's mission with e.g. the work of Roger Sidge who started to write the MathML implementation when Netscape opened its source code or the one of Florian Scholz who made MDN one of the most complete Web resource for MathML.

Mozilla Corporation has kept saying they don't want to invest in MathML developments and the focus right now is clearly on other features like FirefoxOS. Even projects that have a larger audience than the MathML support like the mail client or the editor are not in the priorities so someone else definitely need to step in for MathML. I've tried various methods, with more or less success, to boost the MathML developments like mentoring a GSoC project, funding a summer internship or relying on mentored bugs. I'm now considering crowd funding to help the MathML developments in Gecko (and WebKit). I don't want to do another Fermi estimation now but at first that looks like a very unreliable method. The only revenue generated by the MathML project so far are the $2\frac{⌊100\cdot \pi ⌋}{100}=2\cdot 3.14=6.28$ dollars to the Mozilla Fundation via contributions to my MathML-fonts add-on, so it's hard to get an idea of how much people would contribute to the Gecko implementaton. However, that makes sense since the only people who showed interest in native MathML support so far are individuals or small businesses (e.g. working on EPUB or accessibility) and I think it's worth trying it anyway. That's definitely something I'll consider after MathJax 2.3 is released...

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$.

Friday, May 3 2013

## Exercises in Set Theory: Applications of Forcing

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

The exercises from this chapter was a good opportunity to play a bit more with the forcing method. Exercise 15.15 seemed a straightforward generalization of Easton’s forcing but turned out to be a bit technical. I realized that the forcing notion used in that exercise provides a result in ZFC (a bit like Exercises 15.31 and 15.32 allow to prove some theorems on Boolean Algebras by Forcing).

Remember that $\beth_{0}=\aleph_{0},\beth_{1}=2^{{\beth_{0}}},\beth_{2}=2^{{\beth_{1}}}...,% \beth_{\omega}=\sup\beth_{n},...,\beth_{{\alpha+1}}=2^{{\beth_{{\alpha}}}},...$ is the normal sequence built by application of the continuum function at successor step. One may wonder: is $\beth_{\alpha}$ regular?

First consider the case where $\alpha$ is limit. The case $\alpha=0$ is clear ($\beth_{0}=\aleph_{0}$ is regular) so assume $\alpha>0$. If $\alpha$ is an inacessible cardinal, it is easy to prove by induction that for all $\beta<\alpha$ we have $\beth_{\beta}<\alpha$: at step $\beta=0$ we use that $\alpha$ is uncountable, at successor step that it is strong limit and at limit step that it is regular. Hence $\beth_{\alpha}=\alpha$ and so is regular. If $\alpha$ is not a cardinal then $\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)\leq|\alpha|<\alpha% \leq\beth_{\alpha}$ so $\beth_{\alpha}$ is singular. If $\alpha$ is a cardinal but not strong limit then there is $\beta<\alpha$ such that $2^{\beta}\geq\alpha$. Since $\beta<\alpha\leq\beth_{\alpha}$ there is $\gamma<\alpha$ such that $\beth_{\gamma}>\beta$. Then $\beth_{\alpha}\geq\beth_{{\gamma+1}}=2^{{\beth_{\gamma}}}>2^{\beta}\geq\alpha$. So $\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)\leq\alpha<\beth_{\alpha}$ and $\beth_{\alpha}$ is singular. Finally, if $\alpha$ is a singular cardinal, then again $\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)<\alpha\leq\beth_{\alpha}$ and $\beth_{\alpha}$ is singular.

What about the successor case i.e. $\beth_{{\alpha+1}}$? By Corollary 5.3 from Thomas Jech’s book any $\alpha$, we can show that $\aleph_{{\alpha+1}}$ is a regular cardinal. The Generalized Continuum Hypothesis says that $\forall\alpha,\aleph_{\alpha}=\beth_{\alpha}$. Since it holds in $L$ we can not prove in ZFC that for some $\alpha$, $\beth_{{\alpha+1}}$ is singular.

The generic extension $V[G]\supseteq V$ constructed in exercise 15.15 satisfies GCH and so it’s another way to show that $\beth_{{\alpha+1}}$ can not be proved to be singular for some $\alpha$. However, it provides a better result: by construction, $V[G]\models\beth_{{\alpha+1}}^{V}={(\beth_{{\alpha}}^{V})}^{+}$ and so $V[G]\models[\beth_{{\alpha+1}}^{V}\text{ is a regular cardinal}]$. Since ‘‘regular cardinal’’ is a $\Pi_{1}$ notion we deduce that $\beth_{{\alpha+1}}$ is a regular cardinal in $V$.

Now the question is: is there any ‘‘elementary’’ proof of the fact that $\beth_{{\alpha+1}}$ is regular i.e. without using the forcing method?

--update: of course, I forgot to mention that by König’s theorem, $2^{{\beth_{{\alpha}}}}=\beth_{{\alpha+1}}\geq\operatorname{cf}(\beth_{{\alpha+% 1}})=\operatorname{cf}(2^{{\beth_{{\alpha}}}})\geq{(\beth_{{\alpha}})}^{+}$ so the singularity of $\beth_{{\alpha+1}}$ would imply the failure of the continuum hypothesis for the cardinal $\beth_{\alpha}$ and this is not provable in ZFC.

## Firefox Nightly passes the Acid2 test

Some updates on the MathML Acid Tests... First the patch for bug 717546 landed in Nightly and thus Gecko is now the first layout engine to pass the MathML Acid2 test. Here is a screenshot that should look familiar:

As you know, Google developers forked Webkit and decided to remove from Blink all the code (including MathML) on which they don't plan to work in the short term. As a comparison, here is how the MathML Acid2 test looks like in Chrome Canary:

Next, someone reported that Firefox Mac got more errors in the MathML Acid3 test. I was already aware of some shortcomings anyway and thus took the opportunity to rewrite the tests with a better error tolerance. The changes also fixed some measurement issues with auto resizing on mobile platforms or when the zoom level is not set to the default. I also made the tests for stretchy operators more reliable and as a consequence, Gecko lost two points: the new score is 60/100. I still need to review and describe the tests and hope I won't find more mistakes.

Finally, I also added a MathML Acid1 test. It does not really look like the "classical" Acid1 test and is not "automated", in the sense that a reader must carefully (and in a subjective way) check the basic requirements. But at least it provides a small test in the spirit of CSS Acid 1: all 100%-conformant HTML 5 agents should be able to render these very elementary MathML expressions. Note that the formulas in the MathML Acid1 test are supposed to express mathematical properties of boxes from the CSS Acid1 test.

Thursday, April 4 2013

## Suslin’s Problem

In a previous blog post, I mentioned the classical independence results regarding the Axiom of Choice and the Generalized Continuum Hypothesis. Here, I’m going to talk about a slightly less known problem that is undecidable in ZFC. It is about a characterization of the set of reals $\mathbb{R}$ and its formulation does not involve at all cardinal arithmetics or the axiom of choice, but only properties of ordered sets.

First, the set of rationals $(\mathbb{Q},<)$ is well-known to be countable. It is linearly ordered (for any $x,y\in\mathbb{Q}$ either $x or $y), unbounded (for any $x\in\mathbb{Q}$ there is $y_{1},y_{2}\in\mathbb{Q}$ such that $x and $y_{2}) and dense (for any $x,y\in\mathbb{Q}$ if $x we can find $z\in\mathbb{Q}$ such that $x). It turns out that $\mathbb{Q}$ can be characterized by these order properties:

###### Lemma 0.1.

Let $(P,<)$ be a countable, dense, unbounded linearly ordered set. Then $(P,<)$ is isomorphic to $(\mathbb{Q},<)$.

###### Proof.

Let $P=\{p_{n}:n\in\mathbb{N}\}$ and $\mathbb{Q}=\{q_{n}:n\in\mathbb{N}\}$ be enumerations of $P$ and $\mathbb{Q}$. We shall construct by induction a sequence $f_{0}\subseteq f_{1}\subseteq f_{2}\subseteq...$ of functions such that for all $n\in\mathbb{N}$, $\operatorname{dom}(f_{n})\supseteq\{p_{i}:i, $\operatorname{ran}(f_{n})\supseteq\{q_{i}:i and $\forall x,y\in\operatorname{dom}(f_{n}),x. Then $f=\bigcup_{{n\in\mathbb{N}}}f_{n}$ is a function: if $(x,y),(x,z)\in f$ then there is $n$ large enough such that $(x,y),(x,z)\in f_{n}$ and since $f_{n}$ is a function $y=z$. Moreover, $\operatorname{dom}(f)=\bigcup_{{n\in\mathbb{N}}}\operatorname{dom}(f_{n})=P$ and $\operatorname{ran}(f)=\bigcup_{{n\in\mathbb{N}}}\operatorname{ran}(f_{n})=% \mathbb{Q}$. Finally, for any $x,y\in P$ there is $n$ large enough such that $x,y\in\operatorname{dom}(f_{n})$ and so $x. Hence $f$ is an isomorphism between $(P,<)$ and $(\mathbb{Q},<)$.

Thus let $f_{0}=\emptyset$. If $f_{n}$ is defined, we construct $f_{{n+1}}\supseteq f_{n}$ as follows. Suppose $p_{n}\notin\operatorname{dom}(f_{n})$. If $\forall ip_{i}$ then because $\mathbb{Q}$ is unbounded we can consider the least $n_{0}$ such that $\forall i and set $f_{{n+1}}(p_{n})=q_{{n_{0}}}$. Similarly if $\forall i. Otherwise, let $i_{1},i_{2} such that $p_{{i_{1}}} with $p_{{i_{1}}},p_{{i_{2}}}$ respectively the largest and smallest possible. Because $\mathbb{Q}$ is dense we can consider the least $n_{0}$ such that $f_{{n}}(p_{{i_{1}}}) and again set $f_{{n+1}}(p_{n})=q_{{n_{0}}}$. Similarly, if $n\neq n_{0}$ we use the fact that $P$ is unbounded and dense to find $m_{0}\geq n+1$ that allows to define $f_{{n+1}}(p_{{m_{0}}})=q_{n}$ and ensures $f_{{n+1}}$ is order-preserving.

We now notice that $\mathbb{R}$ is linearly ordered, unbounded, dense and has the least upper-bound property (that is any nonempty bounded subset of $\mathbb{R}$ has a least upper-bound). Moreover, the subset $\mathbb{Q}$ is countable and dense in $\mathbb{R}$ (that is for any $x,y\in\mathbb{R}$ such that $x we can find $z\in\mathbb{Q}$ such that $x). Using the previous lemma, we deduce again that these order properties give a characterization of the set of reals:

###### Theorem 0.1.

Let $(R,<)$ be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that $R$ has a dense countable subset $P$. Then $(R,<)$ is isomorphic to $(\mathbb{R},<)$.

###### Proof.

$P$ is countable by assumption and since $P\subseteq R$ it is also linearly ordered. If $x,y\in P\subseteq R$ and $x then by density of $P$ in $R$ there is $z\in P$ such that $x. So $P$ is actually dense. Similarly, if $x\in P\subseteq R$ then since $R$ is unbounded there is $y_{1},y_{2}\in R$ such that $y_{2} and again by density of $P$ in $R$ we can find $z_{1},z_{2}\in P$ such that $y_{2}. So $P$ is unbounded. By the previous lemma, there is an isomorphism of ordered sets $f:P\rightarrow\mathbb{Q}$.

We define for all $x\in R$, $f_{\star}(x)=\sup_{{y\in P;y. Because $P$ is dense in $R$ and $\mathbb{R}$ has the least upper bound property this is well-defined. If $x\in P$ then for all $y such that $y\in P$ we have $f(y) and so $f_{\star}(x)\leq f(x)$. If $f_{\star}(x) we could find (by density of $\mathbb{Q}$ in $\mathbb{R}$) an element $q\in\mathbb{Q}$ such that $f_{\star}(x). For $p=f^{{-1}}(q)$ we get $p and so $q=f(p)\leq f_{\star}(x)$. A contradiction. So ${f_{\star}}_{{|P}}=f$.

Let $x,y\in R$ such that $x. Because $f$ is increasing we get $f_{\star}(x)\leq f_{\star}(y)$. By density of $P$ in $R$ we can find $p_{1},p_{2}\in P$ such that $x. Again, we get $f_{\star}(x)\leq f_{\star}(p_{1})=p_{1}$ and $p_{2}=f_{\star}(p_{2})\leq f_{\star}(y)$. Hence we actually have $f_{\star}(x). In particular, $f_{\star}$ is one-to-one.

We shall prove that $f_{\star}$ is surjective. Of course $f_{\star}(P)=f(P)=\mathbb{Q}$ so let’s consider $r\in\mathbb{R}\setminus\mathbb{Q}$. Define $x=\sup_{{q. This is well-defined because $\mathbb{Q}$ is dense in $\mathbb{R}$ and $R$ has the the least upper bound property. Then for all $q such that $q\in\mathbb{Q}$ we have $f^{{-1}}(q)\leq x$ by definition. By density of $\mathbb{Q}$ in $\mathbb{R}$ we can actually find $q^{{\prime}}\in\mathbb{Q}$ such that $q and so $f^{{-1}}(q). We have $x>f^{{-1}}(q)\in P$ and so $f_{\star}(x)\geq f(f^{{-1}}(q))=q$. Hence $f_{\star}(x)\geq r$. Suppose that $r and consider (by density of $\mathbb{Q}$ in $\mathbb{R}$) some $q\in\mathbb{Q}$ such that $r and let $p=f^{{-1}}(q)$. If $p then there is $q^{{\prime}}\in\mathbb{Q}$, $q^{{\prime}}, such that $p\leq f^{{-1}}(q^{{\prime}})$. Then $r a contradiction. If instead $p\geq x$ then $f_{{\star}}(x)\leq f_{{\star}}(p)=q which is again a contradiction.

Finally, let $x,y\in R$ such that $f_{\star}(x). Because $R$ is totally ordered either $x or $y. But the latter is impossible since we saw above that it implied $f_{\star}(y). Hence $f_{\star}$ is an isomorphism between $(R,<)$ and $(\mathbb{R},<)$.

Now consider a totally ordered set $(R,<)$. For any $a,b$ we define the open interval $(a,b)=\{x\in R:a. Suppose $P=\{p_{n}:n\in\mathbb{N}\}$ is a dense subset of $R$. If ${\left((a_{i},b_{i})\right)}_{{i\in I}}$ is a family of pairwise disjoint open intervals then we can associate to any $(a_{i},b_{i})$ the least $n_{i}\in\mathbb{N}$ such that $p_{{n_{i}}}\in(a_{i},b_{i})$ (by density of $P$ in $R$). Since the family is disjoint the function $i\mapsto n_{i}$ obtained is one-to-one and so the family is at most countable. One naturally wonders what happens if we replace in theorem 0.1 the existence of a countable dense subset by this weaker property on open intervals:

###### Problem 0.1 (Suslin’s Problem).

Let $(R,<)$ be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that any family of disjoint open intervals in $R$ is at most countable. Is $(R,<)$ isomorphic to $(\mathbb{R},<)$?

We have seen how this problem arises from a natural generalization of a characterization of $\mathbb{R}$. We note that we did not use the Axiom of Choice in the above analysis and that the problem can be expressed using only definitions on ordered sets. However, in order to answer Suslin’s Problem we will need to introduce more concepts. We will assume familiarity with basic notions of Set Theory like ordinals, cardinals or the Axiom of Choice. The first five chapters of Thomas Jech’s book ‘‘Set Theory’’ should be enough. In addition, we will rely on the axiom $\mathrm{MA}_{{\aleph_{1}}}$ and on the Diamond Principle $\Diamond$, that we define here:

###### Definition 0.1 (Martin’s Axiom $\aleph_{1}$, Diamond Principle).

$\mathrm{MA}_{{\aleph_{1}}}$ and $\Diamond$ are defined as follows:

• Let $(P,<)$ be a partially ordered set. Two elements $x,y$ are compatible if there is $z$ such that $z\leq x$ and $z\leq y$. Note that comparable implies compatible.

• $D$ is dense in $P$ if for any $p\in P$ there is $d\in D$ such that $d\leq p$.

• $G\subseteq P$ is a filter if:

• $G\neq\emptyset$

• For any $p,q\in P$ such that $p\leq q$ and $p\in G$ we have $q\in G$

• Any $p,q\in G$ there is $r\in G$ such that $r\leq p,q$.

• $\mathrm{MA}_{{\aleph_{1}}}$: Let $(P,<)$ be a partially ordered set such that any subset of paiwise incompatible elements of $P$ is at most countable. Then for any family of at most $\aleph_{1}$ dense subsets there is a filter $G\subseteq P$ that has a nonempty intersection with each element of this family.

• A set $C\subseteq\omega_{1}$ is closed unbounded if

• It is unbounded in the sense that for any $\alpha<\omega_{1}$ there is $\beta\in C$ such that $\alpha<\beta$

• It is closed for the order topology, or equivalently if for any $\gamma<\omega_{1}$ and any $\gamma$-sequence $\alpha_{0}<\alpha_{1}<...<\alpha_{\xi}<...$ of elements of $C$, $\lim_{{\xi\rightarrow\gamma}}\alpha_{\xi}$ is in $C$.

• A set $S\subseteq\omega_{1}$ is stationary if for any $C$ closed unbounded, $S\cap C\neq\emptyset$.

• $\Diamond$: There is an $\omega_{1}$-sequence of sets $S_{\alpha}\subseteq\alpha$ such that for every $X\subseteq\omega_{1}$ the set $\{\alpha<\omega_{1}:X\cap\alpha=S_{\alpha}\}$ is stationary.

First we show that if $\mathrm{MA}_{{\aleph_{1}}}$ holds, then we get a positive answer to Suslin’s problem:

###### Theorem 0.2.

Assume Martin’s axiom $\mathrm{MA}_{{\aleph_{1}}}$ holds. Let $(R,<)$ be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that any disjoint family of open intervals in $R$ is at most countable. Then $(R,<)$ is isomorphic to $(\mathbb{R},<)$.

###### Proof.

Suppose $(R,<)$ is not isomorphic to $(\mathbb{R},<)$ and in particular does not have any countable dense subset (otherwise we could apply theorem 0.1). We define closed intervals $I_{\alpha}\subseteq R$ by induction on $\alpha<\omega_{1}$. If $I_{\beta}=[a_{\beta},b_{\beta}]$ is defined for all $\beta<\alpha$ then the set $C=\{a_{\beta}:\beta<\alpha\}\cup\{b_{\beta}:\beta<\alpha\}$ is countable and thus is not dense in $R$. Then there is $a_{\alpha} such that $I_{\alpha}=[a_{\alpha},b_{\alpha}]$ is disjoint from $C$. We define the set $S=\{I_{\alpha},\alpha<\omega_{1}\}$. Clearly, $|S|=\aleph_{1}$ and $(S,\subsetneq)$ is partially ordered. We note that if $\beta<\alpha<\omega_{1}$ then by construction $a_{\beta},b_{\beta}\notin I_{\alpha}$ and so either $I_{\alpha}\cap I_{\beta}=\emptyset$ or $I_{\alpha}\subsetneq I_{\beta}$. In particular, comparable is the same as compatible in $S$ and any family of pairwise incomparable/incompatible elements of $S$ is a family of pairwise disjoint intervals of $R$ so at most countable.

Let $\alpha<\omega_{1}$ and define $P_{{I_{\alpha}}}=\{I\in S:I\supsetneq I_{\alpha}\}$. Let $X\subseteq P_{{I_{\alpha}}}$ nonempty. Let $\beta$ the least ordinal such that $I_{\beta}\in X$. If $I_{\gamma}\in X$ then $\beta\leq\gamma$ and $I_{\gamma}\cap I_{\beta}\supseteq I_{\alpha}\neq\emptyset$. Hence by the previous remark $I_{\beta}\supseteq I_{\gamma}$. So $P_{{I_{\alpha}}}$ is well-ordered by $\supseteq$ and we define $o(I_{\alpha})$ the order-type of $P_{{I_{\alpha}}}$. We note that the set $P_{{I_{\alpha}}}$ can be enumerated by $I_{{\alpha_{1}}}\supsetneq I_{{\alpha_{2}}}\supsetneq...\supsetneq I_{\alpha}$ for some $\alpha_{\xi}\leq\alpha$ and so $o(I_{\alpha})<\omega_{1}$. Moreover for any $\alpha,\beta<\omega$, if $I_{{\alpha}}\supsetneq I_{{\beta}}$ then $P_{{I_{\alpha}}}$ is an initial segment of $P_{{I_{\beta}}}$ and so $o(I_{\alpha}). Hence for each $\alpha<\omega_{1}$ the set $L_{\alpha}=\{I\in S:o(I)=\alpha\}$ has pairwise incomparable elements and so is at most countable.

For any $I\in S$, define $S_{I}=\{J\in S:J\subseteq I\}$ and let $T=\{I\in S:|S_{I}|=\aleph_{1}\}$. Let $\alpha<\omega_{1}$ and suppose that $L_{\alpha}\cap T=\emptyset$. Then $S=\bigcup_{{\beta<\alpha}}L_{\beta}\cup\bigcup_{{I\in L_{\alpha}}}S_{I}$ and since the $L_{\beta}$ are at most countable for $\beta<\omega_{1}$ and the $S_{I}$ are at most countable for $I\in L_{\alpha}$ we would have $S$ at most countable, a contradiction. So for each $\alpha<\omega_{1}$, there is $I\in T\cap L_{\alpha}$ and in particular $|T|=\aleph_{1}$. We note that if $I\in T$ and $J\supseteq I$ then $S_{I}\subseteq S_{J}$ and so $J\in T$. In particular, $P_{I}=\{J\in T:J\supsetneq I\}$ and thus without loss of generality we may assume that $S=T$.

For any $\alpha<\omega_{1}$ let $D_{\alpha}=\{I\in D_{\alpha}:o(I)>\alpha\}$. For any $I\in S$, $|S_{I}|=\aleph_{1}$ and $S_{I}=\left(\bigcup_{{\beta\leq\alpha}}S_{I}\cap L_{\beta}\right)\cup S_{I}% \cap D_{\alpha}$. The first term is at most countable and so the second is uncountable and a fortiori nonempty. So $D_{\alpha}$ is a dense subset of $S$.

Using $\mathrm{MA}_{{\aleph_{1}}}$, we find $G\subseteq S$ a filter that intersects each $D_{\alpha}$. By definition, elements of a filter are pairwise compatible and so pairwise comparable. Let us construct by induction on $\alpha<\omega_{1}$, some sets $J_{\alpha}\in G$. If $J_{\beta}$ is constructed for any $\beta<\alpha$ then $\gamma=\sup_{{\beta<\alpha}}o(J_{\beta})<\omega_{1}$ and we can pick $J_{\alpha}\in G\cap D_{\gamma}$. We obtain a decreasing $\omega_{1}$-sequence of intervals $J_{0}\supsetneq J_{1}\supsetneq...\supsetneq J_{\alpha}\supsetneq...$. If $J_{\alpha}=[x_{\alpha},y_{\alpha}]$ then this gives an increasing sequence $x_{0}. The sets $(x_{\alpha},x_{{\alpha+1}})$ form an uncountable family of disjoint open intervals. A contradiction.

Finally, we show that the $\Diamond$ principle provides a negative answer to Suslin’s problem:

###### Theorem 0.3.

Assume the $\Diamond$ principle holds. Then there is a linearly ordered set $(R,<)$ not isomorphic to $(\mathbb{R},<)$, unbounded, dense, that has the least upper-bound property and such that any family of disjoint open intervals is at most countable.

###### Proof.

Let ${(S_{\alpha})}_{{\alpha<\omega_{1}}}$ be a $\Diamond$-sequence. We first construct a partial ordering $\prec$ of $T=\omega_{1}$. We define for all $1\leq\alpha<\omega_{1}$ an ordering $(T_{\alpha},\prec)$ on initial segments $T_{\alpha}\subseteq\omega_{1}$ and obtain the ordering $\prec$ on $\omega_{1}=T=\bigcup_{{\alpha<\omega_{1}}}T_{\alpha}$.

Each $(T_{\alpha},\prec)$ will be a tree i.e. for any $x$ in the tree the set $P_{x}=\{y:y\prec x\}$ is well-ordered. As in the proof of 0.2 we can define $o(x)$ the order-type of $P_{x}$. The level $\alpha$ is the set of elements such that $o(x)=\alpha$. The height of a tree is defined as the supremium of the $o(x)+1$. In a tree, a branch is a maximal linearly ordered subset and an antichain a subset of pairwise incomparable elements. A branch is also well-ordered and so we can define its length as its order-type. $T_{\alpha}$ is constructed such that its height is $\alpha$ and for each $x\in T_{\alpha}$ there is some $y\succ x$ at each higher level less than $\alpha$.

We let $T_{1}=\{0\}$. If $\alpha$ is a limit ordinal then $(T_{\alpha},\prec)$ is the union of $(T_{\beta},\prec)$ for $\beta<\alpha$. If $\alpha=\beta+1$ is a successor ordinal, then the highest level of $T_{\alpha}$ is $L_{\beta}=\{x\in T_{\alpha}:o(x)=\beta\}$. $T_{{\alpha+1}}$ is obtained by adding $\aleph_{0}$ immediate successors to each element of $L_{\beta}$. These successors are taken from $\omega_{1}$ in a way that $T_{{\alpha+1}}$ is an initial segment of $\omega_{1}$.

Let $\alpha$ is a limit ordinal. Let $A=S_{\alpha}$ if it is a maximal antichain in $(T_{\alpha},\prec)$ and take $A$ an arbitrary maximal antichain of $T_{\alpha}$ otherwise. Then for each $t\in T_{\alpha}$ there is $a\in A$ such that either $a\prec t$ or $t\prec a$. Let $b_{t}$ be a branch that contains $a,t$. We construct $(T_{{\alpha+1}},\prec)$ by adding for each branch $b_{t}$ some $x_{{b_{t}}}$ that is greater than all the elements of $b_{t}$. We can choose $b_{t}$ in way that it contains an element of each level less than $\alpha$ and so $o(x_{{b_{t}}})=\alpha$ and the height of $T_{{\alpha+1}}$ is $\alpha+1$. We note that each $t\in T_{{\alpha+1}}$ is either in $T_{\alpha}$ (so comparable with some element of $A$) or greater than (a fortiori comparable with) one element of $A$. So $A$ is an antichain in $(T_{{\alpha+1}},\prec)$.

Now consider a maximal antichain $A\subseteq T=\omega_{1}$ and $C$ the set of ordinals $\alpha<\omega_{1}$ such that ‘‘$A\cap T_{\alpha}$ is a maximal antichain in $T_{\alpha}$ and $T_{\alpha}=\alpha$’’. Let $\alpha_{0}<\alpha_{1}<...<\alpha_{\xi}<...$ ($\xi<\gamma<\omega_{1}$) be a sequence of elements in $C$ and consider the limit ordinal $\lambda=\lim_{{\xi<\gamma}}\alpha_{\xi}$. By construction, $T_{\lambda}=\bigcup_{{\alpha<\lambda}}T_{\alpha}=\bigcup_{{\xi<\gamma}}T_{{% \alpha_{\xi}}}=\bigcup_{{\xi<\gamma}}\alpha_{\xi}=\lambda$. If $x\in T_{\lambda}$, there is $\xi<\gamma$ such that $x\in T_{{\alpha_{\xi}}}$ and so $x$ is comparable with some $y\in A\cap T_{{\alpha_{\xi}}}\subseteq A\cap T_{\lambda}$. So $A\cap T_{\lambda}$ is a maximal antichain in $T_{\lambda}$. Finally $\lambda\in C$ and $C$ is closed.

We note that $T_{1}=\{0\}\geq 1$. If $T_{\alpha}\geq\alpha$ then $T_{{\alpha+1}}$ is obtained by adding at least one element at the end of the initial segment $T_{\alpha}$ and so $T_{{\alpha+1}}\geq\alpha+1$. Finally if $\lambda>0$ is limit and $T_{\alpha}\geq\alpha$ for each $\alpha<\lambda$ then $T_{\lambda}=\bigcup_{{\alpha<\lambda}}T_{\alpha}\geq\sup_{{\alpha<\lambda}}% \alpha=\lambda$. Moreover by definition, each $T_{\alpha}$ is at most countable. Let’s come back to the closed set $C$ above. Let $\alpha_{0}<\omega_{1}$ be arbitrary. For each $n<\omega$, we let $\alpha_{{2n+1}}$ be the limit of the sequence $\alpha_{0}\leq T_{{\alpha_{0}}}\leq T_{{T_{{\alpha_{0}}}}}\leq T_{{T_{{T_{{% \alpha_{0}}}}}}}...$. By definition, $T_{{\alpha_{{2n+1}}}}=\bigcup_{{\xi<\alpha_{{2n+1}}}}T_{\xi}=\alpha_{0}\cup T_% {{\alpha_{0}}}\cup T_{{T_{{\alpha_{0}}}}}...=\alpha_{{2n+1}}$. Because $A$ is a maximal antichain in $T$, for each $x\in T_{{\alpha_{{2n+1}}}}$ we can find some $\alpha_{x}\geq\alpha_{{2n+1}}$ and $a_{x}\in A_{{\alpha_{x}}}$ that is comparable with $x$. Because $T_{{\alpha_{{2n+1}}}}$ is countable we can define $\alpha_{{2n+2}}=\sup_{{x\in T_{{\alpha_{{2n+1}}}}}}\alpha_{x}<\omega_{1}$. Then any $x\in T_{{\alpha_{{2n+1}}}}$ is comparable with some element of $a_{x}\in A\cap T_{{\alpha_{{2n+2}}}}$. Let $\lambda=\lim_{{n<\omega}}\alpha_{n}$. With the same method as to prove the fact that $C$ is closed, the equality $\lambda=\lim_{{n<\omega}}\alpha_{{2n+1}}$ shows that $T_{\lambda}=\lambda$ while the equality $\lambda=\lim_{{n<\omega}}\alpha_{{2n+2}}$ shows that $A\cap T_{\lambda}$ is a maximal antichain in $T_{\lambda}$. So $\lambda\in C$ and $C$ is closed unbounded.

Using the Diamond principle, $\{\alpha<\omega_{1}:A\cap\alpha=S_{\alpha}\}\cap C\neq\emptyset$. If $\alpha$ is in the intersection, then $S_{\alpha}=A\cap T_{\alpha}$ is a maximal antichain in $T_{\alpha}$. By construction, it is also a maximal antichain in $T_{{\alpha+1}}$. Each element of $a\in A\cap T_{{\alpha+1}}$ is at level $o(a)\leq\alpha$. Any $t\in T_{{\alpha+1}}$ is comparable with some element of $A\cap T_{{\alpha+1}}$. Moreover, by contruction any $t^{{\prime}}\in T\setminus T_{{\alpha+1}}$ has some predecessor $t\in T_{{\alpha+1}}$ at level $\alpha$ and there is $a\in A\cap T_{{\alpha+1}}$ that is comparable with $t$. Necessarily, $o(a) and so $a\prec t\preceq t^{{\prime}}$. Thus $A\cap T_{{\alpha+1}}$ is maximal in $T$ and $A=A\cap T_{{\alpha+1}}\subseteq T_{{\alpha+1}}$ is at most countable.

Let $B$ be a branch in $T$. It is clear that $B$ is nonempty. Actually it is infinite: otherwise there is some limit ordinal $\alpha>0$ such that $B\subseteq T_{\alpha}$ and by construction we can find some $y\succ\max B$ contradicting the maximality of $B$. By construction, each $x\in T$ has infinitely many successors at the next level and so these successors are pairwise incomparable. Hence if $x\in B$ then we can pick one $z_{x}\notin B$ among these succcessors. Let $x\prec y$ be two elements of $B$. Then $o(z_{x})=o(x)+1>o(y)+1=o(z_{y})$ so $z_{x}\preceq z_{y}$ is impossible. Suppose $z_{y}\prec z_{x}$. We also have $x\prec z_{x}$ by definition. If $z_{y}\preceq x$ then we would have $z_{y}\in B$ because $B$ is a branch. If $x\prec z_{y}$ we would get $o(x). Hence $z_{x},z_{y}$ are incomparable (in particular distinct) and the set $\{z_{x}:x\in B\}$ is an antichain in $T$ and so $B$ is countable.

Finally, we define $S$ the set of all branches of $T$. By construction, each $x\in T$ has countably many immediate successors and we order them as $\mathbb{Q}$. Let $B_{1},B_{2}$ be two branches and $\alpha$ the least level where they differ. The level 0 is $T_{1}=\{0\}$ so $\alpha>0$. If $\alpha$ is limit then the restriction of the branches $B_{1},B_{2}$ to $T_{\alpha}$ is the same branch $b$ and $T_{{\alpha+1}}$ has been contructed in a way that there is only one possible element at level $\alpha$ to extend this branch and this is a contradiction. So $\alpha$ is actually a successor ordinal $\beta+1$. Hence if $B_{1}(\alpha)\in B_{1}$ and $B_{2}(\alpha)\in B_{2}$ are the immediate successors of the point in $B_{1}\cap B_{2}$ at level $\beta$, we order $B_{1},B_{2}$ according to whether $B_{1}(\alpha) or $B_{1}(\alpha)>B_{2}(\alpha)$, using the $\mathbb{Q}$-isomorphic order we just defined. Clearly, this gives a linear ordering $<_{S}$. It is also unbounded: for any $B\in S$, if $B(1)\in B$ is the element at level 1 pick $x$ greater (or smaller) than for the $\mathbb{Q}$-isomorphic order on successors of $B(0)=0$ and consider a branch extending $0\prec x$.

Now consider two branches $B_{1}<_{S}B_{2}$. Let $\alpha=\beta+1$ be as above. We can find $x$ an immediate successor of $B_{1}(\beta)$ such that $B_{1}(\alpha) for the $\mathbb{Q}$-isomorphic order on immediate successors of $B_{1}(\beta)$. Let $I_{x}=\{B\in S:x\in B\}$. Any $B\in I_{x}$ contains $\{y\in T:y\prec x\}=\{y\in T:y\prec B_{1}(\beta)\}=\{y\in T:y\prec B_{2}(\beta)\}$. Moreover $x=B(\alpha)$ and so $B_{1}. $I_{x}$ is nonempty (we can extend $\{y\in T:y\preceq x\}$ to a maximal branch) and so $S$ is dense. If $I_{x}\cap I_{y}=\emptyset$ then $x,y$ are incomparable. So from any collection of disjoint open intervals ${(B_{{1i}},B_{{2i}})}_{{i\in I}}$ we get an antichain $\{x_{i}:i\in I\}$ and so $I$ is at most countable.

Let $C$ be a countable set of branches in $T$. Since these branches are countable, we can find $\alpha<\omega_{1}$ larger than the length of any branches in $C$. If $x\in T$ is at level greater than $\alpha$ then for all $B\in C$, $x\notin B$ so $B\notin I_{x}$. Finally $C\cap I_{x}=\emptyset$ and $C$ is not dense.

Now let $R$ be the Dedekind-MacNeille completion of $S$. It is unbounded, linearly ordered, has the least upper-bound property and $S$ is dense in $R$. Using the fact that $S$ is dense in $R$ we deduce that $R$ is dense. Similarly, if ${(a_{i},b_{i})}_{{i\in I}}$ is any collection of disjoint open intervals in $R$ we can find $c_{i},d_{i}\in S$ such that $a_{i}. Then ${(c_{i},d_{i})}_{{i\in I}}$ is a collection of disjoint open intervals in $S$ and so $I$ is at most countable.

Finally, it remains to prove that $R$ is not isomorphic to $\mathbb{R}$ and it suffices to show that $R$ does not have any countable dense subset $C$. If $C$ is a countable subset of $R$, then for any elements $a in $C$ we pick $c\in S$ such that $a. This gives a countable subset $C^{{\prime}}$ of $S$. If $a are elements of $S$, we can find $c,d\in C$ such that $a and so $e\in C^{{\prime}}$ such that $a. Thus $C^{{\prime}}$ would be a countable dense subset of $S$. A contradiction.

The $\Diamond$ principle holds in the model $L$ of constructible sets. Using iterated forcing, we can construct a model of ZFC in which $\mathrm{MA}_{{\aleph_{1}}}$ holds. Using theorems 0.2 and 0.3 we deduce that both the positive and negative answers to Suslin’s problem are consistent with ZFC and so Suslin’s problem is undecidable in ZFC. It’s remarkable that a problem that only involves linearly ordered set can be solved using sophisticated methods from Set Theory. The above proofs follow chapters 4, 9, 15 and 16 from Thomas Jech’s book ‘‘Set Theory’’. In particular:

• Lemma 0.1 and theorem 0.1 are based on the sketch given in theorem 4.3.

• Theorem 0.2 is based on the proofs of theorem 16.16 and lemma 9.14 (a).

• Theorem 0.3 is based on the proofs of lemma 15.24, lemma 15.25, theorem 15.26, lemma 15.27 and lemma 9.14 (b).

• Theorem 0.2 implicitely uses theorem 4.4 about the Dedekind-MacNeille completion of a dense unbounded linearly ordered.

• In addition, theorem 0.2 also contains the proof of lemma 8.2 (the intersection of two closed unbounded sets is closed unbounded) the solutions to exercise 2.7 (any normal sequence has arbitrarily large fixed points) and exercise 9.7 (if all the antichains of a normal $\omega_{1}$-tree are at most countable then so are its branches).

• Finally, $\Diamond$ and $\mathrm{MA}_{{\aleph_{1}}}$ are proved to be consistent with ZFC in theorems 13.21 and 16.13.

Wednesday, March 20 2013

## Exercises in Set Theory: Classical Independence Results

Here are new solutions to exercises from Thomas Jech’s book ‘‘Set Theory’’:

Doing the exercises from these chapters gave me the opportunity to come back to the ‘‘classical’’ results about the independence of the Axiom of Choice and (Generalized) Continuum Hypothesis by Kurt Gödel and Paul Cohen. It’s funny to note that it’s easier to prove that AC holds in $L$ (essentially, the definition by ordinal induction provides the well-ordering of the class of contructible sets) than to prove that GCH holds in $L$ (you rely on AC in $L$ and on the technical condensation lemma). Actually, I believe Gödel found his proof for AC one or two years after the one for GCH. On the other hand, it is easy to make GCH fails (just add $\aleph_{2}$ Cohen reals by Forcing) but more difficult to make AC fails (e.g. AC is preserved by Forcing). This can be interpreted as AC being more ‘‘natural’’ than GCH.

After reading the chapters again and now I analyzed in details the claims, I’m now convinced about the correctness of the proof. There are only two points I didn’t verify precisely about the Forcing method (namely that all axioms of predicate calculus and rules of inference are compatible with the Forcing method ; that the Forcing/Generic Model theorems can be transported from the Boolean Algebra case to the general case) but these do not seem too difficult. Here are some notes about claims that were not obvious to me at the first reading. As usual, I hope they might be useful to the readers of that blog:

1. In the first page of chapter 13, it is claimed that for any set $M$, $M\in\mathrm{def}(M)$ and $M\subseteq\mathrm{def}(M)\subseteq\operatorname{\mathcal{P}}(M)$. The first statement is always true because $M=\{x\in M:(M,\in)\models x=x\}\in\mathrm{def}(M)$ and ${(x=x)}^{{(M,\in)}}$ is $x=x$ by definition. However, the second statement can only be true if $M$ is transitive (since that implies $M\subseteq\operatorname{\mathcal{P}}(M)$). Indeed, if $M$ is transitive then for all $a\in M$ we have $a\subseteq M$ and since $x\in a$ is $\Delta_{0}$ we get $a=\{x\in M:(M,\in)\models x\in a\}\in\mathrm{def}(M)$. If moreover we consider $x\in X\in\mathrm{def}(M)$ then $x\in X\subseteq M$ so $x\in M\subseteq\mathrm{def}(M)$ and $\mathrm{def}(M)$ is also transitive. Hence the transitivity of the $L_{\alpha}$ can still be shown by ordinal induction.

2. The proof of lemma 13.7 can not be done exactly by induction on the complexity of $G$, as suggested. For example to prove (ii) for $G=G_{2}=\cdot\times\cdot$, we would consider $\exists u\in F(...)\times H(...)\varphi(u)\Leftrightarrow\exists a\in F(...),% \exists b\in H(...),\varphi((a,b))$ and would like to say that $\varphi((a,b))$ is $\Delta_{0}$. Nevertheless, we can not deduce that from the induction hypothesis. Hence the right thing to do is to prove the lemma for $G_{1}=\{\cdot,\cdot\}$ first and deduce the lemma for $G=(\cdot,\cdot)$ (and $G^{{\prime}}=(\cdot,\cdot,\cdot)$). Then we can proceed by induction.

3. In the proof of theorem 13.18, it is mentioned that the assumption

1. $x<_{\alpha}y$ implies $x<_{\beta}y$

2. $x\in L_{\alpha}$ and $y\in L_{\beta}\setminus L_{\alpha}$ implies $x<_{\beta}y$

implies that if $x\in y\in L_{\alpha}$ then $x<_{\alpha}y$. To show that, we consider $\beta\leq\alpha$ the least ordinal such that $y\in L_{\beta}$. In particular, $\beta$ is not limit ($L_{0}=\emptyset$ and if $y\in L_{\beta}$ for some limit $\beta>0$ then there is $\gamma<\beta$ such that $y\in L_{\gamma}$) and we can write it $\beta=\gamma+1$. We have $y\in L_{\beta}=L_{{\gamma+1}}$ so there is a formula $\varphi$ and elements $a_{1},...,a_{n}\in L_{\gamma}$ such that $x\in y=\{z\in L_{\gamma}:(L_{\gamma},\in)\models\varphi(z,a_{1},...,a_{n})\}$. Hence $x\in L_{\gamma}$. Moreover by minimality of $\beta$, $y\in L_{\beta}\setminus L_{\gamma}$ so by (ii) we have $x<_{\beta}y$ and by (i) $x<_{\alpha}y$.

4. In lemma 14.18, we have expressions that seem ill-defined for example $a_{u}(t)$ where $t\notin\operatorname{dom}(a_{u})$. This happens in other places, like lemma 14.17 or definition 14.27. The trick is to understand that the functions are extended by 0. Indeed, for any $x,y\in V^{B}$ if $x\subseteq y$ and $\forall t\in\operatorname{dom}(y)\setminus\operatorname{dom}(x),y(t)=0$ then

 $\displaystyle\|y\subseteq x\|$ $\displaystyle=\prod_{{t\in\operatorname{dom}(y)}}\left(-y(t)+{\|t\in x\|}\right)$ $\displaystyle=\prod_{{t\in\operatorname{dom}(x)}}\left(-x(t)+{\|t\in x\|}\right)$ $\displaystyle=\|x\subseteq x\|=1$

and similarly we get $\|x=y\|=1$. Then we can use the inequality page 207 ($\|\varphi(x)\|=\|x=y\|\cdot\|\varphi(x)\|\leq\|\varphi(y)\|=\|x=y\|\cdot\|% \varphi(y)\|\leq\|\varphi(x)\|$) to replace $x$ by its extension $y$.

5. In lemma 14.23, the inequality

 $\|x\text{ is an ordinal}\|\leq\|x\in\check{\alpha}\|+\|x=\check{\alpha}\|+\|% \check{\alpha}\in x\|$

seems obvious but I don’t believe that it can be proved so easily at that point. For example the proof from chapter 2 requires at least the Separation axiom and the $\Delta_{0}$ formulation from chapter 10 is based on the Axiom of Regularity. To solve that issue, it seems to me that the lemma should be moved after the proof that axioms of ZFC are valid in $V^{B}$. This is not an issue since lemma 14.23 is only used much later in lemma 14.31.

6. Many details could be added to the proof of theorem 14.24, but let’s just mention Powerset. For any $u\in V^{B}$, some $u^{{\prime}}\in\operatorname{dom}(Y)$ is defined and satisfies $\|u\subseteq X\|\leq\|u=u^{{\prime}}\|$ (this follows from the definitions, using the Boolean inequality $-a+b\leq-a+b\cdot a$ to conclude). Since moreover $\forall t\in\operatorname{dom}(Y),Y(t)=1$ we get

 $\displaystyle\|u\subseteq X\|\implies\|u\in Y\|$ $\displaystyle\geq-\|u=u^{{\prime}}\|+\sum_{{t\in\operatorname{dom}(Y)}}\left(% \|u=t\|\cdot Y(t)\right)$ $\displaystyle=\sum_{{t\in\operatorname{dom}(Y)}}-\left(\|u\neq t\|\cdot\|u=u^{% {\prime}}\|\right)$ $\displaystyle\geq\sum_{{t\in\operatorname{dom}(Y)}}\|u^{{\prime}}=t\|=1$
7. In theorem 14.34, we prove that any $\kappa$ regular in $V$ remains regular in $V[G]$ (the hard case is really $\kappa$ uncountable and this assumption is implicitely used later to say that $\bigcup_{{\alpha<\lambda}}A_{\alpha}$ is bounded). It may not be obvious why this is enough. First recall that for any ordinal $\alpha$, $\operatorname{cf}^{{V[G]}}(\alpha)\leq\operatorname{cf}^{V}(\alpha)$, ${|\alpha|}^{{V[G]}}\leq{|\alpha|}^{{V}}$, and any (regular) cardinal in $V[G]$ is a (regular) cardinal in $V$. Next we have,

 $\displaystyle\exists\alpha\in\mathrm{Ord},\operatorname{cf}^{{V[G]}}(\alpha)% \leq\operatorname{cf}^{{V}}(\alpha)$ $\displaystyle\implies\exists\alpha\in\mathrm{Ord},\operatorname{cf}^{{V[G]}}(% \operatorname{cf}^{V}(\alpha))\leq\operatorname{cf}^{{V[G]}}(\alpha)<% \operatorname{cf}^{{V}}(\alpha)$ $\displaystyle\implies\exists\beta\textrm{ regular cardinal in }V,\textrm{ not % regular cardinal in }V[G]$ $\displaystyle\implies\exists\beta\in\mathrm{Ord},\operatorname{cf}^{{V[G]}}(% \beta)<\beta=\operatorname{cf}^{V}(\beta)$

that is $\forall\alpha\in\mathrm{Ord},\operatorname{cf}^{{V[G]}}(\alpha)=\operatorname{% cf}^{{V}}(\alpha)$ is equivalent to ‘‘$V$ and $V[G]$ have the same regular cardinals’’. Similarly, we can prove that $\forall\alpha\in\mathrm{Ord},{|\alpha|}^{{V[G]}}={|\alpha|}^{{V}}$ is equivalent to ‘‘$V$ and $V[G]$ have the same cardinals’’.

The proof of theorem 14.34 shows that ‘‘$V$ and $V[G]$ have the same regular cardinals’’ and so to complete the proof, it is enough to show that $\forall\alpha,\operatorname{cf}^{{V[G]}}(\alpha)=\operatorname{cf}^{{V}}(\alpha)$ implies $\forall\alpha,{|\alpha|}^{{V[G]}}={|\alpha|}^{{V}}$. So suppose $\forall\alpha,\operatorname{cf}^{{V[G]}}(\alpha)=\operatorname{cf}^{{V}}(\alpha)$ and assume that there is $\alpha$ such that ${|\alpha|}^{{V[G]}}<{|\alpha|}^{{V}}$. Consider the least such $\alpha$. If $\beta={|\alpha|}^{{V}}$ then $\beta\leq\alpha$ so ${|\beta|}^{{V[G]}}\leq{|\alpha|}^{{V[G]}}<{|\alpha|}^{{V}}=\beta$. By minimality of $\alpha$, $\beta=\alpha$ and so $\alpha$ is a cardinal in $V$. $\alpha$ is actually regular in $V$. Otherwise, suppose $\operatorname{cf}^{V}(\alpha)<\alpha$ and let $\alpha=\bigcup_{{\beta<\operatorname{cf}^{V}(\alpha)}}X_{\beta}$ such that ${|X_{\beta}|}^{V}<{|\alpha|}^{V}$. By minimality of $\alpha$, we have ${|\operatorname{cf}^{V}(\alpha)|}^{{V[G]}}={|\operatorname{cf}^{V}(\alpha)|}^{% {V}}$ and ${|X_{\beta}|}^{{V[G]}}={|X_{\beta}|}^{{V}}$. Then ${|\alpha|}^{{V[G]}}={|\operatorname{cf}^{V}(\alpha)|}^{{V[G]}}\sup_{{\beta<% \operatorname{cf}^{V}(\alpha)}}{|X_{\beta}|}^{{V[G]}}={|\operatorname{cf}^{V}(% \alpha)|}^{{V}}\sup_{{\beta<\operatorname{cf}^{V}(\alpha)}}{|X_{\beta}|}^{{V}}% ={|\alpha|}^{{V}}$, a contradiction. Finally, we get $\operatorname{cf}^{V}(\alpha)=\alpha={|\alpha|}^{V}>{|\alpha|}^{{V[G]}}\geq% \operatorname{cf}^{{V[G]}}(\alpha)$. This is again a contradiction and so $\forall\alpha,{|\alpha|}^{{V[G]}}={|\alpha|}^{{V}}$.

Saturday, March 2 2013

## MathML Acid Tests

There has recently been discussion in the Mozilla community about Opera switch from Presto to Webkit and the need to preserve browser competition and diversity of rendering engines, especially with mobile devices. Some people outside the community seem a bit skeptic about that argument. Perhaps a striking example to convince them is to consider the case of MathML where basically only Gecko has a decent native implementation and the situation in the recent eBooks workshop illustrates that very well: MathML support is very important for some publishers (e.g. for science or education) but the main eBook readers rely exclusively on the Webkit engine and its rudimentary MathML implementation. Unfortunately because there is currently essentially no alternatives on mobile platforms, developers of eBook readers have no other choices than proposing a partial EPUB support or relying on polyfill....

After Google's announce to remove MathML from Chrome 25, someone ironized on twitter about the fact that an Acid test for MathML should be written since that seems to motivate them more than community feedback. I do not think that MathML support is something considered important from the point of view of browser competition but I took this idea and started writing MathML versions of the famous Acid2 and Acid3 tests. The current source of these MathML Acid tests is available on GitHub. Of course, I believe that native MathML implementation is very important and I expect at least that these tests could help the MathML community ; users and implementers.

Here is the result of the MathML Acid2 test with the stable Gecko release. To pass the test we only need to implement negative spacing or at least integrate the patch I submitted when I was still active in Gecko developments (bug 717546).

And here is the score of the MathML Acid 3 test with the stable Gecko release. The failure of test 18 was not supposed to happen but I discovered it when I wrote the test. That will be fixed by James Kitchener's refactoring in bug 827713. Obviously, reaching the score of 100/100 will be much more difficult to achieve by our volunteer developers, but the current score is not too bad compared to other rendering engines...

- page 1 of 11