applet-magic.com
Thayer Watkins
Silicon Valley
USA

 Mathematical Filters in Set Theory

## A Filter: A Special Collection of Subsets of a Set

Filters and Ultrafilters are useful mathematical constructs. (Do not bother to ask why these constructs have been given the name filter.)

Set S be a nonempty set. The collection of all subsets of S is called the Power Set of S. (Collection in this context means exactly the same as set. It is used to avoid excessive use of set.) For example, if S={a, b, c} then the power set of S, denoted P(S), is

#### {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} and the empty set ∅

Note that the empty set is considered a subset of any set and that the set itself is considered a subset.

A filter F on S is a collection of subsets of S in which two conditions hold:

• If A and B belong to the collection F then A∩B also belongs to the collection.
• If A belongs to the collection F and A is a subset of B then B also belongs to the collection. (If A⊂B then B is said to be a superset of A.)

It follows from these that the whole set S is a member of any filter.

The two conditions for defining a filter can be reduced to the one condition

#### A∩B ∈ F if and only if (iff) both A and B belong to F

For S={a, b, c} one filter is the collection

#### { {a}, {a, b}, {a, b, c} }

The power set of S is always a filter. The empty set ∅ is a special case concerning filters. Because ∅ is a subset of any subset of S and hence any subset of S is a superset of ∅ it follows that if ∅ belongs to a filter then all subsets belong and hence the filter has to be the power set of S. The power set of S might be called a trivial filter. A filter that does not contain the empty set ∅ is called a proper filter.

## Ultrafilters

A filter of S such that for any subset A either A belongs to the filter or the complement of A in S belongs to the filter is called an ultrafilter. An ultrafilter U is then such that

• A∩B ∈ U if and only if (iff) A∈U and B∈U..
• A∪B ∈ U if and only if (iff) A∈U or B∈U..
• Ac=(S-A) ∈ U iff A∉U.

Because an ultrafilter contains only A or its complement the trivial filter of the power set cannot be an ultrafilter. Thus an ultrafilter is a proper filter.

Consider the collection of subsets of S that contain an element a; i.e., all of the supersets of a and only the supersets of a. The example given above for a filter on the set S={a, b, c}

#### { {a}, {a, b}, {a, b, c} }

is such a collection. Note that the collection does not contain complement of {a}, {b, c}, or the complement of {a, b} which is {c}. This filter satisfies the conditions for being an ultrafilter. In general, the supersets of an element of S constitute an ultrafilter on S. It is called the principal ultrafilter generated by that element.