3
$\begingroup$

The Wikipedia page on the compactness theorem says:

One of those proofs relies on ultraproducts hinging on the axiom of choice as follows:

Proof: Fix a first-order language $L$, and let $\Sigma$ be a collection of $L$-sentences such that every finite subcollection of $L$-sentences, $i\subseteq\Sigma$ of it has a model ${\displaystyle {\mathcal {M}}_{i}}$.

Is the axiom of choice already used here? As an hypothesis, we assume that for each $i$, there is a model $A\models i$. Do we need the axiom of choice here to fix for each $i$ one such specific model $\mathcal M_i$?

$\endgroup$
4
  • $\begingroup$ The axiom of the choice gives you the function $i \mapsto {\mathcal M}_i$. If I remember this correctly, there is also another use of the axiom of choice in constructing an ultrafilter from a filter. $\endgroup$
    – Levon Haykazyan
    Feb 22, 2017 at 14:06
  • $\begingroup$ So we already need the axiom of choice to just speak about the specific M_i for each i? Then, why not post this as an answer? $\endgroup$
    – Please Help
    Feb 22, 2017 at 14:08
  • $\begingroup$ I think that you're using the axiom of choice to build an ultrafilter on the powerset of $\Sigma$ which doesn't contain any finite set (e.g. is nonprincipal). Then Łoś's theorem should imply that the ultraproduct of all the $\mathcal{M}_i$ is a model of $\Sigma$, but it's been a while since I've seen this stuff so I can't really elaborate on any of the details. $\endgroup$
    – Joe Berner
    Feb 22, 2017 at 14:22
  • $\begingroup$ @JoeBerner That's missing the OP's question - they're asking if Choice is also needed to get the set of $\mathcal{M}_i$s. $\endgroup$
    – Noah Schweber
    Feb 22, 2017 at 15:57

1 Answer 1

Reset to default
7
$\begingroup$

Yes, as stated this already appeals to the axiom of choice. We need to choose for each $i$ a model $\cal M_i$.

There is something additional to say about the connection between Los' theorem and compactness, though.

It is a theorem of $\sf ZF$ that Los+Compactness imply choice. And it is consistent that Los' theorem holds, while compactness fails. So when we prove compactness from Los' theorem, we invariably use choice in "preparing the setting in which Los' theorem works".

You can find the surprisingly readable proof of this fact in the following paper:

Howard, Paul E. "Łoś’ theorem and the Boolean prime ideal theorem imply the axiom of choice." Proceedings of American Math. Society 49 (1975): 426-428.

$\endgroup$
3
  • 4
    $\begingroup$ +1. To the OP, note that there are actually three distinct uses of Choice in the ultraproduct proof of compactness: $(i)$ getting the set $\{\mathcal{M}_i: i\in I\}$, $(ii)$ getting a nonprincipal ultrafilter on $I$, and $(iii)$ proving Los' theorem, specifically the existential part (picking an $a_i\in\mathcal{M}_i$ whenever $\mathcal{M}_i\models\exists x\varphi(x)$). $\endgroup$
    – Noah Schweber
    Feb 22, 2017 at 15:58
  • $\begingroup$ @NoahSchweber: Do you really mean "getting the set $\{M_i : i\in I\}$". I would rather say it's a function $i\mapsto M_i$ (i.e. an indexed family $(M_i)_{i\subseteq\Sigma}$) $\endgroup$
    – Please Help
    Feb 22, 2017 at 16:00
  • 1
    $\begingroup$ @PleaseHelp "$\{A_i: i\in I\}$" is often used as shorthand for the set of ordered pairs "$\{\langle i, A_i\rangle: i\in I\}$," which is exactly the function $i\mapsto \mathcal{M}_i$. (This is an abuse of notation, but it's common.) Remember that in set theory, a function $f$ is a set, namely its graph $\{\langle x, y\rangle: f(x)=y\}$. $\endgroup$
    – Noah Schweber
    Feb 22, 2017 at 16:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .