Difference between revisions of "Filter"

From Cantor's Attic
Jump to: navigation, search
(Properties)
(5 intermediate revisions by the same user not shown)
Line 6: Line 6:
  
 
A set $F\subset P(S)$ is a ''filter'' on $S$ if it satisfies the following properties:
 
A set $F\subset P(S)$ is a ''filter'' on $S$ if it satisfies the following properties:
* $S\in F$
+
* $\empty\not\in F$ (proper filter), $S\in F$
* $\empty\not\in F$ (proper filter)
+
 
* $X\cap Y\in F$ whenever $X,Y\in F$ (finite intersection property)
 
* $X\cap Y\in F$ whenever $X,Y\in F$ (finite intersection property)
 
* $Y\in F$ whenever $X\subset Y\subset S$ and $X\in F$ (upward closed)
 
* $Y\in F$ whenever $X\subset Y\subset S$ and $X\in F$ (upward closed)
Line 13: Line 12:
 
A filter $F$ is ''trivial'' if $F=\{S\}$. It is ''principal'' if there exists $X\subset S$ such that $Y\in F$ if and only if $X\subset Y$. Every nonempty subset $X\subset S$ has an associated principal filter.
 
A filter $F$ is ''trivial'' if $F=\{S\}$. It is ''principal'' if there exists $X\subset S$ such that $Y\in F$ if and only if $X\subset Y$. Every nonempty subset $X\subset S$ has an associated principal filter.
  
A filter $F$ is an ''ultrafilter'' if for all $X\subset S$, either $X\in F$ or $S\setminus X\in F$. Equivalently, there is no filter $F'$ such that $F\subset F'$ but $F\neq F'$ (i.e. $F$ is ''maximal''.
+
A filter $F$ is an ''ultrafilter'' if for all $X\subset S$, either $X\in F$ or $S\setminus X\in F$. Equivalently, there is no filter $F'$ such that $F\subset F'$ but $F\neq F'$ (i.e. $F$ is ''maximal'').
  
$F$ is also $\theta$-complete for a cardinal $\theta$ if for every family $\{X_\alpha | \alpha<\lambda\}$ with $\lambda\leq\theta$ and $X_\alpha\in F$ for all $\alpha<\lambda$, then $\cap_{\alpha<\lambda}X_\alpha\in F$. The completeness of $F$ is the smallest cardinal such that there is a subset $X\subset F$ such that $|X|=\theta$ and $\cap X\not\in F$, i.e. it is the largest $\theta$ such that $F$ is $\theta$-complete.
+
$F$ is also $\theta$-complete for a cardinal $\theta$ if for every family $\{X_\alpha | \alpha<\lambda\}$ with $\lambda<\theta$ and $X_\alpha\in F$ for all $\alpha<\lambda$, then $\cap_{\alpha<\lambda}X_\alpha\in F$. The completeness of $F$ is the smallest cardinal such that there is a subset $X\subset F$ such that $|X|=\theta$ and $\cap X\not\in F$, i.e. it is the largest $\theta$ such that $F$ is $\theta$-complete.
  
 
== Properties ==
 
== Properties ==
Line 30: Line 29:
  
 
Let $|S|\geq\aleph_0$. A (nontrivial probabilist $\sigma$-additive) ''measure'' on $S$ is a function $\mu:P(S)\to[0,1]$ such that:
 
Let $|S|\geq\aleph_0$. A (nontrivial probabilist $\sigma$-additive) ''measure'' on $S$ is a function $\mu:P(S)\to[0,1]$ such that:
* $\mu(S)=1$
+
* $\mu(\empty)=0$, $\mu(S)=1$
* $\mu(\empty)=0$
+
 
* $\mu(X)\leq\mu(Y)$ whenver $X\subset Y$
 
* $\mu(X)\leq\mu(Y)$ whenver $X\subset Y$
* $\mu({x})=0$ for every $x\in S$
 
 
* Let $\{X_n|n<\omega\}$ such that $X_i\cap X_j=\empty$ whenever $i<j$, then $\mu(\cup_{n<\omega}X_n)=\Sigma_{n=0}^{\infty}\mu(X_n)$
 
* Let $\{X_n|n<\omega\}$ such that $X_i\cap X_j=\empty$ whenever $i<j$, then $\mu(\cup_{n<\omega}X_n)=\Sigma_{n=0}^{\infty}\mu(X_n)$
  
If $S=\mathbb{R}^n$ for some n, $\mu$ can also be a ''Lebesgue measure'' if, additionally,
+
A measure $\mu$ is $\theta$-additive if $\{X_\alpha|\alpha<\lambda\}$ with $\lambda<\theta$ is such that $X_i\cap X_j=\empty$ whenever $i<j$, then $\mu(\cup_{\alpha<\lambda}X_\alpha)=\Sigma_{\alpha<\lambda}\mu(X_\alpha)$. Every measure $\mu$ is $\aleph_1$-additive (i.e. countably additive / $\sigma$-additive).
* If $X$ is congruent by translation to some measurable $Y$, then $X$ is measurable and $\mu(X)=\mu(Y)$.
+
 
+
A measure $\mu$ is $\theta$-additive if $\{X_\alpha|\alpha<\lambda\}$ with $\lambda\leq\theta$ is such that $X_i\cap X_j=\empty$ whenever $i<j$, then $\mu(\cup_{\alpha<\lambda}X_\alpha)=\Sigma_{\alpha<\lambda}\mu(X_\alpha)$. Every measure $\mu$ is $\aleph_1$-additive (i.e. countably additive / $\sigma$-additive).
+
  
 
$\mu$ is ''2-valued'' (or ''0-1-valued'') if for all $X\subset S$, either $\mu(X)=0$ or $\mu(X)=1$. A set $A\subset S$ such that $\mu(A)>0$ is an ''atom'' for $\mu$ if $\mu(X)=0$ or $\mu(X)=\mu(A)$ for all $X\subset S$. $\mu$ is ''atomless'' if it has no atoms.
 
$\mu$ is ''2-valued'' (or ''0-1-valued'') if for all $X\subset S$, either $\mu(X)=0$ or $\mu(X)=1$. A set $A\subset S$ such that $\mu(A)>0$ is an ''atom'' for $\mu$ if $\mu(X)=0$ or $\mu(X)=\mu(A)$ for all $X\subset S$. $\mu$ is ''atomless'' if it has no atoms.
Line 47: Line 41:
 
==== Properties ====
 
==== Properties ====
  
Let $\mu$ be a 2-valued mesure on $S$. Then $\{X\subset S|\mu(X)=1\}$ is a $\sigma$-complete ultrafilter on $S$. Conversely, if $F$ is a $\sigma$-complete ultrafilter on $S$ then the funcion $\mu:P(S)\to[0,1]$ defined by "$\mu(X)=1$ if $X\in F$, $\mu(X)=0$ otherwise" is a 2-valued measure on $S$.
+
* $\mu(\{x\})=0$ for every $x\in S$.
  
If $\mu$ has an atom $A$, the set $\{X\subset S|\mu(X\cap A)=\mu(A)\}$ is a $\sigma$-complete ultrafilter on $S$. However, if $\mu$ is atomless then every set $X\subset S$ is the disjoint union of two sets of positive measure.  
+
* Let $\mu$ be a 2-valued mesure on $S$. Then $\{X\subset S|\mu(X)=1\}$ is a $\sigma$-complete ultrafilter on $S$. Conversely, if $F$ is a $\sigma$-complete ultrafilter on $S$ then the funcion $\mu:P(S)\to[0,1]$ defined by "$\mu(X)=1$ if $X\in F$, $\mu(X)=0$ otherwise" is a 2-valued measure on $S$.
  
The [[axiom of choice]] implies that some sets of reals are not Lebesgue measurable, in fact that [0,1] is not measurable at all; however, the [[axiom of determinacy]] implies that all sets of reals are Lebesgue measurable.
+
* If $\mu$ has an atom $A$, the set $\{X\subset S|\mu(X\cap A)=\mu(A)\}$ is a $\sigma$-complete ultrafilter on $S$. However, if $\mu$ is atomless then every set $X\subset S$ is the disjoint union of two sets of positive measure.
  
 
=== Relations to large cardinal axioms ===
 
=== Relations to large cardinal axioms ===

Revision as of 09:35, 11 September 2017

A filter on a set $S$ is a special subset of $P(S)$ that contains S itself, does not contain the empty set, and is closed under finite intersections and the superset relation. An ultrafiler is a maximal filter, i.e. it is not a subset of any other filter, or equivalently, every subset of S is either in it or its complement (in S) is. Filters, and especially ultrafilters, are closely connected to several large cardinal notions, such as measurable cardinals and strongly compact cardinals.

Intuitively, the members of a filter are the subsets of $S$ "large" enough to satisfy some property. $S$ is always obviously large, while $\empty$ never is. $F$ being closed under finite intersections means that the intersection of two large sets is still large - $F$'s sets are "so large" they only differ by a "small" set. Also, $F$ being closed under the superset relation means that if a set $X$ contains a large set then $X$ is also large. For example, for any nonempty $X\subset S$, the set of all supersets of $X$ -i.e. the set of all sets "larger" than $X$ - is always a filter.

Definitions

A set $F\subset P(S)$ is a filter on $S$ if it satisfies the following properties:

  • $\empty\not\in F$ (proper filter), $S\in F$
  • $X\cap Y\in F$ whenever $X,Y\in F$ (finite intersection property)
  • $Y\in F$ whenever $X\subset Y\subset S$ and $X\in F$ (upward closed)

