Some Cardinal Arithmetic

Some time ago, Asaf Karagila wrote wonderful post wherein he shows that, even without assuming the axiom of choice one can always find four cardinals \(\mathfrak{p} \lt \mathfrak{q}\) and \(\mathfrak{r} \lt \mathfrak{s}\) such that \(\mathfrak{p}^{\mathfrak{r}} = \mathfrak{q}^{\mathfrak{s}}.\) In the comments, Harvey Friedman asks:

Your theorem is an example of an existential sentence about cardinals in the language with only \(\lt \) and exponentiation. Can you determine which sentences in that language are provable in ZF? More generally, expand the set of sentences about cardinals considered, obviously to include addition and multiplication, and perhaps alternating quantifiers.

After Peter Krautzberger’s tiny blogging challenge, I decided to spend 30 minutes thinking and writing about this…

… 

 

What is combinatorial set theory?

This is a very difficult question that I find myself pondering every so often. I once heard a story that Jim Baumgartner was asked this question at a major logic meeting where all areas — recursion theory, model theory, proof theory, etc. — were well represented and he responded that it was the only area of logic not represented there. Indeed, the best way to describe infinitary combinatorics is to describe what it isn’t, as in the introductory paragraph of Jim’s review of William’s book on the subject:

Combinatorial set theory is frequently distinguished from axiomatic set theory, although the distinction is becoming less and less clear all the time. If there is a difference, it is more one of method than substance. Axiomatic set theory uses the tools of mathematical logic, such as the method of ultrapowers and the theory of forcing and generic sets, while the methods of combinatorial set theory are purely “combinatorial” in nature. In practice, an argument of result is “combinatorial” if it is not overtly model-theoretic, topological, or measure-theoretic.1

I stumbled across the above review while seeking to find a reference for the anecdote about Jim at the meeting. I don’t remember where I got this story from, I may have read it somewhere or I may have heard it from somebody or Jim himself. I didn’t find a reference for the anecdote. However, I did find that Jim wrote some fantastic book reviews. One of the best is his review of Kunen’s classic set theory textbook, where he writes the following about Jech’s encyclopedic Set Theory:

Graduate students went without food to put a copy of this fat green book on their shelves.2

This was the first edition of Jech’s book, of course. The classic is now much fatter, yellow rather than green, and sufficiently affordable that graduate students can acquire a copy without excessive suffering.

  1. James E. Baumgartner, Review: Neil H. Williams, Combinatorial set theory. Bull. Amer. Math. Soc. (N.S.) 1 (1979), 217–219. [link]
  2. James E. Baumbarther, Review: Kenneth Kunen, Set theory. An introduction to independence proofs. J. Symb. Logic 51 (1986), 462–464. [link]
 

Arithmetical consequences of the set-theoretic multiverse

In [2], Joel David Hamkins proposed a set of axioms for the set-theoretic multiverse. Several of these axioms reflect the typical world many set theorists live in, namely that generic extensions, inner models and the like are all legitimate universes. Some set theorists prefer the universe perspective where one such universe is singled out as more legitimate than others and other set theorists prefer to think that any universe is as legitimate as any other. Hamkins is of the latter view and, in many ways, his view is even radically opposed to the universe perspective. Indeed, some of Hamkins’s axioms take the form of “mirages” that gradually eliminate the possibility of singling out a preferred universe. These can be formulated as follows.1

Uncountability Mirage
Every universe is countable from the perspective of a larger universe.
Undefinability Mirage
Every universe is constructible from the perspective of a larger universe.
Wellfoundedness Mirage
Every universe is not wellfounded from the perspective of a larger universe.
Finiteness Mirage
Every universe has a nonstandard $\omega$ from the perspective of a larger universe.

The Undefinability Mirage is a fascinating axiom that I hope to talk about in the near future but it does not directly contradict the universe perspective. The Uncountability Mirage is startling but it isn’t earth-shattering on its own. However, the last two mirages are fundamentally incompatible with the universe perspective. The Finiteness Mirage — which actually implies the Wellfoundedness Mirage — is especially striking since it asserts that no universe understands true finiteness. This is a chilling thought for most mathematicians, even those who do not espouse the classical universe view. After reading Hamkins’s account, I wondered what kind of arithmetical consequences the multiverse axioms have. This is an important question since an arithmetical disagreement between the multiverse view and the universe view would make the divide much more than a different perspective.

… 

 

Back to Cantor?

Set Theory has a fantastic and legendary history. At the end, it left us with ZFC, which is currently recognized as the foundation of mathematics. This state of affairs is arguably one of the best possible outcomes for the foundational crisis that plagued mathematics in the early 20th century. However, the choice to adopt ZFC was by no means unanimous, dissent has always been present, often with good reason. Whether propelled by inertia or by sheer power, for better or for worse, ZFC is now approaching 100 years of reign as the foundation of mathematics.

… 

 

Scheming schemes…

