Relatively recursive expansions
Fundamenta Mathematicae (1992)
- Volume: 140, Issue: 2, page 137-155
- ISSN: 0016-2736
Access Full Article
topAbstract
topHow to cite
topAsh, 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- [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
- [A2] C. J. Ash, Labelling systems and r.e. structures, Ann. Pure Appl. Logic 47 (1990), 99-119. Zbl0712.03021
- [AC] C. J. Ash and J. Chisholm, Notions of relatively recursive categoricity, in preparation.
- [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
- [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.
- [C] J. Chisholm, Effective model theory vs. recursive model theory, J. Symbolic Logic 55 (1990), 1168-1191. Zbl0722.03030
- [K] J. F. Knight, Degrees coded in jumps of orderings, ibid. 51 (1986), 1034-1042. Zbl0633.03038
Citations in EuDML Documents
topNotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.