3
$\begingroup$

If we have a family $(\mathfrak{M}_i)_{i\in I}$ of $L$-structures, and a filter $\mathcal{F}$ over $I$, we can define the reduced product $\prod_{i\in I}\mathfrak{M }_i/\mathcal{F}$. If $\mathcal{F}$ is an ultrafilter, the following property called Łoś's theorem is verified for all formula $F[v_1,...,v_n]$ and all elements $(a_1^i)\dots(a_n^i)$ in $\prod_{i\in I}|\mathfrak{M}_i|$: $$\prod_{i\in I}\mathfrak{M }_i/\mathcal{F}\models F[\widetilde{(a_1^i)},\dots,\widetilde{(a_n^i)}]\Leftrightarrow\{i\in I|\mathfrak{M}_i\models F[a_1^i,\dots,a_n^i]\}\in\mathcal{F}$$

I was wondering if we could find a counter-examples if $\mathcal{F}$ is not an ultrafilter. I can find a language and a structure in which this property is false for a given $\mathcal{F}$. For example take the language $L_0$ with just two 1-ary relation $R$ and $S$, the $L_0$-structure $\mathfrak{M}_0$ with base set $\{0,1\}$, $\overline{R}^{\mathfrak{M}_0}=\{0\}$ and $\overline{S}^{\mathfrak{M}_0}=\{1\}$. Take the formula $F=\forall x,Rx\vee Sx$. Then $\mathfrak{M}\models F$ but $\mathfrak{M}^I/\mathcal{F}\not\models F$ (if $G\in \mathcal{P}(I)$ such that $G\not\in\mathcal{F}$ and $^cG\not\in\mathcal{F}$ take the element $(x^i)_{i\in I}$ which is equal to $1$ on $G$ and $0$ on $^cG$).

Now, given a filter $\mathcal{F}$ which is not an ultrafilter, a language $L$ and structures $\mathfrak{M}_i$, is there always a formula (a sentence ?) which does not verify Łoś's theorem ? If it is false, then, given a filter $\mathcal{F}$ which is not an ultrafilter and a language $L$, can we find structures $\mathfrak{M}_i$ (I would rather have $i\rightarrow\mathfrak{M}_i$ constant) and a formula (a sentence ?) F, which do not verify the theorem ?

$\endgroup$
  • $\begingroup$ by the way you got name almost right. The name is Łoś ;] $\endgroup$ – Trismegistos May 14 '14 at 14:48
  • 1
    $\begingroup$ @Trismegistos: It's hard to get all the diacritics right, particularly if you don't know the language. $\endgroup$ – tomasz May 14 '14 at 18:02
  • $\begingroup$ @Tomasz this is three letter name so it is not particularly hard to eyeball it. $\endgroup$ – Trismegistos May 15 '14 at 8:46
1
$\begingroup$

The answer is yes on both accounts, at least assuming the initial structures are nontrivial (i.e. have more than $1$ element), or at least that it is not true that $\mathcal F$-almost all are trivial.

Consider the formula $\neg (x=y)$, a set $A\notin \mathcal F$ with $A^c\notin\mathcal F$, and let $x_i,y_i$ be two sequences such that $x_i=y_i$ if and only if $i\in A$. Then $(x_i)/\mathcal F\neq (y_i)/\mathcal F$ even though this is not witnessed by a large set of $i$.

The key thing is, for any reduced product, positive combinations are preserved, even with quantifiers, but you need $A\in \mathcal U$ or $A^c\in \mathcal U$ to deal with negation. Otherwise (the supposed more general version of) Łoś's theorem would violate the law of excluded middle.

$\endgroup$
  • 1
    $\begingroup$ I always thought that you just get a Boolean-valued model, rather than a classical $\tt\{T,F\}$ true values. $\endgroup$ – Asaf Karagila May 14 '14 at 18:33
  • 1
    $\begingroup$ @AsafKaragila One natural generalization of the ultraproduct construction to arbitrary filters produces Boolean-valued models (with truth values in $\mathcal{P}(I)/\mathcal{F}$). But there is a quite standard (and older?) notion of reduced product which produces a classical structure. $\endgroup$ – Alex Kruckman May 14 '14 at 18:44
  • $\begingroup$ @Alex: Yes, I am aware of the notion of reduced products. And I'm sure that there are some deeper model theoretic connection between the two notions. $\endgroup$ – Asaf Karagila May 14 '14 at 18:59
1
$\begingroup$

tomasz shows that if $\mathcal{F}$ is not an ultrafilter, you can always find a formula which does not verify Łoś's theorem. However, you might not be able to do this with a sentence. For example, taking $L$ to be the language with just equality, any reduced product of a collection of infinite sets is an infinite set. All infinite sets are elementarily equivalent, so a sentence is satisfied in the reduced product if and only if it is satisfied in all of the factors.

In your second version of the question, however, you allow free choice of structures $\{M_i\}_{i\in I}$, given a fixed $\mathcal{F}$ and $L$. Here you can take each $M_i$ to be a set with two elements. The reduced product will have more than $2$ elements: Let $X$ be such that neither $X$ nor $X^c$ are in $\mathcal{F}$. Then there are four elements which are constant on $X$ and $X^c$, none of which are equal. So the sentence $\exists x\exists y\exists z (x\neq y \land x\neq z\land y\neq z)$ will be true in the reduced product, but in none of the factors.

For more information on Łoś's theorem for reduced products, see my answer here.

$\endgroup$

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.