Intersecting families and definability

I have made some changes to my webpage and now my papers can be found here, on a page in this blog.

I have updated my paper Defining small sets from \kappa-cc families of sets, joint with Clemens, Conley and Miller. I would like to mention one of the questions we leave open.

Consider a family {\mathcal A} of sets and let X=\bigcup{\mathcal A}. We say that {\mathcal A} is intersecting iff any two members of {\mathcal A} share at least an element of X. In our paper we are interested in how definability conditions restrict the size of intersecting families. In particular we show that, even if {\mathcal A} and X are infinite, if all the members of {\mathcal A} are finite, then from {\mathcal A} we can define a finite subset of X.

Let n be such that there is a set in {\mathcal A} of size at most n. Then our arguments also show that there is a finite intersecting family {\mathcal A}'\subseteq[X]^{\le n} definable from {\mathcal A}, and we find upper bounds on how large such {\mathcal A}' is.

Say that {\mathcal A} is n-minimal iff {\mathcal A}\subseteq[X]^{\le n} is intersecting and any intersecting {\mathcal A}'\subseteq[X]^{\le n} definable from {\mathcal A} is at least as large as {\mathcal A} itself. It follows that there is a finite bound \psi(n) on how large such a family {\mathcal A} can be.

Question. Is \psi a (strictly) increasing function?

We can show that \psi(n)<\psi(2n) and a few similar results, but whether \psi is monotone is still open.

[Update, April 23, 2010: To reflect a few recent changes that resulted in a companion paper dealing with infinite sets, we have changed the title to Defining non-empty small sets from families of finite sets.]

Advertisements

One Response to Intersecting families and definability

  1. […] and I have just submitted to Fundamenta Mathematicae the second part of a paper I mentioned here a while ago. The preprint is available at my papers […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: