Blog de Frédéric

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

fredw — Sat, 01 Jun 2013 18:29:00 +0200

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

•

Chapter 16: Iterated Forcing and Martin’s Axiom

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

Exercises in Set Theory: Applications of Forcing

fredw — Fri, 03 May 2013 22:04:00 +0200

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

Chapter 15: Forcing

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

fredw — Fri, 03 May 2013 14:40:00 +0200

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.

Suslin’s Problem

fredw — Thu, 04 Apr 2013 10:09:00 +0200

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<y$ or $y<x$ ), unbounded (for any $x\in\mathbb{Q}$ there is $y_{1},y_{2}\in\mathbb{Q}$ such that $x<y_{1}$ and $y_{2}<x$ ) and dense (for any $x,y\in\mathbb{Q}$ if $x<y$ we can find $z\in\mathbb{Q}$ such that $x<z<y$ ). 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<n\}$ , $\operatorname{ran}(f_{n})\supseteq\{q_{i}:i<n\}$ and $\forall x,y\in\operatorname{dom}(f_{n}),x<y\Leftrightarrow f(x)<f(y)$ . 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<y\Leftrightarrow f_{n}(x)<f_{n}(y)\Leftrightarrow f(x)<f(y)$ . 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 i<n,p_{n}>p_{i}$ then because $\mathbb{Q}$ is unbounded we can consider the least $n_{0}$ such that $\forall i<n,f(p_{i})<q_{{n_{0}}}$ and set $f_{{n+1}}(p_{n})=q_{{n_{0}}}$ . Similarly if $\forall i<n,p_{n}<p_{i}$ . Otherwise, let $i_{1},i_{2}<n$ such that $p_{{i_{1}}}<p_{n}<p_{{i_{2}}}$ 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}}})<q_{{n_{0}}}<f_{{n}}(p_{{i_{2}}})$ 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<y$ we can find $z\in\mathbb{Q}$ such that $x<z<y$ ). 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<y$ then by density of $P$ in $R$ there is $z\in P$ such that $x<z<y$ . 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}<x<y_{2}$ and again by density of $P$ in $R$ we can find $z_{1},z_{2}\in P$ such that $y_{2}<z_{2}<x<z_{1}<y_{1}$ . 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<x}}f(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<x$ such that $y\in P$ we have $f(y)<f(x)$ and so $f_{\star}(x)\leq f(x)$ . If $f_{\star}(x)<f(x)$ we could find (by density of $\mathbb{Q}$ in $\mathbb{R}$ ) an element $q\in\mathbb{Q}$ such that $f_{\star}(x)<q<f(x)$ . For $p=f^{{-1}}(q)$ we get $p<x$ and so $q=f(p)\leq f_{\star}(x)$ . A contradiction. So ${f_{\star}}_{{|P}}=f$ .

Let $x,y\in R$ such that $x<y$ . 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<p_{1}<p_{2}<y$ . 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)<f_{\star}(y)$ . 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<r:q\in\mathbb{Q}}}f^{{-1}}(q)\in R$ . 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<r$ 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<q^{{\prime}}<r$ and so $f^{{-1}}(q)<f^{{-1}}(q^{{\prime}})\leq x$ . 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<f_{\star}(x)$ and consider (by density of $\mathbb{Q}$ in $\mathbb{R}$ ) some $q\in\mathbb{Q}$ such that $r<q<f_{\star}(x)$ and let $p=f^{{-1}}(q)$ . If $p<x$ then there is $q^{{\prime}}\in\mathbb{Q}$ , $q^{{\prime}}<r$ , such that $p\leq f^{{-1}}(q^{{\prime}})$ . Then $r<q=f(p)\leq q^{{\prime}}<r$ a contradiction. If instead $p\geq x$ then $f_{{\star}}(x)\leq f_{{\star}}(p)=q<f_{\star}(x)$ which is again a contradiction.

