Ash C.J., Knight J., Sevenster A. (Ed) — Computable Structures and the Hyperarithmetical Hierarchy :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Ash C.J., Knight J., Sevenster A. (Ed) — Computable Structures and the Hyperarithmetical Hierarchy

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Computable Structures and the Hyperarithmetical Hierarchy

Авторы: Ash C.J., Knight J., Sevenster A. (Ed)

Аннотация:

This book describes a program of research in computable structure theory. The goal is to find definability conditions corresponding to bounds on complexity which persist under isomorphism. The results apply to familiar kinds of structures (groups, fields, vector spaces, linear orderings Boolean algebras, Abelian p-groups, models of arithmetic). There are many interesting results already, but there are also many natural questions still to be answered. The book is self-contained in that it includes necessary background material from recursion theory (ordinal notations, the hyperarithmetical hierarchy) and model theory (infinitary formulas, consistency properties).

Язык:

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Издание: 1st edition

Год издания: 2000

Количество страниц: 366

Добавлена в каталог: 13.05.2008

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

      8 19 80 81
$I(\mathcal{A})$       131 150 247 250 282 284 316 317
$I(\omega_1^{CK}(1+\eta))$       250
      151
$L_{\omega_1\omega}$       vi 89 90 93—96 98 101 102 119 121
$L_{\omega_1\omega}$ , admissible fragment of      123
$P_{\omega_1}$       89 102 103
      15
$\alpha$ -atom      91 92 109 272 273 316 317
$\alpha$ -c.e.      86 87 167 189 191 192
$\alpha$ -c.e., relative to      87 168
$\alpha$ -computable      87
$\alpha$ -free      191 254—262 264—273
$\alpha$ -friendly      241—243 245—247 250—252 254 255 258—260 264 265 267 269 279 283
$\alpha$ -system      227 228 230 231 236 251 261—263 265 270 271 279 280
$\Delta_1^1$       71 77 79—83 121 123—127 130 132—134
$\Delta_1^1$ index      79
$\Delta_n^0$       22 23 25—28 71 74 215 221—223 306
$\Delta_n^0$ , canonical complete oracle      28
$\Delta_n^0$ , partial      28
$\Delta_n^1$       76 77
$\Delta_n^{\alpha}$       74 75 85 111 133—135 227—230 253 255 257—259 262 263 265—267 269 270 272 273 279 280 284 288
$\Delta_n^{\alpha}$ , canonical complete oracle      75 113
$\Delta_n^{\alpha}(X)$       85
$\Delta_n^{\alpha}(X)$ , canonical complete oracle      85
$\equiv_\Upsilon$       16
$\Gamma$ -structure      111 112 209
$\leq_T$       16
$\mathcal{E}$       55 62 135 136
$\mathcal{E}$ , automorphisms of      135
$\mathcal{E}*$ ,      55
$\mathcal{N}$ ,      51 52 54 90 108 136 178 242 291 297 318—320
$\mathcal{S}\mathcal{S}(\mathcal{A})$       293—297 307 308
$\omega$ -c.e., second meaning      87
$\omega$ -system      302
$\omega_1^{CK}$       62 65 129 130 248 249
$\Pi_1^1$       71 79 121 123—130 132—134
$\Pi_1^1$ index      79
$\Pi_n^0$       22—28 52 55 71 74 75
$\Pi_n^1$       76 77
$\Pi_{\alpha}^0$       74 109 111
$\Pi_{\alpha}^0(X)$       85
$\sigma(\mathcal{F})$       250 251 282 283 315
$\Sigma_1^1$       71 79
$\Sigma_1^1$ index      79
$\Sigma_n^0$       22—28 52 55 71 74 75
$\Sigma_n^1$       76 77
$\Sigma_{\alpha}^0$       v 74 75 87 109 111 115 116 118 126 133 134 253 255 257 258 288
$\Sigma_{\alpha}^0$ , relative to      v
$\Sigma_{\alpha}^0(X)$       85
$\varphi_e$       5
$\varphi_e(n)\downarrow$       6
$\varphi_e(n)\uparrow$       6
$\varphi_e^X$       15
$\varphi_e^X(n)\downarrow$       15
$\varphi_e^X(n)\uparrow$       15
$\varphi_{e,r}(n)\downarrow$       6
$\varphi_{e,r}(n)\uparrow$       6
$\varphi_{e,r}^{\tau}(n)\downarrow$       15
$\varphi_{e,r}^{\tau}(n)\uparrow$       15
2-free      189 190
2-system      216
3-system      218 219
Abelian group, language of      36
Abelian p-group      92 109 132 137 139—142 252 311 317
Abelian p-group, length of      132 139 141 317
Abelian p-group, reduced      92 132 168 317
Abramson      309
Addition of ordinals      59 60 67
Admissible set      vi 121 123
Alegria      viii
Algebra      37 210
Algebra of sets      316
Algebra, linear ordering as      37
Algebraically closed field      187 312
Alternating sequence      214
Alternating tree      214 215 221 227 231
Analytical      75 76
Analytical hierarchy      71 75 76 78
Arana      viii
Arithmetic      23
Arithmetic, language of      36
Arithmetic, model of      vii 37 311 318
Arithmetic, Presburger      56
Arithmetic, standard model of      51—53 90 108 136 137 242 291 318
Arithmetical      21—23 26 51 52 71 75—77 80 292 296
Arithmetical hierarchy      21—28 52 71 75 78
Arithmetical, function      28
Arithmetical, partial function      28
Arity      34 49
Ash      vi viii 123 159 174 176 181 182 187 198 213 214 239 252
Ash — Nerode Theorem      183
ASSIGNMENT      37
Atom in Boolean algebra      151 152 273 316
Atomic diagram      42
Atomic model      48 201
Automorphism      40 45 47 54 126 131 135 136 159 161 171 198 199 242
Back-and-forth property      41 47 96 98 126 152
Back-and-forth relation      236 239 244 245 247 250—252 263 279
Back-and-forth relation, derived      251
Back-and-forth relation, standard      239—242 252 254 263 266 270
Back-and-forth relation, stronger      250 251
Barker      159 213 252 253
Barwise      vi 121 123
Benedict      178
Bonnet      315
Boolean algebra      vii 37 91 131 150 209 246 247 250 281 282 289 311 315 316
Boolean algebra, atomic      281 316
Boolean algebra, atomless      150 152 316
Boolean algebra, computably categorical      208
Boolean algebra, language of      36
Boolean algebra, superatomic      vii 132 239 247 263 272 316
Boone      55
Borel set      103
Brouwer      82
c.e.      5 8—12 18
c.e. index      12 18
c.e. relative to      15 17
c.e., relative to      17
Canonical enumeration of Scott set      294 307 308
Canonical index for finite set      8
Cantor      41 60
Cantor Normal Form      60 68 69 91 94 132 245—247 268 317
Cardinal sum of structures      204
Categorical, $\Delta^0_{\alpha}$       239 263 269 272 273
Categorical, computably      197—199 201 202 205 206 208 209 239 263 269
Categorical, relatively $\Delta^0_{\alpha}$       175 269
Categorical, relatively computably      177 197—199 206
Chang      312
Characteristic function      3
Chisholm      160
Cholak      135 206
Chong      214
Church      4 62
Church’s thesis      4—6 15
Church’s Thesis, proof by      5 6
Closure properties of class of $\alpha$ -friendly orderings      252
co- $\alpha$ -c.e.      87
co-c.e.      9 23 87
Code for computation      8
Code for finite sequence      1
Code for finite set      8
Code for formula      49
Code for pair      7
Code for tuple      8
Coherent family of runs      234 235
Commutative sum      60 247
Compactness Theorem      44 45 121
Compactness Theorem, Barwise — Kreisel      vi 121 123 133 135
Complete c.e. set      18

Complete for a class      18
Complete forcing sequence, or c.f.s.      163
Complete type      155
Complete, $\Delta^0_n$ set      27
Complete, $\Pi_1^1$ set, O as      83
Complete, $\Sigma_n^0$ set      27
Completeness theorem      44
Completeness, expressive      159
Completions      50
Complexity of an infinitary formula      94
Complexity of infinitary formula      93
Computable      5 186
Computable $\Pi_{\alpha}$ formula      vi 105 112
Computable $\Sigma_{\alpha}$ , formula      vi 105 112 254
Computable dimension      176 205 206 208
Computable dimension, relative      176
Computable infinitary formula      vi 105 107—111 115—118 121—123 126—129 133 136
Computable infinitary formula, index for      107
Computable infinitary formula, propositional      112 113 117
Computable ordinal      64 142
Computable relation on numbers and functions      75
Computable relative to      15—18
Computable relative to a set      17
Computable relative to a total function      17
Computable relative to a tuple of relations      17
Computable structure      v—vii 51 52
Computable, function      2
Computable, function, partial      2 4
Computable, function, total      2 4
Computable, relation      4
Computably enumerable      5
Computably enumerable, alternate definitions      10
Congruence relation      41 43 287
Conjunction, empty, truth value of      90
Connectives, infinitary      89
Consequence      128
Consistency criterion      43
Consistency criterion for computable infinitary sentence      122
Consistency criterion for set of finitary sentences      121
Consistency criterion for set of infinitary sentences      121
Consistency of a sentence or set of sentences      39
Consistency Property      95
Consistency, criterion      42
Constructive ordinal      64
Constructivization      vii
Constructivization, strong      viii
Continuum Hypothesis      294
Crossley      viii
d-c.e.      v 86 167 189 190
d-c.e. relative to      v
Davey      169 181 192 193 259
Davis      320
Decidable      186
Decidable structure      51 137 155 201
Decides      162
Definability of Forcing Lemma      164
Definability of satisfaction      320
Definable element      51
Definable relation      51
Defining family      101 203
Defining family, formally $\Sigma_{\alpha}^0$       177 179 264 265 268
Defining family, formally c.e.      174 186 197 198 203 205 210
Denotation of term      37
Dense set of forcing conditions      163
Detlefsen      309
Diagram, atomic      vii 39 51
Diagram, complete      vii 39 51
Diagram, open      39
DIMENSION      311
Disjunction, empty, truth value of      90
Division algorithm      53 60
Downey      143 144 147 150 151
Dzgoev      207 208
Effective enumeration of Scott set      294 308
Effective enumeration of Scott set, complexity of      294
Effectiveness condition      184
Effectiveness condition for Ash — Nerode Theorem      183
Elementary embedding      47
Elementary equivalence      38
Elementary extension      38
Elementary substructure      38
Elimination of quantifiers      185 186 312 313
Elimination of quantifiers for vector spaces      311
Embedding theorem      151
Enumeration      152 155 295
Enumeration function      215 225 227
Enumeration function, standard      240 254 263 270
Enumeration reducible      18 19 166 170 178 308
Enumeration relation      24 78 87
Enumeration relation, $\Pi_1^1$       79
Enumeration relation, $\Sigma_1^1$       79
Enumeration theorem      24
Enumeration, of a family of sets      205
Enumeration, univalent      205
Equality      34
Equivalence relation      41 317
Equivalence structure      137 278 311 317
Equivalence structure, invariants      137
Equivalent over a set of sentences      40
Ershov      vii viii 86 87 167 189
Ershov’s hierarchy      87 167 189
Ershov’s hierarchy, relativized      86
Existential type      178
expansion      38 46
Exponentiation of linear orderings      59 315
Exponentiation of orderings      315
Exponentiation of ordinals      59
Expressive completeness      vi
Extension      38
Feiner      143 150 281 282 284
Field      36 90 311—313
Field of algebraic numbers      47
Field of characteristic 0      312
Field of characteristic p      312
Field, algebraically closed      47 137 185—187 312 313
Field, Archimedean ordered      90 108 313
Field, Archimedian ordered      89
Field, characteristic of      312
Field, ordered      36 90 101 160 174 313
Field, ordered field      174
Field, real closed      187 313
Fixed-point theorem      67
Forcing      vi 161 181
Forcing conditions      161
Forcing language      161
Forcing relation, $\|—$       162
Formally $\Sigma_1^0$ relation      183 185
Formally $\Sigma_{\alpha}^0$       165
Formally $\Sigma_{\alpha}^0$ relation      253
Formally c.e. relation      182
Formula, $P_{\omega_1}$       102
Formula, $\Pi_n$       40
Formula, $\Pi__{\alpha}$       93
Formula, $\Sigma_n$       40
Formula, $\Sigma_{\alpha}$       93
Formula, atomic      34
Formula, basic      35
Formula, finitary open      93
Formula, finitary, or elementary      33
Formula, infinitary      89
Formula, infinitary, propositional      102
Formula, of $L_{\omega_1\omega}$       89
Formula, open      35
Formula, predicate      34
Formula, propositional      33
Formula, propositional, atomic      33
Formula, X-computable      179
Free variables of a type      155
Freeness      184 189 191—193
Freeness, appropriate for $\Delta_{\alpha}$ separable relations      259

1 2 3

О проекте