Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Filter"

(New page: A '''filter''' on a set <math>X</math> is a structure of subsets of <math>X</math>. == Definition == Let <math>\mathcal{F}</math> be a set of subsets of <math>X</math>. We say t...)
 
(Added Categories)
 
(4 intermediate revisions by 2 users not shown)
Line 4: Line 4:
  
 
Let <math>\mathcal{F}</math> be a set of subsets of <math>X</math>.  We say that <math>\mathcal{F}</math> is a filter on <math>X</math> if and only if each of the following conditions hold:
 
Let <math>\mathcal{F}</math> be a set of subsets of <math>X</math>.  We say that <math>\mathcal{F}</math> is a filter on <math>X</math> if and only if each of the following conditions hold:
−
* The [[empty set]] is not an element of <math>\mathcal{F}</math>
+
* The [[empty set]] is not an element of <math>\mathcal{F}</math>.
 
* If <math>A</math> and <math>B</math> are subsets of <math>X</math>, <math>A</math> is a subset of <math>B</math>, and <math>A</math> is an element of <math>\mathcal{F}</math>, then <math>B</math> is an element of <math>\mathcal{F}</math>.
 
* If <math>A</math> and <math>B</math> are subsets of <math>X</math>, <math>A</math> is a subset of <math>B</math>, and <math>A</math> is an element of <math>\mathcal{F}</math>, then <math>B</math> is an element of <math>\mathcal{F}</math>.
 
* The intersection of two elements of <math>\mathcal{F}</math> is an element of <math>\mathcal{F}</math>.
 
* The intersection of two elements of <math>\mathcal{F}</math> is an element of <math>\mathcal{F}</math>.
  
 
It follows from the definition that the intersection of any finite family of elements of <math>\mathcal{F}</math> is also an element of <math>\mathcal{F}</math>.  Also, if <math>A</math> is an element of <math>\mathcal{F}</math>, then its [[complement]] is not.
 
It follows from the definition that the intersection of any finite family of elements of <math>\mathcal{F}</math> is also an element of <math>\mathcal{F}</math>.  Also, if <math>A</math> is an element of <math>\mathcal{F}</math>, then its [[complement]] is not.
 +
 +
More generally, one can define a filter on any [[Partially ordered set]] (poset) <math>(P,\leq)</math>: Let <math>F</math> be a subset of <math>P</math>. We say <math>F</math> is a filter if and only if
 +
* <math>F\neq\emptyset</math>.
 +
* For all <math>x,y\in F</math>, there exists <math>z\in F</math> such that <math>z\leq x</math> and <math>z\leq y</math>.
 +
* If <math>x\in F</math> and <math>x\leq y\in P</math>, then <math>y\in F</math>.
 +
A filter on a set <math>S</math> is a filter on the poset <math>(\mathcal{P}(S),\subseteq)</math>.
  
 
== Examples ==
 
== Examples ==
Line 14: Line 20:
 
Let <math>Y</math> be a subset of <math>X</math>.  Then the set of subsets of <math>X</math> containing <math>Y</math> constitute a filter on <math>X</math>.
 
Let <math>Y</math> be a subset of <math>X</math>.  Then the set of subsets of <math>X</math> containing <math>Y</math> constitute a filter on <math>X</math>.
  
−
If <math>X</math> is an [[infinite | infinite set]], then the subsets of <math>X</math> with finite complements constitute a filter on <math>X</math>.  Thsi is called the cofinite filter, or Fréchet filter.
+
If <math>X</math> is an [[infinite | infinite set]], then the subsets of <math>X</math> with finite complements constitute a filter on <math>X</math>.  This is called the cofinite filter, or Fréchet filter.
  
 
== See also ==
 
== See also ==
Line 20: Line 26:
 
* [[Ultrafilter]]
 
* [[Ultrafilter]]
  
 +
[[Category:Definition]]
 +
[[Category:Set theory]]
 
{{stub}}
 
{{stub}}
−
 
−
[[Category:Set theory]]
 

Latest revision as of 16:59, 13 November 2024

A filter on a set $X$ is a structure of subsets of $X$.

Definition

Let $\mathcal{F}$ be a set of subsets of $X$. We say that $\mathcal{F}$ is a filter on $X$ if and only if each of the following conditions hold:

  • The empty set is not an element of $\mathcal{F}$.
  • If $A$ and $B$ are subsets of $X$, $A$ is a subset of $B$, and $A$ is an element of $\mathcal{F}$, then $B$ is an element of $\mathcal{F}$.
  • The intersection of two elements of $\mathcal{F}$ is an element of $\mathcal{F}$.

It follows from the definition that the intersection of any finite family of elements of $\mathcal{F}$ is also an element of $\mathcal{F}$. Also, if $A$ is an element of $\mathcal{F}$, then its complement is not.

More generally, one can define a filter on any Partially ordered set (poset) $(P,\leq)$: Let $F$ be a subset of $P$. We say $F$ is a filter if and only if

  • $F\neq\emptyset$.
  • For all $x,y\in F$, there exists $z\in F$ such that $z\leq x$ and $z\leq y$.
  • If $x\in F$ and $x\leq y\in P$, then $y\in F$.

A filter on a set $S$ is a filter on the poset $(\mathcal{P}(S),\subseteq)$.

Examples

Let $Y$ be a subset of $X$. Then the set of subsets of $X$ containing $Y$ constitute a filter on $X$.

If $X$ is an infinite set, then the subsets of $X$ with finite complements constitute a filter on $X$. This is called the cofinite filter, or Fréchet filter.

See also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Filter&oldid=233320"