Finally, let $x,y\in R$ such that $f_{\star}(x)<f_{\star}(y)$ . Because $R$ is totally ordered either $x<y$ or $y<x$ . But the latter is impossible since we saw above that it implied $f_{\star}(y)<f_{\star}(x)$ . 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<x<b\}$ . 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}<b_{\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})<o(I_{\beta})$ . 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}<x_{1}<x_{2}<...<x_{\alpha}<...$ . 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)<o(t)=\alpha$ 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)<o(z_{y})=o(y)+1\leq 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)<B_{2}(\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)<x<B_{2}(\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}<B<B_{2}$ . $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}<c_{i}<d_{i}<b_{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<b$ in $C$ we pick $c\in S$ such that $a<c<b$ . This gives a countable subset $C^{{\prime}}$ of $S$ . If $a<b$ are elements of $S$ , we can find $c,d\in C$ such that $a<c<d<b$ and so $e\in C^{{\prime}}$ such that $a<c<e<d<b$ . 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.

Exercises in Set Theory: Classical Independence Results

fredw — Wed, 20 Mar 2013 00:01:00 +0100

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:

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

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

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.

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$

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

MathML Acid Tests

fredw — Sat, 02 Mar 2013 18:20:00 +0100

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

Exercises in Set Theory

fredw — Fri, 25 Jan 2013 22:25:00 +0100

I'm finally done with the first part "Basic Set Theory" :-) The two last chapters:

Analysis of Lithium's algorithm

fredw — Tue, 22 Jan 2013 23:33:00 +0100

I’ve recently been working on automated testcase reduction tools for the MathJax project and thus I had the chance to study Jesse Ruderman’s Lithium tool, itself inspired from the ddmin algorithm. This paper contains good ideas, like for example the fact that the reduction could be improved if we rely on the testcase structure like XML nodes or grammar tokens instead of just characters/lines (that’s why I’ve started to write a version of Lithium to work with abstract data structure). However, the authors of the ddmin paper really don’t analyse precisely the complexity of the algorithm, except the best and worst case and there is a large gap between the two. Jesse's analysis is much better and in particular introduces the concepts of monotonic testcase and clustered reduction where the algorithm performs the best and which intuitively seems the usual testcases that we meet in practice. However, the monotonic+clustered case complexity is only “guessed” and the bound $O(M\log _{2}(N))$ for a monotonic testcase (of size $N$ with final reduction of size $M$ ) is not optimal. For example if the final reduction is relatively small compared to $N$ , say $M=\frac{N}{\log _{2}(N)}=o(N)$ then $M\log _{2}(N)=N=\Omega(N)$ and we can’t say that the number of verifications is small compared to $N$ . In particular, Jesse can not deduce from his bound that Lithium’s algorithm is better than an approach based on $M$ binary search executions! In this blog post, I shall give the optimal bound for the monotonic case and formalize that in some sense the clustered reduction is near the best case. I’ll also compare Lithium’s algorithm with the binary search approach and with the ddmin algorithm. I shall explain that Lithium is the best in the monotonic case (or actually matches the ddmin in that case).

Thus suppose that we are given a large testcase exhibiting an unwanted behavior. We want to find a smaller test case exhibiting the same behavior and one way is to isolate subtestcases that can not be reduced any further. A testcase can be quite general so here are basic definitions to formalize a bit the problem:

A testcase $S$ is a nonempty finite sets of elements (lines, characters, tree nodes, user actions) exhibiting an “interesting” behavior (crash, hang and other bugs…)
A reduction $T$ of $S$ is a testcase $T\subseteq S$ with the same “interesting” behavior as $S$ .
A testcase $S$ is minimal if $\forall T\subsetneq S,T\text{ is not a reduction of }S$ .

Note that by definition, $S$ is a reduction of itself and $\emptyset$ is not a reduction of $S$ . Also the relation “is a reduction of” is transitive that is a reduction of a reduction of $S$ is a reduction of $S$ .

We assume that verifying one subset to check if it has the “interesting” behavior is what takes the most time (think e.g. testing a hang or user actions) so we want to optimize the number of testcases verified. Moreover, the original testcase $S$ is large and so a fast reduction algorithm would be to have a complexity in $o(|S|)$ . Of course, we also expect to find a small reduction $T\subseteq S$ that is $|T|=o(|S|)$ .

Without information on the structure on a given testcase $S$ or on the properties of the reduction $T$ , we must consider the $2^{{|S|}}-2$ subsets $\emptyset\neq T\neq S$ , to find a minimal reduction. And we only know how to do that in $O\left(2^{{|S|}}\right)$ operations (or $O\left(2^{{|S|/2}}\right)$ with Grover’s algorithm ;-)). Similarly, even to determine whether $T\subseteq S$ is minimal would require testing $2^{{|T|}}-2$ subsets which is not necessarily $o(|S|)$ (e.g. $|T|=\log _{2}{(|S|)}=o(|S|)$ ). Hence we consider the following definitions:

For any integer $n\geq 1$ , $S$ is $n$ -minimal if $\forall T\subsetneq S,|S-T|\leq n\implies T\text{ is not a reduction of }S$ .
In particular, $S$ is $1$ -minimal if $\forall x\in S,S\setminus\{ x\}\text{ is not a reduction of }S$ .
$S$ is monotonic if $\forall T_{1}\subseteq T_{2}\subseteq S,\, T_{1}\text{ is a reduction of }S\implies T_{2}\text{ is a reduction of }S$ .

Finding a $n$ -minimal reduction will give a minimal testcase that is no longer interesting if we remove any portion of size at most $n$ . Clearly, $S$ is minimal if it is $n$ -minimal for all $n$ . Moreover, $S$ is always $n$ -minimal for any $n\geq|S|$ . We still need to test exponentially many subsets to find a $n$ -minimal reduction. To decide whether $T\subseteq S$ is $n$ -minimal, we need to consider subsets obtained by removing portions of size $1,2,...,\min(n,|T|-1)$ that is $\sum _{{k=1}}^{{\min(n,|T|-1)}}\binom{|T|}{k}$ subsets. In particular whether $T$ is $1$ -minimal is $O(|T|)$ and so $o(|S|)$ if $T=o(|S|)$ . If $S$ is monotonic then so is any reduction $T$ of $S$ . Moreover, if $T\subsetneq S$ is a reduction of $S$ and $x\in S\setminus T$ , then $T\subseteq S\setminus\{ x\}\subsetneq S$ and so $S\setminus\{ x\}$ is a reduction of $S$ . Hence when $S$ is monotonic, $S$ is $1$ -minimal if and only if it is minimal. We will target $1$ -minimal reduction in what follows.

Let’s consider Lithium’s algorithm. We assume that $S$ is ordered and so can be identified with the interval $[1,|S|]$ (think for example line numbers). For simplicity, let’s first assume that the size of the original testcase is a power of two, that is $|S|=N=2^{n}$ . Lithium starts by $n-1$ steps $k=1,2,...,n-1$ . At step $k$ , we consider the chunks among the intervals $[1+j2^{{n-k}},(j+1)2^{{n-k}}]\ (0\leq j<2^{k})$ of size $2^{{n-k}}$ . Lithium verifies if removing each chunk provides a reduction. If so, it permanently removes that chunk and tries another chunk. Because $\emptyset$ is not a reduction of $S$ , we immediately increment $k$ if it remains only one chunk. The $n$ -th step is the same, with chunk of size 1 but we stop only when we are sure that the current testcase $T$ is $1$ -minimal that is when after $|T|$ attempts, we have not reduced $T$ any further. If $N$ is not a power of 2 then $2^{{n-1}}<N<2^{n}$ where $n=\lceil\log _{2}(N)\rceil$ . In that case, we apply the same algorithm as $2^{n}$ (i.e. as if there were $2^{n}-N$ dummy elements at the end) except that we don’t need to remove the chunks that are entirely in that additional part. This saves testing at most $n$ subtests (those that would be obtained by removing the dummy chunks at the end of sizes $2^{{n-1}},2^{{n-2}},...,1$ ). Hence in general if $C_{N}$ is the number of subsets of $S$ tried by Lithium, we have $C_{{2^{n}}}-n\leq C_{N}\leq C_{{2^{n}}}$ . Let $M$ be the size of the $1$ -minimal testcase found by Lithium and $m=\lceil\log _{2}(M)\rceil$ .

