Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 489
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
λ
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 = 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. Рассмотрим также систему 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 = hR
3
; +, {λ·}
λ∈R
i, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умно- жения троек на число λ для всех вещественных чисел λ. Системы A и B яв- ляются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору
a ∈ E
3
его координатную строку (x, y, z) в некотором фиксированном базисе
e
1
,
e
2
,
e
λ
a. Рассмотрим также систему B = hR
3
; +, {λ·}
λ∈R
i, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умно- жения троек на число λ для всех вещественных чисел λ. Системы A и B яв- ляются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору
a ∈ E
3
его координатную строку (x, y, z) в некотором фиксированном базисе
eλ
a. Рассмотрим также систему B = hR3
; +, {λ·}
λ∈R
i, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умно- жения троек на число λ для всех вещественных чисел λ. Системы A и B яв- ляются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору
1
,
3
, является биекцией (ϕ: E
3
↔ R
3
), при кото- рой сохраняются действия операций: ϕ(
Таким образом, ϕ — изоморфизм линейных пространств 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 (Σ) = {x
1
, x
1
· x
2
, (x
1
· x
2
) · x
3
, x
1
· (x
2
· ·x
3
), . . .}. По теореме 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 в некоторый терм x
1
+ x
2
+ . . . + x
m
+
.
ı +
.
ı + . . . +
.
ı. Следовательно,
B(X) = {2m + ni | m ∈ Z, n ∈ ω}. ¤
§ 2.4.
Конгруэнции. Фактор-алгебры.
Теорема о гомоморфизме
Конгруэнцией на алгебре A = hA; Σi называется такое отношение эквива- лентности θ ⊆ A
2
, при котором для любого n ∈ ω, любого n-местного симво- ла f ∈ Σ (напомним, что сигнатура алгебры состоит только из функциональ- ных символов), произвольных наборов (a
1
, a
2
, . . . , a
n
), (b
1
, b
2
, . . . , b
n
) ∈ A
n
,
если a
1
θ b
1
, a
2
θ b
2
, . . . , a
n
θ b
n
, то f (a
1
, a
2
, . . . , a
n
) θ f (b
1
, b
2
, . . . , b
n
).
Это означает, что все операции согласованы с отношением эквивалент- ности θ. Например, для операции сложения это выглядит так: для любых элементов 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.
Декартовы произведения алгебр.
Теорема Биркгофа
Пусть A
i
, i ∈ I, — семейство множеств. Декартовым произведением мно-
жеств A
i
, i ∈ I, называется множество
Y
i∈I
A
i
{f | f : I → ∪
i∈I
A
i
, где f (i) ∈ A
i
для всех i}.
Отметим, что если I = {1, 2
1 2 3 4 5 6 7 8 9 ... 29