cantors-attic

Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.

View the Project on GitHub neugierde/cantors-attic

Quick navigation
The upper attic
The middle attic
The lower attic
The parlour
The playroom
The library
The cellar

Sources
Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine

Filters and ideals

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 partition $\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 (Jech, 2003) or (Kanamori, 2009).

Definitions

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

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

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 either.

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. ideal) is uniform if it only contains sets of the same cardinality.

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 or an ideal being countably complete (or $\sigma$-complete) means that it is $\omega_1$-complete. It is customary to use the term $\sigma$-ideal instead of $\sigma$-complete ideal.

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 following definitions will be useful later in this article: $\mathcal{P}_\kappa(A)$ for $|A|\geq\kappa$ is the set of all subsets of $A$ of cardinality at most $\kappa$. $[A]^{<\kappa}$ and $[A]^\kappa$ are the sets of all subsets of $A$ of cardinality $<\kappa$ and $\kappa$, respectively. Note that $\mathcal{P}_\kappa(A)=[A]^{<\kappa}\cup[A]^\kappa$.

Properties

The finite intersection property is equivalent to $\omega$-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$. 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 infinite cardinal $\kappa$ 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:M\to 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))^M$; in particular if $M=V$ then $(\mathcal{P}(\kappa))^M=\mathcal{P}(\kappa)$ and thus $\kappa$ is measurable.

The nonstationary ideal and the club filter

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 despite being normal and $\kappa$-complete, as it is not an ultrafilter.

Note that if $I$ is a $\kappa$-complete ideal on $\kappa$ containing all singletons of elements of $\kappa$, then $I$ contains all subsets of $\kappa$ of cardinality less than $\kappa$.

Saturated ideals

We say that an ideal $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$. $\omega_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.

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 $\kappa$ carries a normal $\lambda$-saturated $\kappa$-complete ideal $I$ for some $\lambda<\kappa$ then $\kappa$ has the tree property and also it is measurable in $L[I]$ (see constructible universe).

Any cardinal carrying a 2-saturated $\sigma$-ideal is measurable. Any cardinal carrying a $\sigma$-saturated $\sigma$-ideal must be either measurable or $\leq 2^{\aleph_0}$ and real-valued measurable. No successor cardinal $\kappa$ carries a $\kappa$-saturated $\kappa$-complete ideal. On the other hand it is consistent (relative to large cardinals) for a successor $\kappa$ to carry a $\kappa^+$-saturated $\kappa$-complete ideal.

It is consistent relative to a huge cardinal that every regular cardinal $\kappa$ there is a $\kappa^+$-saturated $\kappa$-complete ideal. It is consistent relative to a 2-huge cardinal that, for every $n>0$, $[\omega_{n+1}]^{\omega_n}$ carries a normal fine $\omega_{n+1}$-saturated $\omega_n$-complete ideal. Suppose that $\kappa$ is an almost huge cardinal and $\mu<\kappa$ is regular. Then there is a forcing extension in which $\kappa=\mu^+$ and there is a $\kappa$-complete, $\kappa^+$-saturated ideal on $\kappa$.

Suppose that $\mu$ is a supercompact cardinal and $\kappa>\mu$ is an almost huge cardinal. Then there is a forcing extension that satisfies the generalized continuum hypothesis and “there is a stationary subset $S$ of $\omega_{\omega+1}$ such that the nonstationary ideal on $\omega_{\omega+1}$ restricted to subsets of $S$ is $\omega_{\omega+2}$-saturated”

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

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$. Similarly, if there is a almost huge cardinal then in some generic extension, $\omega_2$ carries a $\omega_3$-saturated $\omega_2$-complete ideal. This ideal however cannot be the nonstationary ideal on $\omega_2$: for every cardinal $\kappa\geq\omega_2$, the nonstationary ideal on $\kappa$ is not $\kappa^+$-saturated.

If there exists a uniform $\omega_2$-saturated ideal on $\omega_2$ then $\Theta^{L(\mathbb{R})}\leq\omega_2$. This inequality if known as the constructive continuum hypothesis, and means that it is impossible to effectively construct a counterexample of the continuum hypothesis within $L(\mathbb{R})$. In the presence of a measurable cardinal, $\Theta^{L(\mathbb{R})}$ has cofinality $\omega$ and so it is then strictly below $\omega_2$. Note that this ideal cannot be $\omega_2$-complete: only limit cardinals $\kappa$ can carry $\kappa$-saturated $\kappa$-complete ideals.

