Let $\mathcal{A}_i (i \in I)$ be a family of $L$-structures, $F \subseteq \mathcal{P}(I)$ a filter and denote by $\mathcal{A}$ the reduced product of this family by $F$. I'll denote the domain of $\mathcal{A}_i$ by $A_i$ and similarly for $\mathcal{A}$. Moreover, if $\alpha \in A$, then I'll denote the $i$ coordinate of a representative of $\alpha$ by $a_i$.

Now, there is a usual argument by induction on the complexity of formulas that shows that, if $\phi$ is positive primitive, then we have

$\mathcal{A} \models \phi$ iff $\{i \in I \; | \; \mathcal{A}_i \models \phi\} \in F$.

What I'm worried about here is about the $\exists y \psi$ case. In the proof by induction, we generally have something like:

$\mathcal{A} \models \exists y \psi$ iff there is $\alpha \in A$ such that $\mathcal{A} \models \psi[\alpha]$ iff $\{ i \in I \; | \; \mathcal{A}_i \models \psi[a_i]\} \in F$, which in turn implies that $\{i \in I \; | \; \mathcal{A}_i \models \exists y \psi\} \in F$.

For the converse, we usually proceed like this:

Suppose $X = \{i \in I \; | \; \mathcal{A}_i \models \exists y \psi\}$ and $X \in F$. We need to build a sequence $a$ such that its corresponding equivalence class $\alpha$ is such that $\mathcal{A} \models \psi[\alpha]$. So, for each $i \in X$, we pick $a_i \in A_i$ such that $\mathcal{A}_i \models \psi[a_i]$, which we can do by the hypothesis. But if $j \not \in X$, then we can pick any arbitrary element of $A_j$. The proof then continues as usual.

This proof of the converse step clearly makes use of the axiom of choice. My question is: are there models of $\mathsf{ZF}$ in which this converse fails?


Edit: To avoid confusions, let me point out that the theorem in question is the version of Łoś's theorem for positive primitive formulas and reduced products (as opposed to the usual version for first-order formulas and ultraproducts), as presented e.g. as Theorem 1(i) in these notes.

Yes, the converse can fail without choice. In fact, this version of Łoś's theorem is equivalent to AC. To see this, let's prove AC.

let $(A_i)_{i\in I}$ be a family of nonempty sets, and let $A$ be their cartesian product. Producing a choice function for the family is equivalent to showing that $A$ is nonempty.

Let $L$ be the language with no symbols (only equality). An $L$-structure is just a set, so $A$ and each $A_i$ are $L$-structures. Consider the filter $F = \{I\}$ on $I$. The reduced product by $F$ in the language $L$ is just the same as the cartesian product.

We have $A_i\models \exists x\, (x=x)$ for all $i\in I$, since each $A_i$ is nonempty, so $\{i\in I\mid A_i\models \exists x\, (x=x)\} \in F$, and hence $A\models \exists x\, (x=x)$. In particular, $A$ is nonempty.

  • $\begingroup$ So, since the converse implies that the reduced product is non-empty, it is equivalent to AC? $\endgroup$ – Nagase Sep 17 '18 at 15:51
  • 1
    $\begingroup$ Yes, it's equivalent to AC. I suppose it would have been better to phrase my answer as a proof of AC from the reduced product transfer principal! I hope it's clear how to do that. $\endgroup$ – Alex Kruckman Sep 17 '18 at 15:52
  • 1
    $\begingroup$ I've rewritten the answer to be an explicit proof of AC from the reduced product form of Łoś's theorem. $\endgroup$ – Alex Kruckman Sep 17 '18 at 16:52

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.