Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $ \mathcal{L} $ be a language for first-order logic whose logical primitives are $ \neg$, $\vee$, $\wedge$, $\forall$, and $\exists$, with the usual formation rules. A sentence $ \sigma $ is then a (well-formed) formula with no free variables, and a positive sentence is a sentence that does not contain $ \neg $.

A reduced product $ \mathfrak{A} $ is defined as usual using an index set $ I $, a collection of models $ M_{i} $ indexed by $ I $, and a filter $ F $ on $ I $. If $ F $ is an ultrafilter, the product is an ultraproduct.

Łoś's Theorem concerns ultraproducts. One of its consequences is that for any sentence $\sigma$, $ \mathfrak{A} \models \sigma $ iff $ \lbrace i \: \epsilon \: I \: \vert \: M_{i} \models \sigma \rbrace \: \epsilon \: F $. This does not hold for reduced products in general

But the usual proof of Łoś's Theorem proceeds by induction on the construction of formulas. It makes use of the hypothesis that $F$ is an ultrafilter only in the clause that deals with $ \neg $. Since a positive sentence contains no negation symbols: For any reduced product $ \mathfrak{A} $ and any positive sentence $ \sigma $, $ \mathfrak{A} \models \sigma$ iff $ \lbrace i \: \epsilon \: I \: \vert \: M_{i} \models \sigma \rbrace \: \epsilon \: F $.

That's right, isn't it? Or did I miss something?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

This is a surprisingly subtle issue. My previous answer was incorrect, and I've deleted it.

Let's start by fixing terminology.

A positive sentence is built up from (positive) atomic formulas using $\land$, $\lor$, $\forall$, and $\exists$ (but not $\lnot$).

A basic Horn formula is of the form $\psi_1\land\dots\land\psi_n \rightarrow \theta$, where the $\psi_i$ and $\theta$ are (positive) atomic formulas.

A Horn sentence is built up from basic Horn formulas using $\land$, $\forall$, and $\exists$ (but not $\lnot$ or $\lor$).

Let $I$ be an infinite set indexing a collection of structures $\langle A_i\rangle_{i\in I}$, $D$ a proper filter on $I$, and $A = \Pi_DA_i$ the reduced product.

Say a sentence $\phi$ is weakly preserved under reduced product if $\{i\,|\,A_i\models\phi\} = I$ implies $A\models \phi$.

Say a sentence $\phi$ is strongly preserved under reduced product if $\{i\,|\,A_i\models\phi\}\in D$ implies $A\models \phi$.

Say a sentence $\phi$ is preserved under reduced factors if $A\models\phi$ implies $\{i\,|\,A_i\models\phi\} \in D$.

Your question asked whether Los's theorem holds for positive sentences in reduced products, i.e. whether every positive sentence is strongly preserved under reduced product and preserved under reduced factors. In fact, positive sentences are preserved under reduced factors, but not necessarily under reduced product (strongly or weakly).

Surprisingly, the problem occurs with the $\lor$ case. Here's an example. Let $L = \{c, P,Q\}$, where $c$ is a constant and $P$ and $Q$ are both unary relation symbols. Define $\langle A_i\rangle_{i\in\mathbb{N}}$ as follows: all $A_i$ consist of just one element, $c$. If $i$ is even, $A_i\models P(c)\land \lnot Q(c)$, but if $i$ is odd, $A_i\models \lnot P(c)\land Q(c)$. Now let $D$ be the cofinite filter on $\mathbb{N}$. Then the reduced product $A$ consists of just one element, $c$, and $A\models \lnot P(c) \land \lnot Q(c)$. So the sentence $P(c)\lor Q(c)$ is false in $A$, despite holding in all of the $A_i$.

Okay, so $\lor$ isn't preserved under reduced products, but it turns out that the other operations are okay (in particular, both quantifiers are). In fact, we can expand our basic building blocks up from atomics to basic Horn sentences and still get the strong preservation under reduced product.

Here's a summary of what's known, as far as I know (most can be found in C+K Section 6.2, recently reprinted by Dover!)

  • Horn sentences are strongly preserved under reduced product.
  • Every sentence which is weakly preserved under reduced product is equivalent to a Horn sentence.
  • Together, since strongly preserved under reduced product implies weakly preserved under reduced product, these imply that "weakly preserved under reduced product" "strongly preserved under reduced product" and "equivalent to a Horn sentence" are all equivalent notions.
  • Every positive sentence is preserved under reduced factors.
  • The converse is not true: there are sentences preserved under reduced factors which are not equivalent to positive sentences.
  • Notice that Los's theorem is exactly "strongly preserved under reduced product" + "preserved under reduced factors". So Los's theorem holds for sentences which are equivalent to both a positive sentence and a Horn sentence. This includes all sentences built up from (positive) atomics by $\land$, $\forall$, and $\exists$. But it may also hold for a larger class of sentences.
share|improve this answer
    
I didn't know Dover republished Chang & Keisler's great book. Thanks! –  Quinn Culver Sep 17 '12 at 23:21
    
So I think we're saying the positive sentences are a proper subset of the Horn sentences. My conjecture that positive sentences are preserved under reduced products is true, but not as general as it could be. -- Thanks for the pointer to C+K Section 6.2; I missed that. –  MikeC Sep 18 '12 at 4:38
    
@MikeC I've updated my answer - take a look. –  Alex Kruckman Sep 19 '12 at 22:43
    
@Alex Your example regarding disjunction is very illuminating. It's entirely correct but seems to make no sense, that a sentence true at all factors is false at the product. It comes down to the fact that a disjunction is not true unless one of its disjuncts is, and neither disjunct in your example is true at the product. -- What I'm really looking for is a way to construct boolean-valued models via reduced products, in which your example would fail. It would fail because the join of two elements can be 1 when neither element is. But I'm not there yet. Thanks for your help. –  MikeC Sep 20 '12 at 5:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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