Lithium will always perform the $n-1$ initial steps above and check at least one subset at each step. At the end, it needs to do $M$ operations to be sure that the testcase is $1$ -minimal. So $C_{N}\geq\lceil\log _{2}(N)\rceil+M-1=\Omega(\log _{2}(N)+M)$ . Now, consider the case where $S$ monotonic and has one minimal reduction $T=[1,M]$ . Then $T$ is included in the chunk $[1,2^{{m}}]$ from step $k=n-m$ . Because $S$ is monotonic, this means that at step $k=1$ , we do two verifications and the second chunk is removed because it does not contain the $T$ (and the third one too if $N$ is not a power of two), at step $k=2$ it remains two chunks, we do two verifications and the second chunk is removed etc until $k=n-m$ . For $k>n-m$ , the number of chunk can grow again: 2, 4, 8… that is we handle at most $2^{{1+k-(n-m)}}$ chunks from step $n-m+1$ to $n-1$ . At step $k=n$ , a first round of at most $2^{m}$ verifications ensure that the testcase is of size $M$ and a second round of $M$ verifications ensure that it is $1$ -minimal. So $C_{N}\leq 1+\left(\sum _{{k=1}}^{{n-m}}2\right)+\left(\sum _{{k=n-m+1}}^{{n}}2^{{1+k-(n-m)}}\right)+2^{m}+M=1+2(n-m)+2^{m}-1+2^{m}+M$ and after simplification $C_{N}=O(\log _{2}(N)+M)$ . Hence the lower bound $\Omega(\log _{2}(N)+M)$ is optimal. The previous example suggests the following generalization: a testcase $T$ is $C$ -clustered if it can be written as the union of $C$ nonempty closed intervals $T=I_{1}\cup I_{2}\cup...\cup I_{C}$ . If the minimal testcase found by Lithium is $C$ -clustered, each $I_{j}$ is of length at most $M\leq 2^{m}$ and so $I_{j}$ intersects at most 2 chunks of length $2^{m}$ from the step $k=n-m$ . So $T$ intersects at most $2C$ chunks from the step $k=n-m$ and a fortiori from all the steps $k\leq n-m$ . Suppose that $S$ is monotonic. Then if $c$ is a chunk that does not contain any element of $T$ then $T\setminus c$ is a reduction of $T$ and so Lithium will remove the chunk $c$ . Hence at each step $k\leq n-m$ , at most $2C$ chunks survive and so there are at most $4C$ chunks at the next step. A computation similar to what we have done for $T=[1,M]$ shows that $C_{N}=O(C(\log _{2}(N)+M))$ if the final testcase found by Lithium is $C$ -clustered. Note that we always have $M=o(N)$ and $\log _{2}(N)=o(N)$ . So if $C=O(1)$ then $C_{N}=O(\log _{2}(N)+M)=o(N)$ is small as wanted. Also, the final testcase is always $M$ -clustered (union of intervals that are singletons!) so we found that the monotonic case is $O(M(\log _{2}(N)+M))$ . We shall give a better bound below.

Now, for each step $k=1,2,...,n-1$ , Lithium splits the testcase in at most $2^{k}$ chunk and try to remove each chunk. Then it does at most $N$ steps before stopping or removing one chunk (so the testcase becomes of size at most $N-1$ ), then it does at most $N-1$ steps before stopping or removing one more chunk (so the testcase becomes of size at most $N-1$ ), …, then it does at most $M+1$ steps before stopping or removing one more chunk (so the testcase becomes of size at most $M$ ). Then the testcase is exactly of size $M$ and Lithium does at most $M$ additional verifications. This gives $C_{N}\leq\sum _{{k=1}}^{{n-1}}2^{k}+\sum _{{k=M}}^{{N}}k=2^{n}-2+\frac{N(N+1)-M(M-1)}{2}=O(N^{2})$ verifications. This bound is optimal if $1\leq M\leq 2^{{n-1}}$ (this is asymptotically true since we assume $M=o(N)$ ): consider the cases where the proper reductions of $S$ are exactly the segments $[1,k]\ (2^{{n-1}}+1\leq k\leq 2^{n}-1)$ and $[k,2^{{n-1}}+1]\ (2\leq k\leq 2^{{n-1}}-M+2)$ . The testcase will be preserved during the first phase. Then we will keep browsing at least the first half to remove elements at position $2^{{n-1}}+2\leq k\leq 2^{n}-1$ . So $C_{N}\geq\sum _{{k=2^{{n-1}}+2}}^{{2^{n}-1}}2^{{n-1}}=2^{{n-1}}\left(2^{{n-1}}-2\right)=\Omega(N^{2})$ .

We now come back to the case where $S$ is monotonic. We will prove that the worst case is $C_{N}=\Theta\left(M\log _{2}(\frac{N}{M})\right)$ and so our assumption $M=o(N)$ gives $M\log _{2}(\frac{N}{M})=\left(-\frac{M}{N}\log _{2}(\frac{M}{N})\right)N=o(N)$ as we expected. During the steps $1\leq k\leq m$ , we test at most $2^{k}$ chunks. When $k=m$ , $2^{{m}}\geq M$ chunks but at most $M$ distinct chunks contain an element from the final reduction. By monocity, at most $M$ chunks will survive and there are at most $2M$ chunks at step $m+1$ . Again, only $M$ chunks will survive at step $m+2$ and so on until $k=n-1$ . A the final step, it remains at most $2M$ elements. Again by monocity a first round of $2M$ tests will make $M$ elements survive and we finally need $M$ additional tests to ensure that the test case is minimal. Hence $C_{N}\leq{\sum _{{k=1}}^{{m}}2^{k}}+{\sum _{{k=m+1}}^{{n}}2M}+M=2^{{m+1}}-3+M(2(n-m)+1)=O(M\log _{2}(\frac{N}{M}))$ . This bound is optimal: if $M=2^{m}$ , consider the case where $T=\{ j2^{{n-m}}+1:0\leq j<2^{{m}}\}$ is the only minimal testcase (and $S$ monotonic) ; if $M$ is not a power of two, consider the same $T$ with $2^{{m}}-M$ points removed at odd positions. Then for each step $1\leq k\leq m-1$ , no chunks inside $[1,2^{n}]$ are removed. Then some chunks in $[1,2^{n}]$ are removed (none if $M$ is a power of two) at step $m$ and it remains $M$ chunks. Then for steps $m+1\leq k\leq n-1$ there are always exactly $2M$ chunks to handle. So $C_{N}\geq\sum _{{m+1\leq k\leq n-1}}2M=2M(n-m-2)=2M(\log _{2}(\frac{N}{M})-2)=\Omega(M\log _{2}(\frac{N}{M}))$ .

We note that we have used two different methods to bound the number of verifications in the general monotonic case, or when the testcase is $C$ -clustered. One naturally wonders what happens when we combine the two techniques. So let $c=\lceil\log _{2}C\rceil\leq m$ . From step $1$ to $c$ , the best bound we found was $O(2^{k})$ ; from step $c$ to $m$ , it was $O(C)$ ; from step $m$ to $n-m$ it was $O(C)$ again ; from step $n-m$ to $n-c$ , it was $O(2^{{1-k-(n-m)}}C)$ and finally from step $n-c$ to $n$ , including final verifications, it was $O(M)$ . Taking the sum, we get $C_{N}=O(2^{c}+((n-m)-c)C+2^{{(n-c-(n-m))}}C+(n-(n-c))M)=O(C\left(1+\log _{2}{\left(\frac{N}{MC}\right)}\right)+M(1+\log _{2}{C}))$ Because $C=O(M)$ , this becomes $C_{N}=O(C\log _{2}{\left(\frac{N}{MC}\right)}+M(1+\log _{2}{C}))$ . If $C=O(1)$ , then we get $C_{N}=O(\log _{2}(N)+M)$ . At the opposite, if $C=\Omega(M)$ , we get $C_{N}=\Omega(M\log _{2}{\left(\frac{N}{M}\right)})$ . If $C$ is not $O(1)$ but $C=o(M)$ then $1=o(\log _{2}{C})$ and $C\log _{2}(C)=o(M\log _{2}{C})$ and so the expression can be simplified to $C_{N}=O(C\log _{2}{\left(\frac{N}{M}\right)}+M\log _{2}{C})$ . Hence we have obtained an intermediate result between the worst and best monotonic cases and shown how the role played by the number of clusters: the less the final testcase is clustered, the faster Lithium finds it. The results are summarized in the following table:

	Number of tests
