Filter (mathematics)

From Academic Kids

In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in topology. The dual notion of a filter is an ideal.

Filters were introduced by Henri Cartan in 1937 and subsequently used by Bourbaki in their book Topologie Générale. An equivalent notion called net was developed in 1922 by E. H. Moore and H. L. Smith.

Contents

General definition

A non-empty subset F of a partially ordered set (P,≤) is a filter, if the following conditions hold:

  1. For every x, y in F, there is some element z in F, such that z ≤ x and z ≤ y. (F is a filter base)
  2. For every x in F and y in P, x ≤ y implies that y is in F. (F is an upper set)

A filter is proper if it is not equal to the whole set P.

While the above definition is the most general way to define a filter for arbitrary posets, it was originally defined for lattices only. In this case, the above definition can be characterized by the following equivalent statement: A non-empty subset F of a lattice (P,≤) is a filter, iff it is an upper set that is closed under finite meets (infima), i.e., for all x, y in F, we find that x ^ y is also in F.

The smallest filter that contains a given element p is a principal filter and p is a principal element in this situation. The principal filter for p is just given by the set {x in P | p ≤ x} and is denoted by prefixing p with an upward arrow.

The dual notion of a filter, i.e. the concept obtained by reversing all ≤ and exchanging ^ with v, is ideal. Because of this duality, the discussion of filters usually boils down to the discussion of ideals. Hence, most additional information on this topic (including the definition of maximal filters and prime filters) is to be found in the article on ideals. There is a separate article on ultrafilters.

Filter on a set

A special case of a filter is a filter defined on a set. Given a set S, a partial ordering ⊆ can be defined on the powerset P(S) by subset inclusion, turning (P(S),⊆) into a lattice. A filter F on S is then a subset of P(S) with the following properties:

  1. S is in F. (F is non-empty)
  2. The empty set is not in F. (F is proper)
  3. If A and B are in F, then so is their intersection. (F is closed under finite joins)
  4. If A is in F and A is a subset of B, then B is in F, for all subsets B of S. (F is an upper set)

A filter base is a subset B of P(S) with the following properties

  1. The intersection of any two sets of B contains a set of B
  2. B is non-empty and the empty set is not in B

A filter base B can be turned into a filter by including all sets of P(S) which contain a set of B.

Given a subset T of P(S) we can ask whether there exists a smallest filter F containing T. Such a filter exists if and only if the finite intersection of subsets of T is non-empty. We call T a subbase of F and say F is generated by T. F can be constructed by taking all finite intersections of T which is then filter base for F.

Examples

  • A simple example of a filter is the set of all subsets of S that include a particular subset C of S. Such a filter is called the principal filter generated by C.
  • The Fréchet filter on an infinite set S is the set of all subsets of S that have finite complement.

Filters in model theory

For any filter F on a set S, the set function defined by

<math>

m(A)=\left\{ \begin{matrix} \,1 & \mbox{if }A\in F \\ \,0 & \mbox{if }S\setminus A\in F \\ \,\mbox{undefined} & \mbox{otherwise} \end{matrix} \right. <math> is finitely additive -- a "measure" if that term is construed rather loosely. Therefore the statement

<math>\left\{\,x\in S: \varphi(x)\,\right\}\in F<math>

can be considered somewhat analogous to the statement that φ holds "almost everywhere". That interpretation of membership in a filter is used (for motivation, although it is not needed for actual proofs) in the theory of ultraproducts in model theory, a branch of mathematical logic.

Filters in topology

In topology and analysis, filters are used to define convergence in a manner similar to the role of sequences in a metric space.

Given a point x the set of all neighbourhoods of x is a filter, <math>N_x<math>. A (proper) filter which is a superset of <math>N_x<math> is said to converge to x, written <math>F \to x<math>. Note that if <math>F \to x<math> and <math>F \subseteq G<math> then <math>G \to x<math>.

Given a filter F on a set X and a function <math>f : X \to Y<math>, the set <math> \{ f(A) : A \in F \} <math> forms a filter base for a filter which, in a slight abuse of notation, we denote by <math>f(F)<math>.

The following useful results hold:

  1. X is Hausdorff iff every filter on X has at most one limit (i.e., converges to at most one point x).
  2. f is continuous at x iff <math> F \to x <math> implies <math>f(F) \to f(x)<math>
  3. X is compact iff every filter on X is a subset of a convergent filter.
  4. X is compact iff every ultrafilter on X converges.

The neighbourhood system for a non empty set A is a filter called the neighbourhood filter for A.

Filters in uniform spaces

Given a uniform space X, a filter F on X is called Cauchy filter if for every U in the entourage, there is an <math>A \in F<math> with <math> (x, y) \in U<math> for every <math>x, y \in A<math>. In a metric space this takes the form F is Cauchy if for every <math> \epsilon > 0 \ \ \exists A \in F \ \ \mathrm{diam}(A) < \epsilon <math>. X is said to be complete if every Cauchy filter converges.

Let <math>F \subseteq G , \ \ G \to x, \ F<math> Cauchy. Then <math>F \to x<math>. Thus every compact uniformity is complete. Further, a uniformity is compact iff it is complete and totally bounded.

See also

References

  • Cartan, H. (1937) "Thèorie des filtres". CR Acad. Paris, 205, 595–598.
  • Cartan, H. (1937) "Filtres et ultrafiltres" CR Acad. Paris, 205, 777–779

External links

An introductory account of the theory of filters in metric and topological spaces (http://www.efnet-math.org/~david/mathematics/filters.pdf)de:Filter (Mathematik) es:Filtro (matemáticas) fr:Filtre (mathématiques) it:Filtro (matematica)

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools