Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?)

share|cite|improve this question

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.

share|cite|improve this answer
Ok, how do you know that F' is in U? – Forever Mozart Dec 19 '12 at 20:43
I added an "except." We have used the fact that the complement of any $1$-element set is in the filter. – André Nicolas Dec 19 '12 at 20:50
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}). – Forever Mozart Dec 19 '12 at 21:05
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. – André Nicolas Dec 19 '12 at 21:14
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? – Cameron Buie Dec 19 '12 at 21:38

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.

share|cite|improve this answer
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. – Forever Mozart Dec 19 '12 at 21:44
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$. – Cameron Buie Dec 19 '12 at 23:05
(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. – Cameron Buie Dec 19 '12 at 23:09
Thanks, I did not understand the definition properly. One final question: "free" and "non-principal" mean the same thing, right? – Forever Mozart Dec 20 '12 at 0:12
You're correct. Some sources use one, some the other, but they mean the same thing. – Cameron Buie Dec 20 '12 at 0:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.