Trying to define an abstract notion of a function that turns sets of sentences into the set of models satisfying those sentences.

97 Views Asked by At

Let $\mathsf{Sen}$ denote a Boolean algebra, thought of as a collection of sentences, and let $\mathsf{Mod}$ denote a set without any additional structure, thought of as a collection of models. I'm trying to define (abstractly) the notion that a function $f : \mathcal{P}(\mathsf{Sen}) \rightarrow \mathcal{P}(\mathsf{Mod})$ turns a set of sentences $A \in \mathcal{P}(\mathsf{Sen})$ into the set of all models satisfying those sentences $f(A) \in \mathcal{P}(\mathsf{Mod})$.

Now its clear that $f$ ought to turn arbitrary unions into intersections. That is, for all $\mathcal{A} \subseteq \mathcal{P}(\mathsf{Sen})$ we require that $$f(\bigcup_{A \in \mathcal{A}} A) = \bigcap_{A \in \mathcal{A}}f(A).$$

So my first question is: going on our intuition involving first/second-order logic and first/second-order models, ought we require that $f$ turn arbitrary intersections into unions? And should we require that $f$ interact nicely with complements?

Now furthermore, $f$ ought to be compatible with the Boolean Algebra structure on $\mathsf{Sen}$. For instance, if $\phi,\psi \in \mathsf{Sen},$ then we want $$f(\{\phi \wedge \psi\}) = f(\{\phi\}) \cap f(\{\psi\}),\quad f(\{\phi \vee \psi\}) = f(\{\phi\}) \cup f(\{\psi\}),\quad f(\{\phi^c\}) = \mathsf{Mod} \setminus f(\{\phi\})$$

My second question is: Are the requirements of the above paragraph sufficient, given that they're only written in terms of singleton sets, when after all $f$ can potentially operate on infinite collections of sentences? Again, let us go with the intuition that comes from thinking about first/second-order logic and first/second-order models.

1

There are 1 best solutions below

3
On BEST ANSWER

$f$ is a Galois connection between the poset of sets of sentences and the poset of sets of models. Here is a general way to induce Galois connections between such posets: let $X, Y$ be sets and let $R \subseteq X \times Y$ be a relation, which we will write $xRy$. Then we get a Galois connection between the poset of subsets of $X$ and the poset of subsets of $Y$ given by the functions

$$f(S) = \{ y : xRy \forall x \in S \}$$

where $S \subseteq X$ and $f(S) \subseteq Y$, and

$$g(T) = \{ x : xRy \forall y \in T \}$$

where $T \subseteq Y$ and $g(T) \subseteq X$. We recover several classical examples of Galois connections this way.

  • The motivating example behind the name: let $L/K$ be a Galois extension, let $X = K$, and let $Y = \text{Gal}(L/K)$. The relation is $xRy$ iff the group element $y$ fixes the element $x$. This induces the Galois connection between subextensions of $L/K$ and subgroups of $Y$ which is the subject of the fundamental theorem of Galois theory

  • Let $X = k[x_1, ... x_n]$ ($k$ an algebraically closed field) and let $Y = k^n$. The relation is $xRy$ iff the function $x$ vanishes on the point $y$. This induces the Galois connection between ideals of $k[x_1, ... x_n]$ and subvarieties of $k^n$ which is the subject of the Nullstellensatz.

  • In this case, let $X$ be the set of sentences and let $Y$ be the set of models. The relation is $xRy$ iff the sentence $x$ is true in the model $y$. This induces the Galois connection between sets of sentences and sets of models which is the subject of the completeness theorem (in first-order logic).

I think it was Lawvere who first noticed this. The slogan is "syntax is adjoint to semantics." Connecting the last two examples together, you can think of sentences as functions on the space of models and taking the set of models satisfying a collection of sentences as taking the subspace on which a collection of functions vanishes.