From: Mike Oliver <oliver@math.ucla.edu>
Subject: Re: Cardinal of set of filters
Date: Fri, 22 Dec 2000 14:29:56 -0800
Newsgroups: sci.math
To: Victor Porton <porton@perm.raid.ru>
Summary: [missing]

Our story so far:  Victor Porton asked for the number of filters
on a given set M.  I responded that if M had cardinality
kappa, then there were 2^2^kappa filters, and I offered a proof, in
which Victor found an error.  I looked it up in Jech and found
that while my proof was wrong, my claim was correct; it's a theorem of 
Pospíšil, and asked if there was interest in my sketching the proof.
Victor was interested, so here goes:

First note that we can replace M by kappa (that is, the elements
of M are ordinals less than kappa) and for simplicity we shall do so.
My attempted proof was to wellorder P(kappa) in order-type 2^kappa,
then create an ultrafilter by working my way through the list
deciding whether the next subset of kappa was to be in the ultrafilter
or in its complement, and then crossing off the list all subsets
of kappa about which it was now decided whether they were in the
ultrafilter. I asserted, wrongly, that this process could always be
continued for 2^kappa steps.  To see the error, note that if I come
to a singleton subset of kappa (say {alpha}), and decide to put that
set in the ultrafilter,then *all* remaining subsets of kappa must now
be crossed off the list --each will be in the ultrafilter if and only
if it contains alpha as an element.

Of course we can arrange never to choose a singleton as an element
of the ultrafilter, but we need to make sure that the same thing
doesn't happen in some more subtle way.  Suppose we've already decided
on the fate of A_beta for beta<alpha, alpha some ordinal less than
2^kappa -- we have to ask ourselves, can we be sure that there are
still decisions left to make?

If we've made decisions for some collection of subsets, then for
any finite collection Y_0, Y_1,...,Y_{n-1} of sets that we've decided
*will* be in the ultrafilter, and any finite collection
N_0,N_1,...,N_{m-1} of sets that we've decided *won't* be,
then we know that the intersection of all the Y's with the
complements of all the N's will be a set in the ultrafilter.
We would be in trouble if this set were a singleton, or even
if it were finite (only principal ultrafilters can contain
finite sets, and there are only kappa principal ultrafilters
on kappa, so at some point we're bound to run out of decisions to
make).

Suppose we could find a collection of full cardinality (i.e. 2^kappa)
of subsets of kappa, with the property that *no* intersection of
the above form could be finite?  Then in particular no such
intersection could be empty, so no matter how we made our yes-or-no
decisions on *these* subsets, we would always get a collection of
subsets having the finite intersection property.  Such a collection
can always be extended to an ultrafilter (using AC), but if we just
want a filter, we don't even need to wellorder them -- this is a little
better than my original approach, because you get that there
are 2^2^kappa filters without knowing that you can wellorder P(kappa).

So we need to find a collection C of subsets of kappa with the
property that any finite intersection of distinct sets from
C and complements of sets from C, is infinite (actually we'll
get that it has full cardinality kappa, allowing us to make
the ultrafilter uniform if we like).  Jech calls this property
"uniform independence".

Consider the set S of all ordered pairs (f,F) where f is
a *finite* subset of kappa, and F is a subset of f.  S has
cardinality kappa, so it's enough to find a full-cardinality
uniformly independent subset of S (you can then pull it back along
a bijection between kappa and S).

To each subset s of kappa, assign a subset C_s of S as follows:
C_s = { (f,F) | ( f \cap s ) \in F }.  ( \cap means "intersection).
We'll let C be the set of all C_s as s ranges over subsets of kappa.
It's easy to see that if s0 != s1 then C_s0 != C_s1, so C has full
cardinality 2^kappa.

To see that C is uniformly independent, suppose s_0,...,s_{n-1}
are such that we want C_s_i to be in the filter, and
t_0,...,t_{m-1} are such that we want the complements of
the C_t_j to be in the filter.  We want to show that
the intersection of all the C_s_i with the complements of
all the C_t_j is a nonempty set, in fact a set of cardinality
kappa.

Remember that all the s_i's are distinct from all the t_j's.
For each i,j, let alpha_ij be the least element of the symmetric
difference of s_i and t_j.  Now let f be any finite subset
of kappa containing *all* the alpha_ij (i.e. f "has enough
information" to distinguish between the "good" sets and
the "bad" sets).

We can then find an F such that (f,F) is in the desired
intersection.  We want (f,F) to be in all the C_s_i,
but not in any of the C_t_j.  So pick F to be
the set of all intersections
             f \cap s_i
for i < n.  By including these intersections we've guaranteed
that (f,F) \in C_s_i (check the definition).  But for
any t_j, the only way (f,F) could be in C_t_j is if
             f \cap s_i = f \cap t_j
for some i,j.  But we've ruled out that possibility by
including all the alpha_ij in f.

That shows that the intersection in question is nonempty;
to see it has cardinality kappa, just observe that there
are kappa choices for f.

Posted and mailed.
==============================================================================

From: Mike Oliver <oliver@math.ucla.edu>
Subject: Re: Cardinal of set of filters
Date: Fri, 22 Dec 2000 19:00:21 -0800
Newsgroups: sci.math

Mike Oliver wrote:

> Consider the set S of all ordered pairs (f,F) where f is
> a *finite* subset of kappa, and F is a subset of f.

Oops, sorry about that.  Should say

   ... and F is a *collection*of* subsets of f.