10
$\begingroup$

Let $L$ be a first order language, and let $S_{L}=\{\sigma:\sigma\;\mbox{is an $L$-sentence}\}$. Also, by logical compatness I mean the Compactness Theorem of first order logic.

Compactness Theorem: Let $\Sigma$ be a set of $L$-sentences. $\Sigma$ is satisfiable if and only if each finite subset of $\Sigma$ is satisfiable.

Now, we may consider the set $X=\{M:M\;\mbox{is an $L$-structure}\}$ and define a topology on $X$ as follows:

For each $L$-sentence $\sigma$ define a basic open set $U_{\sigma}=\{M\in X:M\vDash\sigma\}$. Open sets in $X$ are arbitrary unions and finite intersections of the basic open sets $U_{\sigma}$.

A few facts we observe are: $X$ does not seem to be Hausdorff (not even $T_{0}$), and the connected components of $X$ appear to be the equivalence classes of structures by the relation $\equiv$ of elementary equivalence of $L$-structures.

In fact, for each $L$-structure $M$ we let $T_{M}=\{\sigma\in S_{L}:M\vDash\sigma\}$, and consider the set $Y=\{T_{M}:M\;\mbox{is an $L$-structure}\}$. We can define a topology on $Y$ by defining open sets in $Y$ to be arbitrary unions and finite intersections of basic open sets $V_{\sigma}$ defined for each $L$-sentence $\sigma$ by $V_{\sigma}=\{T\in Y:\sigma\in T\}$.

With this topology $Y$ is totally separated, and hence totally disconnected and Hausdorff. In fact it seems to be homeomorphic to $X/\negthickspace\equiv$ in the quotient topology.

I believe I can show that the Compactness Theorem is true if and only if $Y$ (resp. $X$) is a compact space. My question is:

Is there a purely topological proof showing that $Y$ (resp $X$) is a compact topological space?

Note: Where does this question come from? From working out the analogous situation for propositional logic (i.e. $L$ is a propositional language) and trying to work out the case for first order logic. For propositional logic the analogously obtained $X$ (space of $L$-valuations) and $Y$ are really homeomorphic, and readily seen to be homeomorphic to $\{0,1\}^{L}$ with the product topology. Hence, the Tychonoff Theorem provides the answer to my question. I have not found such a simple path for the first order situation I have described. Perhaps I should define $X$ and $Y$ differently? Where I am going wrong?


Thanks to the comments by Greg Nisbet and Chris Eagle that pointed out $X$ being a proper class. The $U_{\sigma}$ seem proper classes also. Hence, $X$ is given a topology in which the closed "sets” are proper classes (except for the empty set). Can we speak of $X$ being a compact class? It's quotient by $\equiv$ is indeed a set.

Are there any conditions on $L$ or otherwise that would make $X$ a set? (Chris Eagle points to some in a comment below)


Ok, $X$ is a proper class, it can be given a topology with the basic closed "sets" being the proper classes $U_{\sigma}$. All is well since $U_{\sigma}\cup U_{\tau}=U_{\sigma\vee\tau}$, and every closed subclass is of the form $$\displaystyle\bigcap_{\sigma\in S} U_{\sigma},$$ for some subset $S$ of $L$-sentences. Now, is this topology compact? Well, in order for logical compactness to say that $X$ is compact we would need that $$\displaystyle\bigcap_{\sigma\in S} U_{\sigma}\neq\emptyset,$$ whenever $S\subseteq S_{L}$, and that for every finite subset $S_0$ of $S$ $$\displaystyle\bigcap_{\sigma\in S_0} U_{\sigma}\neq\emptyset.$$


I think, one way to make sure $X$ is a set would be to define it to contain only the $L$-structures $M$ satisfying the satisfiable sets of $L$-sentences. That is, for every satisfiable set $S$ of $L$-sentences let $M_{S}$ be an $L$-structure such that $M\vDash S$. Define $$X=\{M_{S}:S\;\mbox{is a satisf. set of $L$-sentences}\}$$


This question is related, and Noah Scweber provides a very useful answer there as well a here.

$\endgroup$
6
  • 1
    $\begingroup$ This is a very interesting question. I think $X$ would have to be a proper class rather than a set though. Also, just out of curiosity, why did you define sets of the form $\{ M \in X : M \models \sigma \}$ to be the basic open sets rather than the basic closed sets (when choosing which topology associated with a given logic to look at)? $\endgroup$ May 20 at 18:48
  • 1
    $\begingroup$ I think it is more conventional to choose those sets to be basic closed, especially if one might be interested in logics without negation. $X$ is a proper class but in a kind of inessential way, because there are only set-many topologically inequivalent points. To make $X$ into a set one could, for instance, look only at structures of cardinality at most $|L|+\aleph_0$. By Lowenheim-Skolem every point of $X$ is elementarily equivalent (hence topologically indistinguishable from) such a structure. $\endgroup$ May 20 at 19:06
  • $\begingroup$ I don't know much about topology, but I think you can freely choose whether the $U_{\sigma}$ are basic open or basic closed, you're just talking about different topologies in both cases. I was thinking making them basic closed would generate a more interesting topology since $\{ M \models \Sigma \}$ would be the intersection of all the $\{ M \models \sigma \}$, and theories formed by "infinite disjunctions", which seem badly behaved in general, would be neither closed nor open. A proper class is a collection that is "too big" to be a set, like the class of all sets or the class of ordinals. $\endgroup$ May 20 at 19:36
  • $\begingroup$ @GregNisbet. I chose the $U_{\sigma}$ to be basic open and proceeded to show that logical compactness implies $X$ is compact by showing that if there is an open cover of $X$ having no finite subcover we can find (thanks to logical compactness) a structure outside the cover. But now that you say $X$ may be a proper class it may mean there is something subtle and wrong about my argument (and with the reverse implication, for that matter, which it seemed even simpler) $\endgroup$
    – John
    May 20 at 20:12
  • 1
    $\begingroup$ In the context of first-order logic it doesn't matter whether you think of the $U_\sigma$ as being basic open or basic closed, you get the same topology either way (because $X \setminus U_\sigma = U_{\neg\sigma}$, as John pointed out). However, if you are interested in non-classical logics that might not have a negation, then GregNisbet is right that taking the $U_\sigma$ as basic closed sets produces a topology that is more directly useful, because then closed sets are essentially (not-necessarily-complete) theories. $\endgroup$ May 20 at 20:43

3 Answers 3

8
$\begingroup$

I suppose that it depends what you would count as "purely topological". Your spaces are defined in terms of $\models$, so in some sense any topological properties of your spaces are reformulations of properties of $\models$. Here's one proof. I'll work in your space $Y$ (which, you are correct, is homeomorphic to $X/\equiv$).

Let $I$ be any set and $\mathcal{U}$ an ultrafilter on $I$. Let $(M_i)_{i \in I}$ be an $I$-sequence of structures. Using Łoś's theorem you can show that $\lim_{i\to\mathcal{U}}T_{M_i} = Th(\prod_{\mathcal{U}}M_i)$, i.e., ultraproducts compute ultralimits in $Y$. In particular, all ultralimits exist in $Y$. It is a purely topological fact that a space is compact if and only if all ultralimits exist, so $Y$ is compact.

Is the above a "purely topological" proof? I'm not sure. On the one hand, it's phrased in topological terms. On the other hand, it's kind of just a re-dressing of the usual ultraproduct proof of the compactness theorem. I'll leave it to you whether or not this is satisfying.

$\endgroup$
1
  • $\begingroup$ Thank you, good point. In the case for propositional logic the homeomorphism onto $\{0,1\}^{L}$ and Tychonoff's Theorem allow us to "forget" about $\vDash$ in a sense. It is in this regard that I mean -purely topological- $\endgroup$
    – John
    May 20 at 19:36
3
$\begingroup$

I think this (very good!) question really begs some additional work, namely a more careful analysis of exactly what was needed for the topological proof of propositional compactness. The semantics for propositional logic is so closely tied to its syntax that it can be a bit tricky to see the analogues of the relevant issues for first-order logic (see also my comments here), so let me be explicit here:

A propositional language is just a set of atomic propositions, $P$. Given a propositional language $P$, a $P$-valuation is just a function $\nu:P\rightarrow\{0,1\}$ (which we extend to $\mathit{Form}_P$ in the usual way).

Let $\mathcal{X}_P$ be the space of $P$-valuations topologized via formulas as usual. Note that if $P=\bigsqcup_{i\in I}Q_i$ then there is a homeomorphism $\mathcal{X}_P\cong \prod_{i\in I}\mathcal{X}_{Q_i}$. This utterly trivial observation is one of the two key points that drives the topological proof of propositional compactness. The other trivial-but-key point is that the spaces of valuations on single atoms are compact (which is obvious, since they're finite); this gives us the desired compactness of all $\mathcal{X}_P$s via Tychonoff.

Actually there is a third trivial-but-key point, which will come up later - it's a fun exercise to try to guess what it is ahead of time! :P


OK, now on to the first-order setting:

The first trivial-but-key observation is a bit annoying for first-order logic since "gluing" structures is more complicated than "gluing" valuations, but it's not too annoying. For simplicity, let's say we just care about the special case of theories in a countable language which contain the sentence $\exists x_1,...,x_n\bigwedge_{1\le i<j\le n}x_i\not=x_j$ for each $n$ (= have no finite models). In this case we can without issue restrict attention to structures with underlying set $\mathbb{N}$. For a countable first-order language $\Sigma$, let $\mathcal{Y}_\Sigma$ be the space of $\Sigma$-structures with domain $\mathbb{N}$; then as before we get $$\mathcal{Y}_\Sigma\cong\prod_{i\in I}\mathcal{Y}_{\Sigma_i}$$ whenever $\Sigma=\bigsqcup_{i\in I}\Sigma_i$.

Exercise: what goes wrong if we don't assume $\Sigma$ is countable here?

Aaaaaand that's the end of the good news. In order to conclude that $\mathcal{Y}_\Sigma$ is compact for any (countable) $\Sigma$ we need to know that $\mathcal{Y}_{\{R\}}$ is compact for each individual symbol $\Sigma$. In the propositional case this was hard not to know, but in the first-order case this is ... as difficult as the full compactness theorem! The problem is that $\mathcal{Y}_{\{R\}}$ is already extremely complicated for $R$ a single binary relation symbol (for example). Not only are there lots of non-isomorphic countable $\{R\}$-structures, there are lots of inequivalent $\{R\}$-sentences (= distinct basic open sets for $\mathcal{Y}_{\{R\}}$).


If we want to pursue a topological approach, then, we're faced with the following sub-question:

Is there a way to "break $\mathcal{Y}_{\{R\}}$ into a product (or similar) of compact (ideally finite) spaces"?

Very much with loss of generality, let's assume $R=R^1$ is a unary relation symbol for simplicity. This is absolutely drastic - unlike a single binary relation symbol, there's very little we can do with a single unary relation symbol - but it will give us a useful first example to consider.

Good news - in this case there is an obvious decomposition! Each $\mathfrak{M}\in\mathcal{Y}_{\{R^1\}}$ can be identified in a natural way with a tuple $(\mathfrak{M}_i)_{i\in\mathbb{N}}$ of one-element $\{R^1\}$-structures - namely, $\mathfrak{M}_i$ is the substructure of $\mathfrak{M}$ with domain $\{i\}$. This is where the assumption of unarity is crucial: if $R$ were (say) binary, then we'd need to talk about building $\mathfrak{M}$ from "overlapping" pieces, which is just annoying.

ABSOLUTELY HORRIFYING NEWS: the basic open sets do not "line up properly!" For example, regardless of what $\mathfrak{M}$ is, each $\mathfrak{M}_i$ will (boringly) satisfy the $\{R^1\}$-sentence $$\forall x_1,x_2(R^1(x_1)\wedge R^1(x_2)\implies x_1=x_2),$$ but some-but-not-all $\mathfrak{M}$s satisfy that sentence. The culprit here of course is quantification. And this brings us to the above-hinted-at third trivial-but-key point. In propositional logic each valuation is built from its sub-valuations in a "basic-open-set-respecting" way. This was also true for first-order logic ... according to the above, too-coarse-to-be-useful decomposition/reconstruction idea. When we start talking about breaking up even the $\mathcal{Y}_{\{R\}}$s, even in the most boring case we run into trouble.

This, I think, is the key negative point:

Propositional logic, semantically speaking, really does reduce to combining obviously-compact spaces in simple ways, while first-order-logic does not.

Incidentally, this suggests a follow-up exercise: consider the extension of propositional logic by a new nullary connective $\star$, where $\star$ is true in a valuation $\nu$ iff $\nu$'s vocabulary is finite. We know that $\star$ adds no real expressive power, since either the vocabulary is finite or it isn't, but this does break the "basic-open-set-respecting" point. Can you modify the topological proof to smoothly accommodate $\star$?

$\endgroup$
2
  • $\begingroup$ This is an excellent answer! It explains quite clearly the "obstruction" I felt when I worked out the case for propositional logic and moved onto first-order logic. What do you think of the proof via ultrafilters as the possibly most topologically flavored one? $\endgroup$
    – John
    May 23 at 2:18
  • $\begingroup$ @John I think it's probably the best there is, along these criteria. $\endgroup$ May 23 at 3:52
1
$\begingroup$

As far as I can tell, the most topologically flavored method to show that $Y$ is compact is via ultrafilters, as Chris Eagle showed. I will accept his answer as the correct one. However, I will write up an answer as a means of gathering some of the ideas discussed in the comments and edits to the question.

Regarding $X$, it is indeed a proper class, as we are allowing structures of any cardinality. If we topologize by saying the proper classes $U_{\sigma}$ are the basic closed classes then finite unions of arbitrary intersections of such classes topologize $X$ because for any $\sigma,\tau\in S_{L}$ $$\displaystyle U_{\sigma}\cup U_{\tau}=U_{\sigma\vee\tau},$$ and every closed subclass is of the form $$\displaystyle\bigcap_{\sigma\in S} U_{\sigma},$$ for some subset $S$ of $L$-sentences. Now, with this topology the Compactness Theorem implies that $$\displaystyle\bigcap_{\sigma\in S} U_{\sigma}\neq\emptyset,$$ whenever $S\subseteq S_{L}$, and that for every finite subset $S_0$ of $S$ $$\displaystyle\bigcap_{\sigma\in S_0} U_{\sigma}\neq\emptyset.$$ Therefore, using the finite intersection property characterization of compactness $X$ is compact.

Now, how do we make $X$ into a set?

  1. One way, as Chris Eagle points out in the comments is to bound the cardinality of the structures in the definition of $X$. For example, cardinality at most $|L|+\aleph_{0}$.
  2. Another way is to use only satisfiable sets of $L$-sentences. For every satisfiable set $S$ of $L$-sentences let $M_{S}$ be an $L$-structure such that $M_{S}\vDash S$. Then let $$X'=\{M_{S}:S\;\mbox{is a satisfiable set of $L$-sentences}\}.$$

With either definition we obtain a set, and the definition of the $U_{\sigma}$, for $\sigma\in S_{L}$ is unchanged. These spaces are compact and they are also homeomorphic by the Löwenheim–Skolem Theorem. In fact, they are homeomorphic to $X/\negthickspace\equiv$, and that brings us neatly to the topological space $Y$.

As I mentioned, Chris Eagle's answer via ultrafilters and Łoś Ultraproduct Theorem is the most topological in flavor I have seen. Compactness of $Y$ can be proven via the Compactness Theorem or the even stronger Completeness Theorem. But that is precisely what I was trying to avoid. I thought perhaps there was a way to show that $Y$ is homeomorphic to a known compact space (as it is done for the case of propositional logic), or at least to be able to use Alexander's Subbasis Lemma (being ZF-equivalent to the Compactness Theorem), or even Thychonoff's Theorem to show that $Y$ is compact. I do not see how.

On a final note, I will add that we can modify the definition of $Y$ by precisely defining its elements so that a "bare-bones" proof that it is compact can be obtained. It is not very topological, tough. Indeed, let $Y'$ denote the set whose elements are precisely the complete and consistent $L$-theories $T$. Just to be absolutely clear, $T\in Y'$ is a set of $L$-sentences such that

  1. For any $\sigma\in S_{L}$ we have $T\vDash\sigma\Rightarrow \sigma\in T$.
  2. For every $\sigma\in S_{L}$ either $\sigma\in T$ or $\neg\sigma\in T$, but never both. Therefore, if $\sigma\not\in T$, then $\neg\sigma\in T$.

The definition of the basic closed sets $V_{\sigma}$, for $\sigma\in S_{L}$ is unchanged.

Due to the precisely defined nature of its elements, the compactness of $Y'$ can be proven directly with the aid of Zorn's Lemma.

Finally, every element $T_{M}\in Y$ is a complete and consistent theory. But if I am not mistaken, proving that every complete and consistent theory $T\in Y'$ is of the form $T_{M}$ for some $L$-structure $M$ requires the completeness Theorem, if I am not mistaken.

$\endgroup$

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.