What is the most expressive logic?

609 Views Asked by At

What is the most expressive logic studied in the literature (in terms of expressing properties about a structure in the sense of model theory)?

Many people talk about second-order logic, but third-order logic somehow does not play such a huge role. (Maybe one reason is that second-order logic can simulate higher-order logic in some sense.) Can one also define $\omega$th-order logic? Can one define $\alpha$th-order logic for each ordinal $\alpha$?

Here are things a very expressive logic would be useful for:

  1. Sometimes, people say "isormorphic structures have the same structural properties". But if one actually tries to formally write this down, one realizes that it is not that easy. The problem is with the notion of "property". Of course, one can take first-order logic and say "isomorphic structures satisfy the same first-order sentences". Okay, but many properties mathematicians are interested in go far beyond first-order logic. One can then say, "alright, then let's take second-order (or third-order, four-order) logic", but then one also has the problem that there is an even stronger logic. Probably there is always a stronger logic – but is there one that suffices for all practical purposes?

  2. People talk about topological properties. Often they want to show that a property is topological. If there is a very expressive logic (that is capable of expressing many topological properties that occur in practice), one often could do this by just showing how to write down the property in the very expressive logic. (Note that one needs third-order logic to formulate the axioms of a topological space.) Is there, for example, a natural logic expressive enough to be able to express the topological property "... is metrizable"?

1

There are 1 best solutions below

7
On BEST ANSWER

The slogan "isomorphic structures have the same structural properties" (or more precisely, "isomorphic structures satisfy the same sentences") is perfectly true. I would even say that to call something a "logic", this is a crucial requirement. What you seem to be concerned with is the converse to this slogan: is there a logic such that if two structures satisfy the same sentences, then they must be isomorphic?

To address this question, let's try to clarify what a "logic" is. There are many ways to do this, but I'll concentrate on one option that seems relevant to your question. A logic $L$ for reasoning about structures in the sense of model theory (as in your question) will include a class $\mathcal{S}(L)$ of sentences, and every sentence $\varphi\in \mathcal{S}(L)$ will be true in some isomorphism-closed class $[\varphi]$ of models. Of course, a logic will also usually include formulas with free variables, which may be true or false of tuples from models, but let's just concentrate on the sentences, for simplicity.

Now we could take a turn for the abstract and define a "logic" to be a class $\mathcal{S}$ of "sentences" and a binary relation $\models$ on $(\text{Str}_L\times \mathcal{S})$, where $\text{Str}_L$ is the class of $L$-structures, such that for every $\varphi\in \mathcal{S}$, the class $[\varphi] = \{M\in \text{Str}_L\mid M\models \varphi\}$ is isomorphism-closed. Then we say a logic $(\mathcal{S},\models)$ is stronger than a logic $(\mathcal{S}',\models')$ if for every $\varphi'\in \mathcal{S}'$, there is some $\varphi\in \mathcal{S}$ such that $[\varphi'] = [\varphi]$. This is (more or less) the point of view of abstract model theory.

From this point of view, there is an obvious strongest logic: The logic which has a "sentence" for every isomorphism-closed class of structures. Then for any structure $M$, there is a sentence $\varphi_M$ such that $M'\models \varphi_M\iff M'\cong M$, so if two structures satisfy the same sentences, then they're isomorphic. Of course, this is somewhat unsatisfying, since this logic has a proper class of "sentences"! In every language $L$, there is a proper class of $L$-structures up to isomorphism, and hence a proper class of isomorphism-closed classes of $L$-structures. So we can't expect to have any reasonable syntax for this logic.

To deal with this problem, we could make the further restriction that the class $\mathcal{S}$ of sentences must be a set. But then, as you suggested in the question, there will always be a stronger logic: For any logic $(\mathcal{S}, \models)$, there will be some pair of non-isomorphic models $M\not\cong M'$ which satisfy all the same sentences in $\mathcal{S}$. And we can add to $\mathcal{S}$ a new sentence which distinguishes $M$ and $M'$ (e.g. a sentence $\varphi_M$ such that $N\models \varphi_M\iff N\cong M$).

The point of all this is that the converse of the slogan is too much to hope for in general: There's no concrete logic such that if two structures satisfy the same sentences of that logic, then they are isomorphic. But if you're interested just in some restricted class of models, then there are indeed logics which "suffice for all practical purposes". For example, if two finite structures satisfy all the same first-order ($L_{\omega\omega}$) sentences, then they are isomorphic. And if two countable structures satisfy all the same sentences of the infinitary logic $L_{\omega_1\omega}$, then they are isomorphic (warning: this pattern doesn't continue to higher cardinalities, i.e. it's not true in general that if two structures of size $<\kappa$ satisfy the same sentences of $L_{\kappa\omega}$, then they're isomorphic).

For more information about the zoo of logics, abstract and otherwise, I recommend the book Model-theoretic logics, edited by Barwise and Feferman. It even has a section (Part E) on logics for topology and analysis, which is relevant to the second part of your question (note that topological spaces are not structures in the sense of classical model theory).