Scott sentences for equivalence structures

DOI10.1007/S00153-019-00701-XMaRDI QIDQ2309506zbMATH OpenOpenAlexFDO

Authors Sara B. Quinn

Publication date 1 April 2020

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-019-00701-x

zbMATH Keywords

equivalence structuresindex setsScott sentences

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Review text

The author gives an example of an equivalence structure for which the index set is \(m\)-complete \(\Pi_3^0\) but for which there is no computable \(\Pi_3\) Scott sentence. It follows from the author's result that if a computable equivalence structure with infinitely many infinite equivalence classes and with arbirarily large finite classes satisfies a \(\Sigma_4\) sentence \(\varphi\) then it has a substructure with finitely many infinite classes satisfying the same sentence \(\varphi\).

Recommendations

• Complexity of Scott sentences
• Scott sentences in uncountable structures
• Index sets and Scott sentences
• scientific article; zbMATH DE number 3928997
• Structurable equivalence relations
• scientific article; zbMATH DE number 3852453
• A remark on equivalent Rosser sentences
• Hanf number for Scott sentences of computable structures
• On optimal Scott sentences of finitely generated algebraic structures
• scientific article; zbMATH DE number 1231455

Cites work

• An interpolation theorem for denumerably long formulas
• Computable models of theories with few models
• Computable structures and the hyperarithmetical hierarchy
• Describing free groups
• Describing free groups. II: \(\Pi ^{0}_{4}\) hardness and no \(\Sigma _{2}^{0}\) basis
• Effective categoricity of equivalence structures
• scientific article; zbMATH DE number 3715794 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 2047478 (Why is no real title available?)
• scientific article; zbMATH DE number 3206304 (Why is no real title available?)
• scientific article; zbMATH DE number 3266609 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Index sets and Scott sentences
• Index sets of computable structures
• Invariant sets in topology and logic
• Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers
• Scott sentences for certain groups
• The effective Borel hierarchy
• The isomorphism problem for computable Abelian _p-groups of bounded length

Cited in

(5)

• Generalization of Shapiro's theorem to higher arities and noninjective notations
• Describing groups
• Index sets of computable structures
• Index sets and Scott sentences
• Complexity of Scott sentences

This page was built for publication: Scott sentences for equivalence structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2309506)