# Filters and preorders

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?

• I’ve seen it, e.g., in this paper. – Brian M. Scott Aug 23 '16 at 2:00
• @BrianM.Scott Thanks, that is a nice paper – 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.
• @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. – Noah Schweber Aug 23 '16 at 2:16
• 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. – Gur Ismael Aug 23 '16 at 7:42