#ultraproducts

[catgirl-lucy]

Boolean Valued Models

I found a cool way to do ultraproducts and now I'm gonna bother you about it :3

I might also explain what a Boolean valued model is or smth, idk

Boolean Algebras

In logic, you have the usual true and false truth-values. Boolean algebras are a generalization of the usual {0,1}-valued truths.

A Boolean algebra (abbreviated: BA) is an algebra (structure with a domain and operators that must satisfy a set of equations) (A,∧,∨,¬,0,1) with a domain A, binary operators ∧ and ∨ called meet and join respectively, a unary operator ¬ called complement and constants 0,1 ∈ A called top and bottom respectively, that satisfies the following set of equations:

(Associativity) (a ∧ b) ∧ c = a ∧ (b ∧ c) and (a ∨ b) ∨ c = a ∨ (b ∨ c);

(Commutativity) a ∧ b = b ∧ a and a ∨ b = b ∨ a;

(Distributivity) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) and a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c);

(Absorption) a ∨ (a ∧ b) = a ∧ b and a ∧ (a ∨ b) = a ∨ b;

(Identity) a ∧ 1 = a and a ∨ 0 = a;

(Complements) a ∧ ¬a = 0 and a ∨ ¬a = 1.

Elements of a Boolean algebra are called Booleans.

I found this cool video by sheafification of g that shows a connection between free algebras and monads. It's not that relevant to this blog-post, but it's still a fun video.

Here are some examples of Boolean algebras:

The degenerate BA 1 = {*} where 0 = 1 = *;

The two-valued (aka binary) BA 2 = {0,1} with 0 ≠ 1 (where ¬1 = 0, 0 ∨ 1 = 1, etc);

The set of finite and cofinite (=with a finite complement) sets of natural numbers, where meet and join are intersection and union, complement is set complement, bottom is the empty set and top is the set of natural numbers ω;

P(ω)/fin (my favourite), where Booleans are equivalence [x] classes of subsets x of ω under the equivalence relation "x ~ y iff |x △ y| is finite", [x] ∧ [y] = [x ∩ y], [x] ∨ [y] = [x ∪ y], ¬[x] = [ω \ x], 0 = [∅] and 1 = [ω].

We'll assume all Boolean algebras we use are non-degenerate (i.e. not 1). I'll identify finite Boolean algebras with their number of elements, e.g. 2 = {0,1} is the two-valued Boolean algebra and 4 = {0,1,a,¬a} is the four-valued Boolean algebra. Every finite BA has 2^n elements for some n, so there is no BA 3 with three elements.

Every BA (A,∧,∨,¬,0,1) has an associated partial order. One can see that, for all Booleans a,b ∈ A, a ∧ b = a and a ∨ b = b are equivalent. For Booleans a and b, we write a ≤ b for a ∧ b = a (equivalently, a ∨ b = b). ≤ defines a partial order on A, which is a complemented lattice with a least and greatest element. In turn, every complemented lattice (P,≤) with a least and greatest element induces a Boolean algebra where a ∧ b is the least upper-bound of a and b, a ∨ b is the greatest lower-bound, 0 is the least element, 1 is the greatest element and complements are complements. Thus, we can define boolean algebras in terms of their order.

Recall that, for a subset A ⊂ P of a partial order (P,≤), an upper-bound of A is some element x ∈ P so that ∀a ∈ A a ≤ x and, conversely, a lower-bound is some element y ∈ P so that ∀a ∈ A y ≤ a. A least element (greatest element) of A is a lower-bound (resp. upper-bound) of A that is in A. The supremum (infimum) of A, if it exists, is the least upper-bound (resp. greatest lower bound) of A. We write ⋀A to denote the infimum of A and ⋁A for the supremum of A.

The Boolean algebras that we're interested in are complete Boolean algebras (abbreviated: CBA's). A CBA is a Boolean algebra A for which, for all X ⊂ A, ⋀X and ⋁X exists. ‘For all X ⊂ A, ⋀X’ implies ‘for all X ⊂ A, ⋁X exists’, and vice versa, so we only need to check for one or the other to verify that A is a CBA. We can see that a ∧ ⋁X = ⋁{a ∧ b | b ∈ X} and a ∨ ⋀X = ⋀{a ∨ b | b ∈ X} for Booleans a and sets of Booleans X. Examples of complete boolean algebras are: any finite boolean algebra, P(ω)/fin, the set of regular open (=equal to the interior of its closure) subsets of the real number line ordered under inclusion, the set P(κ) of subsets of some set κ ordered under inclusion. A non-example is: the set of finite and cofinite subsets of ℕ, as e.g. the set of singletons of the form {2n} for natural n does not have supremum.

Given a Boolean algebra A, a subalgebra of A is a set B ⊂ A that is itself a Boolean algebra, i.e. 0,1 ∈ B and for any a,b ∈ B, we have (a ∧ b) ∈ B, (a ∨ b) ∈ B and (¬a) ∈ B. Given some set X ⊂ A, ⟨X⟩ denotes the subalgebra generated by X, i.e. the ⊂-smallest subalgebra that includes X.

Homomorphisms

In the category of Boolean algebras, a homomorphism (morphism / arrow) from a Boolean algebra A, called the domain, to a Boolean algebra B, called the codomain, is a function f: A → B for which:

f(0) = 0;

f(1) = 1;

f(a ∧ b) = f(a) ∧ f(b);

f(a ∨ b) = f(a) ∨ f(b);

f(¬a) = ¬f(a).

It can be seen that f(¬a) = ¬f(a) follows from the other conditions of a homomorphism, so we only need to check if 0, 1, meet and join are preserved by the morphism.

Composition in this category is just function composition, and the identity arrow of an object is the identity function.

A monomorphism (mono / embedding / an arrow that is into) is a homomorphism that is injective. I'll write f: A ↣ B for ‘f is a monomorphism from A into B’. The image of an embedding is always isomorphic to the domain. A is said to embed into B if there exists an embedding from A into B.

An epimorphism (epi / an arrow that is onto) is a homomorphism that is surjective. I'll write f: A ↠ B for ‘f is an epimorphism from A onto B’.

An isomorphism (iso) is a homomorphism that is bijective. I'll write f: A ≅ B for ‘f is an isomorphism from A to B’. A and B are said to be isomorphic if there exists an isomorphism between A and B. Generally, not every bijective morphism is an isomorphism. For example, the Hilbert curve is a continuous bijection between [0,1] and [0,1]², yet it is not an isomorphism. However, in the category of Boolean algebras, being bijective is enough for being an isomorphism.

A filter F on κ is a set of subsets of κ that contains κ, does not contain the empty set, is closed under finite intersections and for every A ∈ F and every B ⊃ F, we have B ∈ F as well. An ultrafilter is a filter U for which, for every A ⊂ κ, we have either A ∈ U or κ \ A ∈ U. An ultrafilter partitions the subsets of κ up into sets that are large and sets that are small.

The arrows from the Boolean algebra P(κ) to the Boolean algebra 2 correspond with the ultrafilters on κ: for every arrow f: P(κ) → 2, {A ⊂ κ | f(A) = 1} is an ultrafilter, and for every ultrafilter U, the function g: P(κ) → 2 defined by g(A) = 1 if A ∈ U, and g(A) = 0 otherwise, is a homomorphism.

Some homomorphisms preserve suprema and infima of sets, and some don't. What I mean with 'preserving suprema' is that f(⋁X) = ⋁{f(x) | x ∈ X}. E.g. f: P(ω) → 2 defined by f(x) = 1 if 6 ∈ x, f(x) = 0 otherwise, preserves suprema and infima of sets, while any morphism from P(ω)/fin to 2 cannot.

Models

Before I'll explain how Boolean valued models work, I'll explain how the usual models work. This won't be a full explanation, more so a reminder of how models work.

In model theory, a signature σ is a collection of constant symbols, function symbols and relation symbols with arities assigned to each function symbol and relation symbol. For example, you can have a signature (ε) with a single binary relation symbol ε, and no constant symbols or function symbols. Or you can have a signature (∧,∨,¬,0,1) with constant symbols 0 and 1, binary function symbols ∧ and ∨ and a unary function symbol ¬.

Given a signature σ, a model M of σ is a structure with a set |M| called its domain, for each constant symbol in σ some constant in |M|, for each n-ary relation symbol in σ some n-ary relation on |M| and for each n-ary function symbol in σ some n-ary function from |M| to |M|. For example, you can have a model (V_ω,∈) of (ε) with the set V_ω of all hereditarily finite sets as domain and the binary membership relation ∈ as interpretation for the symbol ε. And you can have a model (P(κ),∩,∪,c,∅,κ) of (∧,∨,¬,0,1) with the set P(κ) of subsets of κ as domain, intersection as the interpretation for ∧, union as the interpretation for ∨, set complement as the interpretation for ¬, the empty set as the interpretation for 0 and κ as the interpretation for 1.

Given some signature σ, we can build a language L_σ. Terms in L_σ are variables symbols, constant symbols from σ and f(t₁ .. tₙ) for terms t₁ .. tₙ and an n-ary function symbol f in σ. Atomic formulae are those of the form s = t for terms s and t, or R(t₁ .. tₙ) for terms t₁ .. tₙ and an n-ary relation symbol R in σ. Formulae can be build from atomic formulas using conjunction (φ ∧ ψ for formulas φ and ψ), disjunction (φ ∨ ψ for formulas φ and ψ), negation (¬φ for a formula φ) and using the universal and existential quantifier (∀x φ(x) and ∃x φ(x) for formulas φ(x) and a variable symbol x). This language is the language of first order logic of σ. There are other logics, e.g. those that allow for quantifiers for the existence of uncountably many objects, or those that allow variables ranging over second order objects, and less expressive logics, such as those that restrict the use of quantifiers or have no quantifiers at all. But we'll focus only on first order logic in this blog post.

Given a model M of σ with domain D, we can interpret the formulas in L_σ. Let L_σ(D) be the language L_σ augmented by a constant term symbol for every element of D. Note that every formula in L_σ is still a formula in L_σ(D), though some formulas in L_σ(D) aren't formulas in L_σ. For a formula φ in the language L_σ(D) with no free variables (though constant term symbols representing members of M are still allowed), we can define the relation M ⊧ φ (M satisfies φ) by induction on the complexity of φ:

M ⊧ s = t iff the interpretation of the term s in M is equal to the interpretation of the term t in M;

M ⊧ R(t₁ .. tₙ) iff the interpretation of the relation symbol R in M is true for the interpretations of the terms t₁ .. tₙ in M;

M ⊧ φ ∧ ψ iff M ⊧ φ and M ⊧ ψ;

M ⊧ φ ∨ ψ iff M ⊧ φ or M ⊧ ψ;

M ⊧ ∃x φ(x) iff for all constant term symbols c in L_σ(D) representing a member of M, M ⊧ φ(c), where φ(c) is φ with every free occurrence of x replaced with c;

M ⊧ ∀x φ(x) iff for all constant term symbols c in L_σ(D) representing a member of M, M ⊧ φ(c).

Some models have an explicit equality relation, which forms an equivalence relation on its domain that respects the other relations (i.e. if x = y holds in M, then R(..,x,..) is equivalent to R(..,y,..)). Then, M ⊧ s = t iff the interpretations of the terms s and t in M are equal by M's equality relation. The equality relation isn't needed for models as you can just quotient the domain by the given equality relation, giving a domain on which you don't need the equality relation anymore.

Boolean Valued Models

Boolean valued models have the same signature as the usual models. Next to a signature, they also need some complete boolean algebra A. A will serve as the set of truth-values that formulas in your BVM can have.

Let σ be a signature and let A be a CBA. An A-valued model of σ is a structure M that consists of:

A domain |M| = S with elements called names;

A function [· = ·] from S × S to A called equality;

For each constant term symbol in σ, an associated constant in S;

For each n-ary relation symbol in σ, an associated function from S^n to A;

For each n-ary function symbol in σ, an associated function from S^n to S.

And a BVM must satisfy the following conditions:

(Reflexivity) [a = a] = 1;

(Symmetry) [a = b] = [b = a];

(Transitivity) [a = b] ∧ [b = c] ≤ [a = c];

(Relation Substitution) [a = b] ≤ (R(..,a,..) ∧ R(..,b,..)) ∨ (¬R(..,a,..) ∧ ¬R(..,b,..)) for every relation R in M;

(Function Substitution) [a = b] ≤ [f(..,a,..) = f(..,b,..)] for every function f in M.

The reason why we need an explicit equality relation is because not every equality is a binary 0 or 1. For example, [a = b] might be some Boolean x that is neither 0 nor 1, so we cannot use [· = ·] to define an equivalence relation on S which we can quotient by.

Some definitions of a Boolean valued model view functions as n+1-ary relations and define them that way, instead of defining them as actual functions from names to names.

We can see that the usual models correspond to the 2-valued models: those where everything is either definitely true (1), or definitely false (0).

Like with the usual models, we can define an interpretation ⟦·⟧: L_σ(S) → A for formulas φ in L_σ(S). The function ⟦·⟧ is defined as follows:

⟦s = t⟧ = [s' = t'] where s' and t' are the interpretations of the terms s and t in M;

⟦R(t₁ .. tₙ)⟧ = R(t₁' .. tₙ');

⟦φ ∧ ψ⟧ = ⟦φ⟧ ∧ ⟦ψ⟧;

⟦φ ∨ ψ⟧ = ⟦φ⟧ ∨ ⟦ψ⟧;

⟦¬φ⟧ = ¬⟦φ⟧;

⟦∀x φ(x)⟧ = ⋀[s ∈ S] ⟦φ(s)⟧;

⟦∃x φ(x)⟧ = ⋁[s ∈ S] ⟦φ(s)⟧.

The reason why the BA A should be complete is for the definitions of ⟦∀⟧ and ⟦∃⟧ to make sense. Using different logics, other conditions might be desirable instead of completeness.

If the model M is not clear from context, I'll write ⟦φ⟧_M (instead of ⟦φ⟧) for the interpretation of φ in the model M.

We write M ⊧ φ for ⟦φ⟧ = 1. The theory of M consists of the set of sentences φ for which M ⊧ φ. Though this theory might not be complete, it can be verified that it is consistent (assuming A isn't degenerate). Thus, if you want to prove a theory T is consistent, you can try proving that T is included in the theory of some Boolean valued model. The theory of a (Boolean valued) model M is written Th(M). Theories of 2-valued models are complete.

Given an A-valued model M and a morphism f: A → B, we can turn M into a B-valued model by composing f with the equality function of M and the relation functions of M.

A Boolean valued model M is said to be full if for every formula of the form ∃x φ(x), if M ⊧ ∃x φ(x) then there is a name s for which M ⊧ φ(s).

Boolean Algebra Products

In category theory, the product of two objects A and B is some objects A × B such that there are arrows π₁: A × B → A and π₂: A × B → B called projections for which, for any object C and any two arrows f₁: C → A and f₂: C → B, there is a unique arrow f: C → A × B such that π₁ ○ f = f₁ and π₂ ○ f = f₂.

In the category of Boolean algebras, the product of BAs A and B is the BA A × B where Booleans are pairs (a,b) of Booleans a ∈ A and b ∈ B. All operators are pointwise, e.g. 1 = (1,1) and (a,b) ∧ (c,d) = (a ∧ c, b ∧ d). The projection maps π₁ and π₂ map (a,b) ∈ A × B to a ∈ A and b ∈ B respectively. For any two arrows f₁: C → A and f₂: C → B, we can amalgamate them into an arrow f mapping c to (f₁(c),f₂(c)).

We can generalize the notion of a product between two objects to the product of a family of objects (A_i | i < κ). The product Π[i < κ] A_i of the family (A_i | i < κ) is some object such that, for each index j, there is a projection arrow π_j: (Π[i < κ] A_i) → A_j, and for any object C and any family of arrows (f_i | i < κ), f_i: C → A_i, there is a unique arrow f: C → Π[i < κ] A_i such that π_i ○ f = f_i for every index i.

In the category of BAs, this means that the product of a family of BAs (A_i | i < κ) is some BA Π[i < κ] A_i where Booleans are functions a that map indices i < κ to Booleans a(i) ∈ A_i. Operators are still pointwise, e.g. (a ∨ b)(i) = a(i) ∨ b(i). The projection map π_j maps a ∈ Π[i < κ] A_i to a(j) ∈ A_j. For any family of arrows (f_i | i < κ), f_i: C → A_i, we can amalgamate them into an arrow f mapping c to a where a(i) = f_i(c).

If we take the product of a Boolean algebra A with itself κ times, we just write A^κ instead of Π[i < κ] A. We can see that 2^κ is isomorphic to P(κ).

Given two arrows f: A → C and g: B → D, we can multiply them to get a new arrow f × g: A × B → C × D, which is the unique arrow for which f ○ π_A = π_C ○ f × g and g ○ π_B = π_D ○ f × g, where π_A: A × B → A, π_B: A × B → B, π_C: C × D → C and π_D: C × D → D are the projection maps. In the category of Boolean algebras, f × g is defined as (f × g)(a,b) = (f(a),g(b)). The product of a family of arrows can be defined in a similar way.

Unfortunately, the category of Boolean algebras has no coproducts :(

Model Products & Ultraproducts

If we have a family (A_i | i < κ) of complete Boolean algebras and a family (M_i | i < κ) of Boolean valued models of the same signature σ where, for each i, M_i is an A_i-valued model, we can take the product of these models to get an A = Π[i < κ] A_i-valued model M = Π[i < κ] M_i. This product has the property that, for every index i, if we apply the i-th projection map π_i: A → A_i to this product model M to get an A_i-valued model, we get a model that is isomorphic to the Boolean valued model M_i. The construction of this product model Π[i < κ] M_i is as follows: names in Π[i < κ] M_i are functions s that map indices i < κ to names s(i) ∈ M_i. For a relational symbol R in σ, the truth-value of the relation R(s₁ .. sₙ) in Π[i < κ] M_i is a function a ∈ Π[i < κ] A_i that maps indices i < κ to the truth-value of the relation R(s₁(i) .. sₙ(i)) in M_i. Functions are applied pointwise, so f^M(s₁)(i) = f^M_i(s₁(i)) where f^M and f^M_i are the interpretations of the function symbol f in Π[i < κ] M_i and in M_i respectively.

For example, if we have two 2-valued models M and N of the signature (∈) of the language of set theory, we can take the product M × N which is a 4-valued model where names are pairs (x,y) for x ∈ M and y ∈ N and the truth-value of the relation (w,x) ∈ (y,z) is 0 if neither w ∈ y holds in M nor x ∈ z holds in N, 1 if both w ∈ y holds in M and x ∈ z holds in N, a if only w ∈ y holds in M but x ∈ z does not hold in N, and ¬a if w ∈ y does not hold in M but x ∈ z does hold in N.

As another example, we can take the product Π[i ∈ ω] ({1..i},≤) of finite linear orders {1..i} for natural numbers i, and we get a P(ω)-valued model.

We can also take the product of a Boolean valued model M with itself κ times, denoted M^κ (called the 'power' of M by κ).

Now, here is the fun way I found to do ultraproducts: if we have a family of (2-valued) models (M_i | i < κ) and some ultrafilter U on the cardinal κ, we can take the homomorphism f: P(κ) → 2 induced by U, then we take the product to get a P(κ)-valued model Π[i < κ] M_i, and now we apply f to this model to get a 2-valued model (Π[i < κ] M_i)/U which is the ultraproduct of M_i's by the ultrafilter U.

One cool thing about ultraproducts is: (Π[i < κ] M_i)/U ⊧ φ(s₁ .. sₙ) iff {i < κ | M_i ⊧ φ(s₁(i) .. sₙ(i))} ∈ U. Proving this is left as an exercise to the reader.

Now you know a convoluted way to do ultraproducts.

Bye!!~

Sleep well. Dream of fish.

[eatsleepmath]

Hyperimaginaries don’t commute with ultraproducts

A (finitary) hyperimaginary is a quotient of a definable set by a \(0\)-type-definable equivalence relation, i.e. it’s an equivalence class of things coming from a definable set such that we can check if two things are equivalent by checking a possibly infinite list of conditions.

The prototypical example is “things which are infinitesimally close” in the hyperreals: you say that \(x\) and \(y\) are infinitesimally close in \(^*\mathbb{R}\) if and only if \(|x - y| < \frac{1}{n}\) for all \(n \in \mathbb{N}.\)

Anyways, let \(E\) name this equivalence relation. Then it’s easy to see that

\[\mathbb{R}^{\mathcal{U}}/E \not \simeq \left(\mathbb{R}/E \right)^{\mathcal{U}},\]

since \(\mathbb{R}/E \simeq \mathbb{R}\) (after all, the real numbers are Hausdorff) so that the right hand side is the nonstandard reals \(^* \mathbb{R}\) again (so every number has a cloud of infinitesimals around it) while the left hand side has no points which are infinitesimally close together, because we’ve literally quotiented the clouds together.

This is actually an excellent example of why we shouldn’t expect the process of taking points of hyperimaginaries in a model to commute with ultraproducts: on one hand, if \(E\) is a type-definable equivalence relation on \(X\), and \(\mathcal{U}\) an ultrafilter, then computing \[\left(\prod_{i \in I} M_i/\mathcal{U} \right)(X/E)\] yields \(E\)-equivalence classes of germs \([m_i]_{\mathcal{U}}\). That is, for every condition \(\varphi(x_1, x_2)\) in \(E\) that needs to be checked to conclude that two tuples are \(E\)-equivalent, every pair of \(E\)-equivalent germs \([m_i]_{\mathcal{U}}\) and \([n_i]_{\mathcal{U}}\) agree on \(\varphi\) on some subset \(P \subseteq I\) for \(P\) in \(\mathcal{U}\).

But these \(P\)s depend on \(\varphi\). They aren’t uniform, and there’s possibly no set \(P’\) in the ultrafilter (the intersection of all the \(P\)’s might be empty) on which you could decide if \([m_i]\) and \([n_i]\) are \(E\)-equivalent for every condition \(\varphi \in E\).

On the other hand, you could try computing \[\left( \prod_{i \in I} M_i(X/E) \right) /\mathcal{U}.\] You end up instead with germs of hyperimaginaries, as in \([[m_i]_E]_{\mathcal{U}}\), but this is a tighter equivalence relation: \(([x_i]_E)_i\) and \(([y_i]_E)_i)\) are \(\mathcal{U}\)-equivalent if and only if there is a single \(P \in \mathcal{U}\), uniform for every \(i \in P\) and for every \(\varphi \in E\) so that \(M_i \models \varphi(x_i, y_i)\).

This means that the commutation of these two procedures should fail precisely when the \(P\)’s on the left hand side intersect to something outside of the ultrafilter.

Indeed, in the example we first mentioned, consider the sequences \[(1, 2, 3, \dots)\] and \[(1 + 1/2, 2 + 1/3, 3 + 1/4, \dots).\] If we take them mod-\(\mathcal{U}\), then mod-\(E\), then they are equivalent as hyperimaginaries in \(^*\mathbb{R}\), since for each condition “x is less than \(1/n\) away from y”, these two sequences agree cofinitely many times (and every ultrafilter contains the cofinite filter).  But these cofinite sets of indices are getting smaller and smaller and intersect to \(\emptyset\). And if we take them mod-\(E\), then mod-\(\mathcal{U}\), they remain distinct.

[eatsleepmath]

Here’s another example of how an ultraproduct smooths out finite irregularities: of all the finite symmetric groups, only \(\operatorname{Sym}(6)\) has “exotic” (non-inner) automorphisms. If you take an ultraproduct of all the finite symmetric groups, you can examine the ultralimits of automorphisms of the finite symmetric groups, which we call “internal automorphisms” (like internal sets of the hyperreals), and it turns out that every internal automorphism of \[\prod_{\mathcal{U}}\operatorname{Sym}(n)\] is inner.

Furthermore, if CH holds, then by inspecting cardinalities we see there are many external automorphisms (i.e., not writable as an ultralimit of automorphisms) of this ultraproduct, but that even one of these external automorphisms exist is independent of ZFC.

Neat!

[eatsleepmath]

An ultraproduct of metric spaces is an ultraproduct of metric spaces

I never liked the first definition I saw of an ultraproduct of metric spaces:

Definition. Let \(\mathcal{U}\) be an ultrafilter on \(I\), and let \((X_i, d_i)\) be a sequence of uniformly bounded metric spaces.

Define \(d\) on \(\prod_{i \in I} X\) as follows: \(d\left((x_i)_{i \in I}, (y_i)_{i \in I}\right)\) is the ultralimit \(\lim_{i \to \mathcal{U}} d_i(x_i, y_i)\).

Note that \(d\) is a pseudometric on \(\prod_{i \in I} X_i\).

The ultraproduct of the uniformly bounded metric spaces \(X_i\) with respect to \(\mathcal{U}\) is the metric space \(\prod_{i \to \mathcal{U}} (X_i, d_i)\) obtained by quotienting out the distance-0 balls from \(\left(\prod_{i \to I} X_i, d \right)\).

Ultraproducts of sets are filtered colimits of infinite products.

Definition. Let \(\mathcal{U}\) be an ultrafilter on \(I\), and let \((A_i)_{i \in I}\) be an \(I\)-indexed sequence of sets.

The ultraproduct \(\prod_{i \to \mathcal{U}} A_i\) is defined to be the filtered colimit of the following diagram: the objects are products \(\prod_{i \in P} A_i\) as \(P\) ranges over the sets in the ultrafilter \(\mathcal{U}\), and the transition maps are the truncation maps

\[\prod_{i \in P} A_i \to \prod_{i \in P \cap P'} A_i.\]

In a category with products and filtered colimits, we call the result of this kind of construction a categorical ultraproduct.

In this post, we’re going to show that the above definition can be redeemed: while metric spaces do not form a nice category, pseudometric spaces do—in a way, this is because pseudometric spaces are geometrically axiomatizable (see e.g. the discussion in D1.1 of the Elephant), while metric spaces are not—and so modulo quotienting out the distance-0 balls, an ultraproduct of uniformly bounded metric spaces in the sense of the above definition is the same thing as their categorical ultraproduct in the category of pseudometric spaces.

Precisely put, our goal in this post will be to prove the following

Proposition. Let \((X_i)_{i \in I}\) be a uniformly bounded family of metric spaces. Then the metric space ultraproduct \(\prod_{\mathcal{U}} X_i\) in the sense of the first definition coincides with the quotient of \[\left(\operatorname{\underset{\longrightarrow}{\lim}}_{P \in \mathcal{U}} \left(\prod_{i \in P} (X_i, d_i)\right)\right)\] by distance-\(0\) balls, where the filtered colimit above is computed in the category \(\mathbf{PseudoMet}\) of pseudometric spaces with morphisms the weakly contractive maps.

A product of uniformly bounded metric spaces \(\prod_{i \in I} (X_i, d_i)\) is given a pseudometric \(d\) by \(d\left((x_i)_{i \in I}, (y_i)_{i \in I}\right) \overset{\operatorname{df}}{=} \sup_{i \in I} d_i(x_i, y_i)\).

Let’s figure out how to compute filtered colimits.

Lemma. Let \(\left(X_i, f_{ij} : X_i \to X_j \right)\) be a filtered diagram of pseudometric spaces. Then \(\operatorname{\underset{\longrightarrow}{\lim}} \left(X_i, f_{ij} : X_i \to X_j \right)\) exists, and is given by \[\left( \operatorname{\underset{\longrightarrow}{\lim}} X_i, \overline{d} \right),\] where \(\operatorname{\underset{\longrightarrow}{\lim}} X_i\) is the colimit taken in the \(\mathbf{Set}\), and where \[\overline{d}([x], [y]) \overset{\operatorname{df}}{=} \inf_i d_i(x_i, y_i),\] where \([x]\) and \([y]\) are germs and the infimum is computed only considering those \(X_i\) which have representatives \(x_i\), \(y_i\) for both \([x]\) and \([y]\).

Proof. First, we verify that \(\overline{d}\) defined above is a pseudometric. Symmetry and positivity are clear, so we check the triangle identity. We need to verify \[\inf_i d_i(x_i, y_i) \overset{?}{\leq} \inf_j d_j(x_j, z_j) + \inf_k d_k (z_k, y_k).\]

Now, if this was not true, then \[\inf_i d_i(x_i, y_i) > \inf_j d_j(x_j, z_j) + \inf_k d_k (z_k, y_k),\] so in particular there exist \(j\) and \(k\) such that \[d_j(x_j, z_j) + d_k(z_k, y_k) < \inf_i d_i(x_i, y_i).\] Since we are in a filtered diagram, \(X_j\) and \(X_k\) have an amalamgation \(X_j, X_k \rightrightarrows X_{\ell}\). Since the maps are contractive, \[d_{\ell}(x_{\ell}, y_{\ell}) \leq d_{\ell}(x_{\ell}, z_{\ell}) + d_{\ell}(z_{\ell}, y_{\ell}) \leq d_j(x_j, z_j) + d_k(z_{k}, y_{k}) < \inf_i d_i(x_i, y_i),\] a contradiction.

Now, we convince ourselves that \(\left( \operatorname{\underset{\longrightarrow}{\lim}} X_i, \overline{d} \right)\) is truly a colimit for \(\left(X_i, f_{ij} : X_i \to X_j \right)\). If \((Y, d_Y)\) is a cocone to this diagram, then there is a unique map of sets \(c : \operatorname{\underset{\longrightarrow}{\lim}} X_i \to Y\), and \(c\) is contractive because there is a contractive map \(c_i : X_i \to Y\) for each \(i\) which factors as a function through \(c\), so for any pair \((x_i, y_i)\),

\[\forall j \in J, d_Y(c_i(x_i, y_i)) \leq d_j(x_j, y_j) \hspace{1mm}\implies\hspace{1mm} d_Y(c([x_i], [y_i])) \leq \inf_i d_i (x_i, y_i),\]

proving the lemma. \(\square\)

Proof of the Proposition. First, let us compare the pseudometric spaces \[\prod_{i \in I} (X_i, d_i) \text{  vs  } \prod_{i \to \mathcal{U}} (X_i, d_i).\] There is a natural quotient map \(\prod X_i \to \prod_{i \to \mathcal{U}} X_i\). Is this contractive? Unraveling definitions, we see that we need to check the inequality \[\overline{d}([x_i], [y_i]) = \inf_P \left(\sup_{i \in P} d_i(x_i, y_i) \right) \overset{?}{\leq} \lim_{i \to \mathcal{U}} d_i(x_i, y_i) \overset{\operatorname{df}}{=} a \in \mathbb{R}.\] By definition of ultralimit, we have that for each \(\epsilon\), the \(\epsilon\)-ball \(B_{\epsilon}(a)\) around \(a\) contains \(\mathcal{U}\)-many \(d_i(x_i, y_i)\). Sending \(\epsilon \to 0\), we conclude that the inequality is true.

Actually, we can conclude more. If \(P\) indexes a set \(S \overset{\operatorname{df}}{=} \{d_i(x_i, y_i)\}_{i \in P}\) which witnesses this inequality, we can intersect \(P\) with smaller and smaller \(P'\). These intersections will be nonempty, which means that \(\sup S = a\). So the weak inequality can actually be improved to equality.

Therefore, the quotient map \(\prod X_i \to \prod_{i \to \mathcal{U}} X_i\) is isometric, and so any failure of injectivity must be because points distance \(0\) apart are being glued together. So there is a factorization

where either map to \(\left(\prod_{\mathcal{U}} X_i, d \right)\) is gotten by quotienting distance \(0\) points together. Thus our two descriptions of the metric space ultraproduct are the same. \(\square\)