Дискретно-непрерывная математика (стр. 3 )

Пример 4. Над Z имеем

(1+2)+3 =1+2+3=1+(2+3),

но

(1-2)-3= -4 и 1-(2-3)=2.

Таким образом, операция вычитания не ассоциативна.

Комутативность и ассоциативность являются двумя важнейшими свойствами, которые могут быть определены для простых операций. Перед тем как описывать свойства, которые связывают две операции, определим некоторые термины, относящиеся к специальным элементам множеств, к которым эти операции применяются.

Определение. Пусть — бинарная операция на множестве А и l А такая, что

l а = а для всех а А.

Тогда l называется левой единицей по отношению к на А. Аналогично, если существует r А такое, что

r а = а для всех а А,

тo r является правой единицей по отношению к . Далее, если существует элемент е, который является и левой и правой единицей, т. е.

е а = а е = а для всех а А,

тo е называется (двусторонней) единицей по отношению к .

Пример 5. Над R 0 является правой единицей по отношению к вычитанию и единицей по отношению к сложению, так как

а — 0 = а,

но

0— а≠ а, если а ≠ 0;

а + 0 = а и 0 + а = а для всех а.

Определение. Пусть — операция на А с единицей е и х у = с. Тогда говорят, что х — левый обратный элемент к у, а у — правый обратный элемент к х. Далее, если х и у такие, что

х у = е = у х,

это у называется обратным элементом к х по отношению к , и наоборот.

Замечание. В некоторых работах левые (правые) обратные элементы относят к левой (правой) единице, однако, как мы в скором времени увидим, в большинстве случаев единицы являются двусторонними и, следовательно, не требуется делать никаких различий. Для решения уравнений необходимо существование и единственность единиц и обратных элементов. Менее общим свойством операций является идемпотентность, хотя оно используется в алгебре логики.

Определение. Пусть операция на множестве А и произвольный элемент х А таковы, что хх=х. Тогда говорят, что х идемпотентен по отношению к .

Очевидно, что любое подмножество идемпотентно по отношению к операциям пересечения и объединения.

Определение. Пусть дано множество А, на котором определено две операции и . Тогда, если

а (b с) = (а b) (а с)

для всех а, b,с А, то говорят, что дистрибутивна по отношению к .

Если сказанное выше не совсем понятно, следует провести соответствие между этим тождеством и обычной арифметикой на R, например,

3*(1 + 2) = (3*1)+(3*2).

Наиболее общеизвестная алгебра может быть построена из относительно небольшого набора основных правил. Сейчас мы продемонстрируем, как из элементарных предположений можно извлечь некоторые простые следствия; большинство примеров даны в виде упражнений.

Пример 6. Пусть — операция на множестве А и существует единица по отношению к . Тогда единичный элемент единствен.

Доказательство. Предположим, что х и у — единицы по отношению к , т. е.

х а = а х = а,

у а=а у=а для всех а А.

Тогда х = х у, так как у — единица, и х у=у, поскольку х — единица. Следовательно, х = у.

Пример 7. Пусть — ассоциативная операция на множестве А и е — единица по отношению к . Тогда если а А и х имеет обратный элемент, то обратный элемент едининствен по отношению к .

Доказательство. Предположим, что х' и х" - обратные элементы к х, так что

х х' = х' х = е и х х" = х" х = е.

Тогда

х' = х' е = х' (х х") = (х' х) х" = е х"= х" .

Итак, мы определили операции и описали некоторые их свойства. Теперь посмотрим, что можно сделать с совокупностью операций, заданных на множестве.

Множество с заданными на ней операциями называют алгебраической структурой

Некоторые из алгебраических структур, которые наиболее часто встречаются, будут рассмотрены позднее. Прежде чем приступить к их рассмотрению, посмотрим на арифметику с неформальной точки зрения. В большинстве случаев мы будем опускать формальные определения, делая ударения на «следствия из правил», даже в тех случаях, когда это приводит к непривычным способам использования известных символов, которые обычно используются для представления десятичных чисел,

1.2. «Малая» конечная арифметика

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

Ее можно изучать многими способами. Чтобы уяснить требования арифметической системы, примем конструктивное приближение и рассмотрим целые числа (0, 1, 2, ..,) просто как символы. В дальнейшем будем рассматривать только конечную арифметику, в которой используется лишь конечное множество чисел; сначала это множество будет небольшим. Имеется в виду, что если А~Nm, то требуется т различных символов, при этом никакие комбинации символов не разрешаются. Если используются только десятичные числа, то т≤ 10. Поскольку все множества данного размера биективны, то можно рассматривать только множества Nm.