Skip to main content
5 of 6
added 970 characters in body
Alex Kruckman
  • 5k
  • 2
  • 24
  • 33

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

Alex Kruckman
  • 5k
  • 2
  • 24
  • 33