5
$\begingroup$

I'm trying to put together a general picture of the expressiveness of some logics: First-Order Logics, Fixed-Point Logics, (Finite Variable) Infinitary Logics and the respected versions with Counting. (Source)

$\mathcal{L}^k_{\infty\omega}$ is infinitary logic with $k$ distinct variables and

$$\mathcal{L}^\omega_{\infty\omega} := \bigcup_{k \in \omega} \mathcal{L}^k_{\infty\omega}$$

is finite variable infinitary logic. (Analog for Counting)

This is in the context of Finite Model Theory so in general all structures are finite.

We say $\varphi$ and $\varphi'$ are equivalent if for every structure $\mathcal A$

$$ \mathcal A \models_\mathcal L \varphi \Leftrightarrow \mathcal A > \models_{\mathcal {L'}} \varphi'.$$

If for every $\mathcal L$-sentence there is a equivalent $\mathcal L'$-sentence we write

$$ \mathcal L \leqq \mathcal L'.$$

Expressivness

Most of the relations are relatively straight-forward. $\mathcal{L}^\omega_{\infty\omega}$ cannot express that a graph has an even number of nodes. Hence, both $\mathcal{L}_{\infty\omega}$ and $\mathcal{C}^\omega_{\infty\omega}$ are strictly stronger because they can express any predicate over finite structures.

A though one is $\mathcal{L}_{\infty\omega} \equiv \mathcal{C}_{\infty\omega}$. I think this is correct since $\mathcal{L}_{\infty\omega}$ can express every predicate, thus adding counting should not make it more powerful. This it far from a proof but at most an intuition. Any ideas?

The other one I don't know is $\mathcal{C}^\omega_{\infty\omega} \lneqq \mathcal{C}_{\infty\omega}$. Again my intuition is that it is correct: How can we express any predicate with finite variables even with Counting? Any ideas on that? Maybe an example which is not expressible in $\mathcal{C}^\omega_{\infty\omega}$?

$\endgroup$
6
$\begingroup$

There is a famous example of Cai, Fürer and Immerman, which shows that the $\mathcal{C}_{\infty\omega}^k$-hierarchy is strict and in particular that $\mathcal{C}_{\infty\omega}^\omega$ cannot express every query on finite structures. The paper is quite famous because it disproved a conjecture that IFP+C captures PTIME. Your proof that $\mathcal{L}_{\infty\omega}\equiv\mathcal{C}_{\infty\omega}$ is correct.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.