Difference between revisions of "Filter"

From Cantor's Attic
Jump to: navigation, search
(2 intermediate revisions by the same user not shown)
Line 16: Line 16:
 
$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 $\bigcap_{\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 $\bigcap 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 $\bigcap_{\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 $\bigcap X\not\in F$, i.e. it is the largest $\theta$ such that $F$ is $\theta$-complete.
  
Let $\kappa$ be a cardinal, and $\theta$ an ordinal such that $\kappa <\theta$. $P_\kappa(\theta)$ is defined as the collection of subsets of $\theta$ of size smaller than $\kappa$. An ultrafilter $U\subseteq P_\kappa(\theta)$ is ''fine'' if for every $\alpha < \theta$ the set $\{a\in P_\kappa(\theta)|\alpha\in a\}\in U$. An ultrafilter $U\subseteq P_\kappa(\theta)$ is ''normal'' if $U$ is $\theta$-complete and for every regressive function $f:P_\kappa(\theta)\to\theta$ with $\{a\in P_\kappa(\theta)|f(a)<a\}\in U$ there is some $\alpha <\theta$ where $\{a\in P_\kappa(\theta)|f(a)=\alpha\}\in U$. (A function $f:\alpha\to\beta$ is ''regressive'' if $f(\delta)\leq\delta$ for every $\delta\in\alpha$). An equivalent definition of a ''normal'' ultrafilter is the following: $U$ is closed under ''diagonal intersections'' $\Delta_{a\in\theta}X_a = \{x\in P_\kappa(\theta)|x\in\bigcap_{a\in x}X_a\}$.
+
A filter $F$ on $\kappa$ is ''normal'' if it is closed under diagonal intersections: $\Delta_{\alpha\in\kappa}X_\alpha = \{\xi\in \kappa|\xi\in\bigcap_{\alpha\in\xi}X_\alpha\}$. That is, for every family $\{X_\alpha | \alpha<\kappa\}$ and $X_\alpha\in F$ for all $\alpha<\kappa$, one have $\Delta_{\alpha<\kappa}X_\alpha\in F$.
 +
 
 +
Let $P_\kappa(A)$ for $|A|\geq\kappa$ be the set of all subsets of $A$ of cardinality at most $\kappa$. A $\kappa$-complete ultrafilter $U$ on $P_\kappa(A)$ is a ''fine measure'' (or a ''fine ultrafilter'') if for every $a\in A$, the set $\{x\in P_\kappa(A)|a\in x\}$ is in $U$. If $U$ is fine, then saying it is also normal is equivalent to saying that for every function $f:P_\kappa(A)\to A$, if the set $\{x\in P_\kappa(A)|f(x)\in x\}$ is in $U$ then $f$ is constant on a set in $U$, i.e. there is $k\in A$ such that $U$ also contains the set $\{x\in P_\kappa(A)|f(x)=k\}$.
 +
 
 +
A normal $\kappa$-complete nonprincipal ultrafilter $D$ on a cardinal $\kappa$ is a ''normal measure''. A normal fine ultrafilter $D$ on $P_\kappa(A)$ is a ''normal (fine) measure''.
  
 
== Properties ==
 
== Properties ==
Line 28: Line 32:
 
Let $j:M\to N$ be a (nontrivial) [[elementary embedding]] with critical point $\kappa$. Then the set $\mathcal{U}_j=\{x\subset\kappa|\kappa\in j(x)\}$ is a $\kappa$-complete nonprincipal ultrafilter on $(P(\kappa))^M$; in particular if $M=V$ then $(P(\kappa))^M=P(\kappa)$ and thus $\kappa$ is [[measurable]].
 
Let $j:M\to N$ be a (nontrivial) [[elementary embedding]] with critical point $\kappa$. Then the set $\mathcal{U}_j=\{x\subset\kappa|\kappa\in j(x)\}$ is a $\kappa$-complete nonprincipal ultrafilter on $(P(\kappa))^M$; in particular if $M=V$ then $(P(\kappa))^M=P(\kappa)$ and thus $\kappa$ is [[measurable]].
  
Every set in a normal ultrafilter is [[stationary]].
+
The [[club|club filter]] on a limit ordinal of uncountable cofinality is normal. Every set in a normal measure is [[stationary]], also every [[measurable]] cardinal carries a normal measure. Every [[supercompact]] cardinal $\kappa$ carries $2^{2^\kappa}$ normal measures.
  
 
== Measures ==
 
== Measures ==
Line 65: Line 69:
 
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$. As stated before, if $j:V\to M$ is a nontrivial elementary embedding then $\mathcal{U}_j=\{x\subset\kappa|\kappa\in j(x)\}$ is a $\kappa$-complete nonprincipal ultrafilter on $P(\kappa)$ and $\kappa$ is measurable.
 
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$. As stated before, if $j:V\to M$ is a nontrivial elementary embedding then $\mathcal{U}_j=\{x\subset\kappa|\kappa\in j(x)\}$ is a $\kappa$-complete nonprincipal ultrafilter on $P(\kappa)$ and $\kappa$ is measurable.
  
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.
+
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. Strong compactness is furthermore equivalent to the assertion that for every set $A$ such that $|A|\geq\kappa$ there exists a fine measure on $P_\kappa(A)$. Those measures doesn't have to be normal.
  
If there is $\theta>\kappa$ such that there is a normal fine ultrafilter on $P_\kappa(\theta)$, then $\kappa$ is $\theta$-[[supercompact]]; if it is $\theta$-supercompact for every $\theta\geq\kappa$, then it is '''supercompact'''.
+
If there is a set $\lambda$ with $\lambda\geq\kappa$ such that there is a normal fine measure on $P_\kappa(\lambda)$, then $\kappa$ is $\lambda$-[[supercompact]]; if it is $\lambda$-supercompact for every $\lambda\geq\kappa$, then it is '''supercompact'''. This is equivalent to saying that for every set $A$ with $|A|\geq\kappa$, there is a normal fine measure on $P_\kappa(\lambda)$. Clearly, every supercompact is strongly compact by the last characterization of strong compactness. It is open whether every strongly compact is supercompact.
  
 
== See Also ==
 
== See Also ==
  
 
* [[Filters on N|Filters on $\mathbb{N}$]]
 
* [[Filters on N|Filters on $\mathbb{N}$]]

Revision as of 01:28, 10 October 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 $\bigcap_{\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 $\bigcap X\not\in F$, i.e. it is the largest $\theta$ such that $F$ is $\theta$-complete.

A filter $F$ on $\kappa$ is normal if it is closed under diagonal intersections: $\Delta_{\alpha\in\kappa}X_\alpha = \{\xi\in \kappa|\xi\in\bigcap_{\alpha\in\xi}X_\alpha\}$. That is, for every family $\{X_\alpha | \alpha<\kappa\}$ and $X_\alpha\in F$ for all $\alpha<\kappa$, one have $\Delta_{\alpha<\kappa}X_\alpha\in F$.

Let $P_\kappa(A)$ for $|A|\geq\kappa$ be the set of all subsets of $A$ of cardinality at most $\kappa$. A $\kappa$-complete ultrafilter $U$ on $P_\kappa(A)$ is a fine measure (or a fine ultrafilter) if for every $a\in A$, the set $\{x\in P_\kappa(A)|a\in x\}$ is in $U$. If $U$ is fine, then saying it is also normal is equivalent to saying that for every function $f:P_\kappa(A)\to A$, if the set $\{x\in P_\kappa(A)|f(x)\in x\}$ is in $U$ then $f$ is constant on a set in $U$, i.e. there is $k\in A$ such that $U$ also contains the set $\{x\in P_\kappa(A)|f(x)=k\}$.

A normal $\kappa$-complete nonprincipal ultrafilter $D$ on a cardinal $\kappa$ is a normal measure. A normal fine ultrafilter $D$ on $P_\kappa(A)$ is a normal (fine) measure.

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 $\bigcap G$ is a filter on S. If $G$ is a $\subset$-chain of filters, then $\bigcup G$ is a filter.

Let $j:M\to N$ be a (nontrivial) elementary embedding with critical point $\kappa$. Then the set $\mathcal{U}_j=\{x\subset\kappa|\kappa\in j(x)\}$ is a $\kappa$-complete nonprincipal ultrafilter on $(P(\kappa))^M$; in particular if $M=V$ then $(P(\kappa))^M=P(\kappa)$ and thus $\kappa$ is measurable.

The club filter on a limit ordinal of uncountable cofinality is normal. Every set in a normal measure is stationary, also every measurable cardinal carries a normal measure. Every supercompact cardinal $\kappa$ carries $2^{2^\kappa}$ normal measures.

Measures

Filters are related to the concept of measures.

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

  • $\mu(\empty)=0$, $\mu(S)>0$
  • $\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(\bigcup_{n<\omega}X_n)=\sum_{n=0}^{\infty}\mu(X_n)$

$\mu$ is probabilist if $\mu(S)=1$. $\mu$ is nontrivial because there exists a set $A$ of positive measure, i.e. $\mu(A)>0$, since we required $\mu(S)>0$.

$\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(\bigcup_{\alpha<\lambda}X_\alpha)=\sum_{\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 $\mu(S)=1$) if $S$ has finite measure, and for all $X\subset S$, either $\mu(X)=0$ or $\mu(X)=\mu(S)$. 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 A$. $\mu$ is atomless if it has no atoms.

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

The Lebesgue measure is a certain kind of measure that is linked to the axiom of choice and to the axiom of determinacy.

Properties

  • Let $\mu$ be a 2-valued measure on $S$. Then $\{X\subset S|\mu(X)=\mu(S)\}$ 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 0-1-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$.
  • If $\mu$ is atomless (i.e. has no atoms), $\mu(\{x\})=0$ for every $x\in S$. In fact, $\mu(X)=0$ for every finite or countably infinite set $X\subset S$. Thus every measure on a countable set has an atom (otherwise $\mu(S)$ would be $0$, contradicting the nontriviality of $\mu$).
  • If $\mu$ is atomless, then every set $X\subset S$ of positive measure is the disjoint union of two sets of positive measure, also, $\mu$ has a continuum of different values and if $A$ is a set of positive measure, then for every $b\in [0;\mu(A)]$, there exists $B\subset A$ such that $\mu(B)=b$.

Large cardinals

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$. As stated before, if $j:V\to M$ is a nontrivial elementary embedding then $\mathcal{U}_j=\{x\subset\kappa|\kappa\in j(x)\}$ is a $\kappa$-complete nonprincipal ultrafilter on $P(\kappa)$ and $\kappa$ is measurable.

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. Strong compactness is furthermore equivalent to the assertion that for every set $A$ such that $|A|\geq\kappa$ there exists a fine measure on $P_\kappa(A)$. Those measures doesn't have to be normal.

If there is a set $\lambda$ with $\lambda\geq\kappa$ such that there is a normal fine measure on $P_\kappa(\lambda)$, then $\kappa$ is $\lambda$-supercompact; if it is $\lambda$-supercompact for every $\lambda\geq\kappa$, then it is supercompact. This is equivalent to saying that for every set $A$ with $|A|\geq\kappa$, there is a normal fine measure on $P_\kappa(\lambda)$. Clearly, every supercompact is strongly compact by the last characterization of strong compactness. It is open whether every strongly compact is supercompact.

See Also