Главная » Просмотр файлов » Верещагин Н.К., Шень А. - Языки и исчисления

Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 38

Файл №1076783 Верещагин Н.К., Шень А. - Языки и исчисления (Верещагин Н.К., Шень А. - Языки и исчисления) 38 страницаВерещагин Н.К., Шень А. - Языки и исчисления (1076783) страница 382018-01-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 38)

, an ) и f (a1 , . . . , an ) = a, истинные в A, истинны и в B.Истинные в A формулы вида ϕ(a1 , . . . , an ) принадлежат ThA (A) ипотому истинны и в B; ложные в A формулы имеют отрицания вThA (A) и потому ложны в B.Таким образом, для доказательства теоремы Левенгейма – Сколема о повышении мощности осталось построить нормальную модель теории ThA (A), имеющую сколь угодно большую мощность.Это можно сделать так: добавим множество новых констант ci иформулы ci 6= cj (для всех i 6= j) к теории ThA (A). Полученнаятеория будет совместной по теореме компактности для нормальныхмоделей.

(В самом деле, любая конечная часть её имеет нормальную модель, поскольку содержит конечное число новых констант,172Теории и модели[гл. 5]и им можно придать различные значения в A.) Поэтому и вся теория имеет нормальную модель. Всем константам ci соответствуют вэтой модели разные элементы (поскольку истинна формула ci 6= cj ),поэтому мощность этой модели может быть сколь угодно большой,если использовать достаточно много констант.Этот же приём будет использован нами при построении нестандартной модели арифметики (с.

193). Приведённое рассуждение даёт оценку мощности снизу. Можнополучить и в точности нужную мощность:Теорема 62. Пусть A — бесконечная нормальная интерпретациясигнатуры σ (с равенством) и пусть β — мощность, не меньшая мощностей сигнатуры σ и интерпретации A. Тогда существует нормальное элементарное расширение B ⊃ A мощности β. Мощность сигнатуры σA есть максимум из мощностей σ и A;после добавления новых констант в количестве β штук получитсясигнатура мощности β, и согласно теореме 48 (с. 152) найдётся модель множества ThA (A) мощности β. Преобразование её в нормальную модель (факторизация) может лишь уменьшить мощность, ноβ различных элементов у нас заведомо есть. Аналогичный приём (добавление констант) позволяет легко доказать такое утверждение:Теорема 63.

Если теория (в произвольной сигнатуре с равенством)имеет сколь угодно большие конечные нормальные модели, то онаимеет и бесконечную нормальную модель. Добавим к теории бесконечное число новых констант и аксиомы о том, что все они различны. Любой конечный фрагмент расширенной теории имеет нормальную модель (возьмём достаточно большую конечную модель и проинтерпретируем в ней константы). Потеорме компактности и вся расширенная теория имеет нормальнуюмодель, которая и будет бесконечной нормальной моделью исходнойтеории. Вообще можно задать себе такой естественный вопрос.

Пусть естьнекоторая теория (или даже просто одна формула). Каковы могутбыть мощности её нормальных моделей? Как мы видели, для теорийс конечной сигнатурой верно одно из двух: либо бесконечных моделей вовсе нет, либо есть бесконечные модели всех мощностей. Этогарантируют теоремы Левенгейма – Сколема об элементарной подмодели (теорема 42) и о повышении мощности (теорема 61).Что можно сказать про мощности конечных моделей? Для каждой формулы рассмотрим множество всех возможных мощностей её[п. 2]Повышение мощности173конечных моделей.

Его иногда называют спектром формулы. Этомножество может быть устроено довольно сложным образом: например, для формулы, выражающей аксиомы поля, спектр состоит извсех степеней простых чисел.116. (а) Укажите формулу, спектр которой состоит из всех чётныхположительных чисел. (б) Укажите формулу, спектр которой состоит извсех нечётных чисел. (в) Укажите формулу, спектр которой состоит извсех составных чисел.Любопытно, что проблема конечного спектра (стоящая в книгеКейслера и Чэна [13] под номером 1 среди «старых проблем теориимоделей»), неожиданно оказалась связана с центральной проблемойтеории сложности вычислений — так называемой «проблемой перебора».

(Проблема конечного спектра состоит в следующем: верно ли,что дополнение (до N) к спектру любой формулы является спектромнекоторой другой формулы?)В качестве примера использования теоремы о повышении мощности докажем теорему Гильберта о нулях (теорема 40), не проводя элиминацию кванторов. Пусть система уравнений имеет решениев поле k 0 , являющемся расширением алгебраически замкнутого поля k. Покажем, что она имеет решение и в k.

Построим элементарное расширение k 00 ⊃ k очень большой мощности. Теперь k 0 можновложить в k 00 (это вложение строится по трансфинитной рекурсии:добавляя алгебраический элемент, мы пользуемся алгебраическойзамкнутостью k 00 , добавляя трансцендентный элемент, мы пользуемся большой мощностью k 00 ).

Значит, система имеет решение в k 00 .Поскольку k 00 было элементарным расширением, то система имеетрешение в k.Другое любопытное применение теоремы о повышении мощноститаково. Назовём линейно упорядоченное множество M однородным,если для любых двух возрастающих последовательностей x1 < x2 << . . . < xn и y1 < y2 < . . . < yn найдётся автоморфизм множества M ,переводящий xi в yi (при всех i = 1, . . . , n).Теорема 64.