The above result is linked to a more general theorem: $\Theta^{L(\mathbb{R})}\leq\omega_n$ follows both from the existence of a $\sigma$-ideal on $\omega_n$ such that the forcing notion $\mathcal{P}(\omega_n)/I$ is proper, and from the $\omega_{n+1}$-saturation of the nonstationary ideal on $\omega_n$ restrained to sets of cofinality $\omega_{n-1}$.

There is no uniform $\omega_2$-saturated $\sigma$-ideal on any cardinal between $\omega_\omega$ and $\omega_{\omega_1}$. Let $\lambda$ be a singular cardinal. Then there is no $\lambda$-saturated normal fine ideal on $[\lambda]^\lambda$. In particular, there is no normal fine $\omega_n$-saturated $\sigma$ ideal on $[\omega_\omega]^{\omega_\omega}$, for all $n<\omega$.

Dense ideals

Let $I$ be an ideal on $S$. We say that $I$ is $\lambda$-dense if there is a family $D\subseteq\mathcal{P}(S)\setminus I$ of cardinality $\lambda$ such that for every $X\in\mathcal{P}(S)\setminus I$ there is a $Y\in D$ such that $Y\setminus X\in I$. Every $\lambda$-dense ideal is $\mu$-saturated for all $\mu>\lambda$. $I$ is $\sigma$-dense if it is $\omega_1$-dense.

If there is a $\sigma$-dense $\sigma$-ideal on $\omega_1$ then the axiom of determinacy holds in $L(\mathbb{R})$, in fact the existence of such an ideal is equiconsistent with the axiom of determinacy itself. The existence of a such ideal also implies the failure of one of Martin’s axioms, namely $\text{MA}_{\aleph_1}$. In particular the proper forcing axiom fails. Also, there is a Suslin tree on $\omega_1$.

If the nonstationary ideal on $\omega_1$ is $\sigma$-dense, then the continuum hypothesis fails and $2^{\aleph_0}=2^{\aleph_1}$. If there is a uniform $\sigma$-dense $\sigma$-ideal on $\omega_2$ then the continuum hypothesis holds.

If there is a $\kappa$-dense $\kappa$-complete ideal on a regular cardinal $\kappa$ then the partition property $\kappa^+\to(\kappa^2+1,\alpha)^2_2$ holds for all $\alpha<\kappa^+$.

If there is a $2^{\aleph_0}$-dense ideal $I$ on $[(2^{\aleph_0})^+]^{\omega_1}$ or on $[2^{\aleph_0}]^{<\omega_1}$ then in $L(\mathbb{R})$, every set of reals is Lebesgue measurable, completely Ramsey and has the property of Baire, also the partition property $\omega\to(\omega)^\omega_2$ holds.

Ultrapowers

Main article: Ultrapower

Precipitous ideals

Let $I$ be an ideal on $S$. Consider the notion of forcing $(P,\subseteq)$ where $P=\{X\subseteq S:X\not\in I\}$, and let $G$ be a generic filter on $P$. Then $G$ is an ultrafilter on $S$ 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. An ideal is precipitous is the associated generic ultrapower is well-founded.

The ideal $\{X\subseteq\kappa:|X|<\kappa\}$ is never precipitous. Every $\kappa^+$-saturated $\kappa$-complete ideal on $\kappa$ is precipitous. If $\kappa$ is the successor of a regular cardinal then there is no normal fine precipitous ideal on $[\kappa]^\kappa$.

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$:

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. The existence of a measurable cardinal $\kappa$ implies the existence of a generic extension in which $\kappa=\omega_1$ and $\omega_1$ 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\omega_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.

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:\mathcal{P}(S)\to[0,+\infty]$ such that:

$\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 $\omega_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)

Properties

Normal and fine filters

Let $\kappa$ be an uncountable cardinal. By “filter on $\mathcal{P}_\kappa(A)$” we mean that $F$ contains subsets of $\mathcal{P}_\kappa(A)$, not elements of it. For $\{X_i:i\in A\}$ a sequence of subsets of $\mathcal{P}_\kappa(A)$ indexed by elements of $A$, we define the diagonal intersection $\Delta_{i\in A}X_i$ of this sequence to be $\{x\in\mathcal{P}_\kappa(A) : x\in\bigcap_{i\in x}X_i\}$, itself a subset of $\mathcal{P}_\kappa(A)$.

If $U$ is a $\kappa$-complete nonprincipal ultrafilter on some set $S$ with $|S|\geq\kappa$ we can associate $U$ with its dual 2-valued measure $\mu(X)$ which is 1 iff $X$ is in $U$, and is 0 otherwise. It is usual to refer to $U$ as a measure.

We are going to define fineness and normality for filters on $\kappa$ or on some $\mathcal{P}_\kappa(A)$. Different authors often have different terminology for the concepts defined below, for instance some call normal ultrafilter what we are going to call a normal fine measure. The terminology used here will be used throughout Cantor’s Attic, but when reading papers or other sites on set theory, one should be cautious about the possible differences in terminology.

Let $F$ be a filter on some set $S$ with $|S|\geq\kappa$ (usually the only cases considered will be $S=\kappa$ and $S=\mathcal{P}_\kappa(A)$ for some $A$ with $|A|\geq\kappa$).

Not every normal filter needs to be fine. Fineness is usually unimportant when $S=\kappa$, but it is an important property when $S=\mathcal{P}_\kappa(A)$. Every set in a normal measure on $\kappa$ is stationary in $\kappa$. If $V=L[D]$ where $D$ is a normal measure on some cardinal $\kappa$ then the generalized continuum hypothesis holds.

Given a function $f:\kappa\to\kappa$ and a set $X\subseteq\kappa$, we say that $f$ is regressive on $X$ if $f(\alpha)\leq\alpha$ for all $\alpha\in X$. If $D$ is a measure on $\kappa$, then it is normal if and only if every function regressive on $X$ for $X\in D$, that function is also constant on a set in $D$. This reminds of Fodor’s theorem: every regressive function on $\kappa$ is constant on a stationary subset of $\kappa$. A normal measure contains all the said stationary subsets (but not only them).

Another characterization of normal measures is: a measure $D$ on $\kappa$ is normal if for all $X\subseteq\kappa$, one has $X\in D$ if and only if $\kappa\in j_D(X)$ where $j_D$ is the canonical ultrapower embedding generated by $D$. Similarly, a measure $D$ on $\mathcal{P}_\kappa(\lambda)$ for some $\lambda\geq\kappa$ is normal if for all $X\subseteq\mathcal{P}_\kappa(\lambda)$, one has $X\in D$ if and only if $j``\lambda\in j(X)$ where $j``\lambda=\{j(\alpha) : \alpha<\lambda\}$.

If there is a normal fine $\lambda$-saturated measure on $[\lambda]^{<\kappa}$ then $\lambda^{<\kappa}=\text{max}(\lambda,2^{<\kappa})$.

Large cardinals

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 measure (i.e. a $\kappa$-complete nonprincipal ultrafilter) on $\kappa$. If $j:V\to 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$. The canonical measure contains the set of all inaccessible, Mahlo, and even Ramsey cardinals below $\kappa$, and much more.

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. 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.

If there are cardinals $\kappa$ and $\lambda$ such that there is a normal measure $D$ on $\{X\subseteq\lambda : \text{order-type}(X)=\kappa\}$ then $\kappa$ is huge and there is a nontrivial elementary embedding $j:V\to M$ for a transitive class $M$ such that $\kappa = \mathrm{crit}(j)$, $\lambda = j(\kappa)$, $M^\lambda\subseteq M$ and $X\in D$ if and only if $j``\lambda\in j(X)$. The ordinal $\lambda$ is always a measurable cardinal and is called the target of $j$. It is itself quite big, though it is $\kappa$ that bears most of the strong large cardinal properties. While the least huge cardinal is less than the least supercompact (assuming both exists), the rank $V_\kappa$ satisfies the existence of unboundedly many supercompact cardinals, thus the existence of a such cardinal has much higher consistency strength than the existence of a supercompact cardinal.

See Also

References

  1. Jech, T. J. (2003). Set Theory (Third). Springer-Verlag. https://logic.wikischolars.columbia.edu/file/view/Jech%2C+T.+J.+%282003%29.+Set+Theory+%28The+3rd+millennium+ed.%29.pdf
  2. Kanamori, A. (2009). The higher infinite (Second, p. xxii+536). Springer-Verlag. https://link.springer.com/book/10.1007%2F978-3-540-88867-3
Main library