Best case	$\Theta(\log _{2}(N)+M)$
$S$ is monotonic ; $T$ is $O(1)$ -clustered	$O(\log _{2}(N)+M)$
$S$ is monotonic ; $T$ is $C$ -clustered ( $C=o(M)$ and unbounded)	$O(C\log _{2}{\left(\frac{N}{M}\right)}+M\log _{2}{C})$
$S$ is monotonic	$O\left(M\log _{2}\left(\frac{N}{M}\right)\right);o(N)$
Worst case	$\Theta(N^{2})$

Figure 0.1: Performance of Lithium’s algorithm for some initial testcase

S

of size

N

and final reduction

T

of size

M=o(N)

T

C

-clustered if it is the union of

C

intervals.

In the ddmin algorithm, at each step we add a preliminary round where we try to immediately reduce to a single chunk (or equivalently to remove the complement of a chunk). Actually, the ddmin algorithm only does this preliminary round at steps where there are more than 2 chunks for otherwise it would do twice the same work. For each step $k>1$ , if one chunk $c_{1}$ is a reduction of $S$ then $c_{1}\subseteq c_{2}$ for some chunk $c_{2}$ at the previous step $k-1$ . Now if $S$ is monotonic then, at level $k-1$ , removing all but the chunk $c_{2}$ gives a subset that contains $c_{1}$ and so a reduction of $S$ by monocity. Hence on chunk survive at level $k$ and there are exactly 2 chunks at level $k$ and so the ddmin algorithm is exactly Lithium’s algorithm when $S$ is monotonic. The ddmin algorithm keeps in memory the subsets that we didn’t find interesting in order to avoid repeating them. However, if we only reduce to the complement of a chunk, then we can never repeat the same subset and so this additional work is useless. That’s the case if $S$ is monotonic.

Finally, if $S$ is monotonic Jesse proposes a simpler approach based on a binary search. Suppose first that there is only one minimal testcase $T$ . If $k\geq\min T$ then $[1,k]$ intersects $T$ and so $U_{k}=S\setminus[1,k]\neq T$ . Then $U_{k}$ is not a reduction of $S$ for otherwise a minimal reduction of $U_{k}$ would be a minimal reduction of $S$ distinct from $T$ which we exclude by hypothesis. If instead $k<\min T$ then $[1,k]$ does not intersect $T$ and $U_{k}=S\setminus[1,k]\supseteq T\setminus[1,k]\supseteq T$ is a reduction of $S$ because $S$ is monotonic. So we can use a binary search to find $\min T$ by testing at most $\log _{2}(N)$ testcases (modulo some constant). Then we try with intervals $[1+\min T,k]$ to find the second least element of $T$ in at most $\log _{2}(N)$ . We continue until we find the $M$ -th element of $T$ . Clearly, this gives $M\log _{2}(N)$ verifications which sounds equivalent to Jesse’s bound with even a better constant factor. Note that the algorithm still works if we remove the assumption that there is only one minimal testcase $T$ . We start by $S=S_{1}$ and find $x_{1}=\max\{\min T:T\text{ is a minimal reduction of }S_{1}\}$ : if $k<x_{1}$ then $S\setminus[1;k]$ contains at least one mininal reduction with least element $x_{1}$ and so is a reduction because $S$ is monotonic. If $k\geq x_{1}$ then $S\setminus[1;k]$ is not a reduction of $S$ or a minimal reduction of $S\setminus[1;k]$ would be a minimal reduction of $S$ whose least element is greater than $x_{1}$ . So $S_{2}=S_{1}\setminus[1;x_{1}-1]$ is a reduction of $S_{1}$ . The algorithm continues to find $x_{2}=\max\{\min(T\setminus\{ x_{1}\}):T\text{ is a minimal reduction of }S_{2},\min(T)=x_{1}\}$ etc and finally returns a minimal reduction of $S$ . However, it is not clear that this approach can work if $S$ is not monotonic while we can hope that Lithium is still efficient if $S$ is “almost” monotonic. We remark that when there is only one minimal testcase $T=[1,M]$ , the binary search approach would require something like $\sum _{{k=0}}^{{M-1}}\log _{2}(N-k)=M\log _{2}(N)+\sum _{{k=0}}^{{M-1}}\log _{2}\left(1-\frac{k}{N}\right)\geq M\log _{2}(N)+M\log _{2}\left(1-\frac{M}{N}\right)=M\log _{2}(N)+o(M)$ . So that would be the worst case of the binary search approach whereas Lithium handles this case very nicely in $\Theta(\log _{2}(N)+M)$ ! In general, if there is only one minimal testcase $T$ of size $M\leq\frac{N}{2}$ then $\max(T)$ can be anywhere between $[M,N]$ and if $T$ is placed at random, $\max(T)\leq\frac{3}{4}N$ with probability at least $\frac{1}{2}$ . So the average complexity of the binary search approach in that case will be at least $\frac{1}{2}\sum _{{k=0}}^{{M-1}}\log _{2}(\frac{1}{4}N)=\frac{1}{2}M\log _{2}(N)+o(M)$ which is still not as good as Lithium’s optimal worst case of $O(M\log _{2}(\frac{N}{M}))$ …

MathML in Chrome, a couple of demos and some perspectives...

fredw — Fri, 11 Jan 2013 13:24:00 +0100

For those who missed the news, Google Chrome 24 has recently been released with native MathML support. I'd like to thank Dave Barton again for his efforts during the past year, that have allowed to make this happen. Obviously, some people may ironize on how long it took for Google to make this happen (Mozilla MathML project started in 1999) or criticize the bad rendering quality. However the MathML folks, aware of the history of the language in browsers, will tend to be more tolerant and appreciate this important step towards MathML adoption. After all, this now means that among the most popular browsers, Firefox, Safari and Chrome have MathML support and Opera a basic CSS-based implementation. This also means that about three people out of four will be able to read pages with MathML without the need of any third-party rendering engine.

After some testing, I think the Webkit MathML support is now good enough to be used on my Website. There are a few annoyances with stretchy characters or positioning, but in general the formulas are readable. Hence in order to encourage the use of MathML and let people report bugs upstream and hopefully help to fix them, I decided to rely on the native MathML support for Webkit-based browsers. I'll still keep MathJax for Internet Explorer (when MathPlayer is not installed) and Opera.

I had the chance to meet Dave Barton when I was at the Silicon Valley last October for the GSoC mentor summit. We could exchange our views on the MathML implementations in browsers and discuss the perspectives for the future of MathML. The history of MathML in Webkit is actually quite similar to Gecko's one: one volunteer Alex Milowski decided to write the initial implementation. This idea attracted more volunteers who joined the effort and helped to add new features and to conduct the project. Dave told me that the initial Webkit implementation did not pass the Google's security review and that's why MathML was not enabled in Chrome. It was actually quite surprising that Apple decided to enable it in Safari and in particular all Apple's mobile products. Dave's main achievement has been to fix all these security bugs so that MathML could finally appear in Chrome.

One of the idea I share with Dave is how important it is to have native MathML support in browsers, rather than to delegate the rendering to Javascript libraries like MathJax or browser plug-in like MathPlayer. That's always a bit sad to see that third-party tools are necessary to improve the native browser support of a language that is sometimes considered a core XML language for the Web together with XHTML and SVG. Not only native support is faster but also it integrates better in the browser environment: zooming text, using links, applying CSS style, mixing with SVG diagrams, doing dynamic updates with e.g. Javascript etc all of the features Web users are familiar with are immediately available. In order to illustrate this concretely, here is a couple of demos. Some of them are inspired from the Mozilla's MathML demo pages, recently moved to MDN. By the way, the famous MathML torture page is now here. Also, try this test page to quickly determine whether you need to install additional fonts.

