Complexity of Scott sentences

DOI10.4064/FM865-6-2020MaRDI QIDQ5146417zbMATH OpenOpenAlexFDO

Authors Rachael Alvir, Charles McCoy Csc, J. F. Knight

Publication date 25 January 2021

Published in Fundamenta Mathematicae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.02715

zbMATH Keywords

Borel hierarchycomputable structure theoryfinitely generated groupsinfinitary logicScott sentence

Mathematics Subject Classification ID

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

Abstract: We give effective versions of some results on Scott sentences. We show that if $mathcalA$ has a computable $P{i}_{a}lpha$ Scott sentence, then the orbits of all tuples are defined by formulas that are computable $$ for some $$. (This is an effective version of a result of Montalb'{a}n.) We show that if a countable structure $mathcalA$ has a computable $Sigm{a}_{a}lpha$ Scott sentence and one that is computable $P{i}_{a}lpha$, then it has one that is computable $d$-$$ for some $$. (This is an effective version of a result of A. Miller.) We also give an effective version of a result of D. Miller. Using the non-effective results of Montalb'{a}n and A. Miller, we show that a finitely generated group has a $d$-$Sigm{a}_2$ Scott sentence iff the orbit of some (or every) generating tuple is defined by a $P{i}_1$ formula. Using our effective results, we show that for a computable finitely generated group, there is a computable $d$-$Sigm{a}_2$ Scott sentence iff the orbit of some (every) generating tuple is defined by a computable $P{i}_1$ formula.

Recommendations

• THE COMPLEXITY OF SCOTT SENTENCES OF SCATTERED LINEAR ORDERS
• Sentence and word complexity
• Scott sentences for equivalence structures
• Scott sentences in uncountable structures
• Syntactic complexity of scattered context grammars
• Borel complexity and potential canonical Scott sentences
• Complexity of Sentences over Number Rings
• Index sets and Scott sentences
• Sentences over integral domains and their computational complexities

Cites work

• A robuster Scott rank
• Barwise: Infinitary Logic and Admissible Sets
• Computable enumerations of families of general recursive functions
• Computable structures and the hyperarithmetical hierarchy
• Describing free groups
• Describing groups
• scientific article; zbMATH DE number 3266609 (Why is no real title available?)
• Lectures on Infinitary Model Theory
• Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers
• On optimal Scott sentences of finitely generated algebraic structures
• On the Borel classification of the isomorphism class of a countable model
• Scott sentences for certain groups
• The effective Borel hierarchy
• The Invariant ∏ 0 α Separation Principle

Cited in

(11)

• Scott sentences for certain groups
• Finitely generated groups are universal among finitely generated structures
• Scott sentences for equivalence structures
• Computable Scott sentences for quasi-Hopfian finitely presented structures
• Describing groups
• On optimal Scott sentences of finitely generated algebraic structures
• An introduction to the Scott complexity of countable structures and a survey of recent results
• THE COMPLEXITY OF SCOTT SENTENCES OF SCATTERED LINEAR ORDERS
• Scott sentence complexities of linear orderings
• Defining algorithmically presented structures in first order logic
• Optimal syntactic definitions of back-and-forth types

This page was built for publication: Complexity of Scott sentences

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