Relatively recursive expansions

C. Ash; J. Knight

Fundamenta Mathematicae (1992)

  • Volume: 140, Issue: 2, page 137-155
  • ISSN: 0016-2736

Abstract

top
In this paper, we consider the following basic question. Let A be an L-structure and let ψ be an infinitary sentence in the language L∪R, where R is a new relation symbol. When is it the case that for every B ≅ A, there is a relation R such that (B,R) ⊨ ψ and R ≤ T D ( B ) ? We succeed in giving necessary and sufficient conditions in the case where ψ is a “recursive” infinitary Π 2 sentence. (A recursive infinitary formula is an infinitary formula with recursive disjunctions and conjunctions.) We consider also some variants of the basic question, in which R is r.e., Δ α 0 , or Σ α instead of recursive relative to D(B).

How to cite

top

Ash, C., and Knight, J.. "Relatively recursive expansions." Fundamenta Mathematicae 140.2 (1992): 137-155. <http://eudml.org/doc/211934>.

@article{Ash1992,
abstract = {In this paper, we consider the following basic question. Let A be an L-structure and let ψ be an infinitary sentence in the language L∪R, where R is a new relation symbol. When is it the case that for every B ≅ A, there is a relation R such that (B,R) ⊨ ψ and $R ≤_T D(B)$? We succeed in giving necessary and sufficient conditions in the case where ψ is a “recursive” infinitary $Π_2$ sentence. (A recursive infinitary formula is an infinitary formula with recursive disjunctions and conjunctions.) We consider also some variants of the basic question, in which R is r.e., $Δ_α^0$, or $Σ_α$ instead of recursive relative to D(B).},
author = {Ash, C., Knight, J.},
journal = {Fundamenta Mathematicae},
keywords = {recursive structure; additional relation symbol; infinitary sentence; recursive infinitary formula},
language = {eng},
number = {2},
pages = {137-155},
title = {Relatively recursive expansions},
url = {http://eudml.org/doc/211934},
volume = {140},
year = {1992},
}

TY - JOUR
AU - Ash, C.
AU - Knight, J.
TI - Relatively recursive expansions
JO - Fundamenta Mathematicae
PY - 1992
VL - 140
IS - 2
SP - 137
EP - 155
AB - In this paper, we consider the following basic question. Let A be an L-structure and let ψ be an infinitary sentence in the language L∪R, where R is a new relation symbol. When is it the case that for every B ≅ A, there is a relation R such that (B,R) ⊨ ψ and $R ≤_T D(B)$? We succeed in giving necessary and sufficient conditions in the case where ψ is a “recursive” infinitary $Π_2$ sentence. (A recursive infinitary formula is an infinitary formula with recursive disjunctions and conjunctions.) We consider also some variants of the basic question, in which R is r.e., $Δ_α^0$, or $Σ_α$ instead of recursive relative to D(B).
LA - eng
KW - recursive structure; additional relation symbol; infinitary sentence; recursive infinitary formula
UR - http://eudml.org/doc/211934
ER -

References

top
  1. [A1] C. J. Ash, Recursive labelling systems and stability of recursive structures in hyperarithmetic degrees, Trans. Amer. Math. Soc. 298 (1986), 497-514; Correction, ibid. 310 (1988), 851. Zbl0631.03017
  2. [A2] C. J. Ash, Labelling systems and r.e. structures, Ann. Pure Appl. Logic 47 (1990), 99-119. Zbl0712.03021
  3. [AC] C. J. Ash and J. Chisholm, Notions of relatively recursive categoricity, in preparation. 
  4. [AKMS] C. J. Ash, J. F. Knight, M. Manasse and T. Slaman, Generic copies of countable structures, Ann. Pure Appl. Logic 42 (1989), 195-205. Zbl0678.03012
  5. [AN] C. J. Ash and A. Nerode, Intrinsically recursive relations, in: Aspects of Effective Algebra, J. N. Crossley (ed.), U.D.A. Book Co., Yarra Glen, Australia, 1981, 26-41. 
  6. [C] J. Chisholm, Effective model theory vs. recursive model theory, J. Symbolic Logic 55 (1990), 1168-1191. Zbl0722.03030
  7. [K] J. F. Knight, Degrees coded in jumps of orderings, ibid. 51 (1986), 1034-1042. Zbl0633.03038

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.