proof of alternative characterization of ultrafilter

Proof that AB=X implies A𝒰 or B𝒰

Once we show that A𝒰 implies B𝒰, this result will follow immediately.

On the one hand, suppose that A𝒰 and that there exists a C𝒰 such that AC is empty. Then CB. Since 𝒰 is a filter and C𝒰, this implies that B𝒰.

On the other hand, suppose that A𝒰 and that AC is not empty for any C in 𝒰. Then {A}𝒰 would be a filter subbasis. The filter which it would generate would be finer than 𝒰. The fact that 𝒰 is an ultrafilterMathworldPlanetmath means that there exists no filter finer than 𝒰. This contradictionMathworldPlanetmathPlanetmath shows that, if A𝒰, then there exists a C such that AC is empty. But this would imply that CB which, in turn would imply that B𝒰.

Proof that 𝒰 is an ultrafilter.

Assume that 𝒰 is a filter, but not an ultrafilter and that AB=X implies A𝒰 or B𝒰. Since 𝒰 is not an ultrafilter, there must exist filter 𝒰 which is strictly finer. Hence there must exist A𝒰 such that A𝒰. Set B=XA. Since AB=X and A𝒰, it follows that B𝒰. Since 𝒰𝒰, it is also the case that B𝒰. But A𝒰 as well; since 𝒰 is a filter, AB𝒰. This is impossible because AB𝒰 is empty. Therefore, no such filter 𝒰 can exist and 𝒰 must be an ultrafilter.

Proof of generalization to AB=X

On the one hand, since AB=X implies AB=X, the condition AB=XA𝒰B𝒰 will also imply that 𝒰 is an ultrafilter.

On the other hand, if AB=X, there must exists AA and BB such that AB=X. If 𝒰 is assumed to be a filter, A𝒰 implies that A𝒰. Likewise, B𝒰 implies that B𝒰. Hence, if 𝒰 is a filter such that AB=X implies that either A𝒰 or B𝒰, then 𝒰 is an ultrafilter.

Proof of first proposition regarding finite unions

Let Bj=i=1jAi and let Cj=i=j+1nAi. For each i between 1 and n-1, we have BiCi=X. Hence, either Bi𝒰 or Ci𝒰 for each i between 1 and n-1. Next, consider three possibilities:

  1. 1.

    B1𝒰: Since B1=A1, it follows that A1𝒰.

  2. 2.

    Bn-1𝒰: Since Bn-1Cn-1=X, it follows that Cn-1𝒰. Because Cn-1=An, it follows that An𝒰.

  3. 3.

    B1𝒰 and Bn-1𝒰: There must exist an i{2,,n-1} such that Bi-1𝒰 and Bi𝒰. Since Bi-1𝒰, Ci-1𝒰. Since 𝒰 is a filter, Ci-1Bi𝒰. But also Ci-1Bi=Ai which implies that Ai𝒰.

This examination of cases shows that if i=1nAi=X, then there must exist an i such that Ai𝒰. It is also easy to see that this i is unique — If Ai𝒰 and Aj𝒰 and ij, then AiAj=, but this cannot be the case since 𝒰 is a filter.

Proof of second proposition regarding finite unions

There exist sets Ai such that AiAi and i=1nAi=X. By the result just proven, there exists an i such that Ai𝒰. Since 𝒰 is a filter, Ai𝒰 implies Ai𝒰. Note that we can no longer assert that i is unique because the Ai’s no longer are required to be pairwise disjoint.

Title proof of alternative characterization of ultrafilter
Canonical name ProofOfAlternativeCharacterizationOfUltrafilter
Date of creation 2013-03-22 14:42:23
Last modified on 2013-03-22 14:42:23
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 16
Author rspuzio (6075)
Entry type Proof
Classification msc 54A20