A filter $F$ is trivial if $F=\{S\}$. It is principal if there exists $X\subset S$ such that $Y\in F$ if and only if $X\subset Y$. Every nonempty subset $X\subset S$ has an associated principal filter.

A filter $F$ is an ultrafilter if for all $X\subset S$, either $X\in F$ or $S\setminus X\in F$. Equivalently, there is no filter $F'$ such that $F\subset F'$ but $F\neq F'$ (i.e. $F$ is maximal).

$F$ is also $\theta$-complete for a cardinal $\theta$ if for every family $\{X_\alpha | \alpha<\lambda\}$ with $\lambda<\theta$ and $X_\alpha\in F$ for all $\alpha<\lambda$, then $\cap_{\alpha<\lambda}X_\alpha\in F$. The completeness of $F$ is the smallest cardinal such that there is a subset $X\subset F$ such that $|X|=\theta$ and $\cap X\not\in F$, i.e. it is the largest $\theta$ such that $F$ is $\theta$-complete.

Properties

The finite intersection property is equivalent to $\aleph_0$-completeness. Every set $G\subset P(S)$ with the finite intersection property can be extended to a filter, i.e. there exists a filter $F$ such that $G\subset F$. $F$ being countably complete (or $\sigma$-complete) means that it is $\aleph_1$-complete. The completeness of a countably complete nonprincipal ultrafilter on S is always a measurable cardinal. However, every countably complete filter on a countable or finite set is principal.

Every cardinal $\kappa\geq\aleph_0$ has $2^{2^\kappa}$ ultrafilters. Under the axiom of choice, every filter can be extended to an ultrafilter.

If $G$ is a nonempty sets of filters on S, then $\cap G$ is a filter on S. If $G$ is a $\subset$-chain of filters, then $\cup G$ is a filter.

Measures

Filters are heavily related to the concept of measures.

Let $|S|\geq\aleph_0$. A (nontrivial probabilist $\sigma$-additive) measure on $S$ is a function $\mu:P(S)\to[0,1]$ such that:

  • $\mu(\empty)=0$, $\mu(S)=1$
  • $\mu(X)\leq\mu(Y)$ whenver $X\subset Y$
  • Let $\{X_n|n<\omega\}$ such that $X_i\cap X_j=\empty$ whenever $i<j$, then $\mu(\cup_{n<\omega}X_n)=\Sigma_{n=0}^{\infty}\mu(X_n)$

A measure $\mu$ is $\theta$-additive if $\{X_\alpha|\alpha<\lambda\}$ with $\lambda<\theta$ is such that $X_i\cap X_j=\empty$ whenever $i<j$, then $\mu(\cup_{\alpha<\lambda}X_\alpha)=\Sigma_{\alpha<\lambda}\mu(X_\alpha)$. Every measure $\mu$ is $\aleph_1$-additive (i.e. countably additive / $\sigma$-additive).

$\mu$ is 2-valued (or 0-1-valued) if for all $X\subset S$, either $\mu(X)=0$ or $\mu(X)=1$. A set $A\subset S$ such that $\mu(A)>0$ is an atom for $\mu$ if $\mu(X)=0$ or $\mu(X)=\mu(A)$ for all $X\subset S$. $\mu$ is atomless if it has no atoms.

A set $X\subset S$ is null if $\mu(X)=0$.

Properties

  • $\mu(\{x\})=0$ for every $x\in S$.
  • Let $\mu$ be a 2-valued mesure on $S$. Then $\{X\subset S|\mu(X)=1\}$ is a $\sigma$-complete ultrafilter on $S$. Conversely, if $F$ is a $\sigma$-complete ultrafilter on $S$ then the funcion $\mu:P(S)\to[0,1]$ defined by "$\mu(X)=1$ if $X\in F$, $\mu(X)=0$ otherwise" is a 2-valued measure on $S$.
  • If $\mu$ has an atom $A$, the set $\{X\subset S|\mu(X\cap A)=\mu(A)\}$ is a $\sigma$-complete ultrafilter on $S$. However, if $\mu$ is atomless then every set $X\subset S$ is the disjoint union of two sets of positive measure.

Relations to large cardinal axioms

Let $\kappa$ be an uncountable cardinal.

If there exists a 2-valued $\kappa$-additive measure on $\kappa$, then $\kappa$ is a measurable cardinal. This equivalent to saying that there is a $\kappa$-complete nonprincipal ultrafilter on $\kappa$.

If every $\kappa$-complete filter on $\kappa$ can be extended to a $\kappa$-complete ultrafilter on $\kappa$, then $\kappa$ is strongly compact. The converse is also true, every strongly compact cardinal has this property. Not that nonprincipality is not required here. Obviously, every strongly compact cardinal is measurable, but it is consistent that the first measurable and the first strongly compact cardinals are equal.


    This article is a stub. Please help us to improve Cantor's Attic by adding information.