λa. Рассмотрим также систему B = hR
3
; +, {λ·}
λ∈R
i, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умно- жения троек на число λ для всех вещественных чисел λ. Системы A и B яв- ляются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору
a ∈ E
3
его координатную строку (x, y, z) в некотором фиксированном базисе
e
1
,
e
2
,
e
3
, является биекцией (ϕ: E
3
↔ R
3
), при кото- рой сохраняются действия операций: ϕ(
a+
b) = ϕ(
a)+ϕ(
b) и ϕ(λ·
a) = λ·ϕ(
a).
Таким образом, ϕ — изоморфизм линейных пространств A и B, и, следова- тельно, изучение геометрических векторов можно свести к изучению троек чисел и наоборот.
2. Рассмотрим два равномощных алфавита X, X
0
и алгебры
A = hW (X);ˆi, B = hW (X
0
);ˆi (см. пример 2.1.2). Покажем, что A ' B.
Так как |X| = |X
0
|, то существует биекция ϕ: X ↔ X
0
. Построим по ней би- екцию ψ: W (X) ↔ W (X
0
), при которой слову α ∈ W (X) ставится в соответ- ствие слово β ∈ W (X
0
), получающееся заменой каждого символа x в слове α
на символ ϕ(x). Построенная биекция ψ дает искомый изоморфизм A на B,
поскольку ψ(α
1
ˆα
2
) = ψ(α
1
)ˆψ(α
2
) для любых α
1
, α
2
∈ W (X).
3. Для заданного множества U система hP(U); ∩, ∪, , 0, 1i изоморфна си- стеме hP(U); ∪, ∩, , 1, 0i с биекцией ϕ: A 7→ A. Действительно, по законам де Моргана
ϕ(B ∩ C) = B ∩ C = B ∪ C = ϕ(B) ∪ ϕ(C)
и
ϕ(B ∪ C) = B ∪ C = B ∩ C = ϕ(B) ∩ ϕ(C)
для любых B, C ∈ P(U). Кроме того, ϕ(A) = A = ϕ(A), ϕ(0) = 0 = 1
и ϕ(1) = 1 = 0.
4. Рассмотрим группы A = h(0, ∞); ·i, B = hR; +i и отображение
ϕ: (0, ∞) → R по правилу ϕ(x) = log
p
(x) для некоторого фиксированно- го p ∈ (0, ∞), p 6= 1. Отображение ϕ является изоморфизмом систем A
и B, называемым логарифмом (по основанию p). Это позволяет произво- дить умножение положительных чисел при помощи сложения вещественных чисел на основании тождества a · b = ϕ
−1
(ϕ(a) + ϕ(b)), которое получается из равенства ϕ(a · b) = ϕ(a) + ϕ(b) применением отображения ϕ
−1
к обеим частям. ¤
2.3. ПОДСИСТЕМЫ
57
§ 2.3.
Подсистемы
Алгебраическая система A = hA; Σi называется подсистемой системы
B = hB; Σi (обозначается через A ⊆ B), если выполняются следующие условия:
а) A ⊆ B;
б) для любого функционального символа f
(n)
∈ Σ, соответствующих функций f
A
и f
B
и любых элементов a
1
, a
2
, . . ., a
n
∈ A выполняется равен- ство f
A
(a
1
, . . . , a
n
) = f
B
(a
1
, . . . , a
n
), т. е. интерпретации символа f действуют одинаково на элементах из A;
в) для любого предикатного символа P
(n)
∈ Σ, соответствующих пре- дикатов P
A
и P
B
справедливо равенство P
A
= P
B
∩ A
n
, т. е. предикат P
A
содержит в точности те кортежи отношения P
B
, которые состоят из элемен- тов множества A.
Если Σ — функциональная (предикатная) сигнатура, то подсистема A
алгебры (модели) B называется подалгеброй (подмоделью).
Пример 2.3.1. 1. Если V
0
— подпространство линейного пространства V ,
то V
0
— подсистема (подалгебра) системы V .
2. Если Σ = {P
(1)
}, B = hB; Σi — система, ∅ 6= A ⊆ B, то A = hA; Σi
является подсистемой системы B тогда и только тогда, когда P
A
= P
B
∩A. ¤
Теорема 2.3.1. Если B — алгебраическая система, X ⊆ B, X 6= ∅,
то существует единственная подсистема B(X) ⊆ B с носителем B(X),
такая, что X ⊆ B(X) и B(X) ⊆ A для любой подсистемы A ⊆ B с усло-
вием X ⊆ A.
Доказательство. В качестве B(X) рассмотрим пересечение носите- лей A всех подсистем A ⊆ B, содержащих X. Так как X ⊆ B(X),
то B(X) 6= ∅. Единственность подсистемы B(X) очевидна. ¤
Подсистема B(X) из теоремы 2.3.1 называется подсистемой, порожден-
ной множеством X в B. Она является наименьшей подсистемой системы B,
содержащей множество X.
Пример 2.3.2. Напомним, что если V — линейное пространство, S —
некоторое непустое множество векторов пространства V , то линейная обо- лочка L(S) множества S в V состоит из всевозможных линейных комби- наций векторов из S. Алгебра L(S) является подалгеброй пространства V ,
порожденной множеством S. ¤
58
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
Для описания устройства подсистемы B(X) определим индукцией по по- строению понятие терма сигнатуры Σ:
1) переменные x, y, z, . . . и константные символы из Σ суть термы;
2) если f ∈ Σ — n-местный функциональный символ, t
1
, t
2
, . . ., t
n
—
термы, то f (t
1
, . . . , t
n
) — терм;
3) никаких термов, кроме построенных по пп. 1, 2, нет.
Таким образом, термом является любое функциональное выражение, со- ставленное с помощью переменных и (или) сигнатурных функциональных символов.
Множество всех термов сигнатуры Σ обозначается через T (Σ).
Пример 2.3.3. 1. Термами сигнатуры Σ = {+, ·, 6, 0} будут, например,
0, x, x + y, z · (x + z) + 0 · y, а x + y 6 (0 + z) · x термом не является.
2. Если Σ = {f, g, h} — функциональная сигнатура, где µ(f ) = 3, µ(g) = 1,
µ(h) = 2, то выражения h(f (x
1
, x
2
, x
3
), g(x
2
)), g(f (h(x
1
, x
2
), x
1
, g(x
2
)) — тер- мы, а h(x
1
, f (x
1
, x
3
)) не образует терма.
3. В сигнатуре Σ = {отец
(1)
, Иван
(0)
} терм отец(отец(Иван)) можно про- интерпретировать как “дедушка Ивана”. ¤
Пусть t(x
1
, x
2
, . . . , x
k
) — терм из T (Σ), все переменные которого содер- жатся среди x
1
, x
2
, . . . , x
k
; A = hA; Σi — алгебраическая система. Значение
терма t при значениях a
1
, a
2
, . . . , a
k
∈ A переменных x
1
, x
2
, . . . , x
k
(обозна- чается через t(a
1
, a
2
, . . . , a
k
)) определяется по индукции:
1) если t есть переменная x
i
(константный символ c), то значение t есть a
i
(соответственно c);
2) если терм t есть f (t
1
, . . . , t
n
), а значения t
1
, . . . , t
n
суть b
1
, . . . , b
n
, то зна- чение терма t есть f (b
1
, . . . , b
n
).
Теорема 2.3.2. Если
B = hB; Σi
—
алгебраическая
система,
∅ 6= X ⊆ B, то носитель подсистемы B(X) равен
{t(a
1
, . . . , a
n
) | t ∈ T (Σ), a
1
, . . . , a
n
∈ X}.
Доказательство. Индукцией по числу шагов построения терма t по- лучаем, что если t(x
1
, . . . , x
n
) ∈ T (Σ) и a
1
, . . . , a
n
∈ X, то t(a
1
, . . . , a
n
) ∈ X
для любой подсистемы A ⊆ B, содержащей X. Поэтому достаточно пока- зать, что множество Y {t(a
1
, . . . , a
n
) | t ∈ T (Σ), a
1
, . . . , a
n
∈ X} замкнуто относительно операций системы B. Пусть f
(m)
∈ T (Σ), t
1
, . . . , t
m
∈ T (Σ),
b
i
= t
i
(a
1
, . . . , a
n
) ∈ Y , i = 1, . . . , m. Тогда f (b
1
, . . . , b
m
) ∈ Y , поскольку
f (t
1
, . . . , t
m
) ∈ T (Σ). ¤
2.4. КОНГРУЭНЦИИ. ФАКТОР-АЛГЕБРЫ. ТЕОРЕМА О ГОМОМОРФИЗМЕ 59 Таким образом, носитель подсистемы B( X) состоит из всех элементов, которые получаются при подстановке элементов из X в термы. Пример 2.3.4. 1. Найдем носитель подсистемы B( X) системы B = hQ \ {0 }; ·i для множества X = {1 2 }. Так как сигнатура Σ системы B есть {·}, то T (Σ) = {x1 , x1 · x2 , ( x1 · x2 ) · x3 , x1 · ( x2 · ·x3 ) , . . .}. По теореме 2.3.2 получаем B( X) = {1 2 ,1 2 ·1 2 ,1 2 ·1 2 ·1 2 , . . .} = {1 2 ,1 4 ,1 8 ,1 16 , . . .} = {1 2 n| n > 1 }. 2. Если B = hQ \ {0 }; ·, : i, X = {1 2 }, то, поскольку по сравнению с предыдущим примером сигнатура дополняется операцией деления x : y, множество B( X) содержит также числа 1 2 n: 1 2 m= 2 m−n, m, n > 1, т. е. C = {2 n| n ∈ Z } ⊆ B( X). Так как множество C замкнуто относительно операций умножения и деления, т. е. hC; Σ i является подсистемой системы B и содержит множество X, то B( X) ⊆ C. Следовательно, B( X) = C. 3. Найдем носитель подсистемы B( X) системы B = hC; + ,.ıi для множе- ства X = {−2 , 2 }. Так как все термы из T (Σ) являются переменными, кон- стантой .ı или образуются из переменных и константы .ı с помощью операции сложения, то каждый элемент из B( X) получается подстановкой элементов из X в некоторый терм x1 + x2 + . . . + xm+ .ı + .ı + . . . + .ı. Следовательно, B( X) = {2 m + ni | m ∈ Z , n ∈ ω}. ¤ § 2.4. Конгруэнции. Фактор-алгебры. Теорема о гомоморфизме Конгруэнцией на алгебре A = hA; Σ i называется такое отношение эквива- лентности θ ⊆ A2 , при котором для любого n ∈ ω, любого n-местного симво- ла f ∈ Σ (напомним, что сигнатура алгебры состоит только из функциональ- ных символов), произвольных наборов ( a1 , a2 , . . . , an), ( b1 , b2 , . . . , bn) ∈ An, если a1 θ b1 , a2 θ b2 , . . . , anθ bn, то f ( a1 , a2 , . . . , an) θ f ( b1 , b2 , . . . , bn). Это означает, что все операции согласованы с отношением эквивалент- ности θ. Например, для операции сложения это выглядит так: для любых элементов x, y ∈ A, любых a ∈ θ( x), b ∈ θ( y) элемент a + b принадлежит классу θ( x + y). Рассмотрим фактор-множество множества Aпо конгруэнции θ: A/θ = {θ( x) | x ∈ A}. Определим на этом множестве алгебру сигнатуры Σ. Константе c алгебры A поставим в соответствие элемент θ( c), который в A/θ
60
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
будет интерпретировать константный символ c. Если f — n-местный символ из Σ, то зададим на множестве A/θ действие функции f по правилу
f (θ(x
1
), . . . , θ(x
n
)) θ(f (x
1
, . . . , x
n
)).
Убедимся, что для любых x
1
, . . . , x
n
∈ A это определение корректно, т. е.
не зависит от выбора представителей классов эквивалентности. Действи- тельно, если θ(x
i
) = θ(y
i
), i = 1, 2, . . . , n, то x
i
θ y
i
, откуда в силу свойства конгруэнции имеем
f (x
1
, . . . , x
n
) θf (y
1
, . . . , y
n
),
т. е. θ(f (x
1
, . . . , x
n
)) = θ(f (y
1
, . . . , y
n
)).
Получившаяся алгебра A/θ hA/θ; Σi называется фактор-алгеброй ал- гебры A по конгруэнции θ.
Очевидно, что отображение A → A/θ, при котором элементу x ∈ A ста- вится в соответствие класс θ(x), является эпиморфизмом алгебры A
на фактор-алгебру A/θ. Этот эпиморфизм называется естественным гомо- морфизмом.
Если ϕ: A → B — гомоморфизм алгебр, то множество
Ker ϕ {(a, a
0
) | ϕ(a) = ϕ(a
0
)}
оказывается конгруэнцией на алгебре A и называется ядром гомомор- физма ϕ.
Докажем теорему, согласно которой гомоморфный образ алгебры изо- морфен фактор-алгебре по ядру гомоморфизма.
Теорема 2.4.1 (теорема о гомоморфизме). Если ϕ: A → B — эпи-
морфизм, ψ: A → A/Ker ϕ — естественный гомоморфизм, то существует
изоморфизм χ: B ∼
→ A/Ker ϕ такой, что ϕ ◦ χ = ψ.
Доказательство. Положим χ(b) = ψ(a), где a ∈ A выбрано так, что
b = ϕ(a). Если b = ϕ(a
0
), то (a, a
0
) ∈ Ker ϕ, откуда ψ(a) = ψ(a
0
). Следо- вательно, отображение χ определено корректно. Равенство ϕ ◦ χ = ψ оче- видно. Из него вытекает, что χ — сюръекция. Непосредственно проверяется,
что χ — гомоморфизм. Если χ(b) = χ(b
0
), то ψ(a) = ψ(a
0
), где b = ϕ(a),
b
0
= ϕ(a
0
). Отсюда (a, a
0
) ∈ Ker ϕ, следовательно, b = b
0
, что доказывает взаимную однозначность отображения χ. Так как сигнатура функциональ- на, из существования функции χ
−1
и того, что χ — гомоморфизм, следует,
что χ является изоморфизмом. ¤
2.5. ДЕКАРТОВЫ ПРОИЗВЕДЕНИЯ АЛГЕБР. ТЕОРЕМА БИРКГОФА 61 - •? ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ = ••A B A /Ker ϕϕψχ'Рис. 2.1Отображения ϕ, ψ и χ из теоремы 2.4.1 можно представить диаграммой, показанной на рис. 2.1. § 2.5. Декартовы произведения алгебр. Теорема Биркгофа Пусть Ai, i ∈ I, — семейство множеств. Декартовым произведением мно-жеств Ai, i ∈ I, называется множество Y i∈IAi {f | f : I → ∪i∈IAi, где f ( i) ∈ Aiдля всех i}.Отметим, что если I = {1 , 2 |
Скачать 1.99 Mb.