4
$\begingroup$

I need to show that if $U$ is a free ultrafilter on $\mathbb N$, then

($A \in U$ and $F \subseteq \mathbb N$ finite) $\implies (A\Delta F) \in U$.

To show this do you need maximality? (Would the same hold for any non-principal/free filter; one such that the intersection of all its sets is empty?)

2 Answers 2

4

The complement $F'$ of our finite set is in $U$, because $U$ is non-principal. It follows that $A\cap F'\in U$. But the symmetric difference contains $A\cap F'$. We have not used maximality, except for the assertion that the complement of any $1$-element set is in the filter.

  • 0
    Ok, how do you know that F' is in U?2012-12-19
  • 0
    I added an "except." We have used the fact that the complement of any $1$-element set is in the filter.2012-12-19
  • 0
    Ok, I see why "the complement of any 1-element set is in the filter" would suffice. But maybe you don't need maximality... Suppose X\{x} not in U, for some x. Then for all S in U, x must be in S (S cannot be a subset of X\{x}).2012-12-19
  • 1
    The answer sketched a proof that from complements of $1$-element sets one can get the result. (By finite intersection we can get complement of any finite set.) And we *need* complements of $1$-element sets, because if we pick $A=\mathbb{N}$ and $F$ a one element set, then the symmetric difference is precisely the complement of that $1$-element set.2012-12-19
  • 0
    Given a non-principal filter $U$ on $\Bbb N$, why is it necessarily the case that complements of singletons are in the filter? Or are you simply reducing the maximality condition to the (possibly strictly) weaker assumption that complements of singletons are in the filter?2012-12-19
  • 0
    It is strictly a lot weaker. All we need to do is to add to the filter base the complements of singletons.2012-12-19
  • 0
    Certainly not, it is not true. Take for example a nice filter $V$ on the evens. Now make a filter $U$ on $\mathbb{N}$ by saying that $X\in V$ iff $X$ is the union of an element of $V$ and *all* the odds. Then the complement of $\{1\}$ is not in $U$.2012-12-19
  • 0
    Fantastic! Thank you very much. You've helped me realize a false assumption I'd been making about free filters--namely, that if $F$ is a free filter, then $\bigcap F=\emptyset$.2012-12-19
1

It's a nice result that an ultrafilter on an infinite set $X$ is non-principal if and only if every cofinite subset of $X$ is a member of the ultrafilter. Consequently, for every finite $F\subseteq\Bbb N$, we have $(\Bbb N\smallsetminus F)\in U$, so $A\cap(\Bbb N\smallsetminus F)\in U$, and since $A\cap(\Bbb N\smallsetminus F)\subseteq A\Delta F$, then $(A\Delta F)\in U$.

We don't need that whole result--only that non-principality of a filter implies that every cofinite subset of $\Bbb N$ is a member of the filter. If we can prove that this holds for arbitrary filters (not just ultrafilters), then maximality won't be necessary at all. I suspect, however, that this may not hold in general. I'll think on it and see if I can come up with another way to get there avoiding maximality.

  • 0
    I think I proved this in the comments below: Let F be a free filter on X. As Mr. Nicolas points out, to show F contains every cofinite subset, it suffices to show F contains complements of singletons. Suppose X\{x} not in F for some x. Then for all S in F, S cannot be a subset of X\{x} (else X\{x} is in F). So x must be in S (for each S) contradicting F free.2012-12-19
  • 0
    Actually, knowing that $x\in S$ for all $S\in F$ *doesn't* imply that $F$ isn't free. We **can't** actually show that free filters necessarily contain every cofinite subset. As an example (credit to Andre for this one), let $E$ denote the even natural numbers, suppose $V$ is a free filter on $E$--meaning $V$ is a non-empty set of subsets of $E$ with no $\subseteq$-least member--and define $$U=\bigl\{A\cup(\Bbb N\smallsetminus E):A\in V\bigr\}.$$ It can be shown that $U$ is a free filter on $\Bbb N$, but $1\in S$ for all $S\in U$.2012-12-19
  • 0
    (cont'd) Andre was actually pointing out that we need the additional assumption that the given free filter has every cofinite subset as a member, or we can't draw the desired conclusion. This is a strictly weaker assumption than maximality, but we do need it if we're working with arbitrary filters. *If* we're working with a free filter $F$ such that $\bigcap F=\emptyset$, then we *don't* need this assumption, but this isn't necessarily true of *all* free filters, as the above example shows.2012-12-19
  • 0
    Thanks, I did not understand the definition properly. One final question: "free" and "non-principal" mean the same thing, right?2012-12-20
  • 0
    You're correct. Some sources use one, some the other, but they mean the same thing.2012-12-20
  • 0
    I did find this however:A filter is said to be a free filter if the intersection of all of its members is empty. A principal filter is not free. Since the intersection of any finite number of members of a filter is also a member, no filter on a finite set is free, and indeed is the principal filter generated by the common intersection of all of its members. A nonprincipal filter on an infinite set is not necessarily free.2012-12-20
  • 0
    So some take "free" just to mean the intersection is empty, and "non-principle" to mean not 'generated' by a smallest nonempty set. Although in another source they are the same. So frustrating.2012-12-20
  • 0
    Wow. That's annoying....2012-12-20
  • 0
    Sadly, that's more common than you might think. I've run into [even worse terminology issues](http://math.stackexchange.com/questions/191588/problem-with-tree-definitions) than that.2012-12-20