In this paper we develop an Ehrenfeucht‐Fraïssé game for. Unlike the standard Ehrenfeucht‐Fraïssé games which are modeled solely after the behavior of quantifiers, this new game also takes into account the behavior of connectives in logic. We prove the adequacy theorem for this game. We also apply the new game to prove complexity results about infinite binary strings.

We study the complexity of isomorphism of classes of metric structures using methods from infinitary continuous logic. For Borel classes of locally compact structures, we prove that if the equivalence relation of isomorphism is potentially $\mathbf {\Sigma }^0_2$, then it is essentially countable. We also provide an equivalent model-theoretic condition that is easy to check in practice. This theorem is a common generalization of a result of Hjorth about pseudo-connected metric spaces and a result of Hjorth–Kechris about discrete structures. As (...) a different application, we also give a new proof of Kechris’s theorem that orbit equivalence relations of actions of Polish locally compact groups are essentially countable. (shrink)

We study the isomorphism relation on Borel classes of locally compact Polish metric structures. We prove that isomorphism on such classes is always classifiable by countable structures (equivalently: Borel reducible to graph isomorphism), which implies, in particular, that isometry of locally compact Polish metric spaces is Borel reducible to graph isomorphism. We show that potentially $\boldsymbol {\Pi }^{0}_{\alpha + 1}$ isomorphism relations are Borel reducible to equality on hereditarily countable sets of rank $\alpha $, $\alpha \geq 2$. We also study (...) approximations of the Hjorth-isomorphism game, and formulate a condition ruling out classifiability by countable structures. (shrink)

We can measure the complexity of a logical formula by counting the number of alternations between existential and universal quantifiers. Suppose that an elementary first-order formula $\varphi $ (in $\mathcal {L}_{\omega,\omega }$ ) is equivalent to a formula of the infinitary language $\mathcal {L}_{\infty,\omega }$ with n alternations of quantifiers. We prove that $\varphi $ is equivalent to a finitary formula with n alternations of quantifiers. Thus using infinitary logic does not allow us to express a finitary formula in a (...) simpler way. (shrink)

In this paper we study the logic $\mathcal{L}^\lambda_{\omega\omega}$, which is first-order logic extended by quantification over functions . We give the syntax of the logic as well as the semantics in Heyting categories with exponentials. Embedding the generic model of a theory into a Grothendieck topos yields completeness of $\mathcal{L}^\lambda_{\omega\omega}$ with respect to models in Grothendieck toposes, which can be sharpened to completeness with respect to Heyting-valued models. The logic $\mathcal{L}^\lambda_{\omega\omega}$ is the strongest for which Heyting-valued completeness is known. Finally, (...) we relate the logic to locally connected geometric morphisms between toposes. (shrink)

We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by these relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a $\boldsymbol {\Sigma }^1_1$ complete equivalence relation. We then investigate the algorithmic properties of this reduction. We obtain that elementary bi-embeddability on the class of computable graphs is $\Sigma ^1_1$ complete with respect (...) to computable reducibility and show that the elementary bi-embeddability and bi-embeddability spectra realized by graphs are related. (shrink)

In this paper we study the logic , which is first-order logic extended by quantification over functions (but not over relations). We give the syntax of the logic as well as the semantics in Heyting categories with exponentials. Embedding the generic model of a theory into a Grothendieck topos yields completeness of with respect to models in Grothendieck toposes, which can be sharpened to completeness with respect to Heyting-valued models. The logic is the strongest for which Heyting-valued completeness is known. (...) Finally, we relate the logic to locally connected geometric morphisms between toposes. (shrink)

In this paper we study the logic $\mathcal{L}^\lambda_{\omega\omega}$, which is first-order logic extended by quantification over functions (but not over relations). We give the syntax of the logic as well as the semantics in Heyting categories with exponentials. Embedding the generic model of a theory into a Grothendieck topos yields completeness of $\mathcal{L}^\lambda_{\omega\omega}$ with respect to models in Grothendieck toposes, which can be sharpened to completeness with respect to Heyting-valued models. The logic $\mathcal{L}^\lambda_{\omega\omega}$ is the strongest for which Heyting-valued completeness (...) is known. Finally, we relate the logic to locally connected geometric morphisms between toposes. (shrink)