Misplaced Pages

In the mathematical field of set theory, an ultrafilter on a set ${\displaystyle X}$ is a maximal filter on the set ${\displaystyle X.}$ In other words, it is a collection of subsets of ${\displaystyle X}$ that satisfies the definition of a filter on ${\displaystyle X}$ and that is maximal with respect to inclusion, in the sense that there does not exist a strictly larger collection of subsets of ${\displaystyle X}$ that is also a filter. (In the above, by definition a filter on a set does not contain the empty set.) Equivalently, an ultrafilter on the set ${\displaystyle X}$ can also be characterized as a filter on ${\displaystyle X}$ with the property that for every subset ${\displaystyle A}$ of ${\displaystyle X}$ either ${\displaystyle A}$ or its complement ${\displaystyle X\setminus A}$ belongs to the ultrafilter.

Ultrafilters on sets are an important special instance of ultrafilters on partially ordered sets, where the partially ordered set consists of the power set ${\displaystyle \wp (X)}$ and the partial order is subset inclusion ${\displaystyle \,\subseteq .}$ This article deals specifically with ultrafilters on a set and does not cover the more general notion.

There are two types of ultrafilter on a set. A principal ultrafilter on ${\displaystyle X}$ is the collection of all subsets of ${\displaystyle X}$ that contain a fixed element ${\displaystyle x\in X}$. The ultrafilters that are not principal are the free ultrafilters. The existence of free ultrafilters on any infinite set is implied by the ultrafilter lemma, which can be proven in ZFC. On the other hand, there exists models of ZF where every ultrafilter on a set is principal.

Ultrafilters have many applications in set theory, model theory, and topology. Usually, only free ultrafilters lead to non-trivial constructions. For example, an ultraproduct modulo a principal ultrafilter is always isomorphic to one of the factors, while an ultraproduct modulo a free ultrafilter usually has a more complex structure.

Definitions

Given an arbitrary set ${\displaystyle X,}$ an ultrafilter on ${\displaystyle X}$ is a non-empty family ${\displaystyle U}$ of subsets of ${\displaystyle X}$ such that:

1. Proper or non-degenerate: The empty set is not an element of ${\displaystyle U.}$
2. Upward closed in ${\displaystyle X}$: If ${\displaystyle A\in U}$ and if ${\displaystyle B\subseteq X}$ is any superset of ${\displaystyle A}$ (that is, if ${\displaystyle A\subseteq B\subseteq X}$) then ${\displaystyle B\in U.}$
3. π−system: If ${\displaystyle A}$ and ${\displaystyle B}$ are elements of ${\displaystyle U}$ then so is their intersection ${\displaystyle A\cap B.}$
4. If ${\displaystyle A\subseteq X}$ then either ${\displaystyle A}$ or its complement ${\displaystyle X\setminus A}$ is an element of ${\displaystyle U.}$

Properties (1), (2), and (3) are the defining properties of a filter on ${\displaystyle X.}$ Some authors do not include non-degeneracy (which is property (1) above) in their definition of "filter". However, the definition of "ultrafilter" (and also of "prefilter" and "filter subbase") always includes non-degeneracy as a defining condition. This article requires that all filters be proper although a filter might be described as "proper" for emphasis.

A filter subbase is a non-empty family of sets that has the finite intersection property (i.e. all finite intersections are non-empty). Equivalently, a filter subbase is a non-empty family of sets that is contained in some (proper) filter. The smallest (relative to ${\displaystyle \subseteq }$) filter containing a given filter subbase is said to be generated by the filter subbase.

The upward closure in ${\displaystyle X}$ of a family of sets ${\displaystyle P}$ is the set

${\displaystyle P^{\uparrow X}:=\{S:A\subseteq S\subseteq X{\text{ for some }}A\in P\}.}$

A prefilter or filter base is a non-empty and proper (i.e. ${\displaystyle \varnothing \not \in P}$) family of sets ${\displaystyle P}$ that is downward directed, which means that if ${\displaystyle B,C\in P}$ then there exists some ${\displaystyle A\in P}$ such that ${\displaystyle A\subseteq B\cap C.}$ Equivalently, a prefilter is any family of sets ${\displaystyle P}$ whose upward closure ${\displaystyle P^{\uparrow X}}$ is a filter, in which case this filter is called the filter generated by ${\displaystyle P}$ and ${\displaystyle P}$ is said to be a filter base for ${\displaystyle P^{\uparrow X}.}$

The dual in ${\displaystyle X}$ of a family of sets ${\displaystyle P}$ is the set ${\displaystyle X\setminus P:=\{X\setminus B:B\in P\}.}$ For example, the dual of the power set ${\displaystyle \wp (X)}$ is itself: ${\displaystyle X\setminus \wp (X)=\wp (X).}$ A family of sets is a proper filter on ${\displaystyle X}$ if and only if its dual is a proper ideal on ${\displaystyle X}$ ("proper" means not equal to the power set).

Generalization to ultra prefilters

A family ${\displaystyle U\neq \varnothing }$ of subsets of ${\displaystyle X}$ is called ultra if ${\displaystyle \varnothing \not \in U}$ and any of the following equivalent conditions are satisfied:

1. For every set ${\displaystyle S\subseteq X}$ there exists some set ${\displaystyle B\in U}$ such that ${\displaystyle B\subseteq S}$ or ${\displaystyle B\subseteq X\setminus S}$ (or equivalently, such that ${\displaystyle B\cap S}$ equals ${\displaystyle B}$ or ${\displaystyle \varnothing }$).
2. For every set ${\displaystyle S\subseteq {\textstyle \bigcup \limits _{B\in U}}B}$ there exists some set ${\displaystyle B\in U}$ such that ${\displaystyle B\cap S}$ equals ${\displaystyle B}$ or ${\displaystyle \varnothing .}$
   • Here, ${\displaystyle {\textstyle \bigcup \limits _{B\in U}}B}$ is defined to be the union of all sets in ${\displaystyle U.}$
   • This characterization of "${\displaystyle U}$ is ultra" does not depend on the set ${\displaystyle X,}$ so mentioning the set ${\displaystyle X}$ is optional when using the term "ultra."
3. For every set ${\displaystyle S}$ (not necessarily even a subset of ${\displaystyle X}$) there exists some set ${\displaystyle B\in U}$ such that ${\displaystyle B\cap S}$ equals ${\displaystyle B}$ or ${\displaystyle \varnothing .}$
   • If ${\displaystyle U}$ satisfies this condition then so does every superset ${\displaystyle V\supseteq U.}$ In particular, a set ${\displaystyle V}$ is ultra if and only if ${\displaystyle \varnothing \not \in V}$ and ${\displaystyle V}$ contains as a subset some ultra family of sets.

A filter subbase that is ultra is necessarily a prefilter.

The ultra property can now be used to define both ultrafilters and ultra prefilters:

An ultra prefilter is a prefilter that is ultra. Equivalently, it is a filter subbase that is ultra.

An ultrafilter on ${\displaystyle X}$ is a (proper) filter on ${\displaystyle X}$ that is ultra. Equivalently, it is any filter on ${\displaystyle X}$ that is generated by an ultra prefilter.

Ultra prefilters as maximal prefilters

To characterize ultra prefilters in terms of "maximality," the following relation is needed.

Given two families of sets ${\displaystyle M}$ and ${\displaystyle N,}$ the family ${\displaystyle M}$ is said to be coarser than ${\displaystyle N,}$ and ${\displaystyle N}$ is finer than and subordinate to ${\displaystyle M,}$ written ${\displaystyle M\leq N}$ or N ⊢ M, if for every ${\displaystyle C\in M,}$ there is some ${\displaystyle F\in N}$ such that ${\displaystyle F\subseteq C.}$ The families ${\displaystyle M}$ and ${\displaystyle N}$ are called equivalent if ${\displaystyle M\leq N}$ and ${\displaystyle N\leq M.}$ The families ${\displaystyle M}$ and ${\displaystyle N}$ are comparable if one of these sets is finer than the other.

The subordination relationship, i.e. ${\displaystyle \,\geq ,\,}$ is a preorder so the above definition of "equivalent" does form an equivalence relation. If ${\displaystyle M\subseteq N}$ then ${\displaystyle M\leq N}$ but the converse does not hold in general. However, if ${\displaystyle N}$ is upward closed, such as a filter, then ${\displaystyle M\leq N}$ if and only if ${\displaystyle M\subseteq N.}$ Every prefilter is equivalent to the filter that it generates. This shows that it is possible for filters to be equivalent to sets that are not filters.

If two families of sets ${\displaystyle M}$ and ${\displaystyle N}$ are equivalent then either both ${\displaystyle M}$ and ${\displaystyle N}$ are ultra (resp. prefilters, filter subbases) or otherwise neither one of them is ultra (resp. a prefilter, a filter subbase). In particular, if a filter subbase is not also a prefilter, then it is not equivalent to the filter or prefilter that it generates. If ${\displaystyle M}$ and ${\displaystyle N}$ are both filters on ${\displaystyle X}$ then ${\displaystyle M}$ and ${\displaystyle N}$ are equivalent if and only if ${\displaystyle M=N.}$ If a proper filter (resp. ultrafilter) is equivalent to a family of sets ${\displaystyle M}$ then ${\displaystyle M}$ is necessarily a prefilter (resp. ultra prefilter). Using the following characterization, it is possible to define prefilters (resp. ultra prefilters) using only the concept of filters (resp. ultrafilters) and subordination:

An arbitrary family of sets is a prefilter if and only it is equivalent to a (proper) filter.

An arbitrary family of sets is an ultra prefilter if and only it is equivalent to an ultrafilter.

A maximal prefilter on ${\displaystyle X}$ is a prefilter ${\displaystyle U\subseteq \wp (X)}$ that satisfies any of the following equivalent conditions:

1. ${\displaystyle U}$ is ultra.
2. ${\displaystyle U}$ is maximal on ${\displaystyle \operatorname {Prefilters} (X)}$ with respect to ${\displaystyle \,\leq ,}$ meaning that if ${\displaystyle P\in \operatorname {Prefilters} (X)}$ satisfies ${\displaystyle U\leq P}$ then ${\displaystyle P\leq U.}$
3. There is no prefilter properly subordinate to ${\displaystyle U.}$
4. If a (proper) filter ${\displaystyle F}$ on ${\displaystyle X}$ satisfies ${\displaystyle U\leq F}$ then ${\displaystyle F\leq U.}$
5. The filter on ${\displaystyle X}$ generated by ${\displaystyle U}$ is ultra.

Characterizations

There are no ultrafilters on the empty set, so it is henceforth assumed that ${\displaystyle X}$ is nonempty.

A filter subbase ${\displaystyle U}$ on ${\displaystyle X}$ is an ultrafilter on ${\displaystyle X}$ if and only if any of the following equivalent conditions hold:

1. for any ${\displaystyle S\subseteq X,}$ either ${\displaystyle S\in U}$ or ${\displaystyle X\setminus S\in U.}$
2. ${\displaystyle U}$ is a maximal filter subbase on ${\displaystyle X,}$ meaning that if ${\displaystyle F}$ is any filter subbase on ${\displaystyle X}$ then ${\displaystyle U\subseteq F}$ implies ${\displaystyle U=F.}$

A (proper) filter ${\displaystyle U}$ on ${\displaystyle X}$ is an ultrafilter on ${\displaystyle X}$ if and only if any of the following equivalent conditions hold:

1. ${\displaystyle U}$ is ultra;
2. ${\displaystyle U}$ is generated by an ultra prefilter;
3. For any subset ${\displaystyle S\subseteq X,}$ ${\displaystyle S\in U}$ or ${\displaystyle X\setminus S\in U.}$
   • So an ultrafilter ${\displaystyle U}$ decides for every ${\displaystyle S\subseteq X}$ whether ${\displaystyle S}$ is "large" (i.e. ${\displaystyle S\in U}$) or "small" (i.e. ${\displaystyle X\setminus S\in U}$).
4. For each subset ${\displaystyle A\subseteq X,}$ either ${\displaystyle A}$ is in ${\displaystyle U}$ or (${\displaystyle X\setminus A}$) is.
5. ${\displaystyle U\cup (X\setminus U)=\wp (X).}$ This condition can be restated as: ${\displaystyle \wp (X)}$ is partitioned by ${\displaystyle U}$ and its dual ${\displaystyle X\setminus U.}$
   • The sets ${\displaystyle P}$ and ${\displaystyle X\setminus P}$ are disjoint for all prefilters ${\displaystyle P}$ on ${\displaystyle X.}$
6. ${\displaystyle \wp (X)\setminus U=\left\{S\in \wp (X):S\not \in U\right\}}$ is an ideal on ${\displaystyle X.}$
7. For any finite family ${\displaystyle S_{1},\ldots ,S_{n}}$ of subsets of ${\displaystyle X}$ (where ${\displaystyle n\geq 1}$), if ${\displaystyle S_{1}\cup \cdots \cup S_{n}\in U}$ then ${\displaystyle S_{i}\in U}$ for some index ${\displaystyle i.}$
   • In words, a "large" set cannot be a finite union of sets none of which is large.
8. For any ${\displaystyle R,S\subseteq X,}$ if ${\displaystyle R\cup S=X}$ then ${\displaystyle R\in U}$ or ${\displaystyle S\in U.}$
9. For any ${\displaystyle R,S\subseteq X,}$ if ${\displaystyle R\cup S\in U}$ then ${\displaystyle R\in U}$ or ${\displaystyle S\in U}$ (a filter with this property is called a prime filter).
10. For any ${\displaystyle R,S\subseteq X,}$ if ${\displaystyle R\cup S\in U}$ and ${\displaystyle R\cap S=\varnothing }$ then either ${\displaystyle R\in U}$ or ${\displaystyle S\in U.}$
11. ${\displaystyle U}$ is a maximal filter; that is, if ${\displaystyle F}$ is a filter on ${\displaystyle X}$ such that ${\displaystyle U\subseteq F}$ then ${\displaystyle U=F.}$ Equivalently, ${\displaystyle U}$ is a maximal filter if there is no filter ${\displaystyle F}$ on ${\displaystyle X}$ that contains ${\displaystyle U}$ as a proper subset (that is, no filter is strictly finer than ${\displaystyle U}$).

Grills and filter-grills

If ${\displaystyle {\mathcal {B}}\subseteq \wp (X)}$ then its grill on ${\displaystyle X}$ is the family $${\displaystyle {\mathcal {B}}^{\#X}:=\{S\subseteq X~:~S\cap B\neq \varnothing {\text{ for all }}B\in {\mathcal {B}}\}}$$ where ${\displaystyle {\mathcal {B}}^{\#}}$ may be written if ${\displaystyle X}$ is clear from context. For example, ${\displaystyle \varnothing ^{\#}=\wp (X)}$ and if ${\displaystyle \varnothing \in {\mathcal {B}}}$ then ${\displaystyle {\mathcal {B}}^{\#}=\varnothing .}$ If ${\displaystyle {\mathcal {A}}\subseteq {\mathcal {B}}}$ then ${\displaystyle {\mathcal {B}}^{\#}\subseteq {\mathcal {A}}^{\#}}$ and moreover, if ${\displaystyle {\mathcal {B}}}$ is a filter subbase then ${\displaystyle {\mathcal {B}}\subseteq {\mathcal {B}}^{\#}.}$ The grill ${\displaystyle {\mathcal {B}}^{\#X}}$ is upward closed in ${\displaystyle X}$ if and only if ${\displaystyle \varnothing \not \in {\mathcal {B}},}$ which will henceforth be assumed. Moreover, ${\displaystyle {\mathcal {B}}^{\#\#}={\mathcal {B}}^{\uparrow X}}$ so that ${\displaystyle {\mathcal {B}}}$ is upward closed in ${\displaystyle X}$ if and only if ${\displaystyle {\mathcal {B}}^{\#\#}={\mathcal {B}}.}$

The grill of a filter on ${\displaystyle X}$ is called a filter-grill on ${\displaystyle X.}$ For any ${\displaystyle \varnothing \neq {\mathcal {B}}\subseteq \wp (X),}$ ${\displaystyle {\mathcal {B}}}$ is a filter-grill on ${\displaystyle X}$ if and only if (1) ${\displaystyle {\mathcal {B}}}$ is upward closed in ${\displaystyle X}$ and (2) for all sets ${\displaystyle R}$ and ${\displaystyle S,}$ if ${\displaystyle R\cup S\in {\mathcal {B}}}$ then ${\displaystyle R\in {\mathcal {B}}}$ or ${\displaystyle S\in {\mathcal {B}}.}$ The grill operation ${\displaystyle {\mathcal {F}}\mapsto {\mathcal {F}}^{\#X}}$ induces a bijection

${\displaystyle {\bullet }^{\#X}~:~\operatorname {Filters} (X)\to \operatorname {FilterGrills} (X)}$

whose inverse is also given by ${\displaystyle {\mathcal {F}}\mapsto {\mathcal {F}}^{\#X}.}$ If ${\displaystyle {\mathcal {F}}\in \operatorname {Filters} (X)}$ then ${\displaystyle {\mathcal {F}}}$ is a filter-grill on ${\displaystyle X}$ if and only if ${\displaystyle {\mathcal {F}}={\mathcal {F}}^{\#X},}$ or equivalently, if and only if ${\displaystyle {\mathcal {F}}}$ is an ultrafilter on ${\displaystyle X.}$ That is, a filter on ${\displaystyle X}$ is a filter-grill if and only if it is ultra. For any non-empty ${\displaystyle {\mathcal {F}}\subseteq \wp (X),}$ ${\displaystyle {\mathcal {F}}}$ is both a filter on ${\displaystyle X}$ and a filter-grill on ${\displaystyle X}$ if and only if (1) ${\displaystyle \varnothing \not \in {\mathcal {F}}}$ and (2) for all ${\displaystyle R,S\subseteq X,}$ the following equivalences hold:

${\displaystyle R\cup S\in {\mathcal {F}}}$ if and only if ${\displaystyle R,S\in {\mathcal {F}}}$ if and only if ${\displaystyle R\cap S\in {\mathcal {F}}.}$

Free or principal

If ${\displaystyle P}$ is any non-empty family of sets then the Kernel of ${\displaystyle P}$ is the intersection of all sets in ${\displaystyle P:}$ $${\displaystyle \operatorname {ker} P:=\bigcap _{B\in P}B.}$$

A non-empty family of sets ${\displaystyle P}$ is called:

• free if ${\displaystyle \operatorname {ker} P=\varnothing }$ and fixed otherwise (that is, if ${\displaystyle \operatorname {ker} P\neq \varnothing }$).
• principal if ${\displaystyle \operatorname {ker} P\in P.}$
• principal at a point if ${\displaystyle \operatorname {ker} P\in P}$ and ${\displaystyle \operatorname {ker} P}$ is a singleton set; in this case, if ${\displaystyle \operatorname {ker} P=\{x\}}$ then ${\displaystyle P}$ is said to be principal at ${\displaystyle x.}$

If a family of sets ${\displaystyle P}$ is fixed then ${\displaystyle P}$ is ultra if and only if some element of ${\displaystyle P}$ is a singleton set, in which case ${\displaystyle P}$ will necessarily be a prefilter. Every principal prefilter is fixed, so a principal prefilter ${\displaystyle P}$ is ultra if and only if ${\displaystyle \operatorname {ker} P}$ is a singleton set. A singleton set is ultra if and only if its sole element is also a singleton set.

The next theorem shows that every ultrafilter falls into one of two categories: either it is free or else it is a principal filter generated by a single point.

Proposition — If ${\displaystyle U}$ is an ultrafilter on ${\displaystyle X}$ then the following are equivalent:

1. ${\displaystyle U}$ is fixed, or equivalently, not free.
2. ${\displaystyle U}$ is principal.
3. Some element of ${\displaystyle U}$ is a finite set.
4. Some element of ${\displaystyle U}$ is a singleton set.
5. ${\displaystyle U}$ is principal at some point of ${\displaystyle X,}$ which means ${\displaystyle \operatorname {ker} U=\{x\}\in U}$ for some ${\displaystyle x\in X.}$
6. ${\displaystyle U}$ does not contain the Fréchet filter on ${\displaystyle X}$ as a subset.
7. ${\displaystyle U}$ is sequential.

Every filter on ${\displaystyle X}$ that is principal at a single point is an ultrafilter, and if in addition ${\displaystyle X}$ is finite, then there are no ultrafilters on ${\displaystyle X}$ other than these. In particular, if a set ${\displaystyle X}$ has finite cardinality ${\displaystyle n<\infty ,}$ then there are exactly ${\displaystyle n}$ ultrafilters on ${\displaystyle X}$ and those are the ultrafilters generated by each singleton subset of ${\displaystyle X.}$ Consequently, free ultrafilters can only exist on an infinite set.

Examples, properties, and sufficient conditions

If ${\displaystyle X}$ is an infinite set then there are as many ultrafilters over ${\displaystyle X}$ as there are families of subsets of ${\displaystyle X;}$ explicitly, if ${\displaystyle X}$ has infinite cardinality ${\displaystyle \kappa }$ then the set of ultrafilters over ${\displaystyle X}$ has the same cardinality as ${\displaystyle \wp (\wp (X));}$ that cardinality being ${\displaystyle 2^{2^{\kappa }}.}$

If ${\displaystyle U}$ and ${\displaystyle S}$ are families of sets such that ${\displaystyle U}$ is ultra, ${\displaystyle \varnothing \not \in S,}$ and ${\displaystyle U\leq S,}$ then ${\displaystyle S}$ is necessarily ultra. A filter subbase ${\displaystyle U}$ that is not a prefilter cannot be ultra; but it is nevertheless still possible for the prefilter and filter generated by ${\displaystyle U}$ to be ultra.

Suppose ${\displaystyle U\subseteq \wp (X)}$ is ultra and ${\displaystyle Y}$ is a set. The trace ${\displaystyle U\vert _{Y}:=\{B\cap Y:B\in U\}}$ is ultra if and only if it does not contain the empty set. Furthermore, at least one of the sets ${\displaystyle U\vert _{Y}\setminus \{\varnothing \}}$ and ${\displaystyle U\vert _{X\setminus Y}\setminus \{\varnothing \}}$ will be ultra (this result extends to any finite partition of ${\displaystyle X}$). If ${\displaystyle F_{1},\ldots ,F_{n}}$ are filters on ${\displaystyle X,}$ ${\displaystyle U}$ is an ultrafilter on ${\displaystyle X,}$ and ${\displaystyle F_{1}\cap \cdots \cap F_{n}\leq U,}$ then there is some ${\displaystyle F_{i}}$ that satisfies ${\displaystyle F_{i}\leq U.}$ This result is not necessarily true for an infinite family of filters.

The image under a map ${\displaystyle f:X\to Y}$ of an ultra set ${\displaystyle U\subseteq \wp (X)}$ is again ultra and if ${\displaystyle U}$ is an ultra prefilter then so is ${\displaystyle f(U).}$ The property of being ultra is preserved under bijections. However, the preimage of an ultrafilter is not necessarily ultra, not even if the map is surjective. For example, if ${\displaystyle X}$ has more than one point and if the range of ${\displaystyle f:X\to Y}$ consists of a single point ${\displaystyle \{y\}}$ then ${\displaystyle \{y\}}$ is an ultra prefilter on ${\displaystyle Y}$ but its preimage is not ultra. Alternatively, if ${\displaystyle U}$ is a principal filter generated by a point in ${\displaystyle Y\setminus f(X)}$ then the preimage of ${\displaystyle U}$ contains the empty set and so is not ultra.

The elementary filter induced by an infinite sequence, all of whose points are distinct, is not an ultrafilter. If ${\displaystyle n=2,}$ then ${\displaystyle U_{n}}$ denotes the set consisting all subsets of ${\displaystyle X}$ having cardinality ${\displaystyle n,}$ and if ${\displaystyle X}$ contains at least ${\displaystyle 2n-1}$ (${\displaystyle =3}$) distinct points, then ${\displaystyle U_{n}}$ is ultra but it is not contained in any prefilter. This example generalizes to any integer ${\displaystyle n>1}$ and also to ${\displaystyle n=1}$ if ${\displaystyle X}$ contains more than one element. Ultra sets that are not also prefilters are rarely used.

For every ${\displaystyle S\subseteq X\times X}$ and every ${\displaystyle a\in X,}$ let ${\displaystyle S{\big \vert }_{\{a\}\times X}:=\{y\in X~:~(a,y)\in S\}.}$ If ${\displaystyle {\mathcal {U}}}$ is an ultrafilter on ${\displaystyle X}$ then the set of all ${\displaystyle S\subseteq X\times X}$ such that ${\displaystyle \left\{a\in X~:~S{\big \vert }_{\{a\}\times X}\in {\mathcal {U}}\right\}\in {\mathcal {U}}}$ is an ultrafilter on ${\displaystyle X\times X.}$

Monad structure

The functor associating to any set ${\displaystyle X}$ the set of ${\displaystyle U(X)}$ of all ultrafilters on ${\displaystyle X}$ forms a monad called the ultrafilter monad. The unit map $${\displaystyle X\to U(X)}$$ sends any element ${\displaystyle x\in X}$ to the principal ultrafilter given by ${\displaystyle x.}$

This ultrafilter monad is the codensity monad of the inclusion of the category of finite sets into the category of all sets, which gives a conceptual explanation of this monad.

Similarly, the ultraproduct monad is the codensity monad of the inclusion of the category of finite families of sets into the category of all families of set. So in this sense, ultraproducts are categorically inevitable.

The ultrafilter lemma

The ultrafilter lemma was first proved by Alfred Tarski in 1930.

The ultrafilter lemma/principle/theorem — Every proper filter on a set ${\displaystyle X}$ is contained in some ultrafilter on ${\displaystyle X.}$

The ultrafilter lemma is equivalent to each of the following statements:

1. For every prefilter on a set ${\displaystyle X,}$ there exists a maximal prefilter on ${\displaystyle X}$ subordinate to it.
2. Every proper filter subbase on a set ${\displaystyle X}$ is contained in some ultrafilter on ${\displaystyle X.}$

A consequence of the ultrafilter lemma is that every filter is equal to the intersection of all ultrafilters containing it.

The following results can be proven using the ultrafilter lemma. A free ultrafilter exists on a set ${\displaystyle X}$ if and only if ${\displaystyle X}$ is infinite. Every proper filter is equal to the intersection of all ultrafilters containing it. Since there are filters that are not ultra, this shows that the intersection of a family of ultrafilters need not be ultra. A family of sets ${\displaystyle \mathbb {F} \neq \varnothing }$ can be extended to a free ultrafilter if and only if the intersection of any finite family of elements of ${\displaystyle \mathbb {F} }$ is infinite.

Relationships to other statements under ZF

Throughout this section, ZF refers to Zermelo–Fraenkel set theory and ZFC refers to ZF with the Axiom of Choice (AC). The ultrafilter lemma is independent of ZF. That is, there exist models in which the axioms of ZF hold but the ultrafilter lemma does not. There also exist models of ZF in which every ultrafilter is necessarily principal.

Every filter that contains a singleton set is necessarily an ultrafilter and given ${\displaystyle x\in X,}$ the definition of the discrete ultrafilter ${\displaystyle \{S\subseteq X:x\in S\}}$ does not require more than ZF. If ${\displaystyle X}$ is finite then every ultrafilter is a discrete filter at a point; consequently, free ultrafilters can only exist on infinite sets. In particular, if ${\displaystyle X}$ is finite then the ultrafilter lemma can be proven from the axioms ZF. The existence of free ultrafilter on infinite sets can be proven if the axiom of choice is assumed. More generally, the ultrafilter lemma can be proven by using the axiom of choice, which in brief states that any Cartesian product of non-empty sets is non-empty. Under ZF, the axiom of choice is, in particular, equivalent to (a) Zorn's lemma, (b) Tychonoff's theorem, (c) the weak form of the vector basis theorem (which states that every vector space has a basis), (d) the strong form of the vector basis theorem, and other statements. However, the ultrafilter lemma is strictly weaker than the axiom of choice. While free ultrafilters can be proven to exist, it is not possible to construct an explicit example of a free ultrafilter (using only ZF and the ultrafilter lemma); that is, free ultrafilters are intangible. Alfred Tarski proved that under ZFC, the cardinality of the set of all free ultrafilters on an infinite set ${\displaystyle X}$ is equal to the cardinality of ${\displaystyle \wp (\wp (X)),}$ where ${\displaystyle \wp (X)}$ denotes the power set of ${\displaystyle X.}$ Other authors attribute this discovery to Bedřich Pospíšil (following a combinatorial argument from Fichtenholz, and Kantorovitch, improved by Hausdorff).

Under ZF, the axiom of choice can be used to prove both the ultrafilter lemma and the Krein–Milman theorem; conversely, under ZF, the ultrafilter lemma together with the Krein–Milman theorem can prove the axiom of choice.

Statements that cannot be deduced

The ultrafilter lemma is a relatively weak axiom. For example, each of the statements in the following list can not be deduced from ZF together with only the ultrafilter lemma:

1. A countable union of countable sets is a countable set.
2. The axiom of countable choice (ACC).
3. The axiom of dependent choice (ADC).

Equivalent statements

Under ZF, the ultrafilter lemma is equivalent to each of the following statements:

1. The Boolean prime ideal theorem (BPIT).
2. Stone's representation theorem for Boolean algebras.
3. Any product of Boolean spaces is a Boolean space.
4. Boolean Prime Ideal Existence Theorem: Every nondegenerate Boolean algebra has a prime ideal.
5. Tychonoff's theorem for Hausdorff spaces: Any product of compact Hausdorff spaces is compact.
6. If ${\displaystyle \{0,1\}}$ is endowed with the discrete topology then for any set ${\displaystyle I,}$ the product space ${\displaystyle \{0,1\}^{I}}$ is compact.
7. Each of the following versions of the Banach-Alaoglu theorem is equivalent to the ultrafilter lemma:
   1. Any equicontinuous set of scalar-valued maps on a topological vector space (TVS) is relatively compact in the weak-* topology (that is, it is contained in some weak-* compact set).
   2. The polar of any neighborhood of the origin in a TVS ${\displaystyle X}$ is a weak-* compact subset of its continuous dual space.
   3. The closed unit ball in the continuous dual space of any normed space is weak-* compact.
      • If the normed space is separable then the ultrafilter lemma is sufficient but not necessary to prove this statement.
8. A topological space ${\displaystyle X}$ is compact if every ultrafilter on ${\displaystyle X}$ converges to some limit.
9. A topological space ${\displaystyle X}$ is compact if and only if every ultrafilter on ${\displaystyle X}$ converges to some limit.
   • The addition of the words "and only if" is the only difference between this statement and the one immediately above it.
10. The Alexander subbase theorem.
11. The Ultranet lemma: Every net has a universal subnet.
    • By definition, a net in ${\displaystyle X}$ is called an ultranet or an universal net if for every subset ${\displaystyle S\subseteq X,}$ the net is eventually in ${\displaystyle S}$ or in ${\displaystyle X\setminus S.}$
12. A topological space ${\displaystyle X}$ is compact if and only if every ultranet on ${\displaystyle X}$ converges to some limit.
    • If the words "and only if" are removed then the resulting statement remains equivalent to the ultrafilter lemma.
13. A convergence space ${\displaystyle X}$ is compact if every ultrafilter on ${\displaystyle X}$ converges.
14. A uniform space is compact if it is complete and totally bounded.
15. The Stone–Čech compactification Theorem.
16. Each of the following versions of the compactness theorem is equivalent to the ultrafilter lemma:
    1. If ${\displaystyle \Sigma }$ is a set of first-order sentences such that every finite subset of ${\displaystyle \Sigma }$ has a model, then ${\displaystyle \Sigma }$ has a model.
    2. If ${\displaystyle \Sigma }$ is a set of zero-order sentences such that every finite subset of ${\displaystyle \Sigma }$ has a model, then ${\displaystyle \Sigma }$ has a model.
17. The completeness theorem: If ${\displaystyle \Sigma }$ is a set of zero-order sentences that is syntactically consistent, then it has a model (that is, it is semantically consistent).

Weaker statements

Any statement that can be deduced from the ultrafilter lemma (together with ZF) is said to be weaker than the ultrafilter lemma. A weaker statement is said to be strictly weaker if under ZF, it is not equivalent to the ultrafilter lemma. Under ZF, the ultrafilter lemma implies each of the following statements:

1. The Axiom of Choice for Finite sets (ACF): Given ${\displaystyle I\neq \varnothing }$ and a family ${\displaystyle \left(X_{i}\right)_{i\in I}}$ of non-empty finite sets, their product ${\displaystyle {\textstyle \prod \limits _{i\in I}}X_{i}}$ is not empty.
2. A countable union of finite sets is a countable set.
   • However, ZF with the ultrafilter lemma is too weak to prove that a countable union of countable sets is a countable set.
3. The Hahn–Banach theorem.
   • In ZF, the Hahn–Banach theorem is strictly weaker than the ultrafilter lemma.
4. The Banach–Tarski paradox.
   • In fact, under ZF, the Banach–Tarski paradox can be deduced from the Hahn–Banach theorem, which is strictly weaker than the Ultrafilter Lemma.
5. Every set can be linearly ordered.
6. Every field has a unique algebraic closure.
7. Non-trivial ultraproducts exist.
8. The weak ultrafilter theorem: A free ultrafilter exists on ${\displaystyle \mathbb {N} .}$
   • Under ZF, the weak ultrafilter theorem does not imply the ultrafilter lemma; that is, it is strictly weaker than the ultrafilter lemma.
9. There exists a free ultrafilter on every infinite set;
   • This statement is actually strictly weaker than the ultrafilter lemma.
   • ZF alone does not even imply that there exists a non-principal ultrafilter on some set.

Completeness

The completeness of an ultrafilter ${\displaystyle U}$ on a powerset is the smallest cardinal κ such that there are κ elements of ${\displaystyle U}$ whose intersection is not in ${\displaystyle U.}$ The definition of an ultrafilter implies that the completeness of any powerset ultrafilter is at least ${\displaystyle \aleph _{0}}$. An ultrafilter whose completeness is greater than ${\displaystyle \aleph _{0}}$—that is, the intersection of any countable collection of elements of ${\displaystyle U}$ is still in ${\displaystyle U}$—is called countably complete or σ-complete.

The completeness of a countably complete nonprincipal ultrafilter on a powerset is always a measurable cardinal.

Ordering on ultrafilters

The Rudin–Keisler ordering (named after Mary Ellen Rudin and Howard Jerome Keisler) is a preorder on the class of powerset ultrafilters defined as follows: if ${\displaystyle U}$ is an ultrafilter on ${\displaystyle \wp (X),}$ and ${\displaystyle V}$ an ultrafilter on ${\displaystyle \wp (Y),}$ then ${\displaystyle V\leq {}_{RK}U}$ if there exists a function ${\displaystyle f:X\to Y}$ such that

${\displaystyle C\in V}$ if and only if ${\displaystyle f^{-1}\in U}$

for every subset ${\displaystyle C\subseteq Y.}$

Ultrafilters ${\displaystyle U}$ and ${\displaystyle V}$ are called Rudin–Keisler equivalent, denoted U ≡_RK V, if there exist sets ${\displaystyle A\in U}$ and ${\displaystyle B\in V}$ and a bijection ${\displaystyle f:A\to B}$ that satisfies the condition above. (If ${\displaystyle X}$ and ${\displaystyle Y}$ have the same cardinality, the definition can be simplified by fixing ${\displaystyle A=X,}$ ${\displaystyle B=Y.}$)

It is known that ≡_RK is the kernel of ≤_RK, i.e., that U ≡_RK V if and only if ${\displaystyle U\leq {}_{RK}V}$ and ${\displaystyle V\leq {}_{RK}U.}$

Ultrafilters on ℘(ω)

There are several special properties that an ultrafilter on ${\displaystyle \wp (\omega ),}$ where ${\displaystyle \omega }$ extends the natural numbers, may possess, which prove useful in various areas of set theory and topology.

• A non-principal ultrafilter ${\displaystyle U}$ is called a P-point (or weakly selective) if for every partition ${\displaystyle \left\{C_{n}:n<\omega \right\}}$ of ${\displaystyle \omega }$ such that for all ${\displaystyle n<\omega ,}$ ${\displaystyle C_{n}\not \in U,}$ there exists some ${\displaystyle A\in U}$ such that ${\displaystyle A\cap C_{n}}$ is a finite set for each ${\displaystyle n.}$
• A non-principal ultrafilter ${\displaystyle U}$ is called Ramsey (or selective) if for every partition ${\displaystyle \left\{C_{n}:n<\omega \right\}}$ of ${\displaystyle \omega }$ such that for all ${\displaystyle n<\omega ,}$ ${\displaystyle C_{n}\not \in U,}$ there exists some ${\displaystyle A\in U}$ such that ${\displaystyle A\cap C_{n}}$ is a singleton set for each ${\displaystyle n.}$

It is a trivial observation that all Ramsey ultrafilters are P-points. Walter Rudin proved that the continuum hypothesis implies the existence of Ramsey ultrafilters. In fact, many hypotheses imply the existence of Ramsey ultrafilters, including Martin's axiom. Saharon Shelah later showed that it is consistent that there are no P-point ultrafilters. Therefore, the existence of these types of ultrafilters is independent of ZFC.

P-points are called as such because they are topological P-points in the usual topology of the space βω \ ω of non-principal ultrafilters. The name Ramsey comes from Ramsey's theorem. To see why, one can prove that an ultrafilter is Ramsey if and only if for every 2-coloring of ${\displaystyle ^{2}}$ there exists an element of the ultrafilter that has a homogeneous color.

An ultrafilter on ${\displaystyle \wp (\omega )}$ is Ramsey if and only if it is minimal in the Rudin–Keisler ordering of non-principal powerset ultrafilters.

See also

• Extender (set theory) – in set theory, a system of ultrafilters representing an elementary embedding witnessing large cardinal propertiesPages displaying wikidata descriptions as a fallback
• Filter (mathematics) – In mathematics, a special subset of a partially ordered set
• Filter (set theory) – Family of sets representing "large" sets
• Filters in topology – Use of filters to describe and characterize all basic topological notions and results.
• Łoś's theorem – Mathematical constructionPages displaying short descriptions of redirect targets
• Ultrafilter – Maximal proper filter
• Universal net – A generalization of a sequence of pointsPages displaying short descriptions of redirect targets

Notes

1. ^ Properties 1 and 3 imply that ${\displaystyle A}$ and ${\displaystyle X\setminus A}$ cannot both be elements of ${\displaystyle U.}$
2. Let ${\displaystyle {\mathcal {F}}}$ be a filter on ${\displaystyle X}$ that is not an ultrafilter. If ${\displaystyle S\subseteq X}$ is such that ${\displaystyle S\not \in {\mathcal {F}}}$ then ${\displaystyle \{X\setminus S\}\cup {\mathcal {F}}}$ has the finite intersection property (because if ${\displaystyle F\in {\mathcal {F}}}$ then ${\displaystyle F\cap (X\setminus S)=\varnothing }$ if and only if ${\displaystyle F\subseteq S}$) so that by the ultrafilter lemma, there exists some ultrafilter ${\displaystyle {\mathcal {U}}_{S}}$ on ${\displaystyle X}$ such that ${\displaystyle \{X\setminus S\}\cup {\mathcal {F}}\subseteq {\mathcal {U}}_{S}}$ (so in particular ${\displaystyle S\not \in {\mathcal {U}}_{S}}$). It follows that ${\displaystyle {\mathcal {F}}=\bigcap _{S\subseteq X,S\not \in {\mathcal {F}}}{\mathcal {U}}_{S}.}$ ${\displaystyle \blacksquare }$

Proofs

1. Suppose ${\displaystyle {\mathcal {B}}}$ is filter subbase that is ultra. Let ${\displaystyle C,D\in {\mathcal {B}}}$ and define ${\displaystyle S=C\cap D.}$ Because ${\displaystyle {\mathcal {B}}}$ is ultra, there exists some ${\displaystyle B\in {\mathcal {B}}}$ such that ${\displaystyle B\cap S}$ equals ${\displaystyle B}$ or ${\displaystyle \varnothing .}$ The finite intersection property implies that ${\displaystyle B\cap S\neq \varnothing }$ so necessarily ${\displaystyle B\cap S=B,}$ which is equivalent to ${\displaystyle B\subseteq C\cap D.}$ ${\displaystyle \blacksquare }$

References

1. Davey, B. A.; Priestley, H. A. (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.
2. ^ Narici & Beckenstein 2011, pp. 2–7.
3. ^ Dugundji 1966, pp. 219–221.
4. ^ Bourbaki 1989, pp. 57–68.
5. Schubert 1968, pp. 48–71.
6. ^ Schechter 1996, pp. 100–130.
7. Higgins, Cecelia (2018). "Ultrafilters in set theory" (PDF). math.uchicago.edu. Retrieved August 16, 2020.
8. Kruckman, Alex (November 7, 2012). "Notes on Ultrafilters" (PDF). math.berkeley.edu. Retrieved August 16, 2020.
9. ^ Dolecki & Mynard 2016, pp. 27–54.
10. ^ Dolecki & Mynard 2016, pp. 33–35.
11. Pospíšil, Bedřich (1937). "Remark on Bicompact Spaces". The Annals of Mathematics. 38 (4): 845–846. doi:10.2307/1968840. JSTOR 1968840.
12. ^ Bourbaki 1989, pp. 129–133.
13. ^ Jech 2006, pp. 73–89.
14. ^ Leinster, Tom (2013). "Codensity and the ultrafilter monad" (PDF). Theory and Applications of Categories. 28: 332–370. arXiv:1209.3606. Bibcode:2012arXiv1209.3606L.
15. Bourbaki 1987, pp. 57–68. sfn error: no target: CITEREFBourbaki1987 (help)
16. Schechter 1996, p. 105.
17. Schechter 1996, pp. 150–152.
18. Jech 2006, pp. 75–76.
19. Comfort 1977, p. 420.
20. Bell, J.; Fremlin, David (1972). "A geometric form of the axiom of choice" (PDF). Fundamenta Mathematicae. 77 (2): 167–170. doi:10.4064/fm-77-2-167-170. Retrieved 11 June 2018. Theorem 1.2. BPI & KM ${\displaystyle \implies }$ (*) .... Theorem 2.1. (*) ${\displaystyle \implies }$ AC .
21. Schechter 1996, pp. 105, 150–160, 166, 237, 317–315, 338–340, 344–346, 386–393, 401–402, 455–456, 463, 474, 506, 766–767.
22. ^ Schechter 1996, p. 463.
23. Schechter 1996, p. 339.
24. ^ Schechter 1996, pp. 766–767.
25. ^ Schechter 1996, p. 455.
26. Hodel, R.E. (2005). "Restricted versions of the Tukey-Teichmüller theorem that are equivalent to the Boolean prime ideal theorem". Archive for Mathematical Logic. 44 (4): 459–472. doi:10.1007/s00153-004-0264-9. S2CID 6507722.
27. ^ Muger, Michael (2020). Topology for the Working Mathematician.
28. ^ Schechter 1996, pp. 391–392.
29. Foreman, M.; Wehrung, F. (1991). "The Hahn–Banach theorem implies the existence of a non-Lebesgue measurable set" (PDF). Fundamenta Mathematicae. 138: 13–19. doi:10.4064/fm-138-1-13-19.
30. Pawlikowski, Janusz (1991). "The Hahn–Banach theorem implies the Banach–Tarski paradox" (PDF). Fundamenta Mathematicae. 138: 21–22. doi:10.4064/fm-138-1-21-22.
31. Comfort, W. W.; Negrepontis, S. (1974). The theory of ultrafilters. Berlin, New York: Springer-Verlag. MR 0396267. Corollary 9.3.
32. Rudin, Walter (1956), "Homogeneity problems in the theory of Čech compactifications", Duke Mathematical Journal, 23 (3): 409–419, doi:10.1215/S0012-7094-56-02337-7, hdl:10338.dmlcz/101493
33. Wimmers, Edward (March 1982), "The Shelah P-point independence theorem", Israel Journal of Mathematics, 43 (1): 28–48, doi:10.1007/BF02761683, S2CID 122393776
34. Jech 2006, p. 91(Left as exercise 7.12)

Bibliography

• Arkhangel'skii, Alexander Vladimirovich; Ponomarev, V.I. (1984). Fundamentals of General Topology: Problems and Exercises. Mathematics and Its Applications. Vol. 13. Dordrecht Boston: D. Reidel. ISBN 978-90-277-1355-1. OCLC 9944489.
• Bourbaki, Nicolas (1989) . General Topology: Chapters 1–4 [Topologie Générale]. Éléments de mathématique. Berlin New York: Springer Science & Business Media. ISBN 978-3-540-64241-1. OCLC 18588129.
• Dixmier, Jacques (1984). General Topology. Undergraduate Texts in Mathematics. Translated by Berberian, S. K. New York: Springer-Verlag. ISBN 978-0-387-90972-1. OCLC 10277303.
• Dolecki, Szymon; Mynard, Frédéric (2016). Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company. ISBN 978-981-4571-52-4. OCLC 945169917.
• Dugundji, James (1966). Topology. Boston: Allyn and Bacon. ISBN 978-0-697-06889-7. OCLC 395340485.
• Császár, Ákos (1978). General topology. Translated by Császár, Klára. Bristol England: Adam Hilger Ltd. ISBN 0-85274-275-4. OCLC 4146011.
• Jech, Thomas (2006). Set Theory: The Third Millennium Edition, Revised and Expanded. Berlin New York: Springer Science & Business Media. ISBN 978-3-540-44085-7. OCLC 50422939.
• Joshi, K. D. (1983). Introduction to General Topology. New York: John Wiley and Sons Ltd. ISBN 978-0-85226-444-7. OCLC 9218750.
• Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.
• Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365.
• Schubert, Horst (1968). Topology. London: Macdonald & Co. ISBN 978-0-356-02077-8. OCLC 463753.

Further reading

• Comfort, W. W. (1977). "Ultrafilters: some old and some new results" (PDF). Bulletin of the American Mathematical Society. 83 (4): 417–455. doi:10.1090/S0002-9904-1977-14316-4. ISSN 0002-9904. MR 0454893.
• Comfort, W. W.; Negrepontis, S. (1974), The theory of ultrafilters, Berlin, New York: Springer-Verlag, MR 0396267
• Ultrafilter at the nLab

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy projective Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo

v t e Mathematical logic
General	Axiom list Cardinality First-order logic Formal proof Formal semantics Foundations of mathematics Information theory Lemma Logical consequence Model Theorem Theory Type theory
Theorems (list)  and paradoxes	Gödel's completeness and incompleteness theorems Tarski's undefinability Banach–Tarski paradox Cantor's theorem, paradox and diagonal argument Compactness Halting problem Lindström's Löwenheim–Skolem Russell's paradox
Logics	Traditional Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram Propositional Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞ Predicate First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus
Set theory	Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities Types of sets Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann Maps and cardinality Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary Set theories Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive
Formal systems (list), language and syntax	Alphabet Arity Automata Axiom schema Expression ground Extension by definition conservative Relation Formation rule Grammar Formula atomic closed ground open Free/bound variable Language Metalanguage Logical connective ¬ ∨ ∧ → ↔ = Predicate functional variable propositional variable Proof Quantifier ∃ ! ∀ rank Sentence atomic spectrum Signature String Substitution Symbol function logical/constant non-logical variable Term Theory list Example axiomatic systems (list) of arithmetic: Peano second-order elementary function primitive recursive Robinson Skolem of the real numbers Tarski's axiomatization of Boolean algebras canonical minimal axioms of geometry: Euclidean: Elements Hilbert's Tarski's non-Euclidean Principia Mathematica
Proof theory	Formal proof Natural deduction Logical consequence Rule of inference Sequent calculus Theorem Systems axiomatic deductive Hilbert list Complete theory Independence (from ZFC) Proof of impossibility Ordinal analysis Reverse mathematics Self-verifying theories
Model theory	Interpretation function of models Model equivalence finite saturated spectrum submodel Non-standard model of arithmetic Diagram elementary Categorical theory Model complete theory Satisfiability Semantics of logic Strength Theories of truth semantic Tarski's Kripke's T-schema Transfer principle Truth predicate Truth value Type Ultraproduct Validity
Computability theory	Church encoding Church–Turing thesis Computably enumerable Computable function Computable set Decision problem decidable undecidable P NP P versus NP problem Kolmogorov complexity Lambda calculus Primitive recursive function Recursion Recursive set Turing machine Type theory
Related	Abstract logic Algebraic logic Automated theorem proving Category theory Concrete/Abstract category Category of sets History of logic History of mathematical logic timeline Logicism Mathematical object Philosophy of mathematics Supertask
Mathematics portal

• Families of sets
• Nonstandard analysis
• Order theory