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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Mar 22, 2010 at 1:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .