Алгебраические структуры: группы, кольца и поля

Теорема 5: Композиция функций обладает свойством ассоциативности, т.е. (g ) = (g) для любых функций , g и .

Отображение A множества А на себя такое, что A для каждого из А, называется тождественным или единичным отображением множества А на себя.

Теорема 6: Пусть — отображение множества А на В, тогда B.

Теорема 7: Пусть , g, —функции, удовлетворяющие условию

Dom g = Dom lm ,тогда если g = , то g = .

Функция называется инъективной, если для любых (из Dom ) из условия следует, что . Другими словами, функция инъективна, если для любых из того, что и , следует, что .

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

Теорема 8: Если — отображение из  множества А в множество B, то

A =B.

Теорема 9: Композиция любых двух инъективных функций является инъективной функцией, а композиция любых двух подстановок множества А есть подстановка множества А.

Теорема 10: Если и g функции, то (a) Dom = Im; (b) Im = Dom;

(с) () = ; (d) .

Теорема 11: Инверсия функции f тогда и только тогда является функцией, когда функция инъективна.

Следствие: Если — инъективная функция, то — тоже инъективная функция. При этом если — инъективное отображение А на В, то есть инъективное отображение В на А.

Пусть — отображение множества A на В.

Функция называется левой обратной к функции , если — отображение В на А и A. Функция, обладающая левой обратной, называется  обратимой слева.

Функция называется правой обратной к функции , если — отображение В на А и B. Функция, обладающая правой обратной, называется обратимой справа.

Функция g называется обратной к функции , если g — отображение В на A, gA и g = B. Функция, обладающая обратной, называется обратимой. Функция, обратная к функции , обозначается символом -1.

Теорема 12: Если — инъективное отображение множества А на B, то A, B.

Следствие: Если — инъективное отображение множества А на В, то —обратимая функция, причем функция является обратной к .

Следствие: Если —подстановка множества А, то A.

Теорема 13: Следующие свойства функции равносильны:

(a) инверсия функции является функцией;

(b) функция инъективна;

(c) функция обратима справа:,

(d) функция обратима слева;

(e) функции обратима;

(g) все функции, обратные к {левые, правые, двусторонние), существуют и совпадают с .

Теорема 14: Если функции и g обратимы, то обратима также функция g и (g)-1 = g-1-1.

Функция g называется ограничением (или сужением) функции , если g. Если g, то говорят также, что есть расширение (или продолжение) функции g.

Функция g называется ограничением функции множеством А (или сужением функции на множество A), если g и Domg = A.

Ограничение функции множеством А обозначается A или A.

Если ADom, то функция A является ограничением функции множеством А, т. е. A =A.

Теорема 15: Функция g является ограничением функции тогда и только тогда, когда DomgDom и g() = для любого из Domg.

 

§4 Отношение эквивалентности и отношение порядка.

Бинарное отношение на множестве А называется отношением эквивалентности на А, если оно рефлексивно, симметрично и транзитивно (на А). Отношение эквивалентности часто обозначают символами .

Пример. Пусть А — непустое множество и A = { |A} —отношение тождества на множестве А. Отношение A есть отношение эквивалентности на A.

Пусть Z — множество всех целых чисел и — целое число, отличное от нуля. Отношение R = { Z и — делится на } называется отношением сравнения по модулю . Это отношение является отношением эквивалентности на Z.

Два множества называются равномощными, если существует инъективное отображение одного множества на другое. Отношение равномощности на любой данной совокупности множеств является отношением эквивалентности.

 Классом эквивалентности,  порожденным элементом а, называется множество {}, т. е. множество всех таких из А, что R, и обозначается черезR, а совокупность всех классов эквивалентности отношения R на множестве А обозначается [A]R.

Пусть А — непустое множество. Фактор-множество множества А по отношению эквивалентности R называется множество [A]R всех классов эквивалентности.

Разбиением множества А называется такое семейство его непустых подмножеств, что каждый элемент множества А входит в точности в один член семейства.

Теорема 1: Пусть R — отношение эквивалентности на (непустом) множестве А. Тогда  фактор-множество [A]R является разбиением множества А.

Следствие: Пусть R— отношение  эквивалентности на множестве А, тогда

(1) R для любого из А;

(2) для любых  из A R = [R тогда и только тогда, когда R;

(3) R R тогда и только тогда, когда [R [R = ;  

Пусть S — разбиение непустого множества А и RS — бинарное отношение, определяемое следующим образом: RS тогда и только тогда, когда и принадлежат одному и тому же члену семейства S.

Теорема 2: Отношение RS, соответствующее разбиению S непустого множества А, является отношением эквивалентности на А, причем фактор-множество [A]RS совпадает с разбиением S.

Пусть — отображение множества А в В. Бинарное отношение R,

R = {А}, называется отношением равнообразности отображения .

Теорема 3: Пусть — любое отображение и А= Dom. Отношение равнообразности отображения является отношением эквивалентности на множестве А.

 Бинарное отношение R на множестве A называется отношением порядка на А или порядком на A, если оно транзитивно и антисимметрично.

Отношение порядка R на множестве А называется нестрогим, если оно рефлексивно на A, т. е. R для всякого из А.

Отношение порядка R называют строгим (на A), если оно антирефлексивно на A, т. е. R для любого из A.

Бинарное отношение R на  множестве A называется строгим порядком на A, если оно транзитивно и антирефлексивно на A.

Примеры: 1. Пусть Р(М) — множество всех подмножеств множества М. Отношение включения на множестве Р(М) есть отношение нестрогого порядка. 2. Отношения < и на множестве действительных чисел являются соответственно отношением строгого и нестрогого порядка. 3. Отношение делимости во множестве натуральных чисел есть отношение нестрогого порядка.

Бинарное отношение R на множестве А называется отношением предпорядка или предпорядком на A, если оно рефлексивно на A и транзитивно. Отношение логического следования является предпорядком на множестве формул логики высказываний.

Отношение порядка на множестве A называется отношением линейного порядка или линейным порядком на A, если оно связанно на A, т.е. Отношение порядка, не являющееся линейным, обычно называют отношением частичного порядка или частичным порядком. Пусть <A,⊰ — упорядоченное множество. Элемент из А называется наименьшим (наибольшим) в A, если для любого элемента из A, отличного от . Любое упорядоченное множество имеет не более одного наименьшего и не более одного наибольшего элемента.

Пусть А,⊰> — упорядоченное множество. Элемент из А называется минимальным (максимальным) в A, если выполняется условие; для любого х из A, если , то (если , то ). Упорядоченное множество может иметь несколько минимальных и максимальных элементов.

Линейно упорядоченное множество А, R называется вполне упорядоченным множеством, если каждое непустое подмножество множества А имеет наименьший элемент.

 

II Алгебры и алгебраические системы

 

§ 1. Бинарные операции

 

Бинарной операцией на множестве А называется отображение множества АА в А.

 Обычное сложение и умножение целых чисел суть примеры бинарных операций на множестве целых чисел. Пусть Р (М) — множество всех подмножеств множества М; объединение и пересечение —примеры бинарных операций на множестве Р(М).

 Пусть Аn есть n-я степень непустого множества A и 1. Отображение множества Аn в A называется n-местной операцией на множестве A, а число n —рангом операции. Нульместной операцией на  множестве А называется выделение (фиксация) какого-нибудь элемента множества A, число 0 называется рангом нульместной операции.

Отображение из множества Аn в A называется частичной n-местной операцией на A, если область определения отображения не совпадает с Аn.

Операции ранга 0, 1 и 2 называют также нульарной (нульместной), унарной и бинарной соответственно. Унарную операцию называют также оператором.

Для обозначения n-местной операции обычно используют ту же форму записи, что и для произвольных отображений (функций). Если есть n-местная операция на множестве А и , то пишут и говорят, что —  значение операции для набора аргументов .

Бинарная операция называется коммутативной, если для любых из А выполняется равенство .

Бинарная операция ⏉ называется ассоциативной, если для любых элементов , с из А выполняется равенство .

Элемент из А называется левым нейтральным относительно операции⏉, если для любого из А выполняется равенство . Элемент из А называется правым нейтральным относительно операции ⏉, если для любого из А имеем .

Теорема 1: Если нейтральный элемент относительно бинарной операции ⏉ существует, то он единствен.

Следствие: Если нейтральный элемент относительно операции ⏉ существует, то все левые и правые нейтральные элементы относительно ⏉ с ним совпадают.

Примеры: 1. Число 0 есть нейтральный элемент относительно сложения целых чисел. Число 1 есть нейтральный элемент относительно умножения целых чисел.

2. Пустое множество есть  нейтральный элемент относительно  операции объединения множеств. Универсальное множество является  нейтральным элементом относительно  операции пересечения множеств.

3. Рассмотрим множество  Ф отображений непустого множества А на его непустое собственное подмножество В и операцию — композицию отображений. Множество Ф не имеет ни одного правого нейтрального элемента. Всякий элемент Ф такой, что : для любого из В, является левым нейтральным элементом относительно рассматриваемой операции.

Пусть Т — бинарная операция на множестве A, обладающая нейтральным элементом .

Элемент из A называется левым симметричным к элементу А относительно операции ⏉, если . Элемент из Л называется правым 

симметричным к относительно операции ⏉, если .

Элемент `A называется симметричным к элементу А относительно операции ⏉, если . В этом случае элемент называется симметризуемым, а элементы и — взаимно симметричными.

Примеры: 1. Относительно сложения целых чисел симметричным к данному целому числу является то же число, взятое со знаком минус.

2. Относительно умножения  рациональных чисел  симметричным  к ненулевому числу  является 1/; число нуль не имеет симметричного относительно умножения.

Пусть Т — бинарная операция на множестве А и В А. Подмножество В множества А называется замкнутым относительно операции ⏉, если для

любых из В элемент принадлежит В.

Примеры: 1. Множество всех четных чисел замкнуто относительно сложения и умножения целых чисел. 2. Множество всех нечетных чисел замкнуто  относительно умножения, но не замкнуто относительно сложения

целых чисел. 3. Множество всех элементов (из A), регулярных  относительно ассоциативной операции замкнуто относительно ⏉.

Наиболее часто используются аддитивная и мультипликативная формы записи бинарной операции. При аддитивной форме записи бинарную операцию ⏉ называют сложением и пишут а + b вместо a⏉b, называя элемент а+b суммой а и b. Элемент, симметричный элементу а, обозначают (—а) и называют противоположным элементу а. Нейтральный элемент относительно сложения обозначают символом 0 и называют нулевым элементом относительно сложения.

При аддитивной записи свойства ассоциативности и коммутативности записываются в виде:

a + (b + c) = (a + b) + c, a + b = b + a.

При мультипликативной форме записи бинарную операцию называют умножением и пишут аb (вместо а⏉b), называя элемент аb произведением а и b. Элемент, симметричный а, обозначают а-1 и называют обратным элементу а. Нейтральный элемент относительно умножения обозначают через е или 1 и называют единичным элементом или единицей относительно умножения. При 

мультипликативной записи свойства ассоциативности и коммутативности записываются в виде: a(bc) = (ab)c, ab = ba.

Свойство дистрибутивности умножения относительно сложения записывается в виде: (a + b)c = ac+bc, c(a + b) = ca+cb.

 

§2 Алгебра

Алгеброй называется упорядоченная пара А= (А, ), где А —непустое множество и - множество операций на А. Таким образом, алгебра А определяется двумя множествами: 1) непустым множеством А, обозначаемым также через |А|; это множество называется основным множеством алгебры А, а его элементы — элементами алгебры А ; 2) множеством операций , определенных на А и называемых главными операциями алгебры А .

Если А, — алгебра, то говорят также, что множество А есть алгебра относительно операций .

Алгебры А = <А, и B =<В, '> называются однотипными, если существует инъективное отображение множества на ', при котором любая операция А из и соответствующая ей при отображении операция B из ' имеют один и тот же ранг.

А =А, 1, . . . , r, ar+1, . . . , as, при этом выделенные элементы ar+1, . . . , as значения главных нульместных операций — называются выделенными или главными элементами алгебры А.

Типом алгебры А = A, 1, ..., s называется последовательность (r(1),...,r(s)), где r(i) — ранг операции i. Алгебры A и B = B, 1, ..., s являются однотипными, если их типы совпадают, т. е. ранг операции i совпадает с рангом соответствующей операции i для i=l, ..., s.

Примеры: 1) Пусть + и (сложение и умножение) — арифметические операции на множестве Z целых чисел. Алгебра (Z, +, } является алгеброй типа (2,2). 2) Пусть + и суть арифметические операции на множестве N натуральных чисел. Алгебра <N, +, ) есть алгебра типа (2,2). 3) Пусть Р (U) — множество всех подмножеств непустого множества U и ' суть операции пересечения, объединения и дополнения над подмножествами множества U.