1
vote
1answer
108 views

infinitary logic and partial fixed point logic

Is there a property definable in finite-variable infinitary logic $L^{\omega}_{\omega\infty}$ but not definable in partial fixed point logic FO(PFP) ?
0
votes
0answers
22 views

CRAM[t(n) \subseteq IND[t(n)]

In the proof of lemma 5.3 in Immerman's descriptive complexity (CRAM[t(n) \subseteq IND[t(n)]), he mentions a disjunction depending on the value of the processor's program counter at the "directly" ...
5
votes
0answers
85 views

Can the isomorphism relation for countable models become harder when adding finitely many constants?

I am particularly interesting in the case where $T$ is o-minimal, but I would be interested in any theory $T$ (or even an $L_{\omega_1,\omega}$-sentence) which has this property. Context: view the ...
3
votes
2answers
517 views

Measure of progress towards a proof

Can one define some measure of progress towards a proof of a statement? I'm not sure if it's even possible for general first order logic statements so let's restrict ourselves to propositional ...
3
votes
0answers
275 views

To what extent MSO = WS1S, when adding relations?

Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures: $${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} ...