MathML with CSS text-shadow & transform properties, href & dir attributes as well as Javascript events

$\det (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}) = 45 + 84 + 96 - (105 + 48 + 72) = 0 محدد (\begin{matrix} ١‎ & ٢ & ٣ \\ ٤ & ٥ & ٦ \\ ٧‎ & ٨ & ٩ \end{matrix}) = ٤٥ + ٨٤ + ٩٦ - (١‎٠٥ + ٤٨ + ٧‎٢) = ٠$

HTML and animated SVG inside MathML tokens

$tr {(\begin{matrix} \end{matrix})}^{n} = \sqrt{} = \int_{0}^{\frac{π}{2}} θ^{} ⅆ θ$

MathML inside animated SVG (via the <foreignObject> element):

Note that although Dave was focused on improving MathML, the language naturally integrates with the rest of Webkit's technologies and almost all the demos above work as expected, without any additional efforts. Actually, Gecko's MathML support relies less on the CSS layout engine than Webkit does and this has been a recurrent source of bugs. For example in the first demo, the text-shadow property is not applied to some operators (bug 827039) while it is in Webkit.

In my opinion, one of the problem with MathML is that the browser vendors never really shown a lot of interest in this language and the standardization and implementation efforts were mainly lead and funded by organizations from the publishing industry or by volunteer contributors. As the MathML WG members keep repeating, they would love to get more feedback from the browser developers. This is quite a problem for a language that has among the main goal the publication of mathematics on the Web. This leads for example to MathML features (some of them are now deprecated) duplicating CSS properties or to the <mstyle> element which has most of its attributes unused and do similar things as CSS inheritance in an incompatible way. As a consequence, it was difficult to implement all MathML features properly in Gecko and this is the source of many bugs like the one I mention in the previous paragraph.

Hopefully, the new MathML support in Chrome will bring more interest to MathML from contributors or Web companies. Dave told me that Google could hire a full-time engineer to work on MathML. Apparently, this is mostly because of demands from companies working on Webkit-based mobile devices or involved in EPUB. Although I don't have the same impression from Mozilla Corporation at the moment, I'm confident that with the upcoming FirefoxOS release, things might change a bit.

Finally I also expect that we, at MathJax, will continue to accompany the MathML implementations in browsers. One of the ideas I proposed to the team was to let MathJax select the output mode according to the MathML features supported by the browser. Hence the native MathML support could be used if the page contains only basic mathematics while MathJax's rendering engine will be used when more advanced mathematical constructions are involved. Another goal to achieve will be to make MathJax the default rendering in Wikipedia, which will be much better than the current raster image approach and will allow the users to switch to their browser's MathML support if they wish...

Exercises in Set Theory

fredw — Thu, 03 Jan 2013 22:27:00 +0100

During last December, I've made more progress on the exercises from Thomas Jech's book "Set Theory". After the six first chapters and the seventh chapter, I've worked on chapters 8, 9 and 10. I've published the solutions for most of the exercices here:

I also typeset a couple of exercises from chapter 12 that I solved some years ago but didn't get the opportunity to work on new exercises yet.

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

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

Blog de Frédéric

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

Exercises in Set Theory: Applications of Forcing

Firefox Nightly passes the Acid2 test

Suslin’s Problem

Lemma 0.1.

Proof.

Theorem 0.1.

Proof.

Problem 0.1 (Suslin’s Problem).

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

Theorem 0.2.

Proof.

Theorem 0.3.

Proof.

Exercises in Set Theory: Classical Independence Results

MathML Acid Tests

Exercises in Set Theory

Analysis of Lithium's algorithm

MathML in Chrome, a couple of demos and some perspectives...

Exercises in Set Theory

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