1
$\begingroup$

I am trying to prove Los theorem (the one for ultraproducts, the statement with a proof is here. https://proofwiki.org/wiki/Łoś%27s_Theorem), but using $\forall$ as primitive quantifier. Any proof online uses $\exists$ as primitive quantifier to do the induction step. Could someone please give a proof using $\forall$ instead of $\exists$ to prove it?

I know, the $\forall$ is just $\lnot \exists \lnot$, but now I am searching for a direct proof. I did not expect it to be hard (basically "by definition"). However, after tried manipulating the statement, I still cannot get it. Any help or reference would be appreciated, thank you!

$\endgroup$
1
$\begingroup$

First, if $$\{i\in I:\mathcal A_i \models \forall x\varphi(x)\} \in U$$ then for any $f,$ $$ \{i\in I:\mathcal A_i\models\varphi(f(i))\}\in U$$ (since the latter is a superset of the former) and hence by the IH, $ \forall [f]\in A,\mathcal A\models \varphi([f]).$

For the converse, assume that $$ \{i\in I:\mathcal A_i\models\forall x\varphi(x)\}\notin U,$$ so that $$ \{i\in I:\exists x\in A_i,\mathcal A_i\not\models\varphi(x)\}\in U.$$ Use choice to let $f(i)$ be a witness to the statement $"\exists x\in A_i,\mathcal A_i\not\models\varphi(x)"$ when it's satisfied. Then $$ \{i\in I : \mathcal A_i\not\models \varphi(f(i))\}\in U,$$ so $$ \{i\in I : \mathcal A_i\models \varphi(f(i))\}\notin U$$ and $$ \exists [f]\in A,\mathcal A\not\models \varphi([f])$$

$\endgroup$
  • $\begingroup$ Thank you for answering. I think I get the proof except for one step: How does $\{i\in I:\exists x\in A_i,A_i\not\vdash \varphi(x)\}\in U$ implies $\{i\in I:A_i\not\vdash\varphi(f(i))\}\in U$? (It seems to me that this is claiming "exists a point that the formula is satisfies implies the formula is satisfied in a particular point". I got stuck on this point before.) $\endgroup$ – PropositionX Jun 27 at 2:36
  • $\begingroup$ Because, by the definition of $f,$ $\exists x\in A_i,\mathcal A_i\not\models\varphi(x)$ implies $\mathcal A_i\not\models\varphi(f(i)).$ Thus the second set is a superset of the first. $\endgroup$ – spaceisdarkgreen Jun 27 at 2:58
  • $\begingroup$ This is exactly where I am not convinced (or maybe I misunderstood it): The $f$ just pick a particular witness where the formula is not satisfied, so it is not the fact that once we say "the formula is not satisfied", that must be the fact that it is not satisfied at $f(i)$. However, if a formula is not satisfied at $f(i)$, then there exists a point that the formula is not satisfied. So I think the second set is subset instead of supset of the first set. $\endgroup$ – PropositionX Jun 27 at 3:09
  • 1
    $\begingroup$ "The f just pick a particular witness where the formula is not satisfied"... yes. That means precisely that $\varphi(x)$ is not satisfied for $x=f(i).$ How can it be satisfied at $f(i)$ when it is defined not to be? And yes, the other direction holds too, so they are actually the same set. $\endgroup$ – spaceisdarkgreen Jun 27 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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