Skip to Main Content

MAD Families and the Ramsey Property

Carlos A. Di Prisco

Communicated by Notices Associate Editor Antonio Montalbán

Article cover

1. Almost Disjoint Families

The study of collections of sets of natural numbers poses many interesting questions connected, sometimes surprisingly, to other areas of mathematics. Identifying sets of natural numbers with real numbers is often a way to establish those connections.

It is well known that the axiom of choice or its equivalents can be used to produce badly behaved sets of real numbers, for example non-Lebesgue-measurable or without the Baire property. One of the leading ideas in the development of set theory has been to show that those pathological sets are not definable in simple terms, and their existence cannot be proved without the use of some form of the axiom of choice. We will illustrate this with an example related to almost disjoint families.

Two infinite sets of natural numbers are almost disjoint if their intersection is finite. A family of infinite subsets of is said to be almost disjoint if its elements are pairwise almost disjoint.

Given any infinite partition of into infinite sets, say, , , …, a new infinite set of natural numbers can be formed taking, for example, the first element of each . This new set and the elements of the partition form a larger family which is almost disjoint. Finite partitions of cannot be extended like this. A finite partition of into infinite sets is thus maximal in the sense that it is not properly contained in a larger almost disjoint family.

Any infinite almost disjoint family of infinite subsets of is contained in a maximal almost disjoint family. Applying Zorn’s lemma to the collection of all almost disjoint families that contain the given almost disjoint family we obtain a maximal extension. The question now is if we can prove the existence of infinite maximal almost disjoint families of subsets of without using Zorn’s lemma or some form of the axiom of choice.

Infinite maximal almost disjoint families of subsets of are usually called MAD families, and they have been studied extensively.

A standard diagonalization argument shows that a countable almost disjoint family of subsets of is not a MAD family. If is an almost disjoint family of infinite subsets of , define inductively a sequence of natural numbers taking , , and . If have been defined, let be such that . This is possible since the intersection of is finite. The set is infinite and has finite intersection with each . So, if a family is MAD, it must be uncountable.

An example of an almost disjoint family of uncountable cardinality can be constructed as follows. Consider the (countable) set of all finite sequences of ’s and ’s. Ordering by extension gives this set the structure of the complete binary tree. Each infinite branch through the tree is an infinite set of finite sequences linearly ordered by extension, and corresponds to an infinite sequence of ’s and ’s. So, the set of infinite branches is in one-one correspondence with , the set of all functions from to , which has the cardinality of the real line . Notice that two different branches coincide only on a finite initial segment, so the set of branches is an almost disjoint family of finite binary sequences of cardinality . This family fails to be maximal, as, for example, the set meets each infinite branch in at most one element. Using any bijection between and , this example can be turned into an almost disjoint family of infinite subsets of .

The use of some form of the axiom of choice is unavoidable to prove the existence of MAD families, as it was shown by A. R. D. Mathias in the nineteen seventies in an article titled “Happy families” (5). Mathias explored the relationship between MAD families and a combinatorial property, called the Ramsey property of collections of infinite sets of natural numbers, using certain ideals of sets of natural numbers. We say more about this below.

2. Ideals and Their Complements

Before defining the Ramsey property and presenting its relation to MAD families, we will consider collections of subsets of called ideals, and also their complements.

An ideal of sets is a collection of sets closed under subsets and under finite unions. The elements of an ideal can be considered, in some sense, small sets: a subset of a small set is also small; and the union of two small sets is still a small set.

The collection of all finite subsets of is clearly an ideal. More elaborate examples appear in different guises. Consider a divergent series of real numbers (you could take ); then, the collection is an ideal of subsets of .

Another example is this: let be a topological space and ; then, the collection is an ideal of subsets of .

Other interesting examples related to our topic can be constructed from almost disjoint families. Given an infinite family , the ideal generated by , that is, the family

is almost contained in if is finite.

has interesting properties that will be analyzed below.

A family of subsets of is a coideal if its complement in is an ideal. Thus, is a coideal if it satisfies:

(i)

If and , then .

(ii)

If , then or .

We will only consider here ideals of subsets of that contain all finite subsets of ; and we will be specifically interested in ideals with a rich complement. This richness often means closure under certain operations. For our purposes, we will be interested in coideals closed under diagonalizations in the following sense. If is a decreasing sequence of infinite subsets of , is a diagonalization of the sequence if for every . Equivalently, for every , where is the increasing enumeration of .

Notice that if is a diagonalization of the sequence , then is almost contained in each , i.e., is finite for every and if , all elements of above are in .

A coideal closed under diagonalizations is called selective. In this case, every decreasing sequence of elements of has a diagonalization in .

Selective coideals were called happy families by Mathias in his study of the Ramsey property and maximal almost disjoint families of subsets of (5).

It will be convenient to introduce some notation. denotes the collection of infinite subsets of the set ; and denotes the collection of its finite subsets. If , is the set of subsets of with exactly elements.

It is easy to verify that is a selective coideal. If is a decreasing sequence of elements of , one can construct a diagonalization inductively taking the first element of , and for each taking an element with .

Another example is the complement of the ideal defined above for an infinite almost disjoint family .

Theorem 1 (Mathias, 5).

If is an infinite almost disjoint family, the coideal is a selective coideal.

Notice that if is a MAD family, then a set is in the associated coideal if and only if it has infinite intersection with infinitely many elements of . This observation can be verified with little effort and will be used below when discussing the Ramsey property.

The following lemma is a deep result proved by F. Galvin, originally for the coideal , which will be used in the next section to show that selective coideals have homogeneous sets for all colorings of .

First, we give some definitions. For a family and , let .

Given and , and the increasing enumeration of , we say that is an initial segment of if there is such that . Also,

Lemma 2 (Galvin’s lemma for selective coideals).

Let be a selective coideal, and a collection of finite subsets of . Then, for every there is such that either

(i)

no finite subset of belongs to (i.e., ), or

(ii)

every infinite subset of has an initial segment in .

The proof of this lemma uses a technique called combinatorial forcing that has been important in the development of combinatorial set theory. We include it here for its beauty and to give a good sample of a combinatorial argument. The reader eager to get ahead can skip it.

Proof.

Fix a collection of finite subsets of for the rest of the proof. Let and . We say that accepts if every has an initial segment in ; and rejects if there is no that accepts . We say that decides if it either accepts or rejects .

It follows from the definitions that:

(i)

If accepts , then every accepts .

(ii)

If rejects , then every rejects .

(iii)

For every and every , there is that decides .

(iv)

If accepts , then accepts for every .

(v)

If rejects , then .

Claim 3.

There is that decides each of its finite subsets.

Proof.

Construct a decreasing sequence of elements of such that if , then and decides , and for every , decides every . This can be done applying (iii). As is selective, there is a diagonalization of the sequence , , … in .

If and is the first element of above , then , and so decides . It follows that decides .

We now finish the proof of the lemma. Let decide each of its finite subsets. If accepts , then every infinite subset of has an initial segment in .

Suppose that rejects . Construct a decreasing sequence of elements of such that if , then and rejects for every and every . If is a diagonalization of the sequence , , …, then rejects each of its finite subsets. Then , because if is contained in , then rejects (since rejects ), but this is impossible since any has an initial element in , namely , and so accepts , a contradiction.

3. The Ramsey Property

F. P. Ramsey proved in 1930 a theorem that originated a whole area of combinatorics now called Ramsey theory. This theorem was proved to solve a problem in mathematical logic, and it has many interesting applications in several areas of mathematics.

Theorem 4 (Ramsey, 1930; see 12, Theorem 1.3).

Given positive integers and , for every function there is an infinite such that is constant on .

A set as in the theorem is said to be homogeneous for . It is customary to call such a function, and the partition of it induces, a coloring of , and to say that the set is monochromatic for this coloring.

Consider the simplest non-trivial version of Ramsey’s theorem, for . This version implies, for example, that every sequence of real numbers with infinite range has a monotone subsequence.

In terms of graphs, this version says that any infinite graph has an infinite complete subgraph or an infinite independent set of vertices.

Sometimes it is needed to find a homogeneous set for a coloring in a certain class of subsets of . For this reason, it is interesting to determine what conditions on a family of infinite subsets of imply that it contains homogeneous sets of every .

A coideal on that contains homogeneous sets for every coloring is called a Ramsey coideal.

The following is a consequence of Lemma 2.

Theorem 5.

Every selective coideal is a Ramsey coideal.⁠Footnote2 Farah, in 3, introduced the notion of semiselective coideals. Semiselectivity of a coideal is a property weaker than selectivity, but strong enough so that Lemma 2 holds for semiselective; therefore every semiselective co- ideal is a Ramsey coideal. A comprehensive presentation of these results appears in 12. There are Ramsey coideals that are not semiselective, and semiselective coideals that are not selective. Nevertheless, for ultrafilters on , these properties are equivalent, since any Ramsey ultrafilter is selective.

Proof.

Let be a selective coideal, and . Let be , and apply Lemma 2 to this family of pairs. Then there is such that does not contain any element of and therefore takes constant value on ; or every infinite subset of starts with a pair in and so takes constant value on .

Having considered homogeneous sets for finite partitions of , it is natural to consider homogeneous sets for partitions of . A set determines a partition of in two pieces, and its complement; an infinite set is homogeneous for this partition if all of its infinite subsets belong to the same side of the partition. This motivates the following definitions.

Definition 6.

We say that is Ramsey (or has the Ramsey property) if there is such that or

If is a coideal and , we say that is -Ramsey if there is such that or .

In other words, a set is -Ramsey if contains a homogeneous set for the partition of determined by ; and is Ramsey if it is -Ramsey.

Using the axiom of choice one can find a set that is not Ramsey, but a set like this is not definable in simple terms. If is given the topology inherited from the product topology of (where is taken with the discrete topology), every topologically simple subset of is Ramsey.⁠Footnote3 with this topology is (homeomorphic to) the Baire space. Let us make this more precise. The collection of subsets of of the form is an initial segment of the increasing enumeration of , where is a finite subset of , is a basis for this topology. The collection of Borel subsets of is the smallest collection containing the basic sets () and closed under countable unions and complements.

Theorem 7 (Galvin-Prikry, 4).

Every Borel subset of is Ramsey.

Proof.

Notice that if is open (in the topology inherited from the product topology of , then there is a family of finite subsets of such that if and only if has an initial segment in . Then, the theorem follows for open sets from Galvin’s lemma applied to the coideal .

To complete the proof it is enough to show that the collection of Ramsey subsets of is closed under complements and under countable unions, and therefore it contains all the Borel sets. This is by no means a trivial task and we will skip it.

This theorem can be extended to the -Ramsey property for a semiselective coideal. Moreover, any analytic⁠Footnote4 A set of real numbers is analytic if it is the continuous image of a Borel set. There are analytic sets that are not Borel. set is Ramsey (Silver, 10), and -Ramsey for every selective coideal (Mathias, 5), or even for semiselective (Farah, 3). Ellentuck gave an elegant topological characterization of the Ramsey property. The reader can consult Todorcevic’s book (12, Chapter 7) for a complete presentation of this theory.

The following remarkable relation between MAD families and the Ramsey property was established by Mathias.

Lemma 8 (Mathias, 5).

Let be an infinite almost disjoint family. Then is maximal if and only if the associated coideal is not -Ramsey.

Proof.

If is a MAD family, then, by the observation made after Theorem 1, every contains an infinite subset not in .

And if is not maximal, take almost disjoint from every element of . Then, every infinite subset of is in the coideal .

From Lemma 8 and the fact that every analytic set is -Ramsey for every selective coideal , Mathias concluded that there are no analytic MAD families.

4. All Sets Can Be Ramsey

In this section we examine the possibility of all sets of reals having the Ramsey property. The axiom of choice rules this out since it implies the existence of non-Ramsey sets, but there are models of set theory which do not satisfy the axiom of choice and where all subsets of have the Ramsey property.⁠Footnote5 Axiomatic set theory was developed by Zermelo and Fraenkel to circumvent the paradoxes discovered in the early 20th century. This axiomatic theory is known as ZF, Zermelo-Fraenkel set theory. If the axiom of choice is added, it is denoted by ZFC, and it provides a basis for conventional mathematics. Some of the axioms postulate the existence of certain sets; for example, there exists an infinite set; some other axioms are of the form “If A is a set, then there is a set B with certain properties” (for example, the power set axiom: if A is a set, then there is a set whose elements are the subsets of A); other axioms have a more technical character. A model of set theory is a collection of sets that satisfies the axioms. Not all mathematical questions can be settled from the axioms. A statement that is true in some models of set theory and false in some other models cannot be proved nor disproved from the axioms. The Continuum Hypothesis is such a statement.

Solovay (11) constructed a model of set theory where every set of real numbers is Lebesgue measurable, has the property of Baire, and, if uncountable, contains a perfect subset. Of course, the axiom of choice does not hold in this model, although a weak form of the axiom called dependent choice (DC) is true in the model. The construction of this model starts assuming the existence of an inaccessible cardinal,⁠Footnote6 A cardinal is inaccessible if it is uncountable, it cannot be reached by unions of less than sets each of them of size less than , and if then . The existence of an inaccessible cardinal cannot be proved from the axioms of ZFC. and combines the use of forcing⁠Footnote7 Forcing is a technique used to prove independence results in set theory. It was introduced by Paul Cohen in 1963 to prove the independence of the continuum hypothesis and the axiom of choice from the axioms of Zermelo-Fraenkel set theory. with another important technique for constructing models of set theory, due to Gödel, which consists in taking the sets of a model which are definable in some precise sense. With this in mind, we can describe Solovay’s construction as this: given a model with an inaccessible cardinal , the forcing technique is used to construct a wider model where all infinite cardinals below become countable, making the first uncountable cardinal of the new model; then, within this new model, take the class of all sets constructible from the reals.

Solovay asked if the hypothesis of the existence of an inaccessible cardinal could be avoided to construct a model where all sets of real numbers are Lebesgue measurable, but it was shown by Shelah 9 fourteen years later that the existence of inaccessible cardinals is necessary to obtain such a model. This result revealed a deep and unexpected relation between a property of sets of real numbers and large cardinals. Surprisingly, this hypothesis is not necessary to get a model of set theory where all sets of real numbers have the Baire property (see 9).

In 5, Mathias proved that in Solovay’s model every subset of is Ramsey. It has remained open if the inaccessibility hypothesis is necessary in this case.

Using a stronger large cardinal hypothesis Mathias reached a stronger conclusion. Assuming the existence of a Mahlo cardinal⁠Footnote8 The existence of a Mahlo cardinal is a stronger large cardinal hypothesis than the existence of an inaccessible cardinal. A Mahlo cardinal is inaccessible and has many inaccessible cardinals below it. a similar construction, first using forcing to obtain a wide model where is the first uncountable cardinal, and then considering the inner model , gives a model of set theory where every is -Ramsey for every selective coideal of the wide model. As a consequence, there are no MAD families in this inner model. The usual axioms of set theory hold in this inner model but not the axiom of choice. It follows that the existence of a MAD family cannot be proved from the axioms of set theory without the axiom of choice.

A natural question is then if there are MAD families in Solovay’s original model. This question was answered recently by Törnquist 13. Using a combinatorial argument he showed that there are no MAD families in the traditional Solovay model.

Neeman and Norwood 6 proved a strengthening of Törnquist’s result by showing that in Solovay’s model (obtained using an inaccessible cardinal) every set of reals is -Ramsey for every selective coideal . From this follows, as we have seen, that there are no MAD families in this model.

Other interesting partition properties hold in Solovay’s model. For example, the following parametrization of the Ramsey property (see 12).

Let denote the Baire space, that is, the set of all functions from to with the product topology.

For every there is a perfect⁠Footnote9 A subset of is perfect if it is non-empty, closed, and has no isolated points. Any perfect subset of has the cardinality of the continuum. subset and such that is constant on .

A function determines for each a partition of into two parts. The property above means that there is a perfect set and a set that is homogeneous simultaneously for all the partitions determined by the elements of .

As a final comment, we mention without any details a couple of points about the axiom of determinacy (AD) and the Ramsey property.

For every set of infinite sequences of natural numbers define a game as follows. Two players and alternate playing natural numbers. Player plays , then player plays , then player plays , and so on. Player wins if the infinite sequence they form belongs to ; otherwise, wins. A winning strategy for is a function , from the set of finite sequences of natural numbers to such that wins any run of the game in which and for every . A winning strategy for player is defined analogously.

A set is determined if one of the players has a winning strategy for the game .

The axiom of determinacy, AD, states that every set is determined. AD has become a central topic of contemporary set theory due to its interesting consequences and its correlation to large cardinals.

AD implies that every set of reals is Lebesgue measurable and has other regularity properties, and so it is incompatible with the axiom of choice. It is an open problem if AD implies that every set of real numbers is Ramsey. Prikry 7 proved that this is true for , a strong form of determinacy. Neeman and Norwood give in 6 a partial answer to the question if AD implies that there are no MAD families 13. They show that a form of AD called implies that there are no MAD families. It is not known if AD and are equivalent. Schrittesser and Törnquist 8 have shown, using a weak choice principle, that if all sets are Ramsey, there are no MAD families.

References

[1]
Joan Bagaria and Carlos A. Di Prisco, Parameterized partition relations on the real numbers, Arch. Math. Logic 48 (2009), no. 2, 201–226, DOI 10.1007/s00153-009-0121-y. MR2487224Show rawAMSref\bib{BDP}{article}{ author={Bagaria, Joan}, author={Di Prisco, Carlos A.}, title={Parameterized partition relations on the real numbers}, journal={Arch. Math. Logic}, volume={48}, date={2009}, number={2}, pages={201--226}, issn={0933-5846}, review={\MR {2487224}}, doi={10.1007/s00153-009-0121-y}, } Close amsref.
[2]
C. A. Di Prisco and S. Todorcevic, Souslin partitions of products of finite sets, Adv. Math. 176 (2003), no. 1, 145–173, DOI 10.1016/S0001-8708(02)00064-6. MR1978344Show rawAMSref\bib{DPT}{article}{ author={Di Prisco, C. A.}, author={Todorcevic, S.}, title={Souslin partitions of products of finite sets}, journal={Adv. Math.}, volume={176}, date={2003}, number={1}, pages={145--173}, issn={0001-8708}, review={\MR {1978344}}, doi={10.1016/S0001-8708(02)00064-6}, } Close amsref.
[3]
Ilijas Farah, Semiselective coideals, Mathematika 45 (1998), no. 1, 79–103, DOI 10.1112/S0025579300014054. MR1644345Show rawAMSref\bib{Fa}{article}{ author={Farah, Ilijas}, title={Semiselective coideals}, journal={Mathematika}, volume={45}, date={1998}, number={1}, pages={79--103}, issn={0025-5793}, review={\MR {1644345}}, doi={10.1112/S0025579300014054}, } Close amsref.
[4]
Fred Galvin and Karel Prikry, Borel sets and Ramsey’s theorem, J. Symbolic Logic 38 (1973), 193–198, DOI 10.2307/2272055. MR337630Show rawAMSref\bib{GaPr}{article}{ author={Galvin, Fred}, author={Prikry, Karel}, title={Borel sets and Ramsey's theorem}, journal={J. Symbolic Logic}, volume={38}, date={1973}, pages={193--198}, issn={0022-4812}, review={\MR {337630}}, doi={10.2307/2272055}, } Close amsref.
[5]
A. R. D. Mathias, Happy families, Ann. Math. Logic 12 (1977), no. 1, 59–111, DOI 10.1016/0003-4843(77)90006-7. MR491197Show rawAMSref\bib{Ma}{article}{ author={Mathias, A. R. D.}, title={Happy families}, journal={Ann. Math. Logic}, volume={12}, date={1977}, number={1}, pages={59--111}, issn={0003-4843}, review={\MR {491197}}, doi={10.1016/0003-4843(77)90006-7}, } Close amsref.
[6]
Itay Neeman and Zach Norwood, Happy and mad families in , J. Symb. Log. 83 (2018), no. 2, 572–597, DOI 10.1017/jsl.2017.85. MR3835078Show rawAMSref\bib{NeNo}{article}{ author={Neeman, Itay}, author={Norwood, Zach}, title={Happy and mad families in $L(\mathbb {R})$}, journal={J. Symb. Log.}, volume={83}, date={2018}, number={2}, pages={572--597}, issn={0022-4812}, review={\MR {3835078}}, doi={10.1017/jsl.2017.85}, } Close amsref.
[7]
Karel Prikry, Determinateness and partitions, Proc. Amer. Math. Soc. 54 (1976), 303–306, DOI 10.2307/2040805. MR453540Show rawAMSref\bib{Pr}{article}{ author={Prikry, Karel}, title={Determinateness and partitions}, journal={Proc. Amer. Math. Soc.}, volume={54}, date={1976}, pages={303--306}, issn={0002-9939}, review={\MR {453540}}, doi={10.2307/2040805}, } Close amsref.
[8]
David Schrittesser and Asger Törnquist, The Ramsey property implies no mad families, Proc. Natl. Acad. Sci. USA 116 (2019), no. 38, 18883–18887, DOI 10.1073/pnas.1906183116. MR4012549Show rawAMSref\bib{ST}{article}{ author={Schrittesser, David}, author={T\"{o}rnquist, Asger}, title={The Ramsey property implies no mad families}, journal={Proc. Natl. Acad. Sci. USA}, volume={116}, date={2019}, number={38}, pages={18883--18887}, issn={0027-8424}, review={\MR {4012549}}, doi={10.1073/pnas.1906183116}, } Close amsref.
[9]
Saharon Shelah, Can you take Solovay’s inaccessible away?, Israel J. Math. 48 (1984), no. 1, 1–47, DOI 10.1007/BF02760522. MR768264Show rawAMSref\bib{Sh}{article}{ author={Shelah, Saharon}, title={Can you take Solovay's inaccessible away?}, journal={Israel J. Math.}, volume={48}, date={1984}, number={1}, pages={1--47}, issn={0021-2172}, review={\MR {768264}}, doi={10.1007/BF02760522}, } Close amsref.
[10]
Jack Silver, Every analytic set is Ramsey, J. Symbolic Logic 35 (1970), 60–64, DOI 10.2307/2271156. MR332480Show rawAMSref\bib{Si}{article}{ author={Silver, Jack}, title={Every analytic set is Ramsey}, journal={J. Symbolic Logic}, volume={35}, date={1970}, pages={60--64}, issn={0022-4812}, review={\MR {332480}}, doi={10.2307/2271156}, } Close amsref.
[11]
Robert M. Solovay, A model of set-theory in which every set of reals is Lebesgue measurable, Ann. of Math. (2) 92 (1970), 1–56, DOI 10.2307/1970696. MR265151Show rawAMSref\bib{So}{article}{ author={Solovay, Robert M.}, title={A model of set-theory in which every set of reals is Lebesgue measurable}, journal={Ann. of Math. (2)}, volume={92}, date={1970}, pages={1--56}, issn={0003-486X}, review={\MR {265151}}, doi={10.2307/1970696}, } Close amsref.
[12]
Stevo Todorcevic, Introduction to Ramsey spaces, Annals of Mathematics Studies, vol. 174, Princeton University Press, Princeton, NJ, 2010, DOI 10.1515/9781400835409. MR2603812Show rawAMSref\bib{To}{book}{ author={Todorcevic, Stevo}, title={Introduction to Ramsey spaces}, series={Annals of Mathematics Studies}, volume={174}, publisher={Princeton University Press, Princeton, NJ}, date={2010}, pages={viii+287}, isbn={978-0-691-14542-6}, review={\MR {2603812}}, doi={10.1515/9781400835409}, } Close amsref.
[13]
Asger Törnquist, Definability and almost disjoint families, Adv. Math. 330 (2018), 61–73, DOI 10.1016/j.aim.2018.03.005. MR3787540Show rawAMSref\bib{Tor}{article}{ author={T\"{o}rnquist, Asger}, title={Definability and almost disjoint families}, journal={Adv. Math.}, volume={330}, date={2018}, pages={61--73}, issn={0001-8708}, review={\MR {3787540}}, doi={10.1016/j.aim.2018.03.005}, } Close amsref.

Carlos A. Di Prisco is a professor of mathematics at the Universidad de Los Andes. His email address is ca.di@uniandes.edu.co.

Article DOI: 10.1090/noti2314

Credits

Opening image is courtesy of Dmitry Volkov via Getty.

Photo of Carlos A. Di Prisco is courtesy of Carlos A. Di Prisco.