In everyday language, the word scheme often has a negative connotation: scheme is used as a synonym for devious plan. In mathematical language, the word has no negative aspect at all. In fact, I think that mathematical schemes of all kinds are wonderful things and it often takes me a moment to understand when someone uses scheme to imply wrongful intent. This can lead to awkward social situations, but what I want to talk about here is how axiom schemes can sometimes behave badly and may lead to awkward mathematical situations.

… 

 

Diaconescu’s Theorem

In the 1970s, Radu Diaconescu [1] showed that the Axiom of Choice implies the Principle of Excluded Middle. More specifically, he showed that every topos that satisfies (a very mild form of) the Axiom of Choice is Boolean. Diaconescu’s argument applies in many other contexts too. In this post, I will present a variant of that argument. I will keep the context of the argument deliberately ambiguous to demonstrate its broad applicability.

… 

 

Subposets of small dimension

Behind the scenes at Boole’s Rings, there was some talk on asking more open questions related to our research. I have three related problems that I would like to share. They are strikingly similar in nature, but they properly belong in three different branches of mathematics: the first problem is about finite combinatorics, the second problem is about reverse mathematics, and the third problem is about infinite combinatorics. To me they are three faces of the same question and I currently don’t know how to answer any of them.

Three Problems. Let $d \geq 2$:

  1. Let $F_d(n)$ denote the largest number such that every poset of size $n$ has a $d$-dimensional subposet of size $F_d(n)$. What is the asymptotic growth of $F_d(n)$?
  2. Every (countably) infinite poset has an infinite subposet of dimension at most $d$. What is the logical strength of this statement over $\mathsf{RCA}_0$?
  3. Is there an uncountable poset that has no uncountable $d$-dimensional subposet?

… 

 

On a theorem of Mycielski and Taylor

$\DeclareMathOperator{\cov}{cov}\newcommand{\meager}{\mathcal{M}}$

In 1964, Jan Mycielski [1] proved a wonderful theorem about independent sets in Polish spaces. He showed that if $X$ is an uncountable Polish space and $R_n$ is a meager subset of $X^n$ for each $n \geq 1$, then there is a perfect set $Z \subseteq X$ such that $(z_1,\dots,z_n) \notin R_n$ whenever $z_1,\dots,z_n$ are distinct elements of $Z$. In other words, $Z$ is $R_n$-independent for each $n \geq 1$. This is a wonderfully general theorem that has a multitude of applications.

One of my favorite theorems where Mycielski’s Theorem comes in handy is a remarkable partition theorem due to Fred Galvin [2].

Theorem (Galvin). Let $X$ be an uncountable Polish space and let $c:[X]^2\to\set{0,\dots,k-1}$ be a Baire measurable coloring where $k$ is a positive integer. Then $X$ has a perfect $c$-homogeneous subset.

Galvin proved a similar result for colorings of $[X]^3$, but with a weaker conclusion that triples from the perfect set take on at most two colors. Andreas Blass [3] then extended Galvin’s result to colorings of $[X]^n$, showing that there is a perfect set that takes on at most $(n-1)!$ colors.

Galvin’s result has many applications too. For example, Rafał Filipów and I used it in [4] it to show that if $X$ is a perfect Abelian Polish group, then $X$ contains a Marczewski null set $A$ such that the algebraic sum $A + A$ is not Marczewski measurable.

Alan Taylor [5] generalized the result to Baire measurable colorings $c:[X]^2\to\kappa$ where $\kappa$ is any cardinal smaller than $\cov(\meager)$. Doing so, Taylor similarly generalized Mycielski’s Theorem, but he only stated the result for binary relations. Recently, Rafał Filipów, Tomasz Natkaniec and I needed this generalization for relations of arbitrary arity. Unfortunately, the Mycielski–Taylor result has never been stated in full generality, so we included a proof in our paper [6]. I am copying this proof here because I think the result is of independent interest and our proof is a nice application of Cohen forcing. A nice consequence of this extended Mycielski–Taylor Theorem is that Blass’s result extends to Baire measurable colorings $c:[X]^n\to\kappa$ where $\kappa \lt \cov(\meager)$ in the same way that Taylor generalized Galvin’s result for partitions of pairs.

Theorem (Mycielski, Taylor). Let $X$ be an uncountable Polish space and let $\mathcal{R}$ be a family of fewer than $\cov(\meager)$ closed nowhere dense relations on $X$, i.e., each $R \in \mathcal{R}$ is a closed nowhere dense subset of $X^n$ for some $n = n(R)$. Then $X$ contains a perfect set which is $R$-independent for every $R \in \mathcal{R}$.

… 

[1] J. Mycielski, “Independent sets in topological algebras,” Fund. math., vol. 55, pp. 139-147, 1964.
[Bibtex]
@article {Mycielski,
AUTHOR = {Mycielski, Jan},
TITLE = {Independent sets in topological algebras},
JOURNAL = {Fund. Math.},
FJOURNAL = {Polska Akademia Nauk. Fundamenta Mathematicae},
VOLUME = {55},
YEAR = {1964},
PAGES = {139--147},
ISSN = {0016-2736},
MRCLASS = {08.40 (55.99)},
MRNUMBER = {0173645 (30 \#3855)},
MRREVIEWER = {Th. J. Dekker},
URL = {http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=55},
}
[2] F. Galvin, “Partition theorems for the real line,” Notices amer. math. soc., vol. 15, p. 660, 1968.
[Bibtex]
@article {Galvin,
AUTHOR = {Galvin, Fred},
TITLE = {Partition theorems for the real line},
JOURNAL = {Notices Amer. Math. Soc.},
FJOURNAL = {Notices of the American Mathematical Society},
VOLUME = {15},
YEAR = {1968},
PAGES = {660},
NOTE = {Erratum in volume 16 (1969), p.~1095},
}
[3] [doi] A. Blass, “A partition theorem for perfect sets,” Proc. amer. math. soc., vol. 82, iss. 2, pp. 271-277, 1981.
[Bibtex]
@article {Blass,
AUTHOR = {Blass, Andreas},
TITLE = {A partition theorem for perfect sets},
JOURNAL = {Proc. Amer. Math. Soc.},
FJOURNAL = {Proceedings of the American Mathematical Society},
VOLUME = {82},
YEAR = {1981},
NUMBER = {2},
PAGES = {271--277},
ISSN = {0002-9939},
CODEN = {PAMYAR},
MRCLASS = {03E15 (03E05 04A20 54H05)},
MRNUMBER = {609665 (83k:03063)},
DOI = {10.2307/2043323},
URL = {http://dx.doi.org/10.2307/2043323},
}
[4] F. G. Dorais and R. Filipów, “Algebraic sums of sets in Marczewski-Burstin algebras,” Real anal. exchange, vol. 31, iss. 1, pp. 133-142, 2005/06.
[Bibtex]
@article {DoraisFilipow,
AUTHOR = {Dorais, Fran{\c{c}}ois G. and Filip{\'o}w, Rafa{\l}},
TITLE = {Algebraic sums of sets in {M}arczewski-{B}urstin algebras},
JOURNAL = {Real Anal. Exchange},
FJOURNAL = {Real Analysis Exchange},
VOLUME = {31},
YEAR = {2005/06},
NUMBER = {1},
PAGES = {133--142},
ISSN = {0147-1937},
MRCLASS = {28A05 (39A70)},
MRNUMBER = {2218194 (2007h:28002)},
MRREVIEWER = {K. P. S. Bhaskara Rao},
URL = {http://projecteuclid.org/getRecord?id=euclid.rae/1149516801},
}
[5] A. D. Taylor, “Partitions of pairs of reals,” Fund. math., vol. 99, iss. 1, pp. 51-59, 1978.
[Bibtex]
@article {Taylor,
AUTHOR = {Taylor, Alan D.},
TITLE = {Partitions of pairs of reals},
JOURNAL = {Fund. Math.},
FJOURNAL = {Polska Akademia Nauk. Fundamenta Mathematicae},
VOLUME = {99},
YEAR = {1978},
NUMBER = {1},
PAGES = {51--59},
ISSN = {0016-2736},
MRCLASS = {04A20},
MRNUMBER = {0465873 (57 \#5759)},
MRREVIEWER = {Thomas J. Jech},
URL = {http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=99},
}
[6] F. G. Dorais, R. Filipów, and T. Natkaniec, “On some properties of Hamel bases and their applications to Marczewski measurable functions,” Preprint, 2011.
[Bibtex]
@article {DoraisFilipowNatkaniec,
AUTHOR = {Dorais, Fran{\c{c}}ois G. and Filip{\'o}w, Rafa{\l} and Natkaniec, Tomasz},
TITLE = {On some properties of {H}amel bases and their applications to {M}arczewski measurable functions},
JOURNAL = {preprint},
YEAR = {2011},
}
 

Uncountable perfect graphs

I have been fascinated with perfect graphs for many years. These graphs are very intensely studied in finite combinatorics and new wonderful properties of finite perfect graphs are discovered on a regular basis. However, it is still unclear whether or how these wonderful properties might extend to the countable and uncountable cases. There are several deep questions about this. One of the most interesting question is the consistency of Galvin’s Conjecture. I recently wrote a paper on this question [1]. Since I believe this and related questions deserve more attention, here is a brief survey of known results around Galvin’s Conjecture.

… 

[1] [doi] F. G. Dorais, “A note on conjectures of F. Galvin and R. Rado,” Canad. math. bull., 2011.
[Bibtex]
@article {Dorais,
AUTHOR = {Dorais, Fran{\c{c}}ois G.},
TITLE = {A note on conjectures of {F}. {G}alvin and {R}. {R}ado},
JOURNAL = {Canad. Math. Bull.},
FJOURNAL = {Canadian Mathematical Bulletin. Bulletin Canadien de Math\'ematiques},
YEAR = {2011},
DOI = {10.4153/CMB-2011-192-8},
URL = {http://dx.doi.org/10.4153/CMB-2011-192-8},
NOTE = {to appear},
EPRINT = {1110.6563},
}