• Название:

    Exam program fall 2013


  • Размер: 0.06 Мб
  • Формат: RTF
  • Сообщить о нарушении / Abuse

    Осталось ждать: 20 сек.

Установите безопасный браузер



Предпросмотр документа

1.Программа Гильберта. Математика, как деятельность по формальным правилам. Содержательное представление о полноте и непротиворечивости и возможности их установить.

2.«Наивная теория множеств» Кантора. Отношения, функции, свойства, как множества. Множества, объединение, пересечение, прямое произведение, проекция.

3.Существование множества, заданного своим описанием. Парадокс Рассела.

4.Индуктивные определения и задаваемые ими множества объектов; примеры.

5.Логика высказываний. Синтаксис и семантика. Определение формулы (логики высказываний). Теорема об однозначности анализа.

6.Сокращения при записи формул. Опускание скобок.

7.Значение формулы при данной интерпретации. Свойство подстановки: значение формулы определяется значениями подформул, из которых она образована. Выполнимость и общезначимость (тавтологии). Теорема компактности для логики высказываний.

8.Построение формулы логики высказываний по булевой функции. Теорема о совершенной дизъюнктивной нормальной форме.

9.Представление в логике высказываний распространенных способов рассуждения.

10.Структура данной сигнатуры. Гомоморфизмы, вложения, изоморфизмы, автоморфизмы структур.

11.Логика отношений; синтаксис и семантика логики отношений. Определимость. Истинность. Непротиворечивость.

12.Примеры определимых отношений в упорядоченных множествах.

13.Примеры определимости в арифметике. Китайская теорема об остатках. Бета-функция Гёделя.

14.Алгебра определимостей.

15.Расширение сигнатуры операциями, расширение логики отношений термами. Использование отношений вместо функций.

16.Определимость отношений в поле действительных чисел. Полуалгебраические множества. Теорема Тарского – Зайденберга.

17.Теория. Модель теории. Теория структуры. Соответствие Галуа для теорий и классов моделей.

18.Критерий элементарности подструктуры.

19.Теория с равенством. Теория равенства.

20.Теория линейного порядка. Дискретный порядок с наименьшим элементом. Теория плотного неограниченного линейного порядка. Сложение порядков.

21.Нестандартная арифметика. Галактики.

22.Построение модели. Перечислимость истин.

23.Теорема компактности. Полная теория.

24.Категоричность. Плотный линейный порядок. Признак Лося – Воота.

25.Теорема Лёвенгейма – Сколема об элементарной подмодели.

26.Многообразия определимости. Неопределимость. Группы автоморфизмов. Метод автоморфизмов. Теорема Свенониуса.

27.Соответствие Галуа для многообразий определимостей и групп автоморфизмов. Подмногообразия и надгруппы. Применения теоремы Свенониуса.

28.Подмногообразия в порядке на рациональных числах. Теорема Мучника – Семенова.

29.Определимость одноместных отношений в порядке на натуральных числах.

30.Исчисление логики отношений. Теорема Геделя о полноте (без доказательства).

31.Предварённая нормальная форма.

32.Модальная логика. Шкала Крипке. Исчисление Крипке.

33.Теорема об истинности для исчисления Крипке.

34.Теорема о полноте для исчисления Крипке.

35.Примеры исчислений модальных логик и моделей для них.

36.Модальные логики, задаваемые исчислениями.

37.Модальные логики, определяемые классами шкал.

38.Алфавиты. Ансамбли: слов, цепочек слов, списков. Кодирование элементов ансамблей двоичными словами. Переход к следующему в ансамбле.

39.Действия и проверки. Описания. Общее понятие исчисления. Породимые множества. Теоремы замкнутости для исчислений. Вывод объекта.

40.Грамматики. Тезис Поста.

41.Алгоритмы. Вычислимые функции. Универсальный алгоритм. Универсальная вычислимая функция.

42.Диагональ невычислимости.

43.Алгоритмы Маркова. Тезис Черча.

44.Алгоритмические проблемы. 10-ая проблема Гильберта.

45.Вычислимость, разрешимость, породимость. Соотношения между ними.

46.Перечислимость. Эквивалентные определения. Разрешимость.

47.Сложность вычислений. Задачи, решаемые перебором. Задача о рюкзаке. Задача выполнимости.

48.Универсальная переборная задача. P=NP ?

49.Сложность объекта. Теорема Колмогорова. Случайность.

50.Теорема Тарского о невыразимости истины.

51.Теорема Геделя о неполноте.

52.Арифметика Пеано. Червь Беклемишева.

53.Аксиоматическое построение математики. Теория множеств. Равномощность. Теорема Кантора – Бернштейна. Гипотеза континуума.

54.Вполне упорядоченные множества. Трансфинитная индукция. Теорема Цермело. Аксиома выбора.

55.Независимость Гипотезы Континуума и Аксиомы выбора от Теории множеств. Парадокс Банаха – Тарского.