7
$\begingroup$

I want to know if there are fairly simple combinatorial necessary conditions for when a direct limit of ultrapowers of $V$ is well-founded similar to $\sigma$-completeness. By combinatorial, I mean that these conditions are conditions on the ultrafilters instead of the elementary embeddings they produce.

For simplicity, we shall formulate the question with regards to the following ultrapower construction. Assume that $X$ is a set and $(P_{n})_{n}$ is a sequence of partitions of $X$ such that $P_{n+1}$ refines $P_{n}$ for all $n$ and whenever $x,y\in X,x\neq y$ there is some $n$ where $x,y$ belong to different blocks of the partition $P_{n}$. Furthermore, assume that whenever $R_{n}\in P_{n}$ and $R_{n+1}\subseteq R_{n}$ for all $n$ then $\bigcap_{n}R_{n}$ is non-empty. Let $B=\bigcup_{n\in\omega}\{\bigcup\mathcal{R}|\mathcal{R}\subseteq P_{n}\}$. Then $B$ is a Boolean algebra. Let $U$ be an ultrafilter on $B$. We shall use the ultrafilter $U$ to construct an ultrapower.

Suppose $\mathcal{A}$ is a structure. Then let $\mathcal{A}^{(P_{n})_{n}}$ be the collection of all functions $f:X\rightarrow\mathcal{A}$ where there is some natural number $n$ where $P_{n}\preceq\{f^{-1}[\{a\}]|a\in\mathcal{A}\}$ (the ordering $\preceq$ is refinement of partitions). Now let $\simeq_{U}$ be the equivalence relation on $\mathcal{A}^{(P_{n})_{n}}$ where $f\simeq_{U}g$ if and only if $\{x\in X|f(x)=g(x)\}\in U$. One can define the fundamental operations, constants, and relations on $\mathcal{A}^{(P_{n})_{n}}/\simeq_{U}$ as one does with the classical ultrapower construction. Let the structure $\mathcal{A}^{(P_{n})_{n}}/\simeq_{U}$ be denoted by $\mathcal{A}^{(P_{n})_{n}}/U$.

Is there a fairly simple combinatorial characterization of when the ultrapower $V^{(P_{n})_{n}}/U$ well-founded? For instance, in order for $V^{(P_{n})_{n}}/U$ to be well-founded, the ultrafilters $\{\mathcal{R}\subseteq P_{n}|\bigcup\mathcal{R}\in U\}$ must be $\sigma$-complete. On the other hand, if whenever $R_{n}\in\mathcal{U}$ for all $n$, we have $\bigcap_{n}R_{n}\neq\emptyset$, then the ultrapower $V^{(P_{n})_{n}}/U$ is well-founded. Even though I just listed necessary conditions and sufficient conditions for when an ultrapower is well-founded, I do not know of any conditions that are both necessary and sufficient. Can someone give a reference or a proof of combinatorial necessary and sufficient conditions for when such an ultrapower is well-founded? If $V^{(P_{n})_{n}}/U$ is well-founded, then do we necessarily have $\bigcap_{n}R_{n}\neq\emptyset$ whenever $R_{n}\in U$ for all $n$?

$\textrm{This last question was answered affirmatively by Joel David Hamkins}$

$\textbf{Remark}$

Although I phrased this question in terms of a direct limit of a countable sequence of ultrapowers, this characterization also holds for any kind of direct limit of ultrapowers since any possible infinite descending sequence in an ultrapower of a well-founded set must be in a countable direct limit of ultrapowers. Furthermore, the condition that $\bigcap_{n}R_{n}\neq\emptyset$ whenever $R_{n}\in P_{n},R_{n+1}\subseteq R_{n}$ for all $ n$ does not restrict the types of ultrapowers that one can form since one can always extend the set $X$ to a larger set $\hat{X}$ so that $\bigcap_{n}R_{n}\neq\emptyset$ whenever $R_{n}\in P_{n},R_{n+1}\subseteq R_{n}$. For instance, give $X$ the uniformity where the uniform covers are generated by the uniform partitions $P_{n}$. Then the appropriate set $\hat{X}$ is the completion of the uniform space $X$. Equivalently, one can let $\hat{X}=\varprojlim_{n}P_{n}.$ By replacing $X$ with $\hat{X}$ one obtains an isomorphic ultrapower but where $\bigcap_{n}R_{n}\neq\emptyset$ whenever $R_{n}\in P_{n},R_{n+1}\subseteq R_{n}$ for all $n$.

$\endgroup$
2
  • $\begingroup$ Could you clarify the quantifiers in your definition of ${\cal A}^{(P_n)_n}$? I think you want functions $f$ such that there is some $n$ for which you have $P_n$ refining the preimage of $f$ on the points of $\cal A$, right? That is what would correspond to taking the direct limit of the induced ultrafilters $U_n$ defined on the (power set of the ) partition $P_n$. Please correct me if I have misunderstood. $\endgroup$ Feb 11, 2015 at 0:38
  • $\begingroup$ Joel David Hamkins. Yes. You have understood correctly. I want to deal with countable direct limits of ultrapowers because any possible infinite descending sequence in the ultrapower lives somewhere on a countable direct limit of ultrapowers. $\endgroup$ Feb 11, 2015 at 2:21

1 Answer 1

7
$\begingroup$

The answer is yes.

Theorem. The direct limit ultrapower you describe is well-founded if and only if $\bigcap_n A_n\neq \emptyset$ whenever $A_n\in U$ for all $n$.

Proof. You've already noted the converse direction, since any instance of ill-foundedness amounts to $[f_{n+1}]\in_U [f_n]$, which gives measure one sets $A_n=\{x\mid f_{n+1}(x)\in f_n(x)\}\in U$, with empty intersection.

For the forward implication, suppose that we have $A_n\in U$ with $\bigcap_n A_n=\emptyset$. Each $A_n$ lives on some level of the sequence of partitions, but let us assume for convenience (by padding if necessary) that $A_n$ respects the partition $P_n$. We may also assume that $A_{n+1}\subset A_n$.

There is a tree structure $T$ in this situation, whose nodes are the elements of any of the partitions $P_n$ that are in $A_n$, ordered by inclusion. That is, if $b\in P_n$ and $b\subset A_n$, then we place $b\in T$, and we say that $b$ is a parent to any of the corresponding $c\in P_{n+1}$ with $c\subset b$ and $c\subset A_{n+1}$, if there are any such $c$.

The key insight to make is that this tree is well-founded. Any infinite descending sequence of nodes in the tree amounts to a descending sequence $R_n\in P_n$ of partition elements, and you had stated that $\bigcap_n R_n\neq\emptyset$ in any such case. But any element of that intersection would be in $\bigcap_n A_n$, since $R_n\subset A_n$. So there can be no such infinite descending paths through the tree, and so the tree is well-founded.

Because of this, we may define an ordinal ranking function on the tree. Namely, the rank of any $b\in T$ is the supremum of the $\text{rank}(c)+1$ for all $c\in T$ below $b$. This is well-defined by recursion on the tree. Note that the minimal nodes in $T$ get rank $0$, and the rank of any child node is strictly smaller than the rank of its parent.

Consider the ranking function of the nodes of $T$ that happen to be in $P_n$. Let $f_n(x)=\text{rank}(b)$ whenever $x\in b\in T\cap P_n$ be the corresponding rank function. This is an ordinal-valued function with support in $P_n$. But since the rank of a child node is strictly less than the rank of a parent, we see that $f_{n+1}(x)<f_n(x)$, whenever $x\in c\in T\cap P_{n+1}$. Thus, $[f_{n+1}]<_U [f_n]$, and so we have found ill-foundedness in the direct limit ultrapower. QED

If one doesn't insist that $\bigcap_n R_n\neq\emptyset$ when $R_n$ are nested elements of the partition, then one can make a counterexample with principal ultrafilters concentrating on those partition elements.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.