8
$\begingroup$

Below, everything is first-order.

Say that a sentence $\varphi$ is strategically preserved iff player 2 has a winning strategy in the following game:

  • Players 1 and 2 alternately build a sequence of structures $(\mathfrak{A}_i)_{i\in\omega}$, with each being an induced substructure of the next and each satisfying $\varphi$.

  • Player $2$ wins iff the union structure $\mathfrak{A}_\infty:=\bigcup_{i\in\omega}\mathfrak{A}_i$ satisfies $\varphi$.

Looking at arbitrary chains of models yields a simpler picture: the sentences preserved under arbitrary chains are exactly those equivalent to a $\forall^*\exists^*$-sentence (see e.g. Theorem 3.2.3 of Chang/Keisler). However, the above notion is looser. For example, the sentence $$\exists x\forall y\exists z[xRz\wedge zRy]$$ is strategically preserved but is not preserved under arbitrary chains.

My main question is simply:

Which sentences (up to semantic equivalence) are strategically preserved?

Since this might not have a simple answer, here's a broader question which may be more attackable:

Is there some $n$ such that every strategically preserved sentence is equivalent to a sentence with $n$ quantifier alternations?

Improve this question
$\endgroup$
8
  • $\begingroup$ Pretty sure the second question has a negative answer: you can just alter your example to $\forall y_0 \forall y_1 \exists x_1 \forall y_2 \exists x_2 \cdots \forall y_n \exists x_n \, [(\bigvee_{i=0}^{n-1} y_iRx_{i+1}) \vee (\bigvee_{j=1}^n x_iRy_i)]$. (Edit: Thinking about this more, I’m actually not sure now whether this can be simplified to a lower quantifier complexity.) $\endgroup$
    – David Gao
    Commented Jun 18 at 6:46
  • 1
    $\begingroup$ It seems that the conjunction of two strategically preserved sentences need not be strategically preserved, is that right? That is different from all the classical preservation properties I've heard of, e.g., the conjunction of two positive sentences is positive, the same for universal sentences, Horn sentences, etc. $\endgroup$
    – bof
    Commented Jun 18 at 8:08
  • 2
    $\begingroup$ The sentence $$[\forall xRxx\lor\forall x\neg Rxx]\land\exists x\forall y[y\ne x\land Ryy\to Rxy\land\neg Ryx]$$ is not ("strongly") strategically preserved but it is "weakly" strategically preserved; the player who wants it to hold in the union wins iff he gets to move first. $\endgroup$
    – bof
    Commented Jun 18 at 9:21
  • 2
    $\begingroup$ Have you considered the variants where the structures $\mathfrak A_i$ are not required to satisfy $\varphi$, or where only those played by 2 have to satisfy $\varphi$? Maybe those are more natural and/or more tractable than the one you asked about? $\endgroup$
    – bof
    Commented Jun 18 at 10:10
  • $\begingroup$ @bof The second variant seems interesting. Seems all the examples as of now for the second variant are of the form where $\varphi$ is weaker than some universal-existential formula $\psi$ satisfying the condition that models of $\psi$ are embedding-universal. (That is a sufficient condition, at the very least.) $\endgroup$
    – David Gao
    Commented Jun 18 at 21:07

0

Reset to default

Browse other questions tagged or ask your own question.