Category Archives: Talks

Strong coloring

I am sitting in the 6th European Set Theory Conference in Budapest, and watching all these wonderful talks, and many of them use colors for emphasis of some things. But yesterday one of the talks was using “too many colors”, enough to make me make a comment at the end of the talk after all the questions were answered. Since I received some positive feedback from other people here, I decided to write about it on my blog, if only to raise some awareness of the topic.

There is a nontrivial percentage of the population which have some sort of color vision deficiency. Myself included. Statistically, I believe, if you have 20 male participants, then one of them is likely to have some sort of color vision issues. Add this to the fairly imperfect color fidelity of most projectors, and you get something that can be problematic.

Now, I’m not saying “don’t use any colors”. Not at all. Just keep in mind that some people might have problems with your choice of colors. Using too many colors can be distracting, and one of the slides in the said talk had black text almost on par with the rest of the colored text. This is far from ideal. But since color deficiency can vary from one to another, let me only give an account of my own personal experience. I cannot do anything more, after all.

I have a mild red-green issue. But this means also that yellow and bright green, or light orange, all mix together sometimes; and darker greens can be red or brown (which themselves are often mixed); and blues can mix with purple, and sometimes with pink as well. One other effect of color deficiency is that you are more sensitive to brightness and darkness (the eye compensates the damaged cones by having better rods, so your night vision gets somewhat better, for example).

So when you have a slide with some pink/purple and green/yellow/orange and some blue and some red and some black, my brain will not read the text. My brain will try to make sense of the colors. Not to mention the terrible eye strain coming from the brighter colors (here the quality of the viewing media is important, I’m sure that I’d be fine watching the same slides on a proper computer monitor). There were slides that I had to turn my eyes away from the talk. Yes, it was pretty bad.

What can you do about it? Don’t use colors when you don’t have to. Use boldface or italics for emphasis when possible, or different font family entirely. If you want to use colors, using them sparingly, and try to avoid relatively close colors together and certainly try to avoid brighter colors like light green or yellow. If you know a color blinded person, you can maybe ask them to give some critique on your choice of colors.

Some people commented to me after my remark that they prefer the colors, and they are helpful. I understand that. Again, the point is not to get people to use colors. Just… to use them intelligently. Colors are like spices. I’m not trying to get you to cook without spices, but you’re not going to serve a dish entirely made of cinnamon and cumin.

In the name of all color vision deficient people, thanks in advance for your consideration!

Young Set Theory 2015

Have you heard? Young Set Theory 2015 will take place in Jerusalem! How exciting is that?
Tomorrow (Monday, July 20th) is the last day for registration. This means that you have only a few hours to get yourself together and send an application!

If you are not on this list, you better hurry up to this application form and register! Come on, what are you waiting for???

And if you have registered, then I’ll be seeing you in October!

YST 2015 Poster
Young Set Theory 2015

On the Partition Principle

Last Wednesday I gave a talk about the Partition Principle in our students seminar. This talk covered the historical background of the oldest open problem in set theory, and two proofs that for a long time I avoided learning. I promised to post a summary of the talk here. So here it is. The historical data was taken from the paper by Banaschewski and Moore, “The dual Cantor-Bernstein theorem and the partition principle.” (MR1072073) as well Moore’s wonderful book “Zermelo’s Axiom of Choice” (which has a Dover reprint!).

We begin with two definitions. We write $A\leq B$ to say that there is an injection from $A$ into $B$, and $A\leq^* B$ to say that if $A$ is not empty, then there is a surjection from $B$ onto $A$. These orders are usually defined for cardinals, we will often confuse a set with its cardinality here. Additionally we define two cardinal functions, given a set $A$ the Hartogs number of $A$, denoted by $\aleph(A)=\min\{\alpha\in\Ord\setminus\omega\mid\alpha\nleq A\}$ is the least infinite ordinal which cannot be mapped into $A$ injectively; and the Lindenbaum number of $A$, denoted by $\aleph^*(A)=\min\{\alpha\in\Ord\setminus\omega\mid\alpha\nleq^* A\}$ is the least infinite ordinal that $A$ cannot be mapped onto.

(Two minor remarks, in some places $\aleph$ and $\aleph^*$ are allowed to be finite, I prefer to think about it as a function into $\aleph$ numbers. It also helps to characterize finiteness; the second is that we don’t use $\aleph^*$ here at all, I just found it fitting to add the definition and push even more the efforts to establish the terminology “Lindenbaum number”.)

The Partition Principle (PP) is the principle stating that if $A\leq^*B$ then $A\leq B$, or in words if there is a surjection $f\colon A\to B$, then there is an injection $g\colon B\to A$. In other words, if we partition the set $A$ into $B$ parts, we could only decrease the cardinality.

This is a weakening of the axiom of choice, which can be phrased as the following: if there is a surjection $f\colon A\to B$, then there is an injection $g\colon B\to A$ such that $f\circ g=\operatorname{id}_B$. So clearly $\AC$ implies $\sf PP$.

The partition principle was almost formulated by Burali-Forti in the late 19th century. Almost because Burali-Forti’s formulation had a mistake. The formulation was that $S\leq\bigcup S$. Russell noted that this is false, unless we require that $S$ is a collection of pairwise disjoint sets, in which case we really do say that a partition of $\bigcup S$ can only decrease in size.

This principle was used by Bernstein in 1901, and in 1902 Beppo Levi formulated it explicitly to point out the problem with Bernstein’s proof. Bernstein argued that this is an important principle of mathematics, and indeed one of the motivations given by Zermelo for the axiom of choice was that it proves this principle. Russell claimed that $\sf PP$ proves the axiom of choice, although he did not give proof of that (the claim was indirect, Russell claimed this is equivalent to a different axiom which he proved to be equivalent to $\AC$).

The Polish school of Warsaw had its share of related works. In 1918 Sierpinski reformulated the principle as $f”A\leq A$, for every function $f$ and set $A$. In the same year, Sierpinski proved that from the assumption that $[\RR]^\omega$ and $\RR$ have the same cardinality – something which follows from $\sf PP$ – the existence of a Lebesgue non-measurable set can be proven. Lebesgue disagreed with the proof, and the two had an argument over that topic for several more years.

Lindenbaum and Tarski defined $\leq^*$ in 1926, and formulated the Weak Partition Principle (WPP): $$A\leq^*B\implies B\nless A$$ Namely, we cannot partition a set into strictly more parts than elements (curiously this is a consequence of having all sets Lebesgue measurable, something equally perplexing as the Banach-Tarski theorem).

We can include an intermediate weakening of PP, the dual Cantor-Bernstein theorem, (CB*) which states that $\leq^*$ is antisymmetric as an ordering of cardinals. Namely, if there are surjections from $A$ onto $B$ and vice versa, then there is a bijection between $A$ and $B$.

As remarked $\AC$ implies $\sf PP$, which itself implies $\sf CB^*$ (by reducing it to the Cantor-Bernstein theorem), and $\sf CB^*$ implies $\sf WPP$ (via a similar proof).

In 1965, Levy pointed out that whether or not any of the three implications is reversible is still open (this is actually a paper from a conference in 1963). In 1978 Pelc published a paper which included an equivalence between $\sf PP$ and $\sf CB^*$ under some additional conditions, as well the following theorem by Pincus:

Theorem. (Pincus, 1978)
$\sf PP$ implies that for every $\aleph$-number $\kappa$, $\AC_\kappa$ holds. (Namely, choice from families of size $\leq\kappa$.)

Proof. We will show that from $\sf PP+\AC_{\lt\kappa}$ we can prove $\AC_\kappa$, and then by transfinite induction we can prove that for every $\aleph$ number $\kappa$, $\AC_\kappa$ holds.

Let $\langle X_\alpha\mid\alpha\lt\kappa\rangle$ be a family of non-empty sets. By our assumptions, for each $\gamma<\kappa$, the set $C_\gamma=\prod_{\alpha\lt\gamma}X_\alpha$ is non-empty. We define by induction $\aleph$ numbers, $\lambda_\gamma$ and sets $D_\gamma$:

  • $\lambda_\gamma=\aleph\left(\bigcup_{\delta\lt\gamma}D_\delta\right)+\sup_{\delta\lt\gamma}\lambda_\delta^+$.
  • $D_\gamma=C_\gamma\times\lambda_\gamma$.

