MathOverflow is a question and answer site for professional mathematicians. 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'm trying to teach myself category theory from Steve Awodey's Category Theory. Chapter 2 asserts:

It is not hard to see that a filter F is an ultrafilter just if for every element b ∈ B, either b ∈ F or ¬b ∈ F, and not both (exercise!).

I've managed to prove the backwards implication, but the forwards implication is eluding me. I'm guessing the correct approach is to consider a filter F such that there exists a b ∈ B such that neither b ∈ F or ¬b ∈ F, and construct a superset filter F' which contains b, but I can't figure out how to construct F' and prove that it's a filter. Any hints much appreciated!

share|cite|improve this question
No, you don't need the axiom of choice to prove this fact. (But, in the absence of choice, you might not have any ultrafilters on B so that the fact might be vacuously true.) – François G. Dorais Mar 21 '10 at 19:22
up vote 4 down vote accepted

Assume you have a proper filter $F$ that avoids both $b$ and $\neg b$. Then, you could consider the filter generated by $F\cup\{b\}$ - which is to say the smallest filter $F'$ containing $F$ and $b$.

Since $F$ was a proper filter it follows that $0\not\in F$.

If $0\in F'$, then this means that there is some $f\in F'$ such that $b\wedge f = 0$. Now, $\neg b=0\vee\neg b=(b\wedge f)\vee\neg b=(b\vee\neg b)\wedge(f\vee\neg b)=1\wedge(f\vee\neg b)=f\vee\neg b$. Thus $f≤\neg b$, which means that $\neg b\in F'$.

Since $\neg b\in F'$, either $\neg b\in F$ or $\neg b$ may be acquired by meets and upwards closures from $F\cup\{b\}$. Say $b\wedge f≤\neg b$ for some $f\in F$. Then $b\wedge f= b\wedge f\wedge\neg b = b\wedge\neg b\wedge f = 0\wedge f = 0$ for an $f\in F$ and by the above argument, we derive $\neg b\in F$. This is a contradiction, from which we can derive that $0\not\in F$.

Hence, $0\not\in F'$, and thus $F'$ is a proper ideal strictly containing $F$.

share|cite|improve this answer
You shouldn't need Zorn's lemma to prove the statement. If you have a maximal filter $F$, then this argument shows that for each $b$, $F$ must include either $b$ or $\neg b$. But if a proper filter $F$ includes either $b$ or $\neg b$ for each $b$, then it must be maximal: there's no more room to add any elements and keep it proper. So therefore proper filters are maximal iff they include $b$ or $\neg b$ for each $b$. Now, without Zorn, you don't know if there are any nonprinciple ultrafilters, but that's a different question. – Theo Johnson-Freyd Mar 21 '10 at 18:08
In fact, the proof is complete without the fourth paragraph: you have shown that $F$ is not maximal. – François G. Dorais Mar 21 '10 at 20:11
> If $0 \in F$, then this means that there is some $f \in F$ such that $b \wedge f=0$ If I understand properly, this assumes that if $F$ is a filter, then $F' = F \cup {b \wedge f|f \in F}$ is a filter (which would clearly then be the smallest filter containing $F$ and $b$. I can see that it's closed under meets, but I can't work out how to prove that it's closed upwards. – Paul Crowley Mar 21 '10 at 22:59
Damn, no comment preview and no comment editing? Sorry for the errors in the above markup. "If I understand properly" is the start of my text. Let's see if I can get it right this time: $F' = F \cup \{b \wedge f|f \in F\}$ – Paul Crowley Mar 21 '10 at 23:03
Thank you Theo, I was throwing Zorn's lemma in without thinking it through completely. Somewhat Cargo Cult-ish. – Mikael Vejdemo-Johansson Mar 22 '10 at 1:22

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.