Counting the back-and-forth types
type: Item
instance of: scholarly article
title: Counting the back-and-forth types
zbMATH Open document ID: 1268.03044
author: Antonio Montalbán
publication date: 2012-09-05T00:00:00Z
Mathematics Subject Classification ID: 03C57
zbMATH DE Number: 6078053
zbMATH Keywords: computable structures
zbMATH Keywords: back-and-forth
zbMATH Keywords: jump of structure
zbMATH Keywords: Turing degree
zbMATH Keywords: intrinsical relations
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2000110189
DOI: 10.1093/LOGCOM/EXQ048
published in: Journal of Logic and Computation
review text: The paper is devoted to the study of the interactions between the structural properties of a structure and computational properties of its presentations. Given a class of structures \({\mathcal K}\) and an integer \(n\), the author studies the dichotomy between there being countably many \(n\)-back-and-forth equivalence classes and there being continuum many. In the former case it is shown that there is a countable set of infinitary \(\Pi_n\) relations that captures all of the \(\Pi_n\) information about the structure in \({\mathcal K}\). In the latter case it is shown that, relative to some oracle, every set can be weakly coded in the \((n-1)\)st jump of a structure in \({\mathcal K}\).
reviewed by: M. M. Arslanov
description: scientific article; zbMATH DE number 6078053