Namespaces
Variants
Actions

Difference between revisions of "Filter"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (→‎Comments: better)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
''dual ideal''
 
''dual ideal''
  
A non-empty subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401301.png" /> of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401302.png" /> satisfying the conditions: a) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401303.png" /> and if the infimum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401304.png" /> exists, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401305.png" />; and b) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401306.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401307.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401308.png" />. The concept of a filter is dual to that of an [[Ideal|ideal]] of a partially ordered set.
+
A non-empty subset $F$ of a partially ordered set $(P,{\le})$ satisfying the conditions: a) if $a,b \in F$ and if the infimum $\inf\{a,b\}$ exists, then $\inf\{a,b\} \in F$; and b) if $a \in F$ and $a \le b$, then $b \in F$. The concept of a filter is dual to that of an [[ideal]] of a partially ordered set.
  
A filter over a non-empty set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f0401309.png" /> (or in a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013010.png" />) is a proper filter of the set of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013011.png" />, ordered by inclusion i.e. any non-empty collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013012.png" /> of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013013.png" /> satisfying the conditions: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013014.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013015.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013017.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013018.png" />; the empty set does not belong to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013019.png" />.
+
A filter over a non-empty set $E$ (or in a set $E$) is a proper filter of the set of subsets of $E$, ordered by inclusion i.e. any non-empty collection $F$ of subsets of $E$ satisfying the conditions: If $A,B \in F$ then $A \cap B \in F$; if $A \in F$ and $A \subset B$, then $B \in F$; the empty set does not belong to $F$.
  
A filter base is a system of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013020.png" /> satisfying the two conditions: 1) the empty set does not belong to it; and 2) the intersection of two subsets belonging to it contains some third subset belonging to it. Every filter is completely determined by any of its filter bases. The system of all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013021.png" /> that contain some element of a given filter base is a filter. It is said to be spanned by this base.
+
A ''filter base'' is a system of subsets of $E$ satisfying the two conditions: 1) the empty set does not belong to it; and 2) the intersection of two subsets belonging to it contains some third subset belonging to it. Every filter is completely determined by any of its filter bases. The system of all subsets of $E$ that contain some element of a given filter base is a filter. It is said to be spanned by this base.
  
The set of all filters over a given set is partially ordered by inclusion. A maximal element of it is called an ultrafilter (a maximal proper filter in any Boolean algebra is also called an ultrafilter).
+
The set of all filters over a given set is partially ordered by inclusion. A maximal element of it is called an ''[[ultrafilter]]'' (a maximal proper filter in any Boolean algebra is also called an ultrafilter).
  
Examples of filters. 1) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013022.png" /> be the subset of the natural numbers consisting of those numbers that are multiples of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013023.png" />; the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013024.png" /> is a filter base; the filter spanned by this base consists of those subsets that contain some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013025.png" />. 2) The collection of all subsets containing a certain fixed non-empty subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013026.png" /> is a filter over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013027.png" />, called a principal filter. All filters over a finite set are principal. 3) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013028.png" /> is an infinite set of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013030.png" /> is the collection of all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013031.png" /> whose complements have cardinality less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013032.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040130/f04013033.png" /> is a filter (called a [[Fréchet filter]]). A Fréchet filter is an example of a non-principal filter. 4) The system of subsets containing some fixed point of a set is also a filter; moreover, it is an ultrafilter. 5) Suppose a topology is given on $E$; then the [[neighbourhood]]s of any point $x \in E$ (the subsets of $E$ containing $x$ in the interior) form a filter.
+
Examples of filters. 1) Let $N_k$ be the subset of the natural numbers consisting of those numbers that are multiples of $k$; the system $\{N_k : k=1,2,\ldots \}$ is a filter base; the filter spanned by this base consists of those subsets that contain some $N_k$. 2) The collection of all subsets of $E$ containing a certain fixed non-empty subset $A \subseteq E$ is a filter over $E$, called a ''[[principal filter]]''. All filters over a finite set are principal. 3) If $E$ is an infinite set of cardinality $\mathfrak{a}$ and $F$ is the collection of all subsets of $E$ whose complements have cardinality less than $\mathfrak{a}$, then $F$ is a filter (called a ''[[Fréchet filter]]''). A Fréchet filter is an example of a non-principal filter. 4) The system of subsets containing some fixed point of a set is also a filter; moreover, it is an ultrafilter. 5) Suppose a [[Topological structure (topology)|topology]] is given on $E$; then the [[neighbourhood]]s of any point $x \in E$ (the subsets of $E$ containing $x$ in the interior) form a filter.
  
 
====References====
 
====References====
Line 21: Line 21:
  
 
====Comments====
 
====Comments====
There is some disagreement about the definition of a filter in a partially ordered set where finite infima do not always exist. Most authors would replace condition a) in the first paragraph above by  "if a, b F, then there exists a c F with c≤ a and c≤ b" , cf. [[#References|[a1]]]. This avoids some rather pathological seeming cases.
+
There is some disagreement about the definition of a filter in a partially ordered set where finite infima do not always exist. Most authors would replace condition a) in the first paragraph above by  "if $a,b \in F$, then there exists $c \in F$ with $c \le a$ and $c \le b$" , cf. [[#References|[a1]]]. This avoids some rather pathological seeming cases.
  
A further meaning of the word  "filter"  occurs in the theory of (partially observed) stochastic processes, cf. [[Stochastic processes, filtering of|Stochastic processes, filtering of]].
+
A further meaning of the word  "filter"  occurs in the theory of (partially observed) stochastic processes, cf. [[Stochastic processes, filtering of]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Kunen,  "Set theory" , North-Holland  (1980)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Kunen,  "Set theory" , North-Holland  (1980)</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Latest revision as of 17:00, 25 September 2017

dual ideal

A non-empty subset $F$ of a partially ordered set $(P,{\le})$ satisfying the conditions: a) if $a,b \in F$ and if the infimum $\inf\{a,b\}$ exists, then $\inf\{a,b\} \in F$; and b) if $a \in F$ and $a \le b$, then $b \in F$. The concept of a filter is dual to that of an ideal of a partially ordered set.

A filter over a non-empty set $E$ (or in a set $E$) is a proper filter of the set of subsets of $E$, ordered by inclusion i.e. any non-empty collection $F$ of subsets of $E$ satisfying the conditions: If $A,B \in F$ then $A \cap B \in F$; if $A \in F$ and $A \subset B$, then $B \in F$; the empty set does not belong to $F$.

A filter base is a system of subsets of $E$ satisfying the two conditions: 1) the empty set does not belong to it; and 2) the intersection of two subsets belonging to it contains some third subset belonging to it. Every filter is completely determined by any of its filter bases. The system of all subsets of $E$ that contain some element of a given filter base is a filter. It is said to be spanned by this base.

The set of all filters over a given set is partially ordered by inclusion. A maximal element of it is called an ultrafilter (a maximal proper filter in any Boolean algebra is also called an ultrafilter).

Examples of filters. 1) Let $N_k$ be the subset of the natural numbers consisting of those numbers that are multiples of $k$; the system $\{N_k : k=1,2,\ldots \}$ is a filter base; the filter spanned by this base consists of those subsets that contain some $N_k$. 2) The collection of all subsets of $E$ containing a certain fixed non-empty subset $A \subseteq E$ is a filter over $E$, called a principal filter. All filters over a finite set are principal. 3) If $E$ is an infinite set of cardinality $\mathfrak{a}$ and $F$ is the collection of all subsets of $E$ whose complements have cardinality less than $\mathfrak{a}$, then $F$ is a filter (called a Fréchet filter). A Fréchet filter is an example of a non-principal filter. 4) The system of subsets containing some fixed point of a set is also a filter; moreover, it is an ultrafilter. 5) Suppose a topology is given on $E$; then the neighbourhoods of any point $x \in E$ (the subsets of $E$ containing $x$ in the interior) form a filter.

References

[1] N. Bourbaki, "Elements of mathematics. General topology" , Addison-Wesley (1966) (Translated from French)
[2] P.M. Cohn, "Universal algebra" , Reidel (1981)
[3] A.I. Mal'tsev, "Algebraic systems" , Springer (1973) (Translated from Russian)


Comments

There is some disagreement about the definition of a filter in a partially ordered set where finite infima do not always exist. Most authors would replace condition a) in the first paragraph above by "if $a,b \in F$, then there exists $c \in F$ with $c \le a$ and $c \le b$" , cf. [a1]. This avoids some rather pathological seeming cases.

A further meaning of the word "filter" occurs in the theory of (partially observed) stochastic processes, cf. Stochastic processes, filtering of.

References

[a1] K. Kunen, "Set theory" , North-Holland (1980)
How to Cite This Entry:
Filter. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Filter&oldid=41956
This article was adapted from an original article by V.I. MalykhinT.S. Fofanova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article