This presentation uses javascript. Please enable it or switch to a browser that uses it.

A Generalization of Ultraproducts

Seminar on Applied Mathematical Logic

J. J. Wannenburg and T. Moraschini

  1. Institute of Computer Science, Academy of Sciences of the Czech Republic, Czech Republic

November 2021, Prague

This work was carried out within the project Supporting the internationalization of the Institute of Computer Science of the Czech Academy of Sciences (no. CZ.02.2.69/0.0/0.0/18_053/0017594), funded by the Operational Programme Research, Development and Education of the Ministry of Education, Youth and Sports of the Czech Republic. The project is co-funded by the EU.

A lattice is a partially ordered set in which any two elements \(x\) and \(y\) have

It is distributive if it satisfies \[x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z),\]

bounded if it has a maximum \(\top\) and minimum \(\bot\) element.

A Boolean algebra is a bounded distributive lattice in which every element \(x\) has a complement \(\neg x\), i.e., an element for which \[ x \wedge \neg x = \bot \text{ and } x \vee \neg x = \top. \]

Let \(\mathbf{A}\) be a lattice.

A non-empty subset \(F\) of \(A\) is a filter of \(\mathbf{A}\), when

It is proper if \(F \neq A\).

A proper filter \(F\) is said to be prime when

A filter is an ultrafilter if it is maximal among proper filters.

If \(\mathbf{A}\) is a distributive lattice, then each of its ultrafilters is a prime filter.

The converse is true, when \(\mathbf{A}\) is a Boolean algebra.














Recall that for any set \(I\), its powerset \(\mathcal{P}(I)\), when ordered by \(\subseteq\), is a Boolean algebra where the complement of \(X \subseteq I\) is \(I \setminus X\).

When \(F\) is a filter of \(\mathcal{P}(X)\), we say \(F\) is a filter over \(X\).

Let \(\{\mathbf{A}_i : i \in I \}\) be a family of algebras, and let \(U\) be an ultrafilter over I.

For any first order formula \(\varphi(x_1, \dots, x_n)\) and \(\mathbf{a}_1, \dots, \mathbf{a}_n \in \prod_{i \in I} \mathbf{A}_i\), \[ [\![ \varphi(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] = \{ i \in I: \mathbf{A}_i \models \varphi(\mathbf{a}_1(i), \dots, \mathbf{a}_n(i)) \}. \]

Define a congruence relation on \(\prod_{i \in I} \mathbf{A}_i\) as follows \[ \mathbf{a} \equiv_{U} \mathbf{b} \text{ iff } [\![ \mathbf{a} = \mathbf{b} ]\!] \in U. \]

Then \(\prod_{i \in I} \mathbf{A}_i / \equiv_{U}\) is an ultraproduct of \(\{\mathbf{A}_i : i \in I \}\).

If every \(\mathbf{A}_i = \mathbf{A}\) for some algebra \(\mathbf{A}\), then \(\prod_{i \in I} \mathbf{A} / \equiv_{U}\) is called an ultrapower of \(\mathbf{A}\), and \(\mathbf{A}\) is an ultraroot of \(\prod_{i \in I} \mathbf{A} / \equiv_{U}\).









Łoś’ Theorem

Let \(\{\mathbf{A}_i : i \in I \}\) be a family of algebras, and let \(U\) be an ultrafilter over I. Then for any first order formula \(\varphi(x_1, \dots, x_n)\) and \(\mathbf{a}_1, \dots, \mathbf{a}_n \in \prod_{i \in I} \mathbf{A}_i\) \[ \prod_{i \in I} \mathbf{A}_i / \equiv_{U} \models \varphi(\mathbf{a}_1/ \equiv_{U}, \dots, \mathbf{a}_n/ \equiv_{U}) \text{ iff } [\![ \varphi(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] \in U. \]









Thm

Let \(\mathsf{K}\) be a class of algebras. Then \(\mathsf{K}\) is axiomatized by first order sentences (i.e., elementary) iff \(\mathsf{K}\) is closed under ultraroots and ultraproducts.









Keisler–Shelah Theorem

Two algebras satisfy the same first order sentences iff they have isomorphic ultrapowers.

Let \(\mathbb{I} = \langle I; \leqslant \rangle\) be a poset and let \[ \textup{Up}(\mathbb{I}) = \{ \text{upwardly closed subsets of } I \}.\] Then \(\textup{Up}(\mathbb{I})\) is a distributive lattice, ordered by inclusion.

Note that if \(\mathbb{I}\) is an anti-chain, then \(\textup{Up}(\mathbb{I}) = \mathcal{P}(I)\), in which case, any prime filter of \(\textup{Up}(\mathbb{I})\), would be an ultrafilter over \(I\).

Let \(\mathbb{I} = \langle I; \leqslant \rangle\) be a well-ordered forrest, i.e., the downward closure of every element of \(I\) is well-ordered.

Let \(\{ \mathbf{A}_i : i \in I \}\) be a family of algebras, such that whenever \(i \leqslant j\) there is a homomorphism \(h_{ij} : \mathbf{A}_i \rightarrow \mathbf{A}_j\), and

Let \(F\) be a filter of \(\textup{Up}(\mathbb{I})\). Define the set \(\prod_{F} A_i\) to be \[ \{ \mathbf{a} \in \prod_{i \in I} \mathbf{A}_i : \exists X \in F \text{ s.\ t.\ } h_{ij}(a(i)) = a(j) \text{ whenever } i \leqslant j \text{ in } X \}. \] Then \(\prod_{F} A_i\) is a subuniverse of \(\prod_{i \in I} \mathbf{A}_i\).

The relation \(\equiv_{F}\) restricted to \(\prod_{F} A_i\) (\(\mathbf{a} \equiv_{F} \mathbf{b} \text{ iff } [\![ \mathbf{a} = \mathbf{b} ]\!] \in F\)) is still a congruence of \(\prod_{F} \mathbf{A}_i\).

We call \(\prod_{F} \mathbf{A}_i / \equiv_{F}\) a filter product of \(\{ \mathbf{A}_i : i \in I \}\) and a prime (filter) product, when \(F\) is a prime filter of \(\textup{Up}(\mathbb{I})\).

Examples

Note that when \(\mathbb{I}\) is an antichain, all the homomorphisms are identity maps, and \(\prod_{F} A_i = \prod_{i \in I} A_i\) (because \(I \in F\) and \(i \leqslant j\) only when \(i = j\)). So, prime products do generalize ultraproducts.

Consider the two element chain \(\mathit{2} = \{ 0 < 1 \}\). Let \(\mathbf{A}_0\) and \(\mathbf{A}_1\) be the one- and two-element lattices, respectively. Let \(h_{01} : x \mapsto \top\).

\(\text{Up}(\mathit{2})\) has two prime filters, \(F_0 = \{ \{0,1\} \}\) and \(F_1 = \{\{0,1\},\{1\}\}\).

Then \(\prod_{F_0} A_i = \{(x,\top)\}\) and \(\prod_{F_1} A_i = \{ (x,\top),(x,\bot) \}\). So, \(\prod_{F_0} \mathbf{A}_i / \equiv_{F_0} \cong \mathbf{A}_0\) and \(\prod_{F_1} \mathbf{A}_i / \equiv_{F_1} \cong \mathbf{A}_1\).














Thm 1

An existential positive formula (EPF) has the form \(\exists y_1, \dots, y_m \, \varphi(y_1, \dots, y_m, x_1, \dots, x_n)\) where \(\varphi\) is a disjunction of conjunctions of equations.

Let \(\prod_{F} \mathbf{A}_i / \equiv_{F}\) be prime product. For every EPF \(\varphi(x_1, \dots, x_n)\) and \(\mathbf{a}_1, \dots, \mathbf{a}_n \in \prod_{F} A_i\), \[ \prod_{F} \mathbf{A}_i / \equiv_{F} \models \varphi(\mathbf{a}_1/ \equiv_{F}, \dots, \mathbf{a}_n/ \equiv_{F}) \text{ iff } [\![ \varphi(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] \in F. \]












Proof (highlights)

By induction on the complexity of \(\varphi\).

Suppose \([\![ \psi(\mathbf{a}_1, \dots, \mathbf{a}_n) \sqcup \psi'(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] \in F.\) Note \([\![ \psi(\mathbf{a}_1, \dots, \mathbf{a}_n) \sqcup \psi'(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] = [\![ \psi(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] \cup [\![\psi'(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!].\) So, since \(F\) is prime, \([\![ \psi(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] \in F\) or \([\![ \psi'(\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] \in F.\) Then by the induction hypothesis \(\prod_{F} \mathbf{A}_i / \equiv_{F} \models \psi(\mathbf{a}_1/ \equiv_{F}, \dots, \mathbf{a}_n/ \equiv_{F}) \sqcup \psi'(\mathbf{a}_1/ \equiv_{F}, \dots, \mathbf{a}_n/ \equiv_{F}).\)



Suppose \(X := [\![ \exists y \psi(y,\mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] \in F\). For every \(i \in X\), \(\downarrow i\) is a well-order by assumption on \(\mathbb{I}\). Let \(\bot i = \text{min}(\downarrow i \cap X)\). Let \(Y = \{ \bot i : i \in X \}\). For every \(i \in Y\), choose \(a_i \in A_i\) such that \(\mathbf{A}_i \models \psi(a, \mathbf{a}_1(i), \dots, \mathbf{a}_n(i))\). Define \(\mathbf{a} \in \prod_{F} \mathbf{A}_i\), as follows \[ \mathbf{a}(i) = \begin{cases} h_{(\bot i)i}(a_{\bot i}) &\text{if } i \in X \\ \text{arbitrarily}& \text{otherwise.} \end{cases} \] For every \(i \in X\),

So \(X \subseteq [\![ \psi(\mathbf{a}, \mathbf{a}_1, \dots, \mathbf{a}_n) ]\!]\), whence \([\![ \psi(\mathbf{a}, \mathbf{a}_1, \dots, \mathbf{a}_n) ]\!] \in F\). By the induction hypothesis \(\prod_{F} \mathbf{A}_i / \equiv_{F} \models \exists \psi(y,\mathbf{a}_1/ \equiv_{F}, \dots, \mathbf{a}_n/ \equiv_{F})\).

Thm

A coherent sentence has the form \(\forall x_1, \dots, x_n (\varphi(x_1, \dots, x_n) \implies \varphi'(x_1, \dots, x_n))\) where \(\varphi\) and \(\varphi'\) are EPFs.

Let \(\prod_{F} \mathbf{A}_i / \equiv_{F}\) be prime product. For every coherent sentence \(\varphi\), \[ \text{if } [\![ \varphi ]\!] \in F \text{ then } \prod_{F} \mathbf{A}_i / \equiv_{F} \models \varphi. \]







Thm

A class \(\mathsf{K}\) of algebras is axiomatized by coherent sentences iff \(\mathsf{K}\) is closed under ultraroots and prime products.

Proof

Adapt the Łoś-Suszko Theorem.




A prime product \(\prod_{F} \mathbf{A}_i / \equiv_{F}\) is called a prime power of \(\mathbf{A}\) when every \(\mathbf{A}_i = \mathbf{A}\).

Thm (M. Raftery W., 2020, MLQ, Thm. 7.6)

Let \(\mathsf{K}\) be a quasivariety of finite type, with a finite nontrivial member. Then the following conditions are equivalent.

  1. \(\mathsf{K}\) is Passively Structurally Complete (PSC), i.e., every quasi-equation whose premises are not unifiable over \(\mathsf{K}\) is valid in \(\mathsf{K}\).
  2. The nontrivial members of \(\mathsf{K}\) satisfy the same existential positive sentences.
  3. The nontrivial members of \(\mathsf{K}\) have a common retract.



Thm

Let \(\mathsf{K}\) be a quasivariety of finite type, with a finite nontrivial member. Then \(\mathsf{K}\) is PSC iff any two nontrivial members of \(\mathsf{K}\) have isomorphic prime powers.

Proof

(Forward) follows from Thm 1 and (2) above.

(Backward) Let \(\mathbf{A}\) and \(\mathbf{B}\) be nontrivial members of \(\mathsf{K}\). Then \(\mathbf{A}\) and \(\mathbf{B}\) have a common retract \(\mathsf{C}\) (by (3) above), so there exists homomorphisms \(h: \mathbf{A} \rightarrow \mathbf{A}\) and \(g: \mathbf{B} \rightarrow \mathbf{B}\) such that \(h[\mathbf{A}] \cong \mathbf{C} \cong g[\mathbf{B}]\) and \(h \circ h = h\) and \(g \circ g = g\).

Consider the poset \(\omega\) of non-negative integers, and let \(\mathbf{A}_i = \mathbf{A}\) and \(\mathbf{B}_i = \mathbf{B}\) for every \(i \in \omega\). For every \(i \leq j\) let \(h_{ij} = h\) and \(g_{ij} = g\). And lastly let \(F\) be the all the nonempty upward closed subsets of \(\omega\). Then \(\prod_{F} \mathbf{A}_i / \equiv_{F} \cong \mathbf{C} \cong \prod_{F} \mathbf{B}_i / \equiv_{F}\).

thank you