Finally, let $\lambda=\sup_{\gamma\lt\kappa}\lambda_\gamma$ and $D=\bigcup_{\gamma\lt\kappa}D_\gamma$. There is a natural surjection from $D$ onto $\lambda$, the projection map. Using the Partition Principle, we have that there is an injection $F$ from $\lambda$ back into $D$. Naively we might be tempted to think that this injection reverses this surjection, so it chooses $(h_\gamma,\gamma)$ from each $D_\gamma$. But this need not be the case, we are only guaranteed an injection. However, by noting that $\lambda$ is at least as large as $\alpha(D_\gamma)$ for any $\gamma$, we have that the range of $F$ meets arbitrarily high $D_\gamma$’s. This allows us to define a choice function from the original $X_\alpha$’s. Denote $F(\delta)$ by $(h_\delta,\delta)$, then we define $H(\alpha)=x_\alpha$ if and only if $h_\delta(\alpha)=x_\alpha$, and $\delta=\min\{\delta’\lt\lambda\mid\alpha\in\dom h_{\delta’}\}$. $\qquad\square$

This shows that $\sf PP$ gives us a substantial amount of choice. But unfortunately, not that substantial. In 1964 Levy showed that choice from well-orderable families doesn’t have to imply $\sf DC_{\omega_1}$. Pincus transferred the proof from permutation models to $\ZF$ in 1969. But we can do better, as Jensen showed.

Theorem. (Jensen, 1968)
Suppose that for every $\aleph$ number $\kappa$, $\AC_\kappa$ holds. Then $\DC$ holds.

Proof. Recall that $\DC$ can be formulated as the statement “Every tree of height $\omega$ without leaves has a branch”. So let $(T,\lt_T)$ be a tree of height $\omega$ and without leaves. We first observe that it suffices to find a well-orderable set $A\subseteq T$ such that $(A,{}_T\gt\restriction A)$ is not well-founded (here well-founded means every non-empty set has a minimal element), since we assume that $A$ can be well-ordered this is equivalent as saying there is a decreasing chain which is a branch through $T$. Assume towards contradiction that there is no such subset of $T$.

Let $\mathcal W=\{A\subseteq T\mid A\text{ can be w.o., and }(A,{}_T\gt)\text{ is well-founded}\}$. For each $A\in\mathcal W$ define $\rho_A$ to be the rank function for $(A,{}_T\gt)$. Finally, $\lambda(x)=\sup\{\rho_A(x)\mid x\in A\in\mathcal W\}$.

Now we claim that for every $x\in T$ there is some $A\in\mathcal W$, such that $\lambda(x)=\rho_A(x)$. Namely, $\sup$ is in fact $\max$, if it happened to be a successor ordinal then this obviously true. To prove that in the case of a limit ordinal, define $R_\alpha=\{(A,<)\mid\rho_A(x)=\alpha,\text{ and }<\text{ is a well-ordering of }A\}$ then for all $\alpha\lt\lambda(x)$ this is non-empty. Using $\AC_{|\lambda(x)|}$ we can choose from each $R_\alpha$ a pair, $(A_\alpha,\rho_A(y)=\rho_{A’}(y)=\lambda(y)\geq\lambda(x)$. This is of course a contradiction to definition of $\lambda(x)$. $\qquad\square$

So we have some provable results. The Partition Principle implies choice from well-ordered families, and therefore $\DC$. It implies the existence of non-measurable sets, and it doesn’t give us a whole lot to work with in terms of trying to prove the axiom of choice from it. Since the 1970’s there was the Banaschewski-Moore paper cited above, as well Higasikawa’s paper “Partition principles and infinite sums of cardinal numbers” (MR1351415) from 1995. But here we are, nearly two decades later, and nothing changed in the questions above.

The question $\sf PP\rightarrow\AC$ is simple to formulate, and simple to understand. But much like many other problems in mathematics, it is incredibly difficult to solve.