Ориентированный граф конечной delta(0,alpha) -размерности

Abstract

В данной работе представлены следующие результаты. 1. Для каждого вычислимого ординала-последователя alpha существует вычислимый ориентированный граф (симметрический, иррефлексивный граф), который является delta(0,alpha)-категоричным, но не относительно delta(0,alpha)-категоричным. Данный граф не имеет формально sigma(0,alpha)-семейства Скотта. 2. Для каждого вычислимого ординала-последователя alpha существует вычислимый ориентированный граф (симметрический, иррефлексивный граф) с отношением, которое является внутренне sigma(0,alpha), но не относительно внутренним sigma(0,alpha)-отношением. 3. Для каждого вычислимого ординала-последователя alpha и каждого конечного n существует ориентированный граф (симметрический, иррефлексивный граф) delta(0,alpha)-размерности n. 4. Для каждого вычислимого ординала-последователя alpha существует ориентированный граф (симметрический, иррефлексивный граф), имеющий представления только в степенях таких множеств X, что имеет место delta(0,alpha)(X) != delta(0,alpha). в частности, для каждого конечного n существует ориентированный граф, имеющий представления только в не n-низких степенях.

In present article, we prove the following assertions: 1. For every computable successor ordinal alpha, there exists a delta(0,alpha)-categorical directed graph (symmetric, irreflexive graph) which is not relatively delta(0,alpha) -categorical, i.e. no formally sigma(0,alpha)-Scott family exists for such a structure. 2. For every computable successor ordinal alpha , there exists an intrinsically sigma(0,alpha) -relation on universe of a computable directed graph (symmetric, irreflexive graph which is not a relatively intrinsically sigma(0,alpha) -relation. 3. For every computable successor ordinal alpha and finite n, there exists a delta(0,alpha)-categorical directed graph (symmetric, irreflexive graph) whose delta(0,alpha)-dimension is equal to n. 4. For every computable successor ordinal alpha, there exists a directed graph (symmetric, irreflexive graph) possesing presentations only in the degrees of sets X such that delta(0,alpha)(X) != delta(0,alpha). In particular, for each finite n, there exist is a structure with presentations in just the non-lown degrees.