Для всякой бесконечной мощности найдётся однородное линейно упорядоченное множество такой мощности. Множество рациональных чисел (и вообще любое счётное плотное линейно упорядоченное множество) однородно. В самом деле,соответствие между двумя наборами его элементов постепенно продолжается до автоморфизма (добавляем элементы поочерёдно с тойили другой стороны).

Другой способ убедиться в этом — вспомнитьо том, что это рациональные числа, и взять кусочно-линейный авто-174Теории и модели[гл. 5]морфизм.Для каждого n фиксируем способ продолжения автоморфизмовс n-элементных подмножеств в виде функции fn с 2n + 1 аргументами: f (z, x1 , . . . , xn , y1 , . . . , yn ) означает элемент, в который переходитz при автоморфизме, переводящем xi в yi . Рассмотрим теперь Q какинтерпретацию сигнатуры, включающей порядок и все fi .

По теореме о повышении мощности можно найти элементарно эквивалентную интерпретацию любой заданной мощности. Поскольку свойствафункций fn выражаеются формулами, получится однородное линейно упорядоченное множество заданной мощности. 5.3. Полные теорииВ этом разделе мы попытаемся систематизировать уже известныенам понятия и факты.• Начнём с напоминаний. Сигнатурой мы называли набор предикатных и функциональных символов. Среди формул даннойсигнатуры выделяют замкнутые (формулы без параметров).Сигнатура имеет интерпретации, в которых замкнутые формулы этой сигнатуры бывают истинными и ложными. Произвольное множество замкнутых формул данной сигнатуры называется теорией в этой сигнатуре. Моделью теории называется интерпретация, в которой все формулы теории истинны.Теория называется совместной, если она имеет модель.• Теория называется теорией с равенством, если она включает в себя аксиомы равенства (а её сигнатура содержит символ равенства).

Интерпретация теории с равенством называется нормальной, если равенство интерпретируется как совпадение элементов носителя интерпретации. Совместная теория сравенством имеет нормальную модель (получаемую из произвольной модели факторизацией по отношению равенства).• Говорят, что замкнутая формула ϕ выводима в теории T (является теоремой теории T ), если формула ϕ получается изаксиом исчисления предикатов и формул теории T по правилам вывода. (Обозначение: T ` ϕ.)Формула ϕ выводима в теории T тогда и только тогда, когдав исчислении предикатов выводится некоторая формула видаτ → ϕ, где τ — конъюнкция конечного числа формул из T .[п. 3]Полные теории175Формула ϕ семантически следует из T , если она истинна влюбой модели теории T (обозначение: T ϕ). Семантическоеследование равносильно выводимости (теорема 51, с.

154). Взявв качестве ϕ тождественно ложную формулу ⊥ (скажем, отрицание тавтологии), приходим к понятиям противоречивости(T `⊥) и несовместности (T ⊥, T не имеет моделей). В противоречивой теории выводима любая формула (соответствующей сигнатуры).• Непротиворечивая теория T полна (в данной сигнатуре), еслидля любой замкнутой формулы ϕ этой сигнатуры либо формула ϕ, либо её отрицание ¬ϕ выводится из T .• Для произвольной интерпретации M произвольной сигнатуры σ можно рассмотреть элементарную теорию интерпретации M , обозначаемую Th(M ) и состоящую из всех истинныхв M замкнутых формул сигнатуры σ. Очевидно, эта теорияполна (одна из формул ϕ и ¬ϕ ей принадлежит).

Две интерпретации M1 и M2 элементарно эквивалентны, если их элементарные теории совпадают: Th(M1 ) = Th(M2 ).• Теория T называется конечно аксиоматизируемой, если существует конечное множество T 0 теорем теории T , из которыхвыводятся все утверждения из T (другими словами, если существует конечная теория, имеющая то же самое множествотеорем).• Теория с равенством, имеющая конечную или счётную сигнатуру, называется категоричной в счётной мощности, если всееё счётные нормальные модели изоморфны. Категоричность вданной несчётной мощности определяется аналогично.• Теория с конечной сигнатурой называется разрешимой, если существует алгоритм, который по произвольной замкнутой формуле определяет, выводима ли она в этой теории или нет.117.

Покажите, что добавление к теории любой её теоремы не меняетмножества теорем.Прежде чем переходить к примерам, сделаем два простых наблюдения.Теорема 65 (критерий Лося – Воота). Непротиворечивая теория Tс равенством в конечной или счётной сигнатуре, не имеющая конечных моделей и категоричная в счётной мощности, полна.176Теории и модели[гл. 5] Предположим, что ни одна из формул ϕ и ¬ϕ не выводима втеории T .

Тогда обе теории T ∪ {¬ϕ} и T ∪ {ϕ} непротиворечивы.По теореме 47 (с. 152) они имеют счётные модели, которые остаютсясчётными после факторизации (перехода к нормальным моделям),поскольку теория T не имеет конечных моделей. Эти счётные модели должны быть изоморфными (в силу категоричности). С другойстороны, в одной из них истинна формула ¬ϕ, а в другой — формула ϕ, так что они даже не элементарно эквивалентны (мы знаем израздела 3.9, что такого быть не может).

Характеристики

Тип файла
PDF-файл
Размер
1,57 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6517
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее