Filter and ideals

From Cantor's Attic
(Redirected from Ultrafilter)
Jump to: navigation, search

A filter on a set $S$ is a special subset of $\mathcal{P}(S)$ that contains $S$ itself, does not contain the empty set, and is closed under finite intersections and the superset relation. An ideal on $S$ is the dual of a filter: if $F$ is a filter, the set of the complements (in $S$) of $F$'s elements forms an ideal, and vice-versa; equivalently, an ideal is a special subset of $\mathcal{P}(S)$ that contains the empty set but not $S$ itself, is closed under finite unions and the subset 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. The dual notion is a prime ideal. Thus an ultrafilter and its dual prime ideal partitions $\mathcal{P}(S)$ in two.

Intuitively, the members of a filter are the subsets of $S$ "large" enough to satisfy some property. $S$ is always "large enough", while $\empty$ never is. $F$ being closed under finite intersections means that the intersection of two large sets is still large enough - $F$'s sets only differ by a "too small" set. Also, $F$ being closed under the superset relation means that if a set $X$ contains a large enough set then $X$ is also large enough. For example, for any nonempty $X\subseteq S$, the set of all supersets of $X$ -i.e. the set of all sets "larger" than $X$ - is always a filter. Similarly, the members of an ideal will represent the subsets of $S$ "too small"; $\empty$ is always too small, $S$ never is, the union of two too small sets is still too small and if a set is contained (as a subset) in a too small set, then it is itself too small.

Most of the results in this article can be found in [1].


A set $F\subseteq\mathcal{P}(S)$ is a filter on $\mathcal{P}(S)$ (or just "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\subseteq Y\subseteq S$ and $X\in F$ (upward closed / closed under supersets)

A set $I\subseteq\mathcal{P}(S)$ is an ideal on $\mathcal{P}(S)$ (or just "on $S$") if it satisfies the following properties:

  • $S\not\in I$, $\empty\in I$
  • $X\cup Y\in F$ whenever $X,Y\in I$ (finite union property)
  • $Y\in I$ whenever $Y\subseteq X\subseteq S$ and $X\in I$ (downard closed / closed under subsets)

Given a filter $F$, its dual ideal is $I=\{S\setminus X : X\in F\}$. Conversely, every ideal has a dual filter. If two filters/ideals are not equal, their duals aren't equal neither.

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

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

$F$ is $\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\subseteq F$ such that $|X|=\theta$ and $\bigcap X\not\in F$, i.e. it is the largest $\theta$ such that $F$ is $\theta$-complete. Similarly for ideals, by replacing intersections by unions.

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$. Similarly for ideals, by replacing intersections by unions.

Whenever a filter is either nontrivial, nonprincipal, $\theta$-complete, normal or maximal, so is its dual ideal.


The finite intersection property is equivalent to $\aleph_0$-completeness. Every set $G\subseteq \mathcal{P}(S)$ with the finite intersection property can be extended to a filter, i.e. there exists a filter $F$ such that $G\subseteq F$. A filter or an ideal being countably complete (or $\sigma$-complete) means that it is $\aleph_1$-complete. The completeness of a countably complete nonprincipal ultrafilter or prime ideal 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 and prime ideals. Under the axiom of choice, every filter can be extended to an ultrafilter, and every ideal can be extended to a prime ideal.

If $G$ is a nonempty sets of filters on S, then $\bigcap G$ is a filter on S. If $G$ is a $\subseteq$-chain of filters, then $\bigcup G$ is a filter.

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

The club filter, the non-stationary ideal and saturation

Given a regular uncountable cardinal $\kappa$, the collection of all clubs in $\kappa$ has the finite intersection property, thus it can be extended to a filter. This filter contains precisely the subsets of $\kappa$ with a subset that is a club in $\kappa$. We we call this filter the club filter of $\kappa$. This filter is $\kappa$-complete and normal (i.e. closed under diagonal intersections).

Let $I_{NS}$, the nonstationary ideal on $\kappa$, be the dual ideal of the club filter of $\kappa$. This is a normal $\kappa$-complete ideal. Both $I_{NS}$ and the club filter are minimal: if $F$ is a normal filter containing all initial segements $\{\alpha : \alpha_0<\alpha<\kappa \}$ then it contains the club filter of $\kappa$. This means $I_{NS}$ and the club filter are not maximal, in particular the club filter is not a normal measure (see below) despite being normal and $\kappa$-complete.

Let $I$ be a $\kappa$-complete ideal on $\kappa$ containing all singletons of elements of $\kappa$. $I$ contains all subsets of $\kappa$ of cardinality less than $\kappa$. We say that $I$ is $\lambda$-saturated if there is no collection $W$ of subsets of $\kappa$ such that $|W|=\lambda$, $I$ and $W$ are disjoint, but the intersection of any two elements of $W$ is in $I$. $\aleph_1$-saturation is called $\sigma$-saturation. $I$'s saturation, $\text{sat}(I)$ is the smallest $\lambda$ such that $I$ is $\lambda$-saturated.

An ideal $I$ is prime if and only if $\text{sat}(I)=2$. Trivially every ideal is $(2^\kappa)^+$-saturated. Any $\kappa$ carrying a $\sigma$-saturated $\kappa$-complete ideal must be either measurable or $\leq 2^{\aleph_0}$ and real-valued measurable. If there exists a $\kappa$-saturated $\kappa$-complete ideal on $\kappa$, then there is a such ideal that is additionally normal. Same for $\kappa^+$-saturation.

If there exists a $\aleph_2$-saturated ideal on $\omega_1$ then:

  • $2^{\aleph_0}=\aleph_1$ implies $2^{\aleph_1}=\aleph_2$
  • $2^{\aleph_0}=\aleph_{\omega_1}$ implies $2^{\aleph_1}\leq\aleph_{\omega_2}$.
  • $\aleph_1 < 2^{\aleph_0} < \aleph_{\omega_1}$ implies $2^{\aleph_0} = 2^{\aleph_1}$.
  • $2^{<\aleph_{\omega_1}}=\aleph_{\omega_1}$ implies $2^{\aleph_{\omega_1}}<\aleph_{\omega_2}$

This hypothesis, which follows from Martin's Maximum, is consistent relative to a Woodin cardinal, in fact that ideal can be the nonstationary ideal on $\omega_1$. This cannot happen for cardinals larger than $\omega_1$ however: for every cardinal $\kappa\geq\aleph_2$, the nonstationary ideal on $\kappa$ is not $\kappa^+$-saturated.


Main article: Ultrapower

Precipitous ideals

Let $I$ be an ideal on some uncountable cardinal $\kappa$. Consider the notion of forcing $(P,\subseteq)$ where $P=\{X\subseteq\kappa:X\not\in I\}$, and let $G$ be a generic filter on $P$. Then $G$ is an ultrafilter on $\kappa$ that extends the filter dual to $I$. If $I$ is normal or $\kappa$-complete, so is $G$. In the generic extension $V[G]$, consider the ultrapower $\text{Ult}_G(V)$, which we will call the generic ultrapower. It is always a model of $\text{ZFC}$ but need not be well-founded. A $\kappa$-complete ideal on $\kappa$ is precipitous if the associated generic ultrapower if well-founded. The ideal $\{X\subseteq\kappa:|X|<\kappa\}$ is never precipitous. Every $\kappa^+$-saturated $\kappa$-complete ideal on $\kappa$ is precipitous.

Equivalent definitions

Consider the following infinite game $\mathcal{G}_I$: two players, Empty and Nonempty, alternatively choose sets $S_n$ such that $S_n\not\in I$ and $S_{n+1}\subseteq S_n$. Empty plays first and wins if $\bigcap^\infty_{n=0}S_n=\empty$.

Assume $I$ contains all singleton. Let $S$ be a set not in $I$. An $I$-partition of $S$ is a maximal family $W$ of subsets of $S$ disjoint from $I$ such that the intersection of any two sets in $W$ is in $I$. An $I$-partition $W_0$ is a refinement of an $I$-partition $W_1$, noted $W_0\leq W_1$, if every set in $W_0$ is a subset of some set in $W_1$.

A functional on $S$ is a collection $F$ of functions such that $\{\text{dom}(f):f\in F\}$ is an $I$-partition of $S$ and any two distinct functions of $F$ have a different domain. We order the functionals on $S$ the following way: $F_0<F_1$ if each $f$ in $F$ and $G$ is a function into the ordinals, $\{\text{dom}(f):f\in F\}\leq\{\text{dom}(g):g\in G\}$ and for every $f\in F$, $g\in G$ such that $\text{dom}(f)\subseteq\text{dom}(g)$, one has $f(\alpha)<g(\alpha)$ for every $\alpha\in\text{dom}(f)$.

The following are equivalent for a $\kappa$-complete ideal $I$ on $\kappa$:

  • $I$ is precipitous.
  • Empty has no winning strategy in $\mathcal{G}_I$.
  • For every $S$ not in $I$ there is no sequence of functionals on $S$ such that $F_0>F_1>...>F_n>...$.
  • For every $S$ not in $I$ and $I$-partitions $\{W_n:n<\omega\}$ of $S$ such that $W_0\geq W_1\geq...\geq W_n\geq...$ there exists a sequence $X_0\supseteq X_1\supseteq...\supseteq X_n\supseteq...$ such that $X_n\in W_n$ for all $n$ and $\bigcap^\infty_{n=0}X_n$ is nonempty.

Consistency results

The existence of a precipitous ideal on a regular uncountable cardinal implies the consistency of the existence of an inner model of $\text{ZFC}$ that contains a measurable cardinal. It also implies the existence of a generic extension in which $\kappa=\aleph_1$ and $\kappa$ carries a precipitous ideal.

It is consistent, relative to the existence of a measurable cardinal, that the nonstationary ideal on $\omega_1$ is precipitous. This statement is in fact equiconsistent with the existence of a measurable. On the other hand, the nonstationary ideal on $\omega_2$ being precipitous is a much stronger statement, and is equiconsistent with the existence of measurable of Mitchell order 2, and thus stronger than the existence of a proper class of measurables. The consistency strength of the nonstationary ideal on a successor cardinal $\kappa\geq\aleph_3$ is inbetween the existence of a measurable of Mitchell order $\kappa^+$ and one of order $\kappa^{++}$. For limit cardinals, the consistency strength is in the region of Woodin cardinals.


Filters are related to the concept of measures.

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

  • $\mu(\empty)=0$, $\mu(S)>0$
  • $\mu(X)\leq\mu(Y)$ whenver $X\subseteq 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 for all $X\subseteq S$, either $\mu(X)=0$ or $\mu(X)=1$. A set $A\subseteq S$ such that $\mu(A)>0$ is an atom for $\mu$ if $\mu(X)=0$ or $\mu(X)=\mu(A)$ for all $X\subseteq A$. $\mu$ is atomless if it has no atoms.

A set $X\subseteq 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. (See also projective)


  • Let $\mu$ be a 2-valued measure on $S$. Then $\{X\subseteq 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\subseteq 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\subseteq 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\subseteq 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\subseteq A$ such that $\mu(B)=b$.

Normal fine measures and large cardinals

Let $\kappa$ be an uncountable cardinal. Let $\mathcal{P}_\kappa(A)$ for $|A|\geq\kappa$ be the set of all subsets of $A$ of cardinality at most $\kappa$.

A filter $F$ on $\mathcal{P}_\kappa(A)$ is a fine filter if for every $a\in A$, the set $\{x\in \mathcal{P}_\kappa(A) : a\in x\}\in F$. If $F$ is also $\sigma$-complete and an ultrafilter, it is called a fine measure because it can be identified with its dual measure $\mu$ defined by $\mu(X)=1$ iff $X\in F$, $0$ otherwise.

A fine measure $F$ on $\mathcal{P}_\kappa(A)$ is normal if for every function $f:\mathcal{P}_\kappa(A)\to A$, if the set $\{x\in \mathcal{P}_\kappa(A) : f(x)\in x\}\in F$ then $f$ is constant on a set in $F$, i.e. there is $k\in A$ such that $F$ also contains the set $\{x\in \mathcal{P}_\kappa(A) : f(x)=k\}$. Note that normal fine measures are also normal in the sense that they are closed under diagonal intersections, i.e. for every family $\{X_\alpha : \alpha<\kappa\}$ and $X_\alpha\in F$ for all $\alpha<\kappa$, one has $\Delta_{\alpha<\kappa}X_\alpha\in F$.

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 $j:V\to\mathcal{M}$ is a nontrivial elementary embedding with critical point $\kappa$, then $\mathcal{U}_j=\{x\subseteq \kappa : \kappa\in j(x)\}$ is a $\kappa$-complete nonprincipal ultrafilter on $\mathcal{P}(\kappa)$ and $\kappa$ is measurable. In fact, $\mathcal{U}_j$ is a normal fine measure on $\kappa$, which we can call the "canonical" normal fine measure generated by $j$.

If, for every set $S$, every $\kappa$-complete filter on $S$ can be extended to a $\kappa$-complete ultrafilter on $S$, then $\kappa$ is strongly compact. The converse is also true, every strongly compact cardinal has this property. Not that nonprincipality is not required here. Every strongly compact cardinal is measurable, and 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 $\mathcal{P}_\kappa(A)$. Those measures don't have to be normal.

If there is a set $\lambda$ with $\lambda\geq\kappa$ such that there is a normal fine measure on $\mathcal{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 $\mathcal{P}_\kappa(A)$. Clearly, every supercompact is strongly compact by the last characterization of strong compactness. It is open whether supercompactness is stronger than strong compactness consistency-wise.

Every set in a normal measure is stationary, also every measurable cardinal carries a normal measure containing the set of all inaccessible, Mahlo, and even Ramsey cardinals below it. Every supercompact cardinal $\kappa$ carries $2^{2^\kappa}$ normal measures.

See Also


  1. Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www   bibtex
Main library