5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Certainly $\mathcal{L}_{\infty,\omega}$ is very powerful, but I'm not sure your justification makes sense. (1) You say a Turing Machine $T$ is identified with a sentence $\phi_T$. Is $\phi_T$ the assertion that $T$ halts? What is your sentence expressing? That some Turing Machine which halts (or does not halt, depending on what $H$ is) halts? Remember that many Turing Machines which halt provably halt, and many which do not halt provably do not halt. $\endgroup$
    – Alex Kruckman
    Jul 11, 2014 at 18:22
  • 1
    $\begingroup$ (2) When you say a sentence is undecidable, I assume you mean it's not provable or disprovable. But there's no complete proof system for infinitary logic, so you have to be careful what you mean by notions like this. (3) Note that there are only countably many Turing machines, so the halting set H is countable, so your sentence is already expressible in the much weaker logic $\mathcal{L}_{\omega_1,\omega}$. (4) Finally, we don't even need to step outside of first-order logic to get undecidability! See Gödel. $\endgroup$
    – Alex Kruckman
    Jul 11, 2014 at 18:23
  • $\begingroup$ "$\varphi_T$ identifies a Turing Machine T" means that all models of $\varphi_T$ are isomorphic to T. Does this make sense? Thanks for the hints. $\endgroup$
    – Joachim
    Jul 11, 2014 at 21:58
  • $\begingroup$ That can make sense once you specify an appropriate language for describing Turing machines, but I'm still not sure what you're going for with the big disjunction. I think you should look elsewhere for proof of the power of infinitary logic. For example, the fact that $\mathcal{L}_{\omega_1,\omega}$ can pin down any countable structure up to isomorphism (Scott's isomorphism theorem). $\endgroup$
    – Alex Kruckman
    Jul 11, 2014 at 22:04

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .