Filters on $\mathbb{N}$

From Cantor's Attic
Revision as of 12:12, 11 September 2017 by Wabb2t (Talk | contribs) (Wabb2t moved page Ultrafilter on N to Filters on N)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Reminder on real numbers

One of the classical constructions of real numbers is to consider Cauchy sequences of rational numbers and an equivalence relation. If $\{a_n\}_n$ and $\{b_n\}_n$ are Cauchy sequences, then $\{a_n\}_n\sim \{b_n\}_n$ if the sequence $\{a_n-b_n\}_n$ converges to zero. The reader may refer to their favorite source for more about Cauchy sequences.

Beyond real numbers?

It would seem interesting to be able to consider diverging sequences as candidates for infinite numbers since, at least for monotonic increasing sequences, they exceed all Cauchy sequences.

Let $\{n\}_n$ and $\{n+\frac{1}{n}\}_n$ be two clearly diverging sequences. They satisfy the condition that $\{n-(n+\frac{1}{n})\}_n$ converges to zero.

Yet an additional requirement for these to be considered as numbers would be that if $x,y,a,b$ stand for such sequences and $x\sim a$ and $y\sim b$ (for some equivalence relation) then $x\cdot y\sim a\cdot b$.

In the example given above, the product $\{n\cdot(n+\frac{1}{n})\}_n=\{n^2+1\}_n$ and this does will not satisfy the condition of converging to $\{n^2\}_n$ thus the Cauchy equivalence relation will not do.

The goal that is achieved with ultrafilters is to provide a concept of sequences of real numbers agreeing almost everywhere providing a set endowed with the usual operations and which extends the field of real numbers.


A filter $\mathcal{F}$ on $\mathbb{N}$ is a set of subsets of $\mathbb{N}$ satisfying the following conditions:

  • If $A,B\in \mathcal{F}$ then $A\cap B\in\mathcal{F}\quad$ (Closed under intersection)
  • If $A\in \mathcal{F}$ and $A\subset B\subset \mathbb{N}$ then $B\in \mathcal{F}\quad$ (Superset property)


  • $\{A\subseteq \mathbb{N}\ |\ i\in A\}$ for some natural number $i$.
  • $\{A\subseteq\mathbb{N}\ |\ \mathbb{N}\setminus A \quad\text{ is finite}\}$

The second example is the cofinite filter. It contains complements of finite sets.

A filter which contains the empty set is the powerset of $\mathbb{N}$. A filter which is not the powerset is a proper filter


An ultrafilter on $\mathbb{N}$ is a proper filter which has the extra property that for any subset $A$ of $\mathbb{N}$ either $A$ or its complement $\mathbb{N}\setminus A$ belongs to the ultrafilter.

The first example of filter is in fact an ultrafilter. It is a principal ultrafilter generated by $i$.

Filters and ultrafilters can be defined on other sets than $\mathbb{N}$. If they are defined on finite sets, then all ultrafilters are principal. If a filter contains a finite set then it contains a singleton and is therefore a principal ultrafilter. Hence a nonprincipal ultrafilter must contain all cofinite sets.

The existence of nonprincipal ultrafilters is proven using the axiom of choice, or one of its equivalents such as Zorn's lemma.

(For more on ultrafilters, see the excellent book by Robert Goldblatt [1]).

Sequences of real numbers

Let $\{a_n\}$ and $\{b_n\}$ be two sequences of real numbers. We will say that they agree almost everywhere, modulo a nonprincipal ultrafilter $\mathcal{F}$, if the set $\{k\ |\ a_k=b_k\}$ belongs to the ultrafilter. This determines equivalence classes on sequences of real numbers. The set of these equivalence classes is called the set of hyperreals and is denoted by ${}^*\mathbb{R}$.

Real number are included in the hyperreal by identifying them with constant sequences.

In this setting, sequences which are diverging with respect to the Cauchy criterion, such as $\{n\}$, can become representatives of infinite hyperreal numbers. They are infinite in the sense that, in this example, it exceeds all constant sequences, hence it is greater than any real number.

Similarly, $\{1/n\}$ represents a positive infinitesimal. It is less than any nonzero positive real number.

An interesting question is whether all constructions of the hypperreals are isomorphic i.e., are there properties of the hyperreals which depend on the choice of the nonprincipal ultrafilter? The answer depends on whether one accepts the continuum hypothesis. With the CH, the answer is no, the construction of the hyperreals does not depend on the ultrafilter.


    Main library