1
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$
    – François G. Dorais
    Mar 21, 2010 at 19:22

1 Answer 1

Reset to default
4
$\begingroup$

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$.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – Theo Johnson-Freyd
    Mar 21, 2010 at 18:08
  • 1
    $\begingroup$ In fact, the proof is complete without the fourth paragraph: you have shown that $F$ is not maximal. $\endgroup$
    – François G. Dorais
    Mar 21, 2010 at 20:11
  • $\begingroup$ > 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. $\endgroup$
    – Paul Crowley
    Mar 21, 2010 at 22:59
  • $\begingroup$ 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\}$ $\endgroup$
    – Paul Crowley
    Mar 21, 2010 at 23:03
  • 1
    $\begingroup$ Thank you Theo, I was throwing Zorn's lemma in without thinking it through completely. Somewhat Cargo Cult-ish. $\endgroup$
    – Mikael Vejdemo-Johansson
    Mar 22, 2010 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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