کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662645 1633551 2006 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Effective categoricity of equivalence structures
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Effective categoricity of equivalence structures
چکیده انگلیسی

We investigate effective categoricity of computable equivalence structures A. We show that A is computably categorical if and only if A has only finitely many finite equivalence classes, or A has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence structures are relatively categorical, we further investigate when they are categorical. We also obtain results on the index sets of computable equivalence structures.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 141, Issues 1–2, August 2006, Pages 61-78