5
$\begingroup$

Throughout, all structures are finite.

Say that a class of finite structures $\mathbb{K}$ is $\mathsf{FOL}_\varepsilon^\text{inv}$-elementary iff it is the class of finite models of a sentence in the expansion of first-order logic by Hilbert's $\varepsilon$-operator which – on finite structures – do not depend on the choice of $\varepsilon$-operator used.

Separately, for $\varphi$ a first-order sentence in a language $\Sigma$, say that a class of structures $\mathbb{K}$ in a language $\Pi$ (for simplicity disjoint from $\Sigma$) is $\mathsf{FOL}_\varphi^\text{inv}$-elementary iff there is some $\Sigma\sqcup\Pi$-sentence $\theta$ such that the following are equivalent:

  • $\mathcal{M}\in\mathbb{K}$.

  • $\mathcal{M}$ has some expansion satisfying $\theta\wedge\varphi$.

  • Every expansion of $\mathcal{M}$ satisfying $\varphi$ also satisfies $\theta$.

Note that a priori no $\mathsf{FOL}_\varphi^\text{inv}$-elementarity notion need coincide exactly with $\mathsf{FOL}_\varepsilon^\text{inv}$-elementarity, since the $\varepsilon$-operator is fundamentally a second-order object. For instance, the question of whether $\mathsf{FOL}_\varepsilon^\text{inv}$ coincides with $\mathsf{FOL}_\lambda^\text{inv}$, where $\lambda$ says that $<$ is a linear order of the domain, is stated as an open problem in Otto's Epsilon logic is more expressive tha first-order logic over finite structures (and my understanding is that this is still open).

My question is whether any first-order sentence is known to capture $\varepsilon$:

Is there some $\varphi$ such that the $\mathsf{FOL}_\varphi^\text{inv}$-elementary classes are exactly the $\mathsf{FOL}_\varepsilon^\text{inv}$-elementary classes?

$\endgroup$
2
  • $\begingroup$ If the truth of the sentence doesn't depend on the $\varepsilon$ operator that is used, then can't we omit $\varepsilon$ entirely by using universal quantifiers? $\endgroup$ Commented Apr 24 at 12:20
  • 2
    $\begingroup$ @JoelDavidHamkins Interestingly, no - see the linked paper! Expressions like "$\epsilon\varphi=\epsilon\psi$" add a layer of complexity, and it turns out that (as long as our structure is finite) there are unavoidable "coincidences" that encode meaningful information. This is similar to the fact that (again, over finite structures) there are "FOL-with-any-ordering" sentences which aren't FOL-expressible. $\endgroup$ Commented Apr 24 at 16:36

0

You must log in to answer this question.