On the definition of a logical system

On p261 in §1. Logical Systems in XIII. Lindstrom's Theorems in Ebbinghaus' Mathematical Logic,

1.1 Definition. A logical system $\mathcal{L}$ consists of a function $L$ and a binary relation $\models_\mathcal{L}$. $L$ associates with every symbol set $S$ a set $L(S)$, the set of $S$-sentences of $\mathcal{L}$. (...)

• $L(S)$ is called "the set of $S$-sentences". Does it mean that $L(S)$ only consists of $S$-formulas without free variables? If yes, why can the languages of the first and second order logic systems have $S$-formulas with free variables.

• Do all the logical systems have the same set of structures, i.e. $\cup_S \{S\text{-structure}\}$?

• Is it more accurate to say that a logical system $\mathcal{L}$ consists of $L$, $\cup_S \{S\text{-structure}\}$, and $\models_\mathcal{L}$, even though $\cup_S \{S\text{-structure}\}$ is the same for all the logical systems?

• Is it possible for two logical systems $\mathcal{L_1}$ and $\mathcal{L_2}$ with $L_1 = L_2 $ but $\models_\mathcal{L_1} \neq \models_\mathcal{L_2}$?

Thanks.

Solution 1:

Re: $(1)$, the idea is that we're boiling down the idea of a logical system to a very simple level: its ability to carve out particular classes of structures, namely those of the form $\{\mathcal{M}: \mathcal{M}\models\varphi\}$ for $\varphi$ a sentence in the system. While "natural" logics like FOL or SOL have more structure than this - e.g. they also have notions of formulas with free variables - we "forget" this structure in the above approach; it's additional but unnecessary.

That said, it turns out that we can still talk about definable subsets of structures just using sentences (and so still accomplish everything which is normally done with formulas with free variables)! Specifically, we can think of $S$-formulas as sentences expansions of $S$ by finitely many new constant symbols.

This lets us talk about definable subsets of structures as follows. Looking at FOL for concreteness, suppose $\mathcal{M}$ is an $S$-structure and $\varphi(x)$ is an $S$-formula with free variable $x$. Let $c$ be a constant symbol not in $S$ and consider the FOL sentence $\hat{\varphi}$ gotten by replacing each free instance of $x$ in $\varphi$ by $c$. Then the subset of $\mathcal{M}$ defined by $\varphi$, that is $\varphi^\mathcal{M}$, is exactly the set of $a\in\mathcal{M}$ such that the expansion of $\mathcal{M}$ to $S\cup\{c\}$ gotten by interpreting $c$ as $a$ satisfies $\hat{\varphi}$.

So this "sentences-only" approach doesn't really lose the ability to talk about free variables, it just makes it a bit messier. What is lost is the structure of the syntax: e.g. in a precise sense FOL has computable syntax, but the approach to logical systems above forgets this. For this reason we're often interested in richer notions of "logical system" (see e.g. here); that said, this very bare-bones notion has value in that it lets us prove nontrivial highly general results.

Re: $(2)$, yes. That said, we can consider "generalized logical systems" which have different notions of structure (e.g. maybe we want to consider structures with a topology - see e.g. here, and more generally that whole book is quite interesting).

Re: $(3)$, since that extra information is redundant, your expression isn't more accurate unless we're working in a broader context. That said, it doesn't hurt to include it, and per the above sometimes we'll want to.

Re: $(4)$, certainly. For a simple example, given a logical system $\mathcal{L}=(L,\models_\mathcal{L})$ consider the logical system $$\mathcal{L}'=(L, \{\langle \mathcal{M},\varphi\rangle: \mathcal{M}\not\models_\mathcal{L}\varphi\}).$$ This just negates everything in $\mathcal{L}$. Of course the two logics are equivalent in an appropriate sense.

A more natural example, which is actually important, is second-order logic with the standard semantics vs. second-order logic with the Henkin semantics: they have the same syntax but their satisfaction relations are extremely different (e.g. the latter is compact but the former isn't).

Ebbinghaus/Flum/Thomas also gives a pathological example later on, of a sort of "twisted" FOL, which has the same syntax as FOL and has the compactness and downwards Lowenheim-Skolem properties but is incomparable with FOL. I don't recall its precise definition, though.