mathlogic-s1-v1-0-0-p1

31 Конспект лекций по математической логике (I семестр)

. . . (остальное — упр.) ((а) — база индукции, (б) — индуктивный переход.) "

Теорема 16.23. Пусть A, B Kσ , ψ(x, y) — безкванторная. ψ F(σ) и

A. Тогда:

a

(а) Если A |=

ψ(

), то B |=

ψ(

).

x

x,

a

x

x,

a

(б) Если B |=

ψ(

), то A |=

ψ(

).

x

x,

a

x

x,

a

Т. е. при переходе к надмоделям сохраняется истинность экзистенциальных

формул; при переходе к подмоделям сохраняется истинность универсаль-

ных формул.

! (а) A |=

ψ(

)

A A |= ψ(

) A |= ψ(

),

B

x

x,

a

c

c,

a

c,

a

c

B |= x ψ(

).

x,

a

(б) B |=

ψ(

).

x

x,

a

Пусть A ̸=|

ψ(

). Следовательно, A |= ¬

ψ(

). Следова-

x

x,

a

x

x,

a

тельно, A |=

¬ψ(

). Следовательно, B |=

¬ψ(

). Следо-

x

x,

a

x

x,

a

вательно, B |= ¬

ψ(

) — противоречие. "

x

x,

a

Опр.

16.24.

Пусть A Kσ . Эквивалентность называется конгруэнцией,

n

если

f

σ,

ai an f(

) = f(b).

a, b |A|, если i ≤ n

a

Опр. 16.26. Пусть A Kσ , — конгруэнция на A, P n, fn, c σ. Рассмотрим алгебраическую систему A/ = A/ ; σ . Пусть a A, тогда

A |= P n([a1], . . . , [an]), если b	A	i ≤ n ai bi, A |= P n(b),
f([a1], . . . , [an]) = [f(a1, . . . , an)].
CA/ = [C].
Предл. 16.27. Определение A/ — корректно,
			a, b A.
i ≤ n [ai] = [bi] ai bi f(a1		, . . . , an) f(b1					, . . . , bn).
Следовательно: f([a1], . . . , [an])	= [f	(a1, . . . , an)] =					[f(b1, . . . , bn)] =

= f([b1], . . . , [bn]).

Т. о., конгруэнция — это в точности такая эквивалентность, для которой определение фактор-системы корректно.

Предл. 16.28. Пусть A Kσ , — конгруэнция, h: A → A/ , h(a) = [a]. Тогда h — гомоморфизм.

! Пусть h — отображение, P n, fn, c σ, a |A|.

(1)A |= P(a1, . . . , an) A/ |= P([a1], . . . , [an]). A/ |= P(h(a1), . . . , h(an)).

(2)f(h(a1), . . . , h(an)) = f([a1], . . . , [an]) = [f(a1, . . . , an)] = = h(f(a1, . . . , an)).

(3)CA/ = [C] = h(C).

Т. о. с каждой конгруэнцией связан эпиморфизм. "

Предл. 16.29. Пусть A, B Kσ , h: A → B — гомоморфизм, a c h(a) = h(c). Тогда — конгруэнция.

! (а) — эквивалентность (по определению);

(б) fn σ, a, b A, i ≤ n ai bi h(ai) = h(bi).

h(f(a)) = f(h(a1), . . . , h(an)) = f(h(b1), . . . , h(bn)) = h(f(b)) f(a) f(b) — конгруэнция. "

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике (I семестр)

32

Теорема 16.30. (О сильных эпиморфизмах) Пусть h: A → B — сильный эпиморфизм, a, b A, a c h(a) = h(c). Тогда B изоморфна A/ .

! g: A/ → B		a c,
(1) g: A/ → B, g([a]) = h(A), пусть a, c A и [a] = [c]
т. е. h(a) = h(c) g([a]) = h(a) = h(c) = g([c]).
Докажем корректность. Покажем, что g: A/ → B — изоморфизм.
(2) g биективна.	a b	[a] =
Инъективность: g([a]) = g([b]) h(a) = h(b)
= [b].	a A h(a) = b.
Сюрьективность: пусть b B, h — эпиморфизм

[a] A/ , g([a]) = h(a) = b.

(3) P n, fn, c σ, a A, тогда:

(а) A/ |= P([a1], . . . , [an]) c A i ≤ n ci ai h(ci) = h(ai)

A |= P(c) B |= P(h(a1), . . . , h(an))B |= P(g([a1]), . . . , g([an])).

(б) g(f([a1], . . . , [an])) = g([f(a1, . . . , an)]) = h(f(a)) = = f(h(a1), . . . , h(an)) = f(g([a1]), . . . , g([an])).

(в) g(CA/ ) = g([CA]) = h(CA) = CB. "

Опр. 16.31. Пусть A, B Kσ , f: A → B — гомоморфизм.

f назовём доопределением предикатов, если выполняется σ0 = {все константы, символы функций из σ}, если f: A ↑σ0 → Z ↑σ0 — изоморфизм, где A ↑σ0 = A; σ0 , причём сигнатурные символы опрделяются на A также, как и на A.

Теорема 16.32. (Основная о гомоморфизмах) Всякий гомоморфизм является композицией сильного эпиморфизма, доопределения предикатов и изо-

морфного вложения.

f: A → B — гомоморфизм, C = f(A) B, N, f: A → N — сильный

эпиморфизм, h: N → B — доопределение предикатов, f = g ◦ h ◦ idC , idC : C → C.

! |N| = |C| = C. Пусть σ0 — функциональные и константные символы из

σ.

N ↑σ0 = C ↑σ0 Pn σ, b N N |= P(b) a A A |= P(a).

i ≤ n f(ai) = bi, тогда:

(1)g(a) = f(a), g: A ↑σ0 → C ↑σ0 совпадает с f: A ↑σ0 → C ↑σ0 then g —

сильный гомоморфизм.

(2)h(b) = b b C, тогда g: A ↑σ0 → C ↑σ0

Следовательно, h — доопределение предикатов (упр., т. к. f сохраняет истинность предикатов).

id: C → B — изоморфное вложение. "

Суть: Всякий гомоморфизм — композиция факторизации по конгруэнции, доопределения предикатов и изоморфного вложения.

Версия 1.0.0

33	Конспект лекций по математической логике (I семестр)

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике (I семестр)

34

Версия 1.0.0

35	Конспект лекций по математической логике (I семестр)

Вопросы к экзамену

1.Множества и операции над ними. Простейшие теоретико-множественные тождества.

2.Язык логики высказываний. Понятие формулы. Таблицы истинности. Эквивалентность формул. Связь теоретико-множественных тождеств и тождеств логики высказываний. Основные тождества логики высказываний и теории множеств. Нормальные формы. Приведение формулы к СДНФ и СКНФ.

3.Понятие алгебраической системы, алгебры, модели. Примеры. Логика предикатов. Термы и формулы логики предикатов. Истинность формулы на модели.Тождественно истинные и выполнимые формулы. Семантическая эквивалентность формул. Основные тождества логики предикатов.

4.Отношения и функции. Предпорядок, отношения эквивалентности и частичного порядка. Эквивалентность и разбиение, фактор-множество. Максимальные и минимальные, наибольшие и наименьшие элементы, точная верхняя и нижняя грани. Понятие решетки.

5.Множество-степень, понятие и основные свойства булевой алгебры. Примеры. Атомные и безатомные элементы булевых алгебр.

6.Машины Тьюринга. Функции, вычислимые на машинах Тьюринга.

7.Примитивно-рекурсивные, общерекурсивные и частично-рекурсивные функции.

8.Мощность множества. Теорема Кантора-Бернштейна, теорема Кантора. Счётные множества. Счётность множества слов в конечном алфавите.

9.Континуум. Несчётность множества вещественных чисел. Равномощность множества вещественных чисел и множества всех подмножеств множества натуральных чисел. Бесконечность класса бесконечных мощностей. Континуум-гипотеза и обобщённая континуум-гипотеза. Ординальные и кардинальные числа.

10.Конечные булевы алгебры, теорема Стоуна для конечных булевых алгебр.

11.Секвенциальное исчисление высказываний. Понятие вывода. Допустимые правила вывода.

12.Семантика исчисления секвенций. Теорема о корректности. Теорема о подстановке. Теорема о замене. Теорема о существовании КНФ. Теорема о полноте исчисления секвенций. Теорема об адекватности.

13.Исчисление высказываний гильбертовского типа. Теорема о дедукции (без доказательства). Теорема об эквивалентности гильбертовского и секвенциального исчислений высказываний (без доказательства).

14.Гомоморфизм и изоморфизм алгебраических систем. Подсистемы. Конгруэнтнции, фактор-системы. Основная теорема о гомоморфизмах.

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике (I семестр)

36

Состояние

Доказательства написаны до 10 (включительно).

Определения и формулировки до того же параграфа более-менее надёжны, в более поздних могут содержаться явные ошибки (ещё не проверял).

Отличие от лекций

В некоторых случаях этот конспект отличается от лекций:

1.Лектор любит называть инъективные, сюрьективные и биективные функции функциями «разнозначными», «на» и «взаимнооднозначными» соответственно. Авторы считают, что первые три термина звучат более научно.

2.Иногда одинаковые определения одного понятия повторялись несколько раз в разных частях. Авторы решили, что в печатном конспекте повторения излишни.

3.Выпущены все примеры. (Лень набирать.)

4.Слова и словесные описания иногда заменялись математическими выражениями.

5.Местами произведены другие «эквивалентные» преобразования.

6.Иногда для увеличения читаемости используются квадратные скобки вместо круглых.

7.Среди простых похожих доказательств приведено только первое (чтобы видеть общий метод), а остальные помечены как элементарные.

8.(new) Вместо a1, . . . , an часто употребляется обозначение a, изредко используемое и лектором.

История изменений

1.0.0Ура! Дописан параграф 16. Исправления в пунктах 1.4, 4.8, 5.8.16, 5.8.25, 5.16, 6.5, 6.10, опр. перед 7.25, 8.8, 8.11, 9.5 (а также другие более мел-

кие).

0.9.9Исправления в пунктах 2.1 (убраны скобки у ¬), 2.21 (опечатки), 3.7 (перефразировка), 4.5 (опечатка), 7.23.17 (опечатка), 13.1 (во второй строке), 16.1.2а (замена на ). Другие мелкие исправления.

0.9.8Добавлены некоторые доказательства, исправлены опечатки.

0.9.5Добавлены доказательства с лекций; помечены доказательства, оставленные в качестве упражнения. Исправлены некоторые опечатки. Добавлен список вопросов к экзамену.

0.9.0Первая публичная версия. Набран почти весь материал (до 16).

Версия 1.0.0