I was reading this article by Alexander Paseau on "Proofs of the Compactness Theorem" and, when explaining Henkin's construction for propositional logic, he makes a comment on how it's not necessary to use Zorn's Lemma to obtain the desired maximal set, but only the Ultrafilter Lemma. Now, the proofs of compactness via ultrafilters that I'm aware of make a detour by Lindenbaum's algebra in order to obtain a partial ordering from the preorder defined by $\phi \leq \psi$ iff $\phi \models \psi$. Surprisingly, Paseau bypasses this detour and uses directly the preorder so defined to obtain a maximal set. More formally, let $\Gamma$ be a finitely satisfiable set. He defines

$\Gamma^* = \{ \phi \; | \; \exists \gamma_1, \dots, \gamma_n \in \Gamma ((\gamma_1 \wedge \dots \wedge \gamma_n) \models \phi)\}$

and then claims that $\Gamma^*$ is a filter because (i) $\bot \not \in \Gamma^*$, (ii) if $\phi_1, \phi_2 \in \Gamma^*$, then $\phi_1 \wedge \phi_2 \in \Gamma^*$, and (iii) if $\phi_1 \in \Gamma^*$ and $\phi_1 \models \phi_2$, then $\phi_2 \in \Gamma^*$.

As I said, this would make sense if we were working inside Lindenbaum's algebra, so that there was a partial order in the background; I've never seen the concept of a filter defined in relation to a preorder. Is this something usual, or was Paseau just a bit sloppy in not indicating that he was working with Lindenbaum's algebra?

  • $\begingroup$ I’ve seen it, e.g., in this paper. $\endgroup$ – Brian M. Scott Aug 23 '16 at 2:00
  • $\begingroup$ @BrianM.Scott Thanks, that is a nice paper $\endgroup$ – Nagase Aug 23 '16 at 2:05

I've definitely seen the word "filter" used in the context of preorders to mean what it should - namely, if $\mathbb{P}$ is a preorder and $\mathbb{Q}$ is the associated partial order ($\mathbb{Q}=\mathbb{P}/\equiv_\mathbb{P}$), then a filter $F$ in $\mathbb{P}$ should be exactly the preimage of a filter in $\mathbb{Q}$ under the quotient map. It's easy to check that this is the same as $F$ being upwards closed and closed under finite meets.

  • $\begingroup$ Alright, but even so the filter in the preorder is defined in connection with the associated partial order, right? $\endgroup$ – Nagase Aug 23 '16 at 2:06
  • 1
    $\begingroup$ @Nagase Doesn't have to be - I just gave that definition to connect with the partial orders definition. A filter in a preorder is defined by being closed upwards and under finite meets. We just need to be a little careful about what these terms mean: e.g. "closed upwards" means $\forall x, y(x\in F, y\ge x\rightarrow y\in F)$ ($\ge$, not $>$), and meets in a preorder are not unique ($x$ is a meet of $y$ and $z$ if $x\le y, z$ and for all $x'\le y, z$, $x\ge x'$). There's no need to bring partial orders into it. $\endgroup$ – Noah Schweber Aug 23 '16 at 2:16
  • $\begingroup$ Got it. So the non-uniqueness of meets don't cause any problems? $\endgroup$ – Nagase Aug 23 '16 at 2:18
  • $\begingroup$ @Nagase No, it doesn't. $\endgroup$ – Noah Schweber Aug 23 '16 at 2:18
  • $\begingroup$ I thought that the meet filter condition on predeorder is: wehenever $x,y\in F$ then $F$ contains some lower bound of $x,y$. Which is is the same as being closed under finite meets in $\wedge$-semilattices. $\endgroup$ – Gur Ismael Aug 23 '16 at 7:42

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.