F is ultrafilter over a Boolean algebra implies that for every b, either b or not-b is in F?

[ciphergoth]

Update: made public now enough time has passed that it won't bug my non-math friends.

Hello, welcome to my new hard sums filter! Thanks for joining; if you're on and don't want to be, no problem, just let me know.

Chapter 2 of Category Theory, page 30, introduces Boolean algebras. Background: a preorder is any binary relation which is reflexive and transitive; a poset is any preorder which is antisymmetric. The text goes on to explain:

A Boolean algebra is a poset B equipped with distinguished elements 0, 1, binary operations a ∨ b of “join” and a ∧ b of “meet,” and a unary operation ¬b of “complementation.” These are required to satisfy the conditions

• 0 ≤ a
• a ≤ 1
• a ≤ c and b ≤ c iff a ∨ b ≤ c
• c ≤ a and c ≤ b iff c ≤ a ∧ b
• a ≤ ¬b iff a ∧ b = 0
• ¬¬a = a

[...] A filter in a Boolean algebra B is a nonempty subset F ⊆ B that is closed upward and under meets:

• a ∈ F and a ≤ b implies b ∈ F
• a ∈ F and b ∈ F implies a ∧ b ∈ F

A filter F is maximal if the only strictly larger filter F ⊂ F' is the “improper” filter, namely all of B. An ultrafilter is a maximal filter. 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 think I have a proof of this last assertion, but it's a bit longer than I'd expect for something that says "it is not hard to see". From the way the text just presents the defining axioms and then makes this last assertion, I'd expect that I wouldn't have to prove a lot of stuff on top of them to get there, but it seems like I do.

The backwards part I can see. If F is not an ultrafilter, then there's some strictly larger F ⊂ F' ⊂ B. Let b be any element in F' but not in F. If ¬b were in F', then b ∧ ¬b = 0 would be in F', which would mean that F' = B, a contradiction. Therefore ¬b is not in F', so neither b nor ¬b are in F.

But it's the forward part I'm having trouble with. I asked about this on mathoverflow.net, and it feels as if the answer I got took me to exactly the point I'd got to when I asked the question; the proof invites me to "consider the filter generated by F ∪ b - which is to say the smallest filter F' containing F and b" but I got stuck exactly on proving that such an F' exists.

There's an argument to this effect in the comments, and it seems persuasive but a long way from being a proof. The final sentence reads "And if it's the meet of things included by upwards closure, I may as well pick the thing at the bottom to meet with - thus I can assume it to be a b ∧ f". To turn this into a proof, I think I have to prove that if I close first over meets and then upwards, the resulting set is still closed under meets. I can do that - this is the explicit construction of F' that I started off asking for. But the wording "it is not hard to see" suggests that there must be a simpler, more direct proof that I'm missing.

Anyone see a more straightforward way? Am I over-complicating things and failing to appreciate the elegance of the proof I've already been given? Thanks!

Comments

[josington.livejournal.com]

You can explicitly define such a filter as F' = {a ∧ c : a ∈ F, b ≤ c}. This is clearly a filter over B, with F ⊂ F'. If ¬b ∈ F', we have some particular a, c satisfying the above conditions. Then ¬b ≤ c, so that ¬c ≤ b, making ¬c ≤ c, implying that c ∨ c = 1, which means that c = 1, making ¬b = a ∧ 1 = a ∈ F, a contradiction. Therefore F' is proper.

The explicit proof that F' is proper is a bit long-winded, but I think it's intuitively pretty obvious. Your mileage may vary, of course.

*wishes for LaTeX capacity for LJ*

[josington.livejournal.com]

Rereading your original post, I think I've basically reproduced what you had already. I don't think there's anything shorter than that, though.

[ciphergoth.livejournal.com]

Your expression of it seems somewhat neater. Looks like I just need to recalibrate my idea of what "not hard to see" might mean :-) thanks!

[keirf.livejournal.com]

It seems fairly trivial for filter F defined on a set S - If A and B are in F, then so is A ∧ B. Therefore if A and its complement are in F then the empty set is in F. And the empty set is a subset of all sets, which means all sets are in F, making F an improper filter.

[keirf.livejournal.com]

Incidentally, the partial ordering is defined on the power set of S, P(S), by subset inclusion (A subset of B means A smaller than B).