Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

Скачать файл (1,99Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.12.2023

Просмотров: 499

Скачиваний: 6

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

λa. Рассмотрим также систему B = hR3; +, {λ·}λ∈Ri, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умно- жения троек на число λ для всех вещественных чисел λ. Системы A и B яв- ляются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору a ∈ E3его координатную строку (x, y, z) в некотором фиксированном базисе e1, e2, e3, является биекцией (ϕ: E3↔ R3), при кото- рой сохраняются действия операций: ϕ(a+b) = ϕ(a)+ϕ(b) и ϕ(λ·a) = λ·ϕ(

1.7. ОТНОШЕНИЯ ПОРЯДКА
43
Заметим, что диаграммы Хассе, изображенные на рис. 1.15а и б, сов- падают. Это означает, что эти частично упорядоченные множества имеют одинаковую структуру, причем отличную от структуры третьего ч.у.м., хотя оно тоже содержит восемь элементов. Формально такая общность структуры определяется понятием изоморфизма.
Пусть A = hA; 6
A
i, B = hB, 6
B
i — частично упорядоченные множества.
Отображение f : A → B называется изоморфизмом частично упорядоченных множеств A и B, если выполняются следующие условия:
1) f — биекция между множествами A и B;
2) для любых a
1
, a
2
∈ A, a
1 6
A
a
2
тогда и только тогда, когда
f (a
1
) 6
B
f (a
2
).
Если существует изоморфизм между A и B, то частично упорядоченные множества A и B называются изоморфными и этот факт обозначается через
A ' B.
Теорема 1.7.3. Всякое
частично
упорядоченное
множество
A = hA; 6i изоморфно некоторой системе подмножеств множества A,
частично упорядоченной отношением включения.
Доказательство. Для каждого элемента a ∈ A рассмотрим множество
S
a
= {x ∈ A | x 6 a}. Тогда S
a
⊆ A и Y = {S
a
| a ∈ A} — совокупность всех таких подмножеств. Докажем, что ч.у.м. A изоморфно ч.у.м. hY ; ⊆i.
Рассмотрим отображение ϕ: A → Y такое, что ϕ(a) = S
a
. Отображение ϕ
инъективно. Действительно, если S
a
= S
b
, то a ∈ S
b
и b ∈ S
a
, значит, a 6 b
и b 6 a, откуда по антисимметричности отношения 6 получаем a = b. Отоб- ражение ϕ сюръективно, так как у любого подмножества S
a
есть прообраз a.
Докажем, что ϕ сохраняет отношение частичного порядка. Предположим,
что a 6 b. Тогда из x 6 a в силу транзитивности отношения 6 следует
x 6 b, и, значит, S
a
⊆ S
b
. Напротив, если S
a
⊆ S
b
, то, поскольку a ∈ S
a
,
имеем a ∈ S
b
, откуда a 6 b. ¤
Пусть A = hA; 6i — ч.у.м., a — элемент множества A. Открытым
(замкнутым) начальным сегментом множества A называется множество
O(a, A) {x ∈ A | x < a} (соответственно O[a, A] {x ∈ A | x 6 a}), в ко- тором определено отношение 6
0
, являющееся ограничением отношения 6
из A: b
1 6
0
b
2
тогда и только тогда, когда b
1 6 b
2
в A.
Теорема 1.7.4. Если A и B — в.у.м., то A изоморфно некоторому на-
чальному сегменту множества B или B изоморфно некоторому началь-
ному сегменту множества A. ¤

44
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
§ 1.8.
Аксиомы теории множеств
Сейчас у нас имеются все средства, чтобы сформулировать систему ак- сиом теории множеств ZFC, в рамках которой можно изложить все обще- принятые в современной математике способы рассуждений и не проходит ни один из известных теоретико-множественных парадоксов. Эта система поз- воляет строить все математические объекты исходя из пустого множества.
Представим систему аксиом Цермело—Френкеля (ZF).
1. Аксиома существования пустого множества:
Существует пустое множество ∅.
2. Аксиома существования пары:
Если существуют множества a и b, то существует множество {a, b}.
3. Аксиома суммы:
Если существует множество X, то существует множество
∪X {a | a ∈ b для некоторого b ∈ X}.
4. Аксиома бесконечности:
Существует множество ω {0, 1, . . . , n, . . .}, где 0 ∅, n+1 n∪{n}.
5. Аксиома множества всех подмножеств:
Если существует множество A, то существует множество
P(A) {B | B ⊆ A}.
6. Аксиома замены:
Если P (x, y) — некоторое условие на множества x, y, такое, что для любо- го множества x существует не более одного множества y, удовлетворяющего
P (x, y), то для любого множества a существует множество
{b | P (c, b) для некоторого c ∈ a}.
7. Аксиома экстенсиональности:
Два множества, имеющие одинаковые элементы, равны, т. е. любое мно- жество определяется своими элементами:
A = B ⇔ ∀x (x ∈ A ⇔ x ∈ B).

1.8. АКСИОМЫ ТЕОРИИ МНОЖЕСТВ
45 8. Аксиома регулярности:
Всякое непустое множество x имеет элемент a ∈ x, для которого a∩x = ∅.
Из аксиомы регулярности следует, что каждое множество получается на некотором шаге “регулярного процесса” образования множества всех под- множеств, начинающегося с ∅ и подобного построению натуральных чисел из пустого множества по аксиоме бесконечности. Это означает, что любой элемент любого множества является множеством, сконструированным из пу- стого множества.
Покажем, как аксиоматика ZF позволяет определять теоретико-множес- твенные операции.
Пример 1.8.1. 1. Определим множество A ∪ B исходя из множеств A
и B. По аксиоме существования пары образуется множество {A, B}. С помо- щью аксиомы суммы получаем множество ∪{A, B}, которое по определению совпадает с множеством A ∪ B.
2. Пересечение A ∩ B множеств A и B определяется по аксиоме замены с помощью следующего свойства P (x, y): x = y и x ∈ A. Имеем множество
{b | P (c, b) и c ∈ B} = {b | c = b, c ∈ A и c ∈ B} = {c | c ∈ A и c ∈ B} = A∩B.
3. Покажем, что из аксиом 5 и 6 следует существование множества
A
2
= {(a, b) | a, b ∈ A} для любого множества A. Так как (a, b) = {{a}, {a, b}},
то A
2
⊆ P(P(A)). Пусть свойство P (x, y) означает, что существуют такие
a, b ∈ A, что x = {{a}, {a, b}} и y = x. Тогда множество A
2
равно
{b | P (c, b), c ∈ P(P(A))} и по аксиоме 6 оно существует. ¤
Система аксиом ZFC образуется из ZF добавлением одной из следующих двух эквивалентных аксиом, которые, с одной стороны, являются наименее
“очевидными”, а с другой — наиболее содержательными.
1. Аксиома выбора:
Для любого непустого множества A существует такое отображение
ϕ: P(A) \ {∅} → A, что ϕ(X) ∈ X для любого непустого множества X ⊆ A.
2. Принцип полного упорядочения:
Для любого непустого множества A существует бинарное отношение 6
на A, для которого hA; 6i — в.у.м.
В системе ZFC справедлив принцип трансфинитной индукции, являю- щийся обобщением принципа полной индукции: если hA; 6i — вполне упо-

46
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
рядоченное множество, P (x) — некоторое свойство, то справедливость свой- ства P (x) на всех элементах x ∈ A следует из того, что для любого z ∈ A
выполнимость свойства P на элементах y, где y < z, влечет выполни- мость P (z):
∀z
³¡
(∀y < z) P (y)
¢
⇒ P (z)
´
∀x P (x)
.
Задачи и упражнения
1. Доказать, что {∅} 6= ∅.
2. Доказать, что {{0, 1}, {0, 2}} 6= {0, 1, 2}.
3. Доказать, что существует лишь одно множество, не имеющее элементов.
4. Существуют ли множества A, B и C, для которых
A ∩ B 6= ∅, A ∩ C = ∅, (A ∩ B) \ C = ∅?
5. Доказать, что (A ∪ B) = A ∩ B.
6. Доказать основные теоретико-множественные тождества 1–8 (см. с. 14).
7. Решить систему уравнений:
а)
(
A ∩ X = B,
A ∪ X = C,
где A, B и C — данные множества и B ⊆ A ⊆ C;
б)
(
A \ X = B,
X \ A = C,
где A, B и C — данные множества и B ⊆ A, A ∩ C = ∅;
в)
(
A \ X = B,
A ∪ X = C,
где A, B и C — данные множества и B ⊆ A ⊆ C;
г)
(
A ∪ X = B ∩ X,
A ∩ X = C ∪ X;
д)
(
A \ X = X \ B,
X \ A = C \ X;
е)
(
A ∩ X = B \ X,
C ∪ X = X \ A.

ЗАДАЧИ И УПРАЖНЕНИЯ
47 8. Построить пример множеств A и B таких, что A × B 6= B × A.
9. Пусть [0, 1], [0, 2] — отрезки на числовой прямой. Дать геометрическую интерпретацию множеств [0, 1] × [0, 2], [0, 1]
2
, [0, 2]
3 10. Изобразить отношения
P = {(a, 1), (a, 2), (b, 2), (b, 3), (c, 1), (c, 4)}
и Q = {(1, α), (2, β), (3, α)}. Найти δ
Q
, ρ
Q
, P ◦ Q, [P ], [Q], [P ◦ Q].
11. Для отношений P = {(x, y) ∈ R
2
| x = y
2
} и Q = {(x, y) ∈ R
2
| x · y > 0}
найти P ◦ Q, Q ◦ P , P ◦ P и P
−1 12. Пусть A и B — конечные множества мощности m и n соответственно.
Найти:
а) число бинарных отношений между элементами множеств A и B;
б) число функций из A в B;
в) число инъекций из A в B;
г) число биекций из A в B.
13. Доказать следующие эквивалентности:
а) A × B ∼ B × A; б) (A × B)
C
∼ A
C
× B
C
14. Доказать, что:
а) если A — конечное множество, B — подмножество множества A,
то множество B конечно;
б) если A
1
, . . . , A
n
— конечные множества, то множества A
1
∪ . . . ∪ A
n
и A
1
× . . . × A
n
конечны.
15. Доказать, что если A — счетное множество, B — конечное множество,
то множество A \ B счетно.
16. Доказать, что если множества A
i
, i ∈ ω, счетны, то множество ∪
i∈ω
A
i
счетно.
17. Доказать, что если A — счетное множество, то множество ∪
n∈ω
A
n
всех конечных последовательностей, составленных из элементов множества
A, счетно.
18. Доказать, что множество всех многочленов от одной переменной с ра- циональными коэффициентами счетно.
19. Доказать, что множества точек отрезка и квадрата эквивалентны.

48
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
20. Доказать, что n
3
− n делится на 3 для любого n ∈ ω.
21. Доказать, что имеют место следующие равенства:
а) 1 + 3 + 5 + . . . + (2n − 1) = n
2
;
б) 1 + 4 + 7 + . . . + (3n − 2) =
3n
2
− n
2
;
в) 1 + a + a
2
+ . . . + a
n−1
=
1 − a
n
1 − a
, a ∈ R \ {1}.
22. Доказать, что имеют место следующие неравенства:
а) n
2
> 2n + 1, n ∈ ω, n > 3;
б) 2
n
> n
2
, n ∈ ω, n > 5;
в) n! > n
3
, n ∈ ω, n > 6;
г)
4
n
n + 1
<
(2n)!
(n!)
2
, n ∈ ω, n > 2.
23. Найти множество всех натуральных чисел, для которых истинно нера- венство n! < 2
n
24. Доказать, что каждое натуральное число n > 8 может быть представ- лено в виде n = 3k + 5l, k, l ∈ ω.
25. Найти ошибку в доказательстве того, что все лошади имеют одинако- вую масть.
Доказательство. Покажем с помощью математической индукции,
что любые n лошадей имеют одну и ту же масть. При n = 1 имеет- ся лишь одна лошадь, и поэтому она имеет ту же масть, как она сама.
Рассмотрим теперь индукционное предположение, состоящее в том что любые n лошадей имеют одинаковую масть, и установим, что имеют одну и ту же масть любые n + 1 лошадей. Предположим, что в загон помещена (n+1)-я лошадь. Выведем из загона одну лошадь. Поскольку теперь в загоне n лошадей, по индукционному предположению все они имеют одинаковую масть. Вернем выведенную лошадь в загон и выве- дем другую лошадь. Снова в загоне n лошадей, и все они имеют од- ну масть. Следовательно, все рассматриваемые лошади имеют ту же масть, что и те лошади, которые были выведены. Поэтому все n + 1
лошадей имеют одинаковую масть. В силу принципа математической индукции все лошади имеют одну и ту же масть. ¤

ЗАДАЧИ И УПРАЖНЕНИЯ
49 26. Построить бинарное отношение:
а) рефлексивное, симметричное, не транзитивное;
б) не рефлексивное, антисимметричное, не транзитивное;
в) рефлексивное, не симметричное, транзитивное.
27. Пусть L — множество всех прямых на плоскости. Являются ли экви- валентностями следующие отношения:
а) отношение параллельности двух прямых;

1 2 3 4 5 6 7 8 9 ... 29

б) отношение перпендикулярности двух прямых?
28. Доказать, что отношение {((x
1
, y
1
), (x
2
, y
2
)) | x
2 1
+ y
2 1
= x
2 2
+ y
2 2
} являет- ся отношением эквивалентности на множестве R
2
. Определить классы этой эквивалентности.
29. Доказать, что отношение {(a, b) | (a − b) — рациональное число} явля- ется отношением эквивалентности на множестве вещественных чисел.
30. Пусть на множестве ω определено отношение 6, задаваемое следую- щим правилом:
m 6 n ⇔ m делит n.
Считая, что 0 делит 0, показать, что 6 — частичный порядок. Для произвольных натуральных чисел m и n найти inf{m, n} и sup{m, n}
относительно указанного порядка.
31. Для обычных отношений 6 и < на множестве ω показать, что
< ◦ < 6= <, 6 ◦ < = < и 6 ◦ > = ω
2 32. Построить пример ч.у.м. с единственным минимальным элементом, но без наименьшего.
33. Рассмотрим на множестве R
2
отношение Парето Π:
(x
1
, y
1
) Π (x
2
, y
2
) ⇔ x
1 6 x
2
и y
1 6 y
2
.
Для точек A(a
1
, a
2
) и B(b
1
, b
2
) найти множество нижних и верхних гра- ней множества {A, B}. Чему равен inf{A, B} и sup{A, B}?
34. Построить линейный порядок на множестве комплексных чисел.
35. Составить матрицу отношения полного порядка, при котором нумера- ция элементов ведется: а) по возрастанию; б) по убыванию.

50
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
36. Проверить, являются ли частичными порядками бинарные отношения со следующими матрицами:
а)





1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1





; б)





1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1





; в)





1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1





;
г)





1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1





; д)





1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1





; е)





1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1





;
ж)





1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1





; з)





1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1





; и)





1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1





;
к)





1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1





; л)





1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1





; м)





1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1





Построить диаграммы Хассе для заданных порядков. Есть ли в со- ответствующих частично упорядоченных множествах наименьшие или наибольшие элементы? Какие из этих частичных порядков линейные?
37. Построить всевозможные попарно неизоморфные четырехэлементые ч.у.м. hA; 6i. Какие из этих ч.у.м. самодвойственны, т. е. изоморфны
hA; >i?

Глава 2
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
§ 2.1.
Определения и примеры
Часто объектом изучения в математике и ее приложениях служит мно- жество вместе с определенной на нем структурой. Читателю уже известны поля, формирующие основу обычной арифметики, линейные пространства,
обеспечивающие связь геометрических объектов с операциями над числами,
множества с введенными на них бинарными отношениями. Все эти струк- туры образуют алгебраические системы, представляющие собой некоторые миры с определенными в них законами. Перейдем к точному определению алгебраической системы.
Рассмотрим непустое множество A. В § 1.2 было введено понятие
n-местной операции на множестве A (f : A
n
→ A). Отметим, что, поскольку операция f является функцией, для любого набора (x
1
, . . . , x
n
) ∈ A
n
ре- зультат применения операции f (x
1
, . . . , x
n
) однозначно определен. Так как область значений операции f лежит в множестве A, то будем говорить, что операция f замкнута на множестве A.
Сигнатурой или языком Σ называется совокупность предикатных и функциональных символов с указанием их местности. При этом множе- ства предикатных и функциональных символов не пересекаются. 0-Местный функциональный символ называется константным символом или просто
константой. Если α — функциональный или предикатный символ, то его местность обозначается через µ(α). n-Местные предикатные и функциональ- ные символы часто будем обозначать соответственно через P
(n)
и f
(n)
. Если в рассматриваемой сигнатуре используются стандартные символы, такие,
например, как + для операции сложения, 6 для отношения порядка, | для

52
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
отношения делимости, 0 для константного символа и другие, то мы просто пишем Σ = {6}, Σ = {6, +, ·, 0}, Σ = {+, −, |, 0, 1} и т. д.
Алгебраической системой A = hA; Σi сигнатуры Σ называется непустое множество A, где каждому n-местному предикатному (функциональному)
символу из Σ поставлен в соответствие n-местный предикат (соответственно операция), определенный на множестве A. Множество A называется носите-
лем или универсумом алгебраической системы hA; Σi. Предикаты и функ- ции, соответствующие символам из Σ, называются их интерпретациями.
Обозначать интерпретации будем теми же буквами, что и соответствую- щие символы сигнатуры. Заметим, что интерпретацией любого константного символа является некоторый элемент (константа) из A.
Алгебраические системы в дальнейшем будут обозначаться готическими буквами A, B, . . . (возможно, с индексами), а их носители — соответствующи- ми латинскими буквами A, B, . . . (с соответствующими индексами). Иногда мы будем отождествлять носитель с алгебраической системой.
Мощностью алгебраической системы A называется мощность ее носите- ля A. В дальнейшем будем часто опускать слово “алгебраическая” и назы- вать A системой или структурой.
Непустая сигнатура Σ называется функциональной (предикатной), если она не содержит предикатных (функциональных) символов. Система A на- зывается алгеброй (моделью или реляционной системой), если ее сигнатура функциональна (предикатна).
Пример 2.1.1. 1. Набор hω; +, ·i является алгеброй с двумя двухмест- ными операциями.
2. Набор hω; 6, +, ·,
0
, 0, 1i является системой с бинарным отношением 6
(µ(6) = 2), двухместными операциями +, · (µ(+) = µ(·) = 2), одноместной операцией
0
: n 7→ n + 1 (µ(
0
) = 1) и двумя нуль-местными операциями
(константами) 0, 1 (µ(0) = µ(1) = 0).
3. Набор hZ; +, :,
√
2i не образует алгебру, поскольку деление не является операцией на множестве Z (например, 2 : 3 /
∈ Z), а элемент
√
2 не принадле- жит Z.
4. Набор hP(U); ∩, ∪, , 0, 1i с двухместными операциями ∩, ∪, одномест- ной операцией : A 7→ A, константами 0 = ∅ и 1 = U является алгеброй,
называемой алгеброй Кантора.
5. Алгеброй является любое кольцо.
6. Пара

{f (x) | f : R → R};
d
dx
®
(где
d
dx
— операция дифференцирова- ния) не является алгеброй, поскольку не всякая функция дифференцируема,

2.1. ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ
53
но если рассмотреть множество A = {f (x) | f (x) дифференцируема беско- нечное число раз}, то отображение дифференцирования
d
dx
: f 7→
df
dx
является операцией на A и пара

A;
d
dx
®
образует алгебру. ¤
Заметим, что частичную операцию f , отображающую A
n
в A, можно рассматривать как (n + 1)-местное отношение
R
f
{(x
1
, x
2
, . . . , x
n
, y) | (x
1
, . . . , x
n
) ∈ A
n
и y = f (x
1
, . . . , x
n
)}.
Поэтому в последнем примере пару

{f (x) | f : R → R};
d
dx
®
можно считать алгебраической системой, если рассматривать
d
dx
как бинарное отношение
©
(f, g) | g =
df
dx
ª
Алгебра A сигнатуры Σ = {f }, где µ(f ) = 2, называется группоидом.
Единственная здесь операция f обычно обозначается символом ·: A = hA; ·i.
Если A — конечное множество, действия операции · можно задать квадрат- ной таблицей, в которой для каждой пары (a
i
, a
j
) ∈ A
2
записан результат действия ·(a
i
, a
j
). Такая таблица называется таблицей Кэли группоида A.
Группоид A называется полугруппой, если · — ассоциативная операция, т. е.
для всех элементов x, y, z ∈ A верно x · (y · z) = (x · y) · z. Полугруппа A на- зывается моноидом, если существует элемент e ∈ A, называемый единицей,
такой, что e · x = x · e = x для всех x ∈ A. Полугруппы и моноиды имеют особое значение в теории языков при обработке слов.
Пример 2.1.2. Пусть W (X) — множество слов алфавита X. Определим на W (X) операцию конкатенации ˆследующим образом: если α, β ∈ W (X),
то αˆβ = αβ, т. е. результатом является слово, полученное соединением слов
α и β (например, xyzˆzx = xyzzx). Операция ˆ ассоциативна, т. е. для лю- бых слов α, β, γ верно (αˆβ)ˆγ = αˆ(βˆγ). Следовательно, система hW (X);ˆi
является полугруппой. Так как для всех α ∈ W (X) верно Λˆα = αˆΛ = α,
где Λ — пустое слово, то Λ удовлетворяет свойству единицы. Таким образом,
система hW (X);ˆi является моноидом. ¤
Моноид A = hA; ·i называется группой, если для любого элемента
x ∈ A существует элемент x
−1
∈ A, называемый обратным к x, такой, что
x · x
−1
= x
−1
· x = e. Группа A называется коммутативной или абелевой,
если x · y = y · x для всех x, y ∈ A.
Пример 2.1.3. 1. Если hK; +, ·i — кольцо, то hK; +i — абелева группа.
2. Система hGL
n
(K); ·i, где GL
n
(K) {A | A — матрица порядка n
над полем K, и det A 6= 0} является группой, которая некоммутативна при
n > 2. ¤

54
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
§ 2.2.
Морфизмы
Пусть даны алгебраические системы A = hA; Σi и B = hB; Σi. Отобра- жение ϕ: A → B называется гомоморфизмом системы A в систему B, если выполняются следующие условия:
1) для любого функционального символа f
(n)
∈ Σ, соответствующих функций f
A
и f
B
в системах A и B и любых a
1
, a
2
, . . . , a
n
∈ A выполня- ется
ϕ(f
A
(a
1
, a
2
, . . . , a
n
)) = f
B
(ϕ(a
1
), ϕ(a
2
), . . . , ϕ(a
n
));
2) для любого предикатного символа P
(n)
∈ Σ, соответствующих преди- катов P
A
и P
B
в системах A и B и любых a
1
, a
2
, . . . , a
n
∈ A выполняется
(a
1
, a
2
, . . . , a
n
) ∈ P
A
⇒ (ϕ(a
1
), ϕ(a
2
), . . . , ϕ(a
n
)) ∈ P
B
.
Если ϕ: A → B — гомоморфизм, то будем его обозначать через
ϕ: A → B.
При гомоморфизме сохраняются действия операций и отношения. Это позволяет переносить изучение свойств с одной системы на другую.
Пример 2.2.1. Рассмотрим системы A = hZ; +, 6i и B = hZ
2
; +, 6i, где в системе B сложение задается по правилу
(a
1
, b
1
) + (a
2
, b
2
) = (a
1
+ a
2
, b
1
+ b
2
),
а отношение порядка —
(a
1
, b
1
) 6 (a
2
, b
2
) ⇔ a
1 6 a
2
и b
1 6 b
2
.
Отображение ϕ: Z → Z
2
, при котором ϕ(a) = (a, 0), является гомоморфиз- мом. Действительно, для любых a, b ∈ Z имеем
ϕ(a + b) = (a + b, 0) = (a, 0) + (b, 0) = ϕ(a) + ϕ(b),
и если a 6 b, то (a, 0) 6 (b, 0), т. е. ϕ(a) 6 ϕ(b). ¤
Гомоморфизм ϕ: A → B, являющийся инъекцией, называется мономор-
физмом. Гомоморфизм ϕ: A → B, являющийся сюръекцией, называется
эпиморфизмом, и при этом система B называется гомоморфным образом

2.2. МОРФИЗМЫ
55
системы A. Гомоморфизм ϕ: A → A называется эндоморфизмом. Сюръек- тивный мономорфизм ϕ: A → B, для которого ϕ
−1
— гомоморфизм, называ- ется изоморфизмом A на B и обозначается через ϕ: A ∼
→ B. Если существует изоморфизм ϕ: A ∼
→ B, то системы A и B называются изоморфными и обо- значается это так: A ' B.
Таким образом, условие A ' B означает, что существует биекция
ϕ: A ↔ B, удовлетворяющая следующим условиям:
1) для любого функционального символа f
(n)
∈ Σ, соответствующих функций f
A
и f
B
в системах A и B и любых a
1
, a
2
, . . . , a
n
∈ A выполня- ется
ϕ(f
A
(a
1
, a
2
, . . . , a
n
)) = f
B
(ϕ(a
1
), ϕ(a
2
), . . . , ϕ(a
n
));
2) для любого предикатного символа P
(n)
∈ Σ, соответствующих преди- катов P
A
и P
B
в системах A и B и любых a
1
, a
2
, . . . , a
n
∈ A выполняется
(a
1
, a
2
, . . . , a
n
) ∈ P
A
⇔ (ϕ(a
1
), ϕ(a
2
), . . . , ϕ(a
n
)) ∈ P
B
.
Изоморфизм ϕ: A ∼
→ A называется автоморфизмом системы A. Заметим,
что, поскольку изоморфизм ϕ: A ∼
→ B является биекцией A ↔ B, изоморф- ные системы равномощны.
Утверждение 2.2.1. 1. id
A
: A ∼
→ A.
2. Если ϕ: A ∼
→ B, то ϕ
−1
: B ∼
→ A.
3. Если ϕ: A
1
∼
→ A
2
и ψ: A
2
∼
→ A
3
, то ϕ ◦ ψ: A
1
∼
→ A
3
. ¤
Таким образом, отношение изоморфизма ' является эквивалентностью на любом множестве алгебраических систем (отметим, что класс всех алгеб- раических систем не является множеством, поскольку не существует множе- ства всех множеств). Это означает, что отношение изоморфизма разбивает множества алгебраических систем на классы эквивалентности, в каждом из которых содержатся системы, имеющие “одинаковое устройство”. Это да- ет возможность переносить изучение свойств с одной системы на другую,
изоморфную ей. Так, используя факт изоморфизма геометрического вектор- ного пространства пространству строк, работу с геометрическими объекта- ми можно свести к действиям с наборами чисел, что позволяет применять компьютеры.
Пример 2.2.2. 1. Рассмотрим множество векторов E
3
геометрическо- го векторного пространства с операциями сложения векторов и умножения

56
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
векторов на вещественные числа. Получим систему A = hE
3
; +, {λ·}
λ∈R
i бес- конечной сигнатуры, где одноместные функции λ· ставят в соответствие век- тору a вектор
1 2 3 4 5 6 7 8 9 ... 29

Смотрите также файлы

Билет 1 1 Общая характеристика пд.docx

Проектирование системы кондиционирования воздуха (скв) для помещения зрительного зала кинотеатра.docx

Вы зашли под именем Шамшуров Игорь Владимирович (Выход) анпоо "нспк".pdf

Лабораторная работа 1 по дисциплине (учебному курсу).odt

Практическая работа 2 Работа в текстовом редакторе Word.pdf

Смотрите также файлы

Информация

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

Дополнительно