By an old result of Mathias, there are no mad families in the Solovay model constructed by the Levy collapse of a Mahlo cardinal. By a recent result of Törnquist, the same is true in the classical model of Solovay as well. In a recent paper, we show that ZF+DC+"there are no mad families" is actually equiconsistent with ZFC. I'll present the ideas behind the proof in the first part of the talk.

In the second part of the talk, I'll discuss the definability of maximal eventually different families and maximal cofinitary groups. In sharp contrast with mad families, it turns out that Borel MED families and MCGs can be constructed in ZF. Finally, I'll present a general problem in Borel combinatorics whose solution should explain the above difference between mad and maximal eventually different families, and I'll show how large cardinals must be involved in such a solution. This is joint work with Saharon Shelah.