WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«Определения Главные нумерации Мощность полурешеток Минимальные нумерации Вычислимые нумерации в иерархии Ершова Сергей Оспичев Новосибирск 2012 Сергей Оспичев Вычислимые нумерации в иерархии ...»

Определения

Главные нумерации

Мощность полурешеток

Минимальные нумерации

Вычислимые нумерации в иерархии Ершова

Сергей Оспичев

Новосибирск 2012

Сергей Оспичев Вычислимые нумерации в иерархии Ершова

Определения

Главные нумерации

Мощность полурешеток

Минимальные нумерации

Иерархия Ершова

Пусть O – клинивская система обозначения ординалов, A

и a – обозначение ординала в O.

Определение

Для любого a O множество A принадлежит 1, если

a

существуют вычислимая функция f (x, s) и частично-вычислимая функция g(x, s) и для всех x :

A(x) = lim f (x, s), f (x, 0) = 0;

s g(x, s) g(x, s + 1) o g(x, s) o a f (x, s) = f (x, s + 1) g(x, s + 1) = g(x, s) Сергей Оспичев Вычислимые нумерации в иерархии Ершова Определения Главные нумерации Мощность полурешеток Минимальные нумерации Иерархия Ершова Определение A принадлежит 1, если A 1 a a Определение A принадлежит 1, если A и A – 1 -множества a a Сергей Оспичев Вычислимые нумерации в иерархии Ершова Определения Главные нумерации Мощность полурешеток Минимальные нумерации Вычислимые нумерации Определение Нумерацию назовем 1 -вычислимой, если a { n, m |n m} – 1 -множество.

a Определение µ, если существует вычислимая функция f и для всех n µn = f (n).

Сергей Оспичев Вычислимые нумерации в иерархии Ершова Определения Главные нумерации Мощность полурешеток Минимальные нумерации Определение Вычислимую нумерацию семейства S назовем главной, если любая вычислимая нумерация семейства S сводится к.

Предложение Существует главная нумерация любого непустого конечного семейства в.п. множеств.

Сергей Оспичев Вычислимые нумерации в иерархии Ершова Определения Главные нумерации Мощность полурешеток Минимальные нумерации Теорема (Абешев, Лемпп) Существует S = {A, B} – семейство непересекающихся 2 -множеств без 1 -вычислимой главной нумерации.

Предложение Пусть S – конечное семейство попарно непересекающихся по базе 1 -множеств. Тогда существует 1 -вычислимая главн

–  –  –

Теорема (О., Подзоров) семейство 0 -множеств и для некоторого Пусть S 2 вычислимого направленного подсемейства F S в.п.

множеств F не принадлежит S. Тогда для любой 0 -вычислимой нумерации семейства S существует вычислимая нумерация семейства F, такая что.

–  –  –

Следствие (О., Подзоров) Если семейство S 0 содержит вычислимое направленное подсемейство F S и F S, тогда не существует a -вычислимой главной нумерации S для любого a O.

–  –  –

Пусть S =, {0}, {0, 1}, {0, 1, 2},...

Предложение Не существует 1 -вычислимой главной нумерации семейства a S, для любого a O.

Предложение Существует 1 -вычислимая нумерация семейства S {N}, где a a – клинивское обозначение любого ненулевого ординала.

Предложение Существует 1 -вычислимая главная нумерация семейства S.

–  –  –

Теорема (Хуторецкий) Пусть S – семейство в.п. множеств.

Если µ – вычислимые нумерации семейства S, тогда найдется вычислимая нумерация семейства S, такая что и µ Если существуют две неэквивалентные вычислимые нумерации семейства S, тогда существует бесконечно много таких нумераций.

–  –  –

Теорема (Бадаев, Лемпп) Существует семейство S 1 -множеств, а также 2 -вычислимые нумерации µ и семейства S, такие что µ и для любой вычислимой нумерации семейства S, либо µ, либо.

–  –  –

Теорема (Гончаров, Лемпп, Соломон) Существует бесконечное семейство в.п. множеств с единственной 1 -вычислимой нумерацией.

Теорема Существует бесконечное семейство S с единственной a -вычислимой нумерацией.

–  –  –

Теорема (Бадаев, Манат, Сорби) Для любого ненулевого n {}, и для любого ординального обозначения a ненулевого ординала, существует a -вычислимое семейство S из n множеств, такое что S обладает только одной 1 -вычислимой нумерацией.

a

–  –  –

Определение Нумерацию назовем позитивной, если множество { n, m n = m } вычислимо перечислимо (и разрешимым, это множество вычислимо) Определение Нумерация фридбергова, если для любых n, m n = m.

–  –  –

Следствие Для любого ординального обозначения a непредельного ординала существует бесконечное 1 -вычислимое семейство a a -множеств без 1 -вычислимых фридберговых нумераций, a но существует 1 -вычислимая фридбергова нумерация этого 2a семейства.

–  –  –

Следствие (Манат, Сорби) Существует бесконечное 1 -вычислимое семейство, такое что a существует бесконечно много неэквивалентных a -вычислимых позитивных нумераций, но нет 1 -вычислимых фридберговых нумераций.

a

–  –  –

Теорема (Бадаев, Манат, Сорби, Таласбаева) Пусть S – 1 -вычислимое бесконечное семейство и S, a если a – обозначение четного или предельного ординала ( S иначе). Тогда S существует бесконечно много неэквивалентных a -вычислимых позитивных неразрешимых нумераций.

Следствие (Бадаев, Манат, Сорби, Таласбаева) Существует бесконечно много неэквивалентных a -вычислимых позитивных неразрешимых нумераций семейства всех 1 -множеств.

a

–  –  –



Похожие работы:

«mini-doctor.com Инструкция Эргос таблетки по 50 мг №4 (4х1) ВНИМАНИЕ! Вся информация взята из открытых источников и предоставляется исключительно в ознакомительных целях. Эргос таблетки по 50 мг №4 (4х1) Действующ...»

«ВЛИЯНИЕ КОМПЬЮТЕРОВ И СОТОВЫХ ТЕЛЕФОНОВ НА ЗРЕНИЕ ПОДРОСТКОВ. Женя Пискарева, Конкиева Н.А. СПб ГБОУ СПО "Медицинский колледж №1". Санкт-Петербург,Россия. THE IMPACT OF COMPUTERS AND CELL PHONES AT THE SIGHT OF TEENAG...»

«Государственное бюджетное образовательное учреждение высшего профессионального образования "ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ МЕДИЦИНСКИЙ НИВЕРСИТЕТ" Министерства здравоохранения Российской Федерации В.М. Мирович, Г.М. Федосеева, Е.Г. Горячкина РАСТЕНИЯ И СЫРЬЕ РАСТЕНИЙ СЕМЕЙСТВА АСТРОВЫХ, СОДЕРЖА...»

«"Знать бы, где упасть, так соломки подостлать" (русская поговорка) или что такое "школьная травма" Многие могут представить себе урок физкультуры в школе. Маленький спортивный зал, белая линия вдо...»

«mini-doctor.com Инструкция Рыбий Жир жидкость оральная по 100 мл во флаконе ВНИМАНИЕ! Вся информация взята из открытых источников и предоставляется исключительно в ознакомительных целях. Рыбий Жир жидкость оральная по 100 мл во флаконе Действующее вещество: Витамины в сочетании с прочими препаратами Лекарственная форма: Жидкость Фармак...»

«mini-doctor.com Инструкция Тестостерона Пропионат раствор для инъекций 1 % в этилолеате по 1 мл в ампулах №5 ВНИМАНИЕ! Вся информация взята из открытых источников и предоставляется исключительно в ознакомительных целях. Тестостеро...»

«mini-doctor.com Инструкция Диокор 80 таблетки, покрытые пленочной оболочкой, по 80 мг/12,5 мг №10 (10х1) ВНИМАНИЕ! Вся информация взята из открытых источников и предоставляется исключительно в ознакомительных целях. Диокор 80 таблетки, покрытые пленочной оболочкой, по 80 мг/12,5 мг №10 (10х1) Действующее вещество: Вальзартан и диуретик...»

«РОССИЙСКОЕ ОБЩЕСТВО ДЕРМАТОВЕНЕРОЛОГОВ И КОСМЕТОЛОГОВ ФЕДЕРАЛЬНЫЕ КЛИНИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЕДЕНИЮ БОЛЬНЫХ ВРОЖДЕННЫМ БУЛЛЕЗНЫМ ЭПИДЕРМОЛИЗОМ Москва 2015 Персональный состав рабочей группы по подготовке федеральных клинических...»









 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.