-3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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$"? $\endgroup$ Commented Jul 7 at 17:14
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jul 7 at 17:46
  • 2
    $\begingroup$ 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)$? $\endgroup$ Commented Jul 7 at 17:49
  • $\begingroup$ 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 \}$ $\endgroup$ Commented Jul 7 at 20:25
  • $\begingroup$ 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)}$? $\endgroup$ Commented Jul 7 at 20:34

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$ $\endgroup$ Commented Jul 9 at 6:01
  • 1
    $\begingroup$ @Stanleysun I have updated my answer with a counterexample to the equivalence. $\endgroup$ Commented 2 days ago
  • $\begingroup$ Very clever construction, thank you! I understand. $\endgroup$ Commented 2 days ago

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.