Is infinitary logics $\mathcal{L}_{\infty\omega}$ an abstract logic?

380 Views Asked by At

Infinitary logics $\mathcal{L}_{\infty\omega}$ is an extension of first-order logics such that

  • $\bigvee\Phi \in \mathcal{L}_{\infty\omega}$ if $\Phi$ is a set of $\mathcal{L}_{\infty\omega}$-sentences
  • $\bigwedge\Phi \in \mathcal{L}_{\infty\omega}$ if $\Phi$ is a set of $\mathcal{L}_{\infty\omega}$-sentences

with the obvious semantics of an infinite disjunction or conjunction.

Since other than "set" there is no restriction, infinitary logic is very powerful. Consider, that every Turing Machine $\mathfrak{T}$ is identified by a first-order sentence $\varphi_{\mathfrak T}$.

Then

$$ \bigvee_{\mathfrak T \in H} \varphi_{\mathfrak T},$$

where $H$ is the Halting Problem, is undecidable.

Now I have this definition of abstract logic:

A abstract logic is a pair $(\mathcal{L},\models_{\mathcal{L}})$ consisting of a set of $\mathcal{L}$-sentences for each signature $\tau$ and a mapping which associates a property $\mathcal P_\varphi$ of $\tau$-structures with each $\varphi \in \mathcal{L}[\tau]$.

My question: $\mathcal{L}_{\infty\omega}$ is an abstract logic?

I think yes, since $\mathcal{L}[\tau]$ is a set (right?) and there properties $\mathcal{P}_\varphi$ (not necessarly decidable) for each $\varphi \in \mathcal{L}[\tau]$.

I feel really on shaky ground with this stuff. Is it correct? Any ideas?

1

There are 1 best solutions below

0
On BEST ANSWER

By your definition, $\mathcal{L}_{\infty,\omega}$ is not an abstract logic, because there are a proper class of $\mathcal{L}_{\infty,\omega}$-sentences. Indeed, $\mathcal{L}_{\infty,\omega}$ contains first-order, so there are at least $\aleph_0$-many $\mathcal{L}_{\infty,\omega}$-sentences. Let's say I have a collection of $\kappa$ many $\mathcal{L}_{\infty,\omega}$ sentences, $\{\phi_\alpha\mid \alpha\in\kappa\}$. Then for any subset $X\subseteq \kappa$, I can form the sentence $\bigwedge_{\alpha\in X} \phi_\alpha \land \bigwedge_{\alpha\notin X}\lnot\phi_\alpha$, so I have a collection of $2^\kappa$ many $\mathcal{L}_{\infty,\omega}$-sentences. Iterating and taking unions at limit stages, I can form collections of $\mathcal{L}_{\infty,\omega}$-sentences of sizes going all the way up the beth hierarchy. There are just too many sentences for the class of sentences to be a set.

It's worth noting, however, that not all sources require the collection of sentences to be a set. One of the canonical books on this topic is "Model Theoretic Logics", edited by Barwise and Feferman, and they write "... such that $\mathcal{L}[\tau]$ is a class (the class of $\mathcal{L}$-sentences of vocabulary $\tau$)..." (actually I guess "they" here is Ebbinghaus, who wrote Chapter II).

You can find their definition (Definition 1.1.1), and in fact the whole book on Project Euclid. Wikipedia gives a reference to Chang and Keisler, who also agree that an abstract logic can have a class of sentences.

If we allow a proper class of sentences, then $\mathcal{L}_{\infty,\omega}$ is an abstract logic.