Two equivalent statements about formulas projected onto an Ultrafilter

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.

• I'm confused by your notation. For each $i\in X$, $f(i)$ is a formula which has $x_{x(i)}$ as a free variable? Could it have more free variables? Did you really mean to write "the formulas indexed by $\equiv$"? Commented Jul 7 at 17:14
• Also, is $f(i)$ a formula, or have you valuated one of the variables of formula $f$ at the individual $i$? And you mention $\mu$ and $\nu$ in the hypothesis of statement 1, but only $\mu$ appears in the conclusion, so I am confused about the intended quantification for that. Commented Jul 7 at 17:46
• Your equivalence $\nu\equiv\mu$ seems to be only about same-value of the valuations, not truth of the formula at those valuations, whereas the conclusion of statement 1 depends on the truth of the formula. So isn't this obviously wrong? Perhaps you are missing a hypothesis about $(M,\nu)$? Commented Jul 7 at 17:49
• I am sorry that my incorrect translation has caused reading difficulties. I translated the Chinese content using gpt, and the effect is not good. I have modified part of it. $x_x(i)$ is only a variable in the language. It may not be a free variable of $f(i)$, and it may not even appear in $f(i)$. $∀x_x(i)f(i)$ is only the universalization of a variable in the language. $f(i)$ is only a formula, and $f$ is a function $\{ (i, f(i))| f(i)\text{ is a formula in the language and } i ∈ X \}$ Commented Jul 7 at 20:25
• Let me try again to understand. Does $\mu\equiv_{\forall x_{x(i)} f(i)} \nu$ mean that $\mu$ and $\nu$ agree on all the free variables in $f(i)$ except possibly for $x_{x(i)}$? Commented Jul 7 at 20:34

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. 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.

• Thanks for your reply. Your understanding is correct. I will add some background to my question, which arises from my personal interest (and my attempt to secure a postgraduate admission offer). I am trying to apply ultrafilter to formulas, specifically in reasoning. This is why I am using a function (a selection function) as an unusual main object($[f]$ is the equivalence class obtained by naturally quotienting the selection function $𝑓$ by the equivalence relation.). To clarify, I will define that for an assignment $\mu$, $(M, \mu) \models [f]$ iff $\{i \mid (M, \mu) \models f(i)\} \in U$ Commented Jul 9 at 6:01
• @Stanleysun I have updated my answer with a counterexample to the equivalence. Commented 2 days ago
• Very clever construction, thank you! I understand. Commented 2 days ago