Two equivalent statements about formulas projected onto an Ultrafilter

Question

Question 1:

In the same language, let $ X $ be a nonempty set, and let $ \{ (\forall x_{x(i)} f(i)) \ | \ i \in X \} $ be a set of formulas. We use $ x(i) $ to denote the index of the variable on which the universal quantifier acts in the formula $\forall x_{x(i)} f(i) $. Let $ \equiv $ denote that two assignments have the same value for the free variables of the formula indexed by $ \equiv $ (In its lower right corner). Let $ U $ be an ultrafilter on $ X $, and $ (M, \nu) $ be a model structure in this language.

The question is:

Statement 1: For all assignments $ \mu $ in the structure $ M $, if $ \{ i \ | \ \nu \equiv_{(\forall x_{x(i)} f(i))} \mu \} \in U, $ then $ \{ i \ | \ (M, \mu) \models f(i) \} \in U. $

And Statement 2: $ \{ i \ | \ \text{for all assignments } \mu \text{ in } M, \nu \equiv_{(\forall x_{x(i)} f(i))} \mu, \text{ then } (M, \mu) \models f(i) \} \in U. $

Are these two statements equivalent?

Question 2:

Is there a simpler formula that can equivalently replace this: $ \{i \mid \{j \mid \phi(i,j) \} \in U\} \in U \quad \text{and} \quad \{j \mid \{i \mid \phi(i,j) \} \in U\} \in U, $ where $U$ is an ultrafilter?

I understand that we might express it using some commutative statement of generalized quantifiers, such as $\forall^* i \forall^* j \phi(i,j)$, but I still hope to get some concrete content rather than just a different representation.

Additionally, I feel that the content of these two questions is quite different, but the difficulty I encounter when thinking about them feels very similar. What is it? I currently do not have the ability to abstract what this common difficulty is.

Answer 1

First, since I found your notation confusing, I hope you don't mind if I rewrite your Question 1 in more standard notation.

Fix a language $L$. Let $I$ be a non-empty set, and let $(\varphi_i)_{i\in I}$ be a family of $L$-formulas, all of which have free variables from a set $V=\{x_0,x_1,x_2\dots\}$. For each $i\in I$, let $V_i\subseteq V$ be the finite set of variables which are free in $\varphi_i$. We also pick a variable $x_{k_i}\in V$ for each $i\in I$, which may or may not be free in $\varphi_i$.

Let $M$ be an $L$-structure. An assignment $a = (a_x)_{x\in V}$ is a family of elements from $M$ indexed by $V$ (so the variable $x$ gets assigned to $a_x\in M$). Given assignments $a$ and $b$, we write $a\equiv_i b$ if $a_x = b_x$ for all $x\in (V_i\setminus \{x_{k_i}\})$.

Fix an assignment $a$ and an ultrafilter $U$ on $I$.

Statement 1: For all assignments $b$, if $\{ i \mid a \equiv_i b \} \in U$, then $\{ i \mid M\models \varphi_i(b) \} \in U. $

Statement 2: $ \{ i \mid \text{for all assignments } b , \text{if }a \equiv_i b, \text{then } M\models \varphi_i(b)\} \in U.$

Are these two statements equivalent?

---

Next, to make the logical structure of the statements more transparent, I'll rewrite the statements using the quantifier $\forall^*$, which means for "almost all" $i$ in the sense of the ultrafilter.

Statement 1: $\forall b\, ((\forall^* i\, a\equiv_i b)\rightarrow (\forall ^* i\, M\models \varphi_i(b)))$

Statement 2: $\forall^* i \forall b\, (a\equiv_i b\rightarrow M\models \varphi_i(b))$

Now the nice thing about the ultrafilter $\forall^*$ quantifier is that it commutes with / distributes over all propositional connectives. So Statement 1 is equivalent to $\forall b\forall^* i\,(a\equiv_i b\rightarrow M\models \varphi_i(b))$.

Unfortunately, the quantifier $\forall^* i$ does not commute with $\forall b$. Statement 2 obviously implies Statement 1, since $\forall^* i\forall b$ is stronger than $\forall b\forall^* i$. But the converse may not hold.

---

I'll give a counterexample to the implication from Statement 1 to Statement 2.

Let $L$ be the empty language (the language of equality). Let $I = \omega$ and $U$ any nonprincipal ultrafilter on $\omega$.

For each $i\in \omega$, let $\varphi_i$ be $\bigwedge_{0\leq j<k\leq i+1} x_j = x_k$. Note that the set of free variables in $\varphi_i$ is $V_i = \{x_0,\dots,x_{i+1}\}$. Let $k_i = i+1$, so the specified variable $x_{k_i}$ is $x_{i+1}$.

Let $M$ be any set with at least two elements, and let $0$ and $1$ be distinct elements of $M$. Let $a$ be the constant assignment with value $0$, i.e., $a_k = 0$ for all $k$. Note that for an assignment $b$ and $i\in \omega$, $a\equiv_i b$ if and only if $b_j = a_j = 0$ for all $j\leq i$ (since $V_i\setminus \{x_{k_i}\} = \{x_0,\dots,x_i\}$).

Now with this setup, Statement 1 is true. Let $b$ be an assignment, and suppose $\{i\mid a\equiv_i b\}\in U$. I claim that $b = a$. Indeed, for all $j\in \omega$, since $\{i\mid a\equiv_i b\}$ is infinite, there exists $i\geq j$ such that $a\equiv_i b$, and hence $b_j = a_j = 0$. Thus $b$ is the constant assignment with value $0$, so $\{i\mid M\models \varphi_i(b)\} = \omega \in U$.

But Statement 2 is false. Fix $i\in \omega$, and let $b$ be the assignment with $b_j = 0$ for all $j\leq i$ and $b_j = 1$ for all $j>i$. Then $a\equiv_i b$, but $M\not\models \varphi_i(b)$, since $b_{i+1} = 1 \neq 0 = b_i$.

Thus $\{ i \mid \text{for all assignments } b , \text{if }a \equiv_i b, \text{then } M\models \varphi_i(b)\} = \varnothing \notin U$.

---

Regarding Question 2, you probably know that if $U$ and $V$ are ultrafilters on $X$, then $U\otimes V = \{Y\subseteq X^2\mid \{i\mid \{j\mid (i,j)\in Y\}\in V\}\in U\}$ is an ultrafilter on $X^2$. So you can rewrite your statement as $\{(i,j)\mid \phi(i,j)\}\cap \{(j,i)\mid \phi(i,j)\}\in U\otimes U$. But this is just different notation. I doubt there is a conceptually simpler way to describe the concept.

Answer 2

I would like to express my gratitude to Alex Kruckman for his insightful answer. His counterexample not only resolved my issue but also provided significant inspiration. For my personal understanding and completeness, I aim to fully grasp the principles underlying this question.

Fortunately, I have achieved this understanding, and I plan to extend and elucidate the principles behind this counterexample through a self-answered approach. Essentially, these two statements are not equivalent due to the fact that ultrafilters and consistency (in the sense of ultrafilters) restrict the arbitrariness of universal quantifiers. Identical assignments limit this arbitrariness to a specific point of the identical assignments, thus no longer arbitrary.

---

Therefore, we present Statement 3: $\forall u \in U (\{i \mid x_{k_i} \in \cup \{ V_j \setminus \{x_{k_j} \} \mid j \in u \}\} \in U)$. Under the same assumptions, we have the following theorem:

$$ \text{Statement 1} \iff (\text{Statement 2} \lor \text{Statement 3}) \land \{i \mid M \models \varphi_i (a)\} \in U $$

Proof: We first prove that if $(\text{Statement 2} \lor \text{Statement 3}) \land \{i \mid M \models \varphi_i (a)\} \in U$, then $\text{Statement 1}$. Since it is easy to see that $\text{Statement 2}$ implies $\text{Statement 1}$, we only need to consider the case where $\text{Statement 2}$ is false, but $\text{Statement 3}$ and $\{i \mid M \models \varphi_i (a)\} \in U$ are true.

For any assignment $b$, if $\{i \mid a \equiv_i b\} \in U$, let $u_b = \{i \mid a \equiv_i b\}$, then $u_b \in U$. By $\text{Statement 3}$ being true, we have$\{i \mid x_{k_i} \in \cup \{V_j \setminus \{x_{k_j}\} \mid j \in u_b\}\} \in U$.

Since for any $i \in I$, $x_{k_i} \in \cup \{V_j \setminus \{x_{k_j}\} \mid j \in u_b\}$ is equivalent to the existence of $j_i \in u_b$ such that $x_{k_i} \in V_{j_i} \setminus \{x_{k_{j_i}}\}$. From $u_b = \{i \mid a \equiv_i b\}$, we get $\forall i \in u_b (\forall x \in V_i \setminus \{x_{k_i}\} (a_x = b_x))$. Therefore, we have $\{i \mid a_{x_{k_i}} = b_{x_{k_i}}\} \in U$, and further $\{i \mid \forall x \in V_i (a_x = b_x)\} \in U$. From $\{i \mid M \models \varphi_i (a)\} \in U$, we get $\{i \mid M \models \varphi_i (b)\} \in U$, which means $\text{Statement 1}$ is true.

Next, we prove that if $\text{Statement 1}$ is true, then $(\text{Statement 2} \lor \text{Statement 3}) \land \{i \mid M \models \varphi_i (a)\} \in U$. Similarly, since it is easy to see that if $\text{Statement 1}$ is true, then $\{i \mid M \models \varphi_i (a)\} \in U$ is true, we only need to prove that if both $\text{Statement 2}$ and $\text{Statement 3}$ are false, then $\text{Statement 1}$ must be false.

If $\text{Statement 3}$ is false, then $\exists u \in U (\{i \mid x_{k_i} \notin \cup \{V_j \setminus \{x_{k_j}\} \mid j \in u\}\} \in U)$. Let $u_0$ satisfy this condition, i.e., $\{i \mid \forall j \in u_0 (x_{k_i} \notin V_j \setminus \{x_{k_j}\})\} \in U$.

If $\text{Statement 2}$ is false, then $\{i \mid \exists b_i (a \equiv_i b_i \land M \not\models \varphi_i (b_i))\} \in U$. Let $u_1$ be this set.

Let $u_2 = u_0 \cap u_1$, and let $b$ be any assignment satisfying $\forall i \in u_2 (b \equiv_i a \land b(x_{k_i}) = b_i (x_{k_i}))$. By the property of $u_0$, such an assignment $b$ exists.

Therefore, $u_2$ satisfies $\forall i \in u_2 (\forall x \in V_i (b(x) = b_i(x)))$, and thus $\forall i \in u_2 (M \not\models \varphi_i (b))$.

This means $\{i \mid M \not\models \varphi_i (b)\} \in U$ and $\{i \mid a \equiv_i b\} \in U$, hence $\{i \mid M \models \varphi_i (b)\} \notin U$, making $\text{Statement 1}$ false.

Thus, the proposition is proved.

It is also evident that while $\text{Statement 1}$ and $\text{Statement 2}$ are not always equivalent, they are equivalent when $\text{Statement 3}$ is false or $\{i \mid M \not\models \varphi_i (a